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) 如果该集合上定义了一种运算 +:

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

如果该群还满足:

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

则该群被称为阿贝尔群.

有限域

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

  1. 封闭性: a \in \mathbb{F}, b \in \mathbb{F}，则 a + b \in \mathbb{G}; a \cdot b \in \mathbb{G}
  2. 结合律: 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)
  3. 存在加法单位元 0 \in \mathbb{F}，使得 a \in \mathbb{F}，a + 0 = 0 + a = a
  4. 存在乘法单位元 e \in \mathbb{F}，使得 a \in \mathbb{F}，a \cdot e = e \cdot a = a
  5. 交换律： a \in \mathbb{F}, b \in \mathbb{F}， a + b = b + a，a \cdot b = b \cdot a
  6. 逆元: 对于集合内任意元素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}无意义
  7. 分配律: 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} : 拓展欧几里得算法

椭圆曲线上的群

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

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

几何意义上的加法

最重要的情况:

  1. 如果 P=Q, P + Q，物理意义是切线, 与曲线交于另一点R, 满足：2P = -R
  2. 如果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

  1. 计算斜率 k = \frac{P_y - Q_y}{P_x - Q_x}

  2. 曲线方程连立上直线方程 y = kx + c

    => 0 = x^3 - k^2x^2 + (a - 2kc)x + b - c^2

  3. 铭记三次求根公式之三根之和是二次项系数的相反数: T_x = k^2 - P_x - Q_x

  4. 由于斜率 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

  1. 将 n 用二进制表示；以151为例子，151_{10} = 10010111_2 = 2^0 + 2^1 + 2^2 + 2^4 + 2^7

  2. nP = P + 2P + 2^2P + 2^4P + 2^7P

  3. 根据上面两项计算规则，分别计算P, 2P，P + 2P

  4. 计算2^2P = 4P = 2 \cdot 2P，对2P做相同点相加即可

  5. 同理计算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 为基点的循环子群的阶

找基点的方法

  1. 计算椭圆曲线的阶N (Schoof's algorithm: https://en.wikipedia.org/wiki/Schoof%27s_algorithm)
  2. 选择一个阶为n的子群。n必须是素数且必须是N的因子
  3. 计算辅因子 h = N/n
  4. 在曲线上选择一个随机的点 T
  5. 计算G = hT，点乘
  6. 如果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

  1. CA选用共同曲线，并下发相同基点G，其阶数为 n, 则私钥的取值范围为d \in \{1, ..., n - 1\}
  2. Alice随机选择私钥d_A，计算 Pubkey: P_A = d_AG, 通过非安全信道传递给Bob
  3. Bob随机选择私钥d_B，计算 Pubkey: P_B = d_BG，通过非安全信道传递给Alice
  4. 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

签名算法

  1. 随机选择 k \in \{1, ..., n -1 \}

  2. 计算T = kG = (T_x, T_y)

  3. 计算数字 r = T_x \mod n， 若r = 0则返回1

  4. 计算s = k^{-1}(z + rd) \mod n, 如果s = 0，返回1

  5. 最后签名：(r, s)

验证算法

  1. 计算 u_1 = s^{-1}z \mod n
  2. 计算 u_2 = s^{-1}r \mod n
  3. 计算 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方法
  1. 随机选择 a, b \in \{1, ... n\}, 计算T = aG + bP, r = T_x
  2. 计算 s = rb^{-1}, e = arb^{-1}
  3. 若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，校验通过

相关算法与代码：https://github.com/GoldSaintEagle/ECDSA-SM2-Signing-Attack

SM2签名

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

签名算法

  1. 随机选择 k \in \{1, ..., n -1 \}

  2. 计算T = kG = (T_x, T_y)

  3. 计算数字 r = T_x + z \mod n， 若r = 0则返回1

  4. 计算s = (1 + d)^{-1}(k - rd) \mod n, 如果s = 0，返回1

  5. 最后签名：(r, s)

验证算法

  1. 计算消息值摘要z' = SM3(message)
  2. 计算T' = sG + (r + s)P
  3. 判断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' 摘要有误

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • HTTPS原理剖析
    原文链接：http://blog.jobbole.com/86660/ 1 前言 百度已经于近日上线了全站 HTT...
    xlhzj阅读 1,180评论 0赞 2
  • 区块链之加密原理总结(一)
    先放一张以太坊的架构图： 在学习的过程中主要是采用单个模块了学习了解的，包括P2P,密码学，网络，协议等。直接开...
    麻脸大叔阅读 11,535评论 1赞 10
  • 曲线上的“加密货币”(二)
    上一篇文章(《曲线上的“加密货币”(一)》)介绍了Bitcoin网络中对ECC的使用，说明了支付时解锁脚本与锁定脚...
    oceanken阅读 1,548评论 1赞 5
  • 密码学相关知识梳理
    前言 本文梳理主要基于书籍《Java加密与解密的艺术》、维基百科、百度百科以及网络上众多资料，如有涉及版权问题，请...
    hello_cyz阅读 2,334评论 1赞 7
  • 深入理解HTTPS
    级别： ★★☆☆☆标签：「HTTPS」「CA」「加密」作者： snow 审校： QiShare团队 前言 感谢伟...
    QiShare阅读 1,376评论 1赞 19

友情链接更多精彩内容