椭圆曲线密码学简介（三）：ECDH和ECDSA

Posted on In Views: Disqus:
本文对在加密货币当中大量使用的椭圆曲线密码学进行介绍，本文在上一篇文章的基础上，进一步就采用椭圆曲线密码学的加密算法`ECDH`和数字签名算法`ECDSA`进行介绍。

本文主要翻译自这篇文章，并参考笔者之前翻译的另外一篇文章ECDSA算法如何保护我们的数据。

译者注

本文承接上文所引出的离散对数问题，在加密和数字签名两个场景就离散对数问题的具体应用方式展开具体的讨论。首先介绍了用于定义一个特定椭圆曲线离散域的子群的领域参数，然后基于这组领域参数分别在加密领域介绍ECDH算法，在数字签名领域介绍ECDSA算法。

领域参数（Domain parameters）

我们的椭圆曲线算法是在一个定义在一个椭圆曲线离散有限域的循环子群上面的，因此，我们的算法需要以下参数：

  • 标识有限域规模的素数pp
  • 椭圆曲线方程的系数aa和 bb
  • 产生子群的基准点GG
  • 子群的阶nn
  • 子群的协因子hh

一言以蔽之，我们算法的领域参数就是一个包含六个元素的元组(p,a,b,G,n,h)(p,a,b,G,n,h)

随机曲线（Random curves）

当我们在说离散对数问题是“hard”的时候，其实也并不完全对。有些特定的椭圆曲线所对应的离散对数问题可以用特殊目的的算法进行高效地破解。举个例子，所有满足p=hnp=hn的曲线（有限域的阶与椭圆曲线的阶相同）在Smart’s attack面前是脆弱的，该算法可以用经典计算机在多项式时间复杂度内解决离散对数问题。

现在，假设我给你一条椭圆曲线的领域参数。那么存在这样一个可能性，我已经发现了一些你并不知道的难度较低的椭圆曲线，并且还可能构思了一些破解我所给定的曲线的算法。我要如何向你证明我并不知道这条曲线的任何弱点呢？换句话说，我如何向你确保我所给你的这条曲线是安全的呢？

为了解决这类问题，有时候我们需要一个额外的领域参数：种子参数。这是一个用于产生方程系数和/或基准点的随机数。这些参数通过计算种子的哈希获得。众所周知，哈希的计算是“easy”的，但是求逆是“hard”的。

从一个种子产出一个随机曲线示意图：随机数被用于计算曲线的不同参数

如果我们想从领域参数反方向构建一个种子，需要解决哈希求逆的难题

通过种子产生的曲线可以被认为是随机的。这种通过哈希来产生参数的原则被称为nothing up my sleeve，通过哈希计算产生的数可以在根本上排除其具有掩藏特性的嫌疑，在密码学当中被大量的使用。

从某种程度上说，这个技巧可以确保给定的曲线没有被特殊的认为加工以向其作者暴露其脆弱性。事实上，如果我同时给你一条曲线和一个种子，这意味着我并不能随意选择参数，你也能够相对比较明确其实我并不能对该曲线进行特殊目的的攻击。

用于产生和验证随机曲线的标准算法在ANSI X9.62当中有进行描述，主要基于SHA-1，如果你对此比较好奇，你可以阅读这篇文档：a specification by SECG，了解产生可验证的随机曲线的算法。

原作者写了一段简单的Python 脚本来验证当前所有基于OpenSSL的随机曲线，强烈推荐看一下。

椭圆曲线密码学（Elliptic Curve Cryptography）

前面经过了很多的铺垫，不过最终我们来到了这里，可以讲下椭圆曲线密码学到底是什么了，简洁的版本如下：

  • 私钥（private key）是从{1,...,n−1}\{1,...,n-1\}随机选取的一个正整数dd，其中nn是子群的阶
  • 公钥（public key）则是点H=dGH=dG，其中GG是子群的基准点

你看，如果我们知道dd和 GG，结合其它的领域参数，求解HH是“easy”的。但是，如果我们知道HH和 GG，求解私钥dd是“hard”的，因为这需要我们解决离散对数问题。

接下来我们介绍两个基于椭圆曲线密码学的公钥算法：

  • ECDH（Elliptic Curve Diffie-Hellman）：主要用于加密
  • ECDSA（Elliptic Curve Digital Signature Algorithm）：主要用于数字签名

ECDH加密算法（Encryption with ECDH）

ECDH是Diffie-Hellman algorithm基于椭圆曲线的变种，更像是一个key-agreement protocol，而不是一个加密算法。因为，ECDH仅仅定义了各种密钥如何产生以及在各方之间如何交换，具体如何用这些密钥来对数据进行加密由用户自己决定。

