[译] 椭圆曲线密码学: ECDH 和 ECDSA

本文翻译自爱尔兰AWS工程师 ANDREA CORBELLINI 关于椭圆曲线密码学四篇博客中的第三篇, 原文采用 CC-BY 4.0 协议 进行授权
原文链接 : https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/
原作者: ANDREA CORBELLINI
译者: chxj1992

这篇文章是 ECC:入门 系列文章的第三篇.

在之前的文章中, 我们了解了什么是椭圆曲线以及定义了群律以便对椭圆曲线上的点进行一些数学计算.然后我们将椭圆曲线限定在了以一个质数为模的整数有限域上. 在此限制下, 我们看到了椭圆曲线上的点可以生成出循环子群并且我们还介绍了 基点, 余子式 的概念.

最后我们知道, 有限域上的标量乘法计算是一个"容易"的问题, 而离散对数问题却是非常"困难"的. 现在我们将会看到以上这些东西将如何融入密码学中.

域参数

我们的椭圆曲线算法是建立在有限域上的椭圆曲线的循环子群之上的. 因此, 我们的算法需要以下参数:

  • 质数 p 指定了有限域的大小
  • 椭圆曲线方程的系数 a 和 b
  • 生成子群的基点 G
  • 子群的阶 n
  • 子群的余子式 h

综上, 我们算法的域参数可以写作一个六元组 (p, a, b, G, n, h).

随机曲线

我说离散对数问题是"困难的", 但这种说法其实不完全正确. 因为某些类型的椭圆曲线其实是非常脆弱的, 其离散对数问题可以被特定的算法高效地解决. 比如, 所有满足等式 p = hn (即有限域的阶等于椭圆曲线的阶) 可以被Smart's attack轻松攻破, 这种算法可以借助经典计算机在多项式时间内解决这类离散对数问题.

现在, 假设我给了你一组椭圆曲线域参数. 那么存在这样一种可能: 我新发现了一类没有人知道的脆弱的曲线, 并且我设计了一种"快速"的算法可以计算出这类曲线上的离散对数问题.我如何说服你相信我其实并不知道有这样的漏洞? 我怎样向你保证这个曲线是"安全的" (在这个场景下指的是, 我没有办法利用它进行攻击)

为了解决这类问题, 有时我们还需要加入一个额外的域参数: 种子 S. 这是一个用于生成方程系数 a, b 或者基点 G 的随机数. 这些参数可以通过计算种子 S 的哈希值得到. 如我们所知, 哈希可以很"容易"地被计算出, 但想反推出原始值却很"困难".

这张简单的流程图展示一个种子是如何生成一条随机曲线的: 用随机数的哈希值计算出椭圆曲线的不同参数.

如果我们想作弊并试图通过曲线的参数构造出对应种子, 那我们必须解决一个非常"困难"问题: 反推哈希.

通过种子生成的曲线被称作 可验证随机. 利用哈希函数生成曲线参数的方法就是所谓的 "nothing up my sleeve" (译者注: "我的袖子里什么都没有" 这个说法来源于魔术, 意思是向其他人证明没有作弊), 这在密码学中很常用.

这个小技巧为 证明这并非提供者特意构造的存在漏洞的曲线 提供了一定程度的保证. 事实上, 如果我向你提供一个附带种子参数的曲线, 这就意味着我无法任意选择参数 a 和 b, 那么你就可以一定程度上确认我无法对这条曲线发起某种特定的攻击. 我这里说只是"在一定程度上"的原因将在下篇文章中作出解释.

用于生成和检查随机曲线的标准算法基于 SHA-1算法 实现, 并在 ANSI X9.62 中有具体的描述. 如果你好奇的话, 你可以阅读这篇 SECG规范 关于生成和验证随机曲线的算法(搜索"可验证的随机曲线和基点生成器"("Verifiably Random Curves and Base Point Generators")).

我写了一个Python小脚本可以用于验证OpenSSL目前支持的全部随机曲线. 我强烈建议你拉下来看看.

