ECC&SM2

---

ECC

基本内容

概念

ECC 全称为椭圆曲线加密，EllipseCurve Cryptography，是一种基于椭圆曲线数学的公钥密码。与传统的基于大质数因子分解困难性的加密方法(RSA)不同，ECC 依赖于解决椭圆曲线离散对数问题的困难性。它的优势主要在于相对于其它方法，它可以在使用较短密钥长度的同时保持相同的密码强度。目前椭圆曲线主要采用的有限域有:

1. 以素数为模的整数域 GF§，通常在通用处理器上更为有效。
2. 特征为 2 的伽罗华域 GF（$2^m$），可以设计专门的硬件。

运算规则

因为曲线的对称轴是X轴，假定任意点P，可以在相对X轴的位置找到点−P，令−O即为O。
若P和Q是曲线上的二点，可以用以下的方式定义唯一的第三点P + Q。先划出通过P和Q的直线，大多数的情形下，此直线会和曲线交于第三点R，令P + Q为−R，是R相对X轴的对应点。同时，一些特殊情况如下图所示。

算法

1. 函数方程:$y^2=x^3+ax+b$, 其中$4a^3+27b^2\ne 0$
2. 椭圆曲线离散对数问题(ECDLP): 给定点P和Q，确定整数k使$Q=k\ast P$。此外， 一般认为在一个有限域乘法群上的离散对数问题（DLP）和椭圆曲线上的离散对数问题（ECDLP）并不等价；ECDLP比DLP要困难的多。
3. 在密码的使用上，会选择曲线$E(p)$和其中一个特定的基点G，并且公开这些资料。再选择一个随机整数k作为私钥；公布值为$Q=k\ast G$的公钥。

加密应用

通常来说，加密过程先选择一条椭圆曲线$E_q(a,b)$，然后选择其上的一个生成元 $G$，假设其阶为 $n$，之后再从区间$[1,n-1]$ 选择一个正整数$d_a$ 作为密钥，计算$Q_a=d_a\ast G$ 。
其中，公钥为$Q_a$，私钥为 $d_a$ 。$E_q(a,b),q,G$ 都会被公开。

ECDH(Elliptic Curve Diffie–Hellman key Exchange)

首先，需要事先提前确定函数参数作为公开信息，定义了所使用的椭圆曲线。然后，双方再按上述加密方法，得到Alice的密钥为$(d_A,Q_A)$，Bob的密钥为$(d_B,Q_B)$。接着，双方将自己的公钥 $Q_A与Q_B$ 进行交换。最后，得到公共的密钥$(x_k,y_k)=d_A{Q}_B=d_A{d}_{B}G=d_B{d}_{A}G=d_B{Q}_A$ 。

ECElGamal

若用户B要给用户A发送加密消息，则B先查询A生成的$E_q(a,b),q,G$ 信息后，将明文m转化为曲线上一点， 再生成（1，q-1）范围内随机数k，计算点$(x1,y1)=kG$与点$(x2,y2)=k{P}_a$ 。最后计算$C=m+(x2,y2)$ 并将$((x1,y1),C)$ 发送给A。
在A解密信息时，只需计算$m=C-d_a(x1,y1)$ 即可。

ECDSA(Elliptic Curve Digital Signature Algorithm)

首先，选择一个已经提供了预处理的已知高效和安全的标准化曲线，生成一个20字节的随机数$k$，得出点$P=kG$。其中，$P$ 的 $x$ 坐标为签名结果的前20字节$R$ 。然后，用SHA1计算出信息的20字节的哈希值$z$ ，用方程$S=k^{-1}(z+d_A\times R)(modn)$ 计算出签名结果后20字节$S$，得到签名结果$(R,S)$。验证签名时，只需要验证点$P=S^{-1}\times z\times G+S^{-1}\times R\times Q_a(modn)$ 的 $x$ 坐标与 $R$ 的值是否相等即可。
生成本签名的两个主要方程$P=kG$与$S=k^{-1}(z+d_A\times R)(modn)$ 中有两个未知数$k和d_A$，在PS3的ECDSA签名时使用了相同的随机数$k$，在反复签名过程只需得到两组$z、S$和$z^{\prime }、S^{\prime }$ 就可以像解二元一次方程组一样，用$k={\frac{z-z^{\prime }}{S-S}}^{\prime }$ 与$d_A=(S\times k-z)/R$ 就可以伪造官方签名。