这个问题是如下解决的：双方（还是喜闻乐见的Alice and Bob）想安全的交换信息，第三方可能截取信息，但可能无法进行解码。这是传输层安全（TLS）设计的原则之一，下面来一起看一个例子。

具体工作原理如下：

  • 第一步，Alice和Bob产生各自的私钥和公钥，Alice的私钥和公钥分别为dAd_A和 HA=dAGH_A=d_A G，Bob的私钥和公钥分别为dBd_B和 HB=dBGH_B=d_B G。需要注意的是，Alice和Bob使用相同的领域参数：在相同的有限域内定义的相同的椭圆曲线上的相同的基准点GG

  • Alice和Bob通过不安全的渠道交换他们的公钥HAH_A和 HBH_B，第三方可能截取HAH_A和 HBH_B， 但是无法仅仅通过公钥避开离散对数难题而推导出私钥dAd_A和 dBd_B

  • Alice用自己的私钥和Bob的公钥计算S=dAHBS=d_A H_B，然后Bob也用自己的私钥和Alice的公钥计算S=dBHAS=d_B H_A，事实上，对于Alice和Bob，这个SS是相同的：

S=dAHB=dA(dBG)=dB(dAG)=dBHA\begin{aligned} S &= d_A H_B \\ &= d_A(d_B G) \\ &= d_B(d_A G) \\ &= d_B H_A \end{aligned}

截取信息的中间人，只知道HAH_A和 HBH_B以及其它的领域参数，但是依然无法获得在Alice和Bob之间共享的秘密信息SS。这个问题就是众所周知的Diffie-Hellman problem，可以具体表述如下：

给出三个点PP，aPaP 和bPbP，求abPabP

或者等价于：

给出三个整数kk，kxk^x 和kyk^y，求kxyk^{xy}

后面这个等价基于幂模运算，在原始的Diffie-Hellman算法当中使用。

Alice和Bob可以非常方便的计算出共享的机密信息，对于截取信息的第三方来说却非常难

Diffie-Hellman problem背后的基本原理在Youtube video by Khan Academy当中也有解释，一会儿也会对采用幂模运算的原始Diffie-Hellman算法进行介绍。

采用椭圆曲线的Diffie-Hellman problem被认为是“hard”的，可以等同于离散对数问题的难度级别，不过并没有数学上面的严格证明。我们能够确认的是并没有比离散对数更难，因为解决离散对数问题是解决Diffie-Hellman problem的一种方式。

现在，Alice和Bob已经获得了共享的机密信息，这样他们就可以用对称加密的方式进行数据交换。

举个例子，Alice和Bob可以使用SS的 xx坐标作为安全加密算法AES或者3DES对信息进行加密的密钥。

这个和TLS的做法类似，区别在于，TLS将坐标于其它相关的数字连接起来，然后计算连接结果字符串的哈希。

ECDH应用举例（Playing with ECDH）

这段代码可以用来计算基于特定椭圆曲线的公钥和私钥以及共享加密信息。

不同于我们之前所使用的例子，这段代码使用了一个标准的曲线，而不是一个在一个很小域上面的简单曲线。这个曲线是secp256k1，也是比特币里面用于数字签名的曲线。具体的领域参数如下：

  • pp = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
  • aa = 0
  • bb = 7
  • xGx_G = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798
  • yGy_G = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8
  • nn = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
  • hh = 1

这些参数来自OpenSSL 源码

这段代码非常简单，包含了一些我之前描述过的算法：点加法、翻倍与累加、ECDH等等。建议阅读并跑一下，代码的输出如下：

1
2
3
4
5
6
Curve: secp256k1
Alice's private key: 0xc72e432030e533d59619f1ccb345015d874c5397e3fce829847b010e7f75e1a9
Alice's public key: (0x757abaa45b6938d6db9b91ca66f9ff7bac0e05ed78aa89a22a2a6a9d3bce0da4, 0x8815d45af0415f6d8d9506b15e989506968f159bf76b99a10f5200955ecba331)
Bob's private key: 0xce6f22b6d8dd621d23d0f1a6219e36619df2531d4985e47eb0c154375229e896
Bob's public key: (0x524a4c7666ec851b60a0540e24b66da2029d3baf8cb792d4e1a8f413a8a365a2, 0x39ded69ea9a5aac69fb53b736c310c267e16c3c0863576bd5aa4ebefb9b8b5db)
Shared secret: (0x68054720a6a2c983e95365c1addac5f5f5f5bd8239dce8757630247bb3368812, 0x7185800dc5f2010bb3f71f0c180d6b14f85a55302679f558d103277eaf55cd93)