椭圆曲线密码学

虽然花费了很多时间, 不过我们终于到这儿了! 所以, 简单直白地说:

  1. 私钥是从 $\{1, \dots, n - 1\}$ 中选择的一个随机整数 d (n 是子群的阶)
  2. 公钥是点 H = dG (G 是子群的基点)

看见了吗? 如果我们已知 d 和 G (当然还有其他域参数), 算出 H 是很"容易的". 但是如果我们已知 H 和 G, 想要算出私钥 d 却很"困难", 因为这需要我们解决离散对数难题.

现在我们将要介绍两种以之为基础的公钥算法: 用于加密的 ECDH(Elliptic curve Diffie-Hellman) 和用于数字签名的 ECDSA(Elliptic Curve Digital Signature Algorithm).

ECDH 加密

ECDH 是 Diffie-Hellman 算法在椭圆曲线上的一个变体. 与其说它是一种加密算法不如说是一种秘钥交换协议来得更准确. 它的意思是说 ECDH定义了(某种程度上)秘钥如何生成以及在双方完成交换. 具体如何使用秘钥进行加密是由我们决定的.

这个问题可用如下方法解决: 双方(通常是Alice和Bob)希望能安全地交换信息, 而某个第三方(中间人)可能截获他们, 但是也许不能将他们解码. 这是TLS背后的原则之一, 可见下面的例子.

具体工作原理如下:

  1. 首先, Alice和Bob各自生成公钥和私钥. 已知Alice的私钥为$d_A$, 公钥为$H_A = d_AG$, Bob的私钥为$d_B$, 公钥为$H_B = d_BG$. 注意, Alice和Bob使用的域参数是相同的: 即相同的基点 G 和相同有限域上的相同椭圆曲线.
  2. Alice和Bob通过一个非安全的通道交换其公钥$H_A$和$H_B$. 中间人有可能截获公钥$H_A$和$H_B$, 但是除非解决离散对数难题否则无法找出$d_A$或$d_B$.
  3. Alice可以算出 $S = d_A H_B$(用自己的私钥和Bob的公钥), Bob可以计算出 $S = d_B H_A$(用自己的私钥和Alice的公钥). 注意Alice和Bob计算出的S是相同的, 因为: $$ S = d_A H_B = d_A (d_B G) = d_B (d_A G) = d_B H_A $$ 而中间人只知道 $H_A$ 和 $H_B$(还有其他的域参数)却并不能找出共享的秘钥 S. 这就是所谓的 Diffie-Hellman 难题, 可以作如下表述:
     已知三点 P, aP 和 bP, 求 abP 的结果 
    也可表述为:
     已知三个整数 k, $k^x$ 和 $k^y$, 求 $k^{xy}$ 的结果 
  4. (后一种表述形式是原始的Diffie-Hellman算法, 基于模运算实现.)

Diffie-Hellman秘钥交换: Alice和Bob可以"容易地"计算出共享秘钥, 而中间人却需要解决"困难的"问题.

Diffie-Hellman问题的原理在Khan Academy的这个视频里也做了阐述, 在视频里解释了基于模运算的Diffie-Hellman算法(不是基于椭圆曲线的).

椭圆曲线上的Diffie-Hellman难题被假定为一个"困难的"问题. 即使缺少严格的数学证明, 这也被认为是和离散对数难题一样"困难"的问题. 我们可以确定的是这个问题不会比离散对数难题"更加困难", 因为解决离散对数难题正是求解Diffie-Hellman难题的途径之一.

现在Alice和Bob得到了共享秘钥, 他们可以交换经过对称加密处理的数据了.

比如, 他们可以使用 S 的 x 坐标作为使用如 AES3DES 加密消息的秘钥. 这差不多也是 TLS 做的事, 区别在于 TLS 将 x 坐标和另一个与连接信息相关的数字相连后, 再计算出其结果的哈希值.

试验 ECDH

我创建了另一个Python脚本来计算公私钥和基于椭圆曲线的共享秘钥.