破译手段

一般来说ECC的破译是针对不恰当的模数n下手的。

n很小

直接将曲线上所有点跑一次对比公钥得出私钥即可。

baby-step giant-step

对于公钥$Q=k\ast G(modn)$ ，令$m=\lceil \sqrt{n}\rceil$ 。将$k改写为am+b$ ，在$[0,m]$区间计算 $bG$ 存在哈希表中，就是“小步”。在$[0,m]$区间计算 $amG$ ，就是“大步”。
将$Q-amG与bG$进行对比，求出相等时的$a、b$ 就可以得到私钥$k=am+b$ 。
本算法的时间和空间复杂度是 $O(\sqrt{n})$ 。

import time

a = 1234577
b = 3213242
n = 7654319
k = 1584718
E = EllipticCurve(GF(n), [0, 0, 0, a, b])
G = E(5234568, 2287747)
Q = k * G

print('Curve: {}'.format(E))
print('G = {}'.format(G))
print('Q = {} = {} * G'.format(Q,k))
    

time_start = time.time()
m = int(sqrt(n)) + 1
    
r = G
baby_steps = {r: 1}
for b in range(2, m):
    r = r + G
    baby_steps[r] = b
        
r = Q
s = m*G

for a in range(m):
    try:
        b = baby_steps[r]
    except KeyError:
        pass
    else:
        steps = m + a
        ans = a * m + b
        break
    r = r - s

time_end = time.time()
print('ans =', ans)
print('Took', steps, 'steps')
print('Took', time_end - time_start, 'seconds')

Pollard’s rho

Pollard’s rho 是另一个用来计算离散对数的算法。它有和Baby-step giant-step同样的渐近时间复杂度 $O(\sqrt{n})$ ，但是它的空间复杂度仅仅是 $O(1)$ 。
本算法目标是找到四个整数$a,b,A,B$ 使得$aG+bQ=AG+BQ$ 成立，那么可以得到$(a+bk)G=(A+Bk)G$，进一步得出$a-A=(B-b)k$，最后得出$k=(a-A)(B-b{)}^{-1}$。
为了找出满足条件的$a,b,A,B$，Pollard’s rho给出的算法是：对于一个点$X_i=a_{i}G+b_{i}Q$ ，使用一个伪随机方程$f(X_i)=(a_{i+1},b_{i+1})=X_{i+1}$ 来确定出下一个点，直至出现循环$X_j=X_i$（由点的有限性决定）。（进一步的资料可以参看Elliptic Curve Cryptography: breaking security and a comparison with RSA - Andrea Corbellini）

sage求解ECC离散对数

import time

a = 1234577
b = 3213242
n = 7654319
k = 1584718
E = EllipticCurve(GF(n), [0, 0, 0, a, b])
G = E(5234568, 2287747)
Q = k * G

print('Curve: {}'.format(E))
print('G = {}'.format(G))
print('Q = {} = {} * G'.format(Q,k))

time_start = time.time()
#通用方法
ans = discrete_log(Q, G, operation='+')
time_normal = time.time() - time_start
print("discrete_log(): answer = {}, took {} seconds".format(ans, time_normal))
 
#Rho方法
ans = discrete_log_rho(Q, G, operation='+')
time_rho = time.time() - time_start
print("discrete_log_rho(): answer = {}, took {} seconds".format(ans, time_rho))

#lambda方法
ans = discrete_log_lambda(Q, G, (0, n),operation='+')
time_lambda = time.time() - time_start
print("discrete_log_lambda(): answer = {}, took {} seconds".format(ans, time_lambda))