Ephemeral ECDH

可能有些人除了ECDH，还听说过ECDHE。在ECDHE当中的“E”代表“Ephemeral”，指的是密钥的交换是暂时的。

举个ECDHE的应用例子，在TLS当中，服务器和用户端在每次建立起连接的时候都产生密钥对，然后用TLS证书对密钥进行签名后在双方进行交换。

ECDSA数字签名算法（Signing with ECDSA）

关于数字签名算法──ECDSA，在这篇文章已经有了较为详细的描述，不过为了行文的完整性，这里还是再复述一遍。

我们考虑这样的一个场景：Alice想用他的私钥dAd_A对一个信息进行签名，然后Bob想用Alice的公钥HAH_A来验证这个签名。没有其它人，只有Alice才能够产生这样有效的签名。因为Alice的公钥可以公开，因此，每个人可以检查这个签名。

再一次，Alice和Bob使用相同的领域参数。接下来要看的算法是ECDSA，应用与椭圆曲线的数字签名算法的变种。

ECDSA工作在加密信息的哈希上面，而不是信息本身。哈希函数的选择由用户自己确定，显然，为了确保安全性，还是需要采用密码级安全的哈希函数。加密信息的哈希需要进行截取以确保哈希的字节长度与子群的阶nn相等，被截取的哈希是一个正整数，通常用zz来表示。

Alice采用的信息签名算法工作流程如下：

  • 从{1,...,n−1}\{1,...,n-1\}中随机选择一个整数kk
  • 计算点P=kGP=kG，其中GG是领域参数当中的基点
  • 计算数字r=xPmod  nr=x_P \mod n，其中xPx_P是点PP的 xx坐标
  • 如果r=0r=0，选择另外一个kk
  • 计算s=k−1(z+rdA)mod  ns=k^{-1}(z+r d_A) \mod n，其中dAd_A是Alice的私钥，k−1k^{-1}是 kk模 nn的乘法逆元
  • 如果s=0s=0，则选择另外一个kk继续

最后(r,s)(r,s)是数字签名对。

Alice用他的私钥和随机数对哈希进行签名，Bob用Alice的公钥来验证信息是否正确签名

用朴实的语言来描述，该算法首先产生机密信息kk，然后将这个机密信息用椭圆曲线上面的点乘法（根据之前的知识，这个算法也是单向容易，反向难）隐藏在rr当中。然后将rr通过方程s=s=k−1(z+rdA)mod  ns=s=k^{-1}(z+r d_A) \mod n捆绑在加密消息哈希当中。

需要注意的是为了计算ss，我们需要计算kk 模nn的逆元，我们已经在前面讲到只有在nn是素数的时候这个算法才能够有效。如果子群有非素数的阶，那么ECDSA是不能使用的。几乎所有标准曲线都用一个素数阶，而那些具有非素数阶的曲线并不适合于ECDSA。

数字签名验证（Verifying signatures）

为了对数字签名进行验证，我需要Alice的公钥HAH_A，截取后的哈希zz，当然，也需要签名对(r,s)(r,s)，主要分以下三步：

  • 计算u1=s−1zmod  nu_1=s^{-1}z \mod n
  • 计算u2=s−1rmod  nu_2=s^{-1}r \mod n
  • 计算点P=u1G+u2HAP=u_1G+u_2 H_A

如果r=xPmod  nr=x_P \mod n则签名是有效的

算法的正确性（Correctness of the algorithm）

初看起来，隐藏在算法背后的逻辑并不是那么清晰，不过，当我们将目前所有列出的方程都放到一起就清楚明了了。

让我们从P=u1G+u2HAP=u_1G + u_2 H_A开始，我们知道，从公钥的定义可知，HA=dAGH_A=d_A G，其中dAd_A是私钥，我们可以将式子改写如下：

P=u1G+u2HA=u1G+u2dAG=(u1+u2dA)G\begin{aligned} P &= u_1G + u_2 H_A \\ &= u_1 G + u_2 d_A G \\ &= (u_1+u_2 d_A)G \end{aligned}

再次利用u1u_1和 u2u_2的定义，我们可以将式子改写如下：

P=(u1+u2dA)G=(s−1z+s−1rdA)G=s−1(z+rdA)G\begin{aligned} P &= (u_1+u_2 d_A)G \\ &= (s^{-1}z+s^{-1}rd_A)G \\ &= s^{-1}(z+rd_A)G \end{aligned}