不同于我们目前看到的所有例子, 这个脚本使用了一条标准曲线而非某个小空间上的简单曲线. 我选择的曲线叫 secp256k1, 来自 SECG (Standards for Efficient Cryptography Group, 由 Certicom 建立). 比特币也使用了相同的曲线用于数字签名. 具体域参数如下:

  • p = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
  • a = 0
  • b = 7
  • $x_G = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798$
  • $y_G = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8$
  • n = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
  • h = 1

(以上参数来自 OpenSSL 源码)

当然, 你可以修改这个脚本或者选择其他的曲线和域参数, 不过要确保使用质数域和魏尔斯特拉斯普通态(Weierstrass normal form)曲线, 否则次脚本将无法正常工作.

这个脚本十分简单并且包含了我们前面介绍过的一些算法: 点加, 倍加, ECDH. 我建议你阅读并运行这些代码, 它将会输出如下结果:

Curve: secp256k1
Alice's private key: 0xe32868331fa8ef0138de0de85478346aec5e3912b6029ae71691c384237a3eeb
Alice's public key: (0x86b1aa5120f079594348c67647679e7ac4c365b2c01330db782b0ba611c1d677, 0x5f4376a23eed633657a90f385ba21068ed7e29859a7fab09e953cc5b3e89beba)
Bob's private key: 0xcef147652aa90162e1fff9cf07f2605ea05529ca215a04350a98ecc24aa34342
Bob's public key: (0x4034127647bb7fdab7f1526c7d10be8b28174e2bba35b06ffd8a26fc2c20134a, 0x9e773199edc1ea792b150270ea3317689286c9fe239dd5b9c5cfd9e81b4b632)
Shared secret: (0x3e2ffbc3aa8a2836c1689e55cd169ba638b58a3a18803fcf7de153525b28c3cd, 0x43ca148c92af58ebdb525542488a4fe6397809200fe8c61b41a105449507083)

临时性 ECDH

你们中的一些人可能听说过 ECDHE 而非 ECDH. 最后的 "E" 代表 "Ephemeral"(临时的) 这表示交换的秘钥是临时性的而非固定不变的.

如在 TLS 中, 当建立连接时客户端和服务端都在不断通过 ECDHE 生成各自的公私钥. 然后公钥将被 TLS 证书(用于认证)签名后在双方间交换.

用 ECDSA 签名

有如下场景: Alice 想用自己的私钥($d_A$)对消息做签名, 而 Bob 想用Alice的公钥($H_A$)验证签名. 除了 Alice 外没有人能给出有效的签名, 而任何人都能够验证其签名.

和之前一样, Alice 和 Bob 使用了相同的域参数. 我们将要介绍的算法是 DSA 算法在椭圆曲线上的一个变体叫 ECDSA.

ECDSA 作用于消息的哈希值而非消息本身. 这里的哈希算法我们可以自己选择, 但显然我们应该选择一种密码学安全的哈希算法. 消息的哈希会被截断, 其位长和n(子群的阶)的位长相等. 被截断的哈希是一个整数, 写作 z.

Alice用来签名消息的算法具体执行步骤如下:

  1. 从$\{1, \dots, n - 1\}$中选择一个随机整数 k (n仍然表示子群的阶)
  2. 算出点 P = kG (G 是子群的基点)
  3. 算出数字 $r = x_P \bmod{n}$ ($x_P$ 是 P点的 x 坐标)
  4. 如果 r = 0, 则重新选择一个k并重新执行以上步骤
  5. 计算 $s = k^{-1} (z + rd_A) \bmod{n}$ ($d_A$ 是 Alice的私钥, 而 $k^{-1}$ 是 以 n 为模的 k 的倒数)
  6. 如果 s = 0, 则再选一个 k 并重试上述步骤

这对 (r, s) 即为签名.

Alice 用其私钥 $d_A$ 和随机数 k 对 z 的哈希值进行签名. Bob 可以用 Alice 的公钥 $H_A$ 来验证消息已被正确签名.