#小步大步法计算离散对数,不过不知道为什么跑不了...
ans = bsgs(G, Q, (0, n), operation='+')
time_bsgs = time.time() - time_start
print("bsgs(): answer = {}, took {} seconds".format(ans, time_bsgs))

---

SM2

SM2是中华人民共和国政府采用的一种公开密钥加密标准，由国家密码管理局于2010年12月17日发布，相关标准为“GM/T 0003-2012 《SM2椭圆曲线公钥密码算法》”。2016年，成为中国国家密码标准（GB/T 32918-2016）。
在商用密码体系中，SM2主要用于替换RSA加密算法，其算法公开。据国家密码管理局表示，SM2基于ECC，其效率较低，安全性与NIST Prime256相当。
SM2主要包括三部分：签名算法、密钥交换算法、加密算法。
下面简单介绍签名算法和加密算法，基于sage的实现过程贴在下面，如果想使用现有的库，可以参考国密gmssl介绍（SM2、SM3、SM4算法） - 红雨520 - 博客园 (cnblogs.com)。

签名算法

签名方式

from gmssl import sm3, func
from random import randint
import gmpy2, math

a = 0x787968B4FA32C3FD2417842E73BBFEFF2F3C848B6831D7E0EC65228B3937E498
b = 0x63E4C6D3B23B0C849CF84241484BFE48F61D59A5B16BA06E6E12D1DA27C5249A
p = 0x8542D69E4C044F18E8B92435BF6FF7DE457283915C45517D722EDB8B08F1DFC3
E = EllipticCurve(GF(p), [0, 0, 0, a, b])
xg = 0x421DEBD61B62EAB6746434EBC3CC315E32220B3BADD50BDC4C4E6C147FEDD43D
yg = 0x0680512BCBB42C07D47349D2153B70C4E5D7FDFCBFA36EA1A85841B9E46E09A2
n = 0x8542D69E4C044F18E8B92435BF6FF7DD297720630485628D5AE74EE7C32E79B7
G = E(xg, yg)
da = 0x128B2FA8BD433C6C068C8D803DFF79792A519A55171B1B650C23661D15897263
Pa = da * G
xp, yp = Pa[:2]

def int_to_bytes(x, q = p, byteorder='big'):
    t = math.ceil(math.log2(q))
    l = math.ceil(t / 8)
    return int(x).to_bytes(l, byteorder)

ida = b'[email protected]'
entla = (int(8 * len(ida))).to_bytes(2, byteorder='big')
za = entla + ida + int_to_bytes(a) + int_to_bytes(b) +int_to_bytes(xg) + int_to_bytes(yg) + int_to_bytes(xp) + int_to_bytes(yp)
za = int_to_bytes(int(sm3.sm3_hash(func.bytes_to_list(za)), 16))
m = b'message digest'
e = int(sm3.sm3_hash(func.bytes_to_list(za + m)), 16)

while True:
    #k = randint(1,n-1)
    k = 0x6CB28D99385C175C94F94E934817663FC176D925DD72B727260DBAAE1FB2F96F
    x1, y1 = (k * G)[:2]
    r = mod(e + x1, n)
    if r and r + k != n:
        s = mod(gmpy2.invert(1 + da, n) * (k - r * da), n)
        if s:
            break

sign = (r,s)
print("The massage is:{}\nThe sign is:{}".format(m,sign))

验证方式

from gmssl import sm3, func
from random import randint
import gmpy2, sys

a = 0x787968B4FA32C3FD2417842E73BBFEFF2F3C848B6831D7E0EC65228B3937E498
b = 0x63E4C6D3B23B0C849CF84241484BFE48F61D59A5B16BA06E6E12D1DA27C5249A
p = 0x8542D69E4C044F18E8B92435BF6FF7DE457283915C45517D722EDB8B08F1DFC3
E = EllipticCurve(GF(p), [0, 0, 0, a, b])
xg = 0x421DEBD61B62EAB6746434EBC3CC315E32220B3BADD50BDC4C4E6C147FEDD43D
yg = 0x0680512BCBB42C07D47349D2153B70C4E5D7FDFCBFA36EA1A85841B9E46E09A2
n = 0x8542D69E4C044F18E8B92435BF6FF7DD297720630485628D5AE74EE7C32E79B7
G = E(xg, yg)
da = 0x128B2FA8BD433C6C068C8D803DFF79792A519A55171B1B650C23661D15897263
Pa = da * G
xp, yp = Pa[:2]

