ECDSA与SM2

椭圆曲线基本学习

文章：https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/#elliptic-curves

书籍：密码学原理与实践第6章

椭圆曲线方程

$\left\{ (x, y) \in \mathbb{R}^2\ |\ y^2 = x^3 + ax + b,\ 4 a^3 + 27 b^2 \ne 0 \right\}\ \cup\ \left\{ 0 \right\}$

群与阿贝尔群

$\mathbb{G}$ 是一个 群 (Group) 如果该集合上定义了一种运算 $+$ :

封闭性: $a \in \mathbb{G}, b \in \mathbb{G}$ ,则 $a + b \in \mathbb{G}$ ;
结合律: $a \in \mathbb{G}, b \in \mathbb{G}, c \in \mathbb{G}$ , $(a + b) + c = a + (b +c)$ ;
存在单位元 $0 \in \mathbb{G}$ , 使得 $a \in \mathbb{G}$ ， $a + 0 = 0 + a = a$ ;
每一个元素存在逆元：对于集合内任意元素 $a, \exists b \in \mathbb{G}$ 满足 $a + b = 0$ ，记做 $a = -b$

如果该群还满足:

交换律： $a \in \mathbb{G}, b \in \mathbb{G}$ ， $a + b = b + a$

则该群被称为阿贝尔群.

有限域

$\mathbb{F}$ 是一个 域(Field) 如果该集合上定义了两种运算 $(\cdot\ ;+)$

封闭性: $a \in \mathbb{F}, b \in \mathbb{F}$ ，则 $a + b \in \mathbb{G}; a \cdot b \in \mathbb{G}$
结合律: $a \in \mathbb{F}, b \in \mathbb{F}, c \in \mathbb{F}$ ， $(a + b) + c = a + (b +c);\ (a \cdot b) \cdot c = a \cdot (b \cdot c)$
存在加法单位元 $0 \in \mathbb{F}$ ，使得 $a \in \mathbb{F}$ ， $a + 0 = 0 + a = a$
存在乘法单位元 $e \in \mathbb{F}$ ，使得 $a \in \mathbb{F}$ ， $a \cdot e = e \cdot a = a$
交换律： $a \in \mathbb{F}, b \in \mathbb{F}$ ， $a + b = b + a$ ， $a \cdot b = b \cdot a$
逆元: 对于集合内任意元素 $a, \exists b \in \mathbb{F}; \exists c \in \mathbb{F}$ 满足 $a + b = 0; a \cdot c = e$ ，记做 $a = -b;\ a = c^{-1}$ ， $0^{-1}$ 无意义
分配律: $a \in \mathbb{F}, b \in \mathbb{F}, c \in \mathbb{F}$ ； $a \cdot (b + c) = a \cdot b + a \cdot c$

注意：加法逆元定义减法，乘法逆元定义除法

有限域指的是元素有限的域，属于计算机和密码学的基本数学原理之一

典型的有限域例子： $\mathbb{F}_p = \{0, 1, ..., p-1\}$ , $p$ 为质数，

定义 (+)： $a + b \mod p$

定义 ( $\cdot$ )： $a \cdot b \mod p$

计算 $a ^ {-1}$ : 拓展欧几里得算法

椭圆曲线上的群

曲线上的点的集合组成群
$x$ 无穷远点为单位元 $0$
点 $P$ 与它的逆 $Q$ 关于直线 $x = 0$ 对称
加法定义： $P + Q + R = 0$ ，如果这三点是非0点，且在同一条直线上(即一条直线与该曲线相交于三点，无穷远点为0) $=> P + Q = -R$

加法同样需要满足结合律.

几何意义上的加法

最重要的情况:

如果 $P=Q, P + Q$ ，物理意义是切线, 与曲线交于另一点 $R$ , 满足： $2P = -R$
如果 $P, Q$ 直线的第三点刚好为 $P\ or\ Q$ ，则也将包含一条切线，计算相同: $P + Q + P = 0\ => P + Q = -P$

代数意义上的加法