直白地说, 这个算法首先生成了一个秘钥(k). 多亏点乘秘钥可以被隐藏在 r 里(众所周知, 从一个方向"简单", 从另一个方向"困难"). 然后 r 将通过方程 $s = k^{-1} (z + rd_A) \bmod{n}$ 和消息的哈希绑定.

需要注意, 为了计算出 s, 我们需要计算出以 n 为模的 k 的倒数. 在前一篇文章中我们曾提到只有当 n 是一个质数时算法才是成立的, 如果子群的阶不是质数的话, ECDSA 将不可用. 所以几乎所有的标准曲线的阶都是质数这并非是一个巧合, 毕竟那些有非质数阶的曲线并不适用于 ECDSA.

验证签名

为了验证签名我们需要知道 Alice 的公钥 $H_A$, (截断的)哈希值 z 以及签名 (r,s).

  1. 计算整数 $u_1 = s^{-1} z \bmod{n}$
  2. 计算整数 $u_2 = s^{-1} r \bmod{n}$
  3. 计算点 P = u_1 G + u_2 H_A

当 $r = x_P \bmod{n}$ 成立则证明签名是有效的.

算法的正确性

这个算法背后的逻辑可能无法被一眼看出, 但如果我们把前面写的两个等式放在一起看, 答案就会变得清晰一些.

我们从 $P = u_1 G + u_2 H_A$ 开始. 根据公钥的定义 $H_A = d_A G$ (d_A 为私钥) 我们可以得出: $$ \begin{array}{rl} P & = u_1 G + u_2 H_A \\ & = u_1 G + u_2 d_A G \\ & = (u_1 + u_2 d_A) G \end{array} $$ 根据 $u_1$ 和 $u_2$ 的定义, 我们可以得出: $$ \begin{array}{rl} P & = (u_1 + u_2 d_A) G \\ & = (s^{-1} z + s^{-1} r d_A) G \\ & = s^{-1} (z + r d_A) G \end{array} $$ 在此我们为了简化问题省略了两个等式中的 "mod n", 由于 G 生成的循环子群的阶为 n, 因此 "mod n" 实际上是多余的.

在前面, 我们定义了 $s = k^{-1} (z + rd_A) \bmod{n}$, 将等式两边同时乘以 k 除以 s, 我们可以得到: $k = s^{-1} (z + rd_A) \bmod{n}$. 带入 P 的方程, 我们可以得出: $$ \begin{array}{rl} P & = s^{-1} (z + r d_A) G \\ & = k G \end{array} $$ 这个关于 P 的方程和之前第二步签名算法中是一样的! 在生成签名和验证签名时, 我们通过不同的方程计算了出相同的点 P. 这就是算法能够成立的原因.

试验 ECDSA

当然, 我也写了一个用于生成签名的验证签名的 Python 脚本. 代码使用了 ECDH 脚本中的一些部分, 包括特定的域参数以及公私钥的生成算法.

下面是脚本的输出:

Curve: secp256k1
Private key: 0x9f4c9eb899bd86e0e83ecca659602a15b2edb648e2ae4ee4a256b17bb29a1a1e
Public key: (0xabd9791437093d377ca25ea974ddc099eafa3d97c7250d2ea32af6a1556f92a, 0x3fe60f6150b6d87ae8d64b78199b13f26977407c801f233288c97ddc4acca326)

Message: b'Hello!'
Signature: (0xddcb8b5abfe46902f2ac54ab9cd5cf205e359c03fdf66ead1130826f79d45478, 0x551a5b2cd8465db43254df998ba577cb28e1ee73c5530430395e4fba96610151)
Verification: signature matches

Message: b'Hi there!'
Verification: invalid signature

Message: b'Hello!'
Public key: (0xc40572bb38dec72b82b3efb1efc8552588b8774149a32e546fb703021cf3b78a, 0x8c6e5c5a9c1ea4cad778072fe955ed1c6a2a92f516f02cab57e0ba7d0765f8bb)
Verification: invalid signature