sign = (29375463689586694004441797766812698475196461455414953189449609414504196861893, 60122289537728058839560707331935112824530480120531053760171818818928767094586)
r, s = sign[:]

if (1 <= r <= n - 1) and (1 <= s <= n - 1):
    za = b'\xf4\xa3\x84\x89\xe3+E\xb6\xf8v\xe3\xac!h\xca9#b\xdc\x8f#E\x9c\x1d\x11F\xfc=\xbf\xb7\xbc\x9a'
    m = b'message digest'
    e = int(sm3.sm3_hash(func.bytes_to_list(za+m)),16)
    t = int(mod(r + s, n))
    if t:
        x1, y1 = (s * G + t * Pa)[:2]
        R = mod(e + x1, n)
        if R == r:
            print("Correct!")
            sys.exit()

raise Exception("Invalid signature!")

加密算法

加密方式

from gmssl import sm3, func
from random import randint
import gmpy2, math

a = 0x787968B4FA32C3FD2417842E73BBFEFF2F3C848B6831D7E0EC65228B3937E498
b = 0x63E4C6D3B23B0C849CF84241484BFE48F61D59A5B16BA06E6E12D1DA27C5249A
p = 0x8542D69E4C044F18E8B92435BF6FF7DE457283915C45517D722EDB8B08F1DFC3
E = EllipticCurve(GF(p), [0, 0, 0, a, b])
xg = 0x421DEBD61B62EAB6746434EBC3CC315E32220B3BADD50BDC4C4E6C147FEDD43D
yg = 0x0680512BCBB42C07D47349D2153B70C4E5D7FDFCBFA36EA1A85841B9E46E09A2
n = 0x8542D69E4C044F18E8B92435BF6FF7DD297720630485628D5AE74EE7C32E79B7
G = E(xg, yg)
db = 0x1649AB77A00637BD5E2EFE283FBF353534AA7F7CB89463F208DDBC2920BB0DA0
Pb = db * G
xp, yp = Pb[:2]

def int_to_bytes(x, q = p, byteorder='big'):
    t = math.ceil(math.log2(q))
    l = math.ceil(t / 8)
    return int(x).to_bytes(l, byteorder)

def KDF(z, klen):
    v = 256
    ct = 0x00000001
    H = b''
    for _ in range(math.ceil(klen / v)):
        H = H + (int(sm3.sm3_hash(func.bytes_to_list(z + int(ct).to_bytes(4,'big'))), 16)).to_bytes(32, 'big')
        ct = ct + 1
    return H[:klen / 8]


m = b'encryption standard'
# k = randint(1, n - 1)
k = 0x4C62EEFD6ECFC2B95B92FD6C3D9575148AFA17425546D49018E5388D49DD7B4F
c1 = k * G
# 在此C1选用未压缩的表示形式, 点转换成字节串的形式为PC||x1||y1, 其中PC为单一字节且PC=04, 仍记为C1
c1 = b'04' + int_to_bytes(c1[0]) + int_to_bytes(c1[1])

(x2, y2) = (k * Pb)[:2]
klen = 8 * len(m)
t = KDF(int_to_bytes(x2) + int_to_bytes(y2), klen)
c2 = int_to_bytes(int.from_bytes(m, byteorder='big') ^^int.from_bytes(t, byteorder='big'))

c3 = (int(sm3.sm3_hash(func.bytes_to_list(int_to_bytes(x2) + m + int_to_bytes(y2))), 16)).to_bytes(32, 'big')
c = c1 + c2 + c3
print(c)

解密方式

from gmssl import sm3, func
from random import randint
from Crypto.Util.number import long_to_bytes
import gmpy2, math, sys