不同两点相加

$P(P_x, P_y), Q(Q_x, Q_y)，P\ \ne Q$ , 求 $T(T_x, T_y) = P + Q$

曲线方程： $y^2 = x^3 +ax + b$

计算斜率 $k = \frac{P_y - Q_y}{P_x - Q_x}$
曲线方程连立上直线方程 $y = kx + c$

=> $0 = x^3 - k^2x^2 + (a - 2kc)x + b - c^2$
铭记三次求根公式之三根之和是二次项系数的相反数: $T_x = k^2 - P_x - Q_x$
由于斜率 $k = \frac{T_y - P_y}{T_x - P_x}$ ， $T_y = k(T_x - P_x) + P_y$

相同两点相加

$P(P_x, P_y)$ ，求 $T(T_x,T_y) = P + P = 2P$

和上面基本相同，但计算直线斜率需要根据切线计算

对曲线方程两边求隐微分:

$\mathrm{d}(y^2) = \mathrm{d}(x^3 +ax + b)$ => $2y\mathrm{d}y = (3x^2 + a)\mathrm{d}x$

将 $P_x, P_y$ 带入，获得斜率:

$k = \frac{\mathrm{d}y}{\mathrm{d}x} = \frac{3P_x^2 + a}{2P_y}$

所以 $T_x = k^2 - 2P_x$ ， $T_y = k(T_x - P_x) + P_y$

标量积

$P(P_x, P_y)$ ，求 $nP = \underbrace{P + P + P + ... + P}_{\text{n times}}$ ， $n > 2$

将 $n$ 用二进制表示；以151为例子， $151_{10} = 10010111_2 = 2^0 + 2^1 + 2^2 + 2^4 + 2^7$
$nP = P + 2P + 2^2P + 2^4P + 2^7P$
根据上面两项计算规则，分别计算 $P, 2P，P + 2P$
计算 $2^2P = 4P = 2 \cdot 2P$ ，对 $2P$ 做相同点相加即可
同理计算 $2^3P = 8P = 2 \cdot 4P$ ， $2^4P = 16P = 2 \cdot 8P$ , 依次类推，每计算到一个二进制中为 $1$ 的阶数，完成一次两点相加即可

曲线上的有限域

取几何曲线上的坐标 $(x, y)$ ， $x, y \in \mathbb{F}_p$ , $p$ 是一个质数，形成一条离散曲线：
$\begin{array}{rcl} \left\{(x, y) \in (\mathbb{F}_p)^2 \right. & \left. | \right. & \left. y^2 \equiv x^3 + ax + b \pmod{p}, \right. \\ & & \left. 4a^3 + 27b^2 \not\equiv 0 \pmod{p}\right\}\ \cup\ \left\{0\right\} \end{array}$

从连续曲线上的加法可以推出有限域上的加法公式：

$P(P_x, P_y), Q(Q_x, Q_y)，P\ \ne Q$ , 求 $T(T_x, T_y) = P + Q$
$\begin{array}{rcl} k & = &(P_y - Q_y)(P_x - Q_x)^{-1} \bmod{p} \\ T_x & = & (k^2 - P_x - Q_x) \bmod{p} \\ T_y & = & [P_y + k(T_x - P_x)] \bmod{p} \\ \end{array}$
若 $P\ = Q$
$k = (3 P_x^2 + a)(2 P_y)^{-1} \bmod{p}$

曲线上的循环子群

循环子群的阶

对于离散曲线上的任意点 $P$ , 存在最小的 $n$ 使得 $nP = 0$ , 此时 $n$ 称作以 $P$ 为基点的循环子群的阶

找基点的方法