这里为了简化，我们将后续的mod  n\mod n省略，另外，因为由GG产生的循环子群的阶为nn，因此，mod  n\mod n是多余的。

在前面，我们定义s=s=k−1(z+rdA)mod  ns=s=k^{-1}(z+r d_A) \mod n，方程两边都乘以kk在除以ss，我们得到k=s−1(z+rdA)mod  nk=s^{-1}(z+r d_A)\mod n，将这个方程代入前面计算PP的方程，我们有：

P=s−1(z+rdA)G=kG\begin{aligned} P &= s^{-1}(z+rd_A)G \\ &= kG \end{aligned}

这个方程与前面算法第二步当中产生签名算法计算PP的方程是相同的，那意味着产生签名和验证签名的时候，我们计算同一个点PP，只是采用了不同的方程，这也是算法有效的原因。

ECDSA应用举例（Playing with ECDSA）

当然，原作者同样写了一段python代码用来签名的产生和验证。这段代码与ECDH的代码有部分相同，特别是领域参数和公/私钥对产生算法。

下面是这段代码可能的一个输出内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
urve: secp256k1
Private key: 0xdef65e81fb94235e4e52d89c2cd29718bb42c8b944700c26c4cac2f16e5f0d73
Public key: (0x42186bb04e3070de0370eff1aa4b88d6e20db8013a2daf16146119bafb211290, 0x62d3d86ee0469feab6b3fff7a295084392ef506d6836a920583520aa7e40d20b)

Message: b'Hello!'
Signature: (0x77c9fcd26adec8871bd9983c7e3aaed841e15095c2c25b4a0c46f3c4448ae7a5, 0xeb058fb78abdad4e316b44c09f1af610c389c8ae29b6f4ad19489e1c903a6807)
Verification: signature matches

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

Message: b'Hello!'
Public key: (0x7526ae6817faace403ac5dfddd6adbb3ca42a04ad58fc418d43eca4ea1c08cbd, 0x11c8b82217d09e046529ad0692859be73c3cbeca36254fa9084dccf2c8b35cc3)
Verification: invalid signature

你可以看到，这段代码首先对一段信息进行签名（字节信息“Hello!”），然后对签名进行验证。然后，试图用同样的签名对另外一段信息（“Hi there”）进行验证且失败了。最后，试图采用另外一个随机的公钥对同样的信息进行验证也失败了。

kk的重要性（The importance of kk）

当我们产生ECDSA签名的时候，保持随机数kk的机密性和随机性非常重要。如果我们在多个签名使用了同一个kk，或者我们的随机数生成器某种程度上是可预测的，则很容易受到攻击而泄漏我们的私钥！

下面举一个多年前sony公司犯过的一个错误。通常，PS3平台只能运行Sony用ECDSA签名过的游戏。这样，如果我想为我的PS3平台创建一个新游戏，在没有Sony的签名的情况下，我无法进行私自发布。但是，问题在于所有Sony产生的签名使用了同一个随机数kk。

在这种情况下，我们只要购买两个签名过的游戏，抽取出它们的哈希z1z_1和 z2z_2以及签名对（(r1,s1),(r2,s2)(r_1,s_1),(r_2,s_2)），和领域参数一起就可以破解出Sony的私钥dSd_S。下面是具体步骤：

  • 首先，r1=r2r_1=r_2，因为r=xPmod  nr=x_P \mod n且 P=kGP=kG对于两个签名是一样的
  • 从ss的定义可以推导出(s1−s2)mod  n=k−1(z1−z2)mod  n(s_1-s_2)\mod n = k^{-1}(z_1-z_2)\mod n
  • 上式两旁都乘以kk，有：k(s1−s2)mod  n=(z1−z2)mod  nk(s_1-s_2)\mod n=(z_1-z_2)\mod n
  • 再两边除以(s1−s2)(s_1-s_2)得到：k=(z1−z2)(s1−s2)−1mod  nk=(z_1-z_2)(s_1-s_2)^{-1}\mod n

最后的式子可以让我们只用两个哈希和对应的签名来计算kk，得到kk以后我们可以使用ss的定义方程计算私钥：

s=k−1(z+rdS)mod  n→dS=r−1(sk−z)mod  ns=k^{-1}(z+rd_S)\mod n \rightarrow d_S=r^{-1}(sk-z)\mod n

即便kk不是静态的，如果是可预测的，同样的技术也可以用于对私钥的破解。

预告

下一篇，也是这个系列的最后一篇，主要关注离散对数问题的求解、若干椭圆曲线密码学的重要问题以及RSA与ECC的比较等等，希望大家不用错过。

参考资料