a = 0x787968B4FA32C3FD2417842E73BBFEFF2F3C848B6831D7E0EC65228B3937E498
b = 0x63E4C6D3B23B0C849CF84241484BFE48F61D59A5B16BA06E6E12D1DA27C5249A
p = 0x8542D69E4C044F18E8B92435BF6FF7DE457283915C45517D722EDB8B08F1DFC3
E = EllipticCurve(GF(p), [0, 0, 0, a, b])
xg = 0x421DEBD61B62EAB6746434EBC3CC315E32220B3BADD50BDC4C4E6C147FEDD43D
yg = 0x0680512BCBB42C07D47349D2153B70C4E5D7FDFCBFA36EA1A85841B9E46E09A2
n = 0x8542D69E4C044F18E8B92435BF6FF7DD297720630485628D5AE74EE7C32E79B7
G = E(xg, yg)
db = 0x1649AB77A00637BD5E2EFE283FBF353534AA7F7CB89463F208DDBC2920BB0DA0
Pb = db * G
xp, yp = Pb[:2]

def int_to_bytes(x, q = p, byteorder='big'):
    t = math.ceil(math.log2(q))
    l = math.ceil(t / 8)
    return int(x).to_bytes(l, byteorder)

def KDF(z, klen):
    v = 256
    ct = 0x00000001
    H = b''
    for _ in range(math.ceil(klen / v)):
        H = H + (int(sm3.sm3_hash(func.bytes_to_list(z + int(ct).to_bytes(4,'big'))), 16)).to_bytes(32, 'big')
        ct = ct + 1
    return H[:klen / 8]

# 默认点转换为字节串的形式为PC||x1||y1, 其中PC为单一字节且PC=04
c = b'04$\\&\xfbh\xb1\xdd\xdd\xb1,Kk\xf9\xf2\xb6\xd5\xfe`\xa3\x83\xb0\xd1\x8d\x1cAD\xab\xf1\x7fbR\xe7v\xcb\x92d\xc2\xa7\xe8\x8eR\xb1\x99\x03\xfd\xc4sx\xf6\x05\xe3h\x11\xf5\xc0t#\xa2K\x84@\x0f\x01\xb8e\x00S\xa8\x9bA\xc4\x18\xb0\xc3\xaa\xd0\r\x88l\x00(dg\x9c=s`\xc3\x01V\xfa\xb7\xc8\n\x02vq-\xa9\xd8\tJcKvm:(^\x07H\x06SBm'
l = math.ceil(math.ceil(math.log2(p)) / 8)
c1 = E(int.from_bytes(c[2:2 + l], 'big'), int.from_bytes(c[2 + l:2 + 2 * l], 'big'))

x2, y2 = (db * c1)[:2]
klen = 8 * (len(c) - 2 * l - 2 - 32)
c2 = c[2 + 2 * l:-32]
t = KDF(int_to_bytes(x2) + int_to_bytes(y2), klen)
if int.from_bytes(t, byteorder='big') != 0:
    m = long_to_bytes(int.from_bytes(c2, byteorder='big') ^^int.from_bytes(t, byteorder='big'))
    
    u = (int(sm3.sm3_hash(func.bytes_to_list(int_to_bytes(x2) + m + int_to_bytes(y2))), 16)).to_bytes(32, 'big')
    c3 = c[-32:]
    if u == c3:
        print("Crrect! THe massage is:", m)
        sys.exit()
        
raise Exception("Error!")

参考资料：

1. 椭圆曲线密码学 - 维基百科，自由的百科全书 (wikipedia.org)
2. ECC - CTF Wiki (ctf-wiki.org)
3. Elliptic Curve Cryptography: breaking security and a comparison with RSA - Andrea Corbellini
4. Understanding How ECDSA Protects Your Data. : 15 Steps - Instructables
5. SM2椭圆曲线公钥密码算法
6. SM 国密算法踩坑指南 - 楼下小黑哥 - 博客园 (cnblogs.com)