正如你所见, 脚本先对消息("Hello!")做了签名, 然后对签名进行验证. 然后, 它试图用另一条消息("Hi there!")对相同的签名进行验证, 验证失败了. 最后, 它尝试用正确的消息对签名进行验证, 但使用的公钥是随机生成的, 验证也失败了.

译者注:
ECDSA 签名与验签的逻辑实际上等效于如下构造出如下等式(也是离散对数难题), 其中 $u_1 = z/s, u_2 = r/s$: $$ u_1G + u_2H_A = kG $$ 由以上方程可推出: $$ u_2H_A = (k – u_1)G $$ $$ H_A = ((k – u_1)/u_2)G $$ 若私钥($d_A$)已知, 可得出: $$ d_AG = ((k – u_1)/u_2)G \quad 或 \quad d_A = (k – u_1)/u_2 $$ 如果私钥 $d_A$ 已知, k为任意随机数, 我们很容易(二元一次方程)就能求出使 $d_A = (k – u_1)/u_2$ 成立的 $u_1$ 和 $u_2$. 但如果不知道私钥 $d_A$ 的话, 则只能通过 $H_A = ((k – u_1)/u_2)G$ 找出 $u_1$ 和 $u_2$, 而这是一个离散对数难题. 而验证签名的过程相当于将告知的 $u_1$ 和 $u_2$ 带上述等式中进行验证, 如果成立则能证明提供签名的一方确实是知道私钥的.

(以上论述摘自 Programming Bitcoin Charter3:Elliptic Curve Cryptography P63)

k 的重要性

在用 ECDSA 生成签名时, 确保秘钥 k 不泄露是非常重要的. 如果我们用相同的 k 生成所有的签名, 或者随机生成的 k 是可以被预测的话, 攻击者就可能可以找出我们的私钥!

索尼在几年前就曾犯过类似的错误. 简单地说, PS3 游戏主机只能运行索尼用 ECDSA 签名过的游戏, 因此, 如果我想制作一款 PS3 的新游戏, 我是不可能在没有索尼授权的情况下发布这款游戏的. 但问题出在: 索尼使用某个固定的 k 生成了所有的签名.

(显然, 索尼的随机数生成显然是受到了 XKCDDilbert 这两幅漫画的启发.)

在这种情况下, 我们只要购买两款签过名的正版游戏就能很容易地恢复出索尼的私钥 $d_S$. 提取他们的哈希值($z_1$ 和 $z_2$)以及签名($(r_1, s_1)$ 和 $(r_2, s_2)$), 再加上椭圆曲线的域参数. 方法如下:

  • 首先, 有 $r_1 = r_2$ (因为 $r = x_P \bmod{n}$ 而 P = kG 对于两个签名都是相同的)
  • 又因为 $(s_1 - s_2) \bmod{n} = k^{-1} (z_1 - z_2) \bmod{n}$ (可由 s 的方程推出)
  • 等式两边同时乘以 k 可得: $k (s_1 - s_2) \bmod{n} = (z_1 - z_2) \bmod{n}$
  • 再除以 $(s_1 - s_2)$ 得 $k = (z_1 - z_2)(s_1 - s_2)^{-1} \bmod{n}$

通过以上推导可知, 我们能够通过两个哈希值和各自的签名计算出 k. 现在, 我们可以通过 s 的方程就能提取出私钥: $$ s = k^{-1}(z + rd_S) \bmod{n}\ \ \Rightarrow\ \ d_S = r^{-1} (sk - z) \bmod{n} $$ 当 k 虽然不是一个固定值但可以被预测时, 我们也可以采用类似的技术方法.

未完待续

真心希望大家能喜欢我写的东西. 和以前一样, 如果需要任何帮助请写下评论或发私信给我.

下周我将发布本系列文章的第四篇也是最后一篇. 这篇文章是讨论关于解决离散对数问题的技术, 椭圆曲线密码学里的一些重要问题, 以及 ECC 和 RSA 的对比. 可千万别错过哦!

Show Comments