ECC&SM2

ECC

基本内容

概念

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

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

运算规则

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

算法

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

加密应用

通常来说，加密过程先选择一条椭圆曲线 $E_q(a,b)$ ，然后选择其上的一个生成元 $G$ ，假设其阶为 $n$ ，之后再从区间 $[1, n - 1]$ 选择一个正整数 $d_a$ 作为密钥，计算 $Q_a=d_a*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，计算点 $(x 1, y 1) = k G$ 与点 $x2,y2)=kP_a$ 。最后计算 $C = m + (x 2, y 2)$ 并将 $((x 1, y 1), C)$ 发送给A。
在A解密信息时，只需计算 $m = C - d_a(x1,y1)$ 即可。

ECDSA(Elliptic Curve Digital Signature Algorithm)

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

破译手段

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

n很小

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

baby-step giant-step

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

import timea = 1234577
b = 3213242
n = 7654319
k = 1584718
E = EllipticCurve(GF(n), [0, 0, 0, a, b])
G = E(5234568, 2287747)
Q = k * Gprint('Curve: {}'.format(E))
print('G = {}'.format(G))
print('Q = {} = {} * G'.format(Q,k))time_start = time.time()
m = int(sqrt(n)) + 1r = G
baby_steps = {r: 1}
for b in range(2, m):r = r + Gbaby_steps[r] = br = Q
s = m*Gfor a in range(m):try:b = baby_steps[r]except KeyError:passelse:steps = m + aans = a * m + bbreakr = r - stime_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$ 使得 $a G + b Q = A G + BQ$ 成立，那么可以得到 $(a + bk) G = (A + B k) 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 timea = 1234577
b = 3213242
n = 7654319
k = 1584718
E = EllipticCurve(GF(n), [0, 0, 0, a, b])
G = E(5234568, 2287747)
Q = k * Gprint('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, matha = 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'ALICE123@YAHOO.COM'
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 = 0x6CB28D99385C175C94F94E934817663FC176D925DD72B727260DBAAE1FB2F96Fx1, 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:breaksign = (r,s)
print("The massage is:{}\nThe sign is:{}".format(m,sign))

验证方式

在这里插入图片描述

from gmssl import sm3, func
from random import randint
import gmpy2, sysa = 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, matha = 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 = 256ct = 0x00000001H = 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 + 1return 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, sysa = 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 = 256ct = 0x00000001H = 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 + 1return 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!")

参考资料：

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