计算椭圆曲线的阶 $N$ (Schoof's algorithm: https://en.wikipedia.org/wiki/Schoof%27s_algorithm)
选择一个阶为 $n$ 的子群。n必须是素数且必须是 $N$ 的因子
计算辅因子 $h = N/n$
在曲线上选择一个随机的点 $T$
计算 $G = hT$ ，点乘
如果 $G = 0$ , 返回4，否则找到基点 $G$ , 子群的阶为 $n$ , $h$ 被称为辅因子

原理: 根据拉格朗日定理， $n$ 整除 $N$ 且 $n$ 为质因子，且任意点 $T$ 满足 $NT = 0$ ，则： $n(hT) = 0$ 恒成立, 那么若 $hT\ \ne 0$ ，则 $hT$ 作为基点的阶一定为 $n$ . ( $n$ 一定是素数, 否则不成立)

曲线上的离散对数问题

对于曲线上的基点 $G$ ，已知 $n$ 计算 $P = nG$ 是容易的

但是已知 $P, G$ , 计算 $n$ 是很困难的

ECDH & ECDSA

ECDH

CA选用共同曲线，并下发相同基点 $G$ ，其阶数为 $n$ , 则私钥的取值范围为 $d \in \{1, ..., n - 1\}$
Alice随机选择私钥 $d_A$ ，计算 Pubkey: $P_A = d_AG$ , 通过非安全信道传递给Bob
Bob随机选择私钥 $d_B$ ，计算 Pubkey: $P_B = d_BG$ ，通过非安全信道传递给Alice
Alice和Bob分别计算 $S = d_AP_b = d_BP_A = d_Ad_BG$ ，共享秘密成功

秘密共享成功后可以每次通信时明文传递salt, 每次通过 $key = KDF(salt + S)$ ，得到具体通信对称秘钥，加密通讯(TLS/SSL)

通过服务器动态生成的ECDH一般称作ECDHE

ECDSA

定义依然继承上文， $n$ 为 $G$ 作为基点的子群阶数

定义 $bit(x)$ 为表示 $x$ 需要的比特数；注意计算DSA时，若摘要值的比特数 $bits(digest(plain\_test)) > bits(n)$ ，则需要截取摘要值的低 $bits(n)$ 进行签名.

符号标记

截取前n-bits函数： $trun_{bit(n)}(digest)$

截取后的摘要值： $z = trun_{bit(n)}(digest(plain\_test))$ ， $digest$ 需要选择安全摘要算法：内部要求SHA-256以上

私钥： $d$

公钥： $P = dG$

签名算法

随机选择 $k \in \{1, ..., n -1 \}$
计算 $T = kG = (T_x, T_y)$
计算数字 $r = T_x \mod n$ ，若 $r = 0$ 则返回1
计算 $s = k^{-1}(z + rd) \mod n$ , 如果 $s = 0$ ，返回1
最后签名： $(r, s)$

验证算法

计算 $u_1 = s^{-1}z \mod n$
计算 $u_2 = s^{-1}r \mod n$
计算 $T' = u_1G\ +\ u_2P$

若 $T'_x = r \mod n$ ，验签成功，否则失败

正确性

我们尝试计算的其实还是 $T = kG$ ，若此时 $z$ 是正确摘要值，则有:

$k = s^{-1}(z + rd)\ mod\ n\ =>\ k = s^{-1}z + s^{-1}rd \mod n$

带入上式 $T = s^{-1}zG + s^{-1}rdG = u_1G + u_2(dG) = u1G + u_2P$

所以若 $z$ 发生改变，则此时计算出来的 $T'_x\ \ne\ r \mod n$

随机数相等下的私钥复原

若每次取出的随机数 $k$ 都相等：

获取两份签名与摘要： $z_1, (r_1, s_1)$ 和 $z_2, (r_2, s_2)$

容易得到: $r_1 = r_2 = (kG)_x \mod n$

之后通过 $s_1 - s_2$ 计算 $k$ ：

$s_1 - s_2 = k^{-1}(z_1 + rd - z_2 - rd) \mod n$

$=> k = (z_1 - z_2)(s_1 - s_2)^{-1} \mod n$

之后计算 $d$ 就很简单了:

$d = r^{-1}(s_1k - z_1) \mod n$

通过签名恢复公钥

若已知曲线上 $x = r$ 对应的两点 $R, R'$ ，则可以从签名 $(s, r)$ 中恢复公钥 $P$ :

$s = k^{-1}(z + rd) \mod n$

$=> skG = (z + rd)G$

注意 $kG = R$ 或者 $kG = R'$ , 分别作为备选带入上式，同时 $P = dG$ :

$=>\ sR - zG = r(dG)\ => P = r^{-1}(sR - zG)$

or $=>\ P = r^{-1}(sR' - zG)$

实现方法

点压缩：增加2bit来标识，一个用来标识 $R_x = r\mod n$ 或者 $R_x = r$ ，另一个标识 $R_y$ 是基数还是偶数：

因为 $R, R'$ 关于 $x$ 轴对称， $R_y + R'_y = 0 \mod p$ ，所以 $R_y ,P'_y$ 为一基一偶，可用一个bit标识

这样可以达到多用增加一个byte(04标记等)，来达成无需传递公钥即可验签

相关算法与代码：https://busy.org/@oflyhigh/397bw1

伪造签名

构造e方法

随机选择 $a, b \in \{1, ... n\}$ , 计算 $T = aG + bP, r = T_x$
计算 $s = rb^{-1}, e = arb^{-1}$
若 $e$ 为伪造摘要值, 可伪造合法签名 $(r, s)$

正确性:

$u_1 = s^{-1}e \mod \ n$

$u_2 = s^{-1}r \mod\ n$

将 $s, e$ 带入

$u_1G + u_2P = (rb^{-1})^{-1}(arb^{-1})G + (rb^{-1})^{-1}rP = (rr^{-1})(bb^{-1})aG + (rr^{-1})bP = aG + bP = T$

由于 $r = T_x \mod n$ ，校验通过

SM2签名

标记不变， $z = SM3(message)$ 是消息的摘要值（国密要求摘要使用SM3）， $d$ 是私钥， $P = dG$ 是公钥

签名算法

随机选择 $k \in \{1, ..., n -1 \}$
计算 $T = kG = (T_x, T_y)$
计算数字 $r = T_x + z \mod n$ ，若 $r = 0$ 则返回1
计算 $s = (1 + d)^{-1}(k - rd) \mod n$ , 如果 $s = 0$ ，返回1
最后签名： $(r, s)$

验证算法

计算消息值摘要 $z' = SM3(message)$
计算 $T' = sG + (r + s)P$
判断 $r\ ?= T'_x + z \mod n$

正确性

首先计算 $k$ :

$s = (1 + d)^{-1}(k - rd) \mod n$

=> $s(1 + d) + rd = k \mod n$ => $s + (s + r)d = k \mod n$

所以：

$T = kG = sG + (s + r)(dG) = sG + (s + r)P = T'$

因此可以推导：

$r = (T_x + z) = (T'_x + z) \mod n$

所以如果 $r = T'_x + z' \mod n$ ，则 $z'$ 验签通过，否则 $z'$ 摘要有误

最后编辑于：2020.04.21 14:07:46

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,001评论 6赞 498
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,210评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 161,874评论 0赞 351
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,001评论 1赞 291
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,022评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,005评论 1赞 295
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,929评论 3赞 416
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,742评论 0赞 271
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,193评论 1赞 309
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,427评论 2赞 331
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,583评论 1赞 346
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,305评论 5赞 342
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,911评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,564评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,731评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,581评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,478评论 2赞 352

ECDSA与SM2

椭圆曲线基本学习

椭圆曲线方程

群与阿贝尔群

有限域

椭圆曲线上的群

几何意义上的加法

代数意义上的加法

不同两点相加

相同两点相加

标量积

曲线上的有限域

曲线上的循环子群

循环子群的阶

找基点的方法

曲线上的离散对数问题

ECDH & ECDSA

ECDH

ECDSA

符号标记

签名算法

验证算法

正确性

随机数相等下的私钥复原

通过签名恢复公钥

实现方法

伪造签名

构造e方法

SM2签名

签名算法

验证算法

正确性

推荐阅读更多精彩内容