椭圆曲线密码学:ECDH和ECDSA

Posted by Mr小军 on 2018-10-30

这期内容是ECC:基本介绍(ECC:a gentle introduction)系列的第三篇.

在之前的内容中,我们介绍了什么是椭圆曲线并且为了在椭圆曲线的点上做一些数学运算我们定义了一个 群公理然后我们 限定椭圆曲线到整数模一个素数的有限域 .在这个限定下,我们介绍了椭圆曲线的点生成的循环子群并且介绍了术语 基点, 阶和 辅助因子.

最后,我们看到有限域上的标量乘法是一个“简单”问题,而离散对数问题似乎是一个“难”问题.现在我们将要看到所有这些在密码学中的应用.

域参数

我们的椭圆曲线算法运行在有限域上的椭圆曲线的循环子群中.因此我们的算法需要下面的参数:

  • 素数P用来指定有限域的大小
  • 椭圆曲线等式的系数a和b
  • 基点G用来生成我们的子群
  • 子群的阶n
  • 子群的辅助因子h
    结论是,我们的算法的 域参数是一个六元组(p,a,b,G,n,h).

随机曲线

当我说离散对数问题是“困难”的,其实并不完全正确.存在 一些椭圆曲线尤其脆弱并且允许用使用特定目的的算法来有效的解决离散对数问题.例如,所有满足p=hn(这时有限域的阶等于椭圆曲线的阶)的曲线对于Smart的攻击Smart’s attack都很脆弱,这个可以被用来在传统计算机上多项式时间内解决离散对数问题.

现在,假设我给你一个椭圆曲线的域参数.有可能我发现了一个其他人不知道的新的脆弱的曲线,并且可能我已经在给你的曲线构造了一个“快”算法来解决离散对数问题.我如何说服你相信,我并不知道这个曲线的任何弱点. 我如何向你保证这个曲线是“安全的”(这意味着我不能利用它发起特定目的的攻击)?

为了尝试解决这个问题,有时候我们有一个额外的域参数:种子 S.这是一个随机数,用来生成系数a和b,或者基点G,或者两者一起.这些参数是通过计算种子 S的散列值来生成的.散列值,我们都知到,是计算“简单”,但是逆推“困难”的.

如何从种子生成随机曲线的一个简单草图:一个随机数的散列值被用来计算曲线的不同参数.

如果我们想欺骗并且从域参数构造出一个种子,我们必须解决一个“难”的问题:散列值反转

通过种子生成的曲线被认为是 可验证的随机数.用散列值来生成参数的准测被称为nothing up my sleeve,并且被普遍的用在密码学中.

这种技巧应该给予一些保证,即 这个曲线没有被精心设计用来暴露一些漏洞给作者.事实上, 如果我和种子一起给你一个曲线,这意味着我并不能随心所欲的选择参数a和b,并且你应该相对的确定这个曲线不能被我用做特定目的的攻击.我为什么说“相对的”原因将在下一篇介绍.

ANSI X9.62描述了一种标准的用来生成和检测随机曲线的算法,该算法基于SHA-1.如果你好奇的话,你可以阅读这个算法,用于在 a specification by SECG 上生成可验证的随机曲线(寻找“可验证的随机曲线和基点生成器”).

我写了一个小Python脚本 验证当前OpenSSl提供的所有随机曲线.我强烈建议你看看.

椭圆曲线密码学

花费了很长时间,但是最后我们到达了!因此,纯粹而简单:

  1. 私钥是一个从{1,…,n-1}(n是这个子群的阶)选取的随机整数d.
  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 algorithm的一个变体.它实际上是一个密钥交换算法,而不是一个加密算法.这基本上意味着ECDH定义了(某种程度上)双方如何生成和交换密钥.实际上如何使用这个密钥加密数据取决于我们.

它解决了如下问题:双方(通常是Alice和Bob)想安全的交换消息,但是第三方(中间人)可能会截获消息,但是不能解密消息.这是TLS的一个原理之一,仅仅给你一个例子.

它是这样工作的:

  1. 首先, Alice和Bob生成了他们自己的公钥和私钥. Alice有私钥\(d_A\)和公钥\(H_A\)=\(d_{A}G\),Bob有\(d_B\)和\(H_B\)=\(d_{B}G\).注意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的H是相等的,事实上:

中间人实际上只知道\(H_A\)和\(H_B\)（以及其他的域参数）因此无法找出共享密钥\(S\)。这就是大家熟悉的Diffie-Hellman问题，可以表述如下：

给出三个点\(P\)，\(aP\)和\(bP\)，\(abP\)的结果是什么？

或者等价的：

给出三个整数\(K\),\(K^x\)和\(K^y\)，\(K^{xy}\)的结果是什么？

（Diffie-Hellman算法更早的基于模数运算的表示形式）

Diffie-Hellman密钥交换：Alice和Bob能够“轻易”计算出共享密钥，中间人需要解决“困难”的问题。

Diffie-Hellman问题背后的原理在一个不错的视频（ YouTube video by Khan Academy）中有很解释，视频后面解释了应用于模数运算的Diffie-Hellman算法（而不是椭圆曲线）.

椭圆曲线上的Diffie-Hellman问题别假设为一个“困难“问题。它被认为是和离散对数问题一样“困难”，虽然没有数学证明。我们能确定的是它不能“更困难”，因为解决对数问题是解决Diffie-Hellman的一个方法。

现在Alic和Bob获得了共享的密钥，他们可以用对称加密交换数据了。

例如，他们可以使用S的坐标x作为加密的密钥利用加密算法AES或者3DES来加密消息。这或多或少就是TLS做的，不同点是TLS把x坐标和一个和连接相关的数字连接起来，并且计算了它们组成的字节的散列值。

玩转ECDH

我写了另一个脚本（ another Python script） 来计算椭圆曲线上的公钥/私钥和共享密钥。

不像目前为止我们看到的其他例子，这个脚本使用了标准曲线，而不是一个小域上简单椭圆曲线。我选的曲线是secp256k1，来自 SECG ("椭圆曲线组的标准"由 Certicom 创立) 这个曲线也被用到了比特币中（ This same curve is also used by Bitcoin）用来做数字签名。这是域参数：

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

(这些数字是我们从 OpenSSL source code OpenSSL源码中取得的。)

当然你可以随意修改脚本使用其他的曲线和域参数，只要保证使用有素数域并且Weierstrass正常形式曲线，不然脚本不能正常运行。

这个脚本非常简单，包括了我们目前为止描述的一些算法：点加法，加倍（double）和相加(add),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。ECDHE中的这个"E"代表"Ephemeral",是指“密钥交换是短暂的”，而不是静态的。

例如ECDHE用在TLS中，客户端和服务端在连接建立时各自生成自己的公私钥对。然后密钥用TLS证书签名（用来鉴定）后在两端交换。

用ECDSA签名

方案如下：Alice想要用她的私钥（dA）签名一段消息，Bob想要用Alice的公钥（HA）验证签名。除了Alice其他人都不能创建一个合法的签名。任何人都能验证这个签名。

同样，Alice和Bob使用同样的域参数。我们将要看到的算法是ECDSA,是数字签名算法（Digital Signature Algorithm）在椭圆曲线中应用的一个变种。

ECDSA作用在消息的散列值上，而不是消息本省。散列函数的选择取决于我们自己，但是显而易见应该选择一个加密安全的散列函数（cryptographically-secure hash function）.消息的散列值应该被截断以便它的比特长度和n一样。（子群的阶）。被截断的散列值是一个整数被表示为z。

Alice执行用来签名消息的算法如下：

  1. 随机从{1,…n-1}选取一个整数（这里n依然是子群的阶）。
  2. 计算点P=kG（这里G是子群的基点）。
  3. 计算数字r=xp mod n（这里xp是点P对的x坐标）。
  4. 如果r=0，选择另一个k然后再试一次。
  5. 计算s=k^-1(z+rdA) mod n（这里dA是Alice的私钥，k^-1是k模n的乘法逆）。
  6. 如果s=0，选取另一个k再试一次。

（r,s）对就是签名

Alice用私钥dA和随机数k签名散列值z。Bob用公钥HA验证被正确签名的的消息。

简单来说，这个算法首先生成一个保密的k。多亏点的乘法这个k被隐藏在r中（正如我们所知道的，这个正向计算很“简单”，反向计算“很难”）。然后r根据等式s=k^-1(z+rdA) mod n绑定在消息的散列值。

注意，为了计算s，我们计算了k模n的逆。在前面的文章中我们说过了，只有当n是素数是这个才能保证有效。**如果子群没有素数阶，ECDSA无法使用。**所有标准曲线都有素数阶并未偶然，那些没有素数阶的不适合ECDSA。

验证签名

要验证签名我们需要用到Alice的公钥HA，（被截断的）散列值z，当然还有签名（r，s）。

  1. 计算整数u1=s^-1z mod n.
  2. 计算整数u2=s^-1r mod n.
  3. 计算点P=u1G+u2HA;
    只有当r=xp mod n时签名合法。

算法的正确性

可能在第一眼看到时这个算法的逻辑并不明显，然而，如果我们把前面写的等式放在一起，一切就会变得明了。

我们先从P=u1G+u2HA开始.我们从公钥的定义中知道，HA=dAG（这里dA是私钥）。我们可以这样写：

用u1和u2的定义，我们可以写成这样：

这里为了简介我们省略了"mod n"，并且因为G构造的循环子群的阶为n，因此"mod n"是多余的。

前面，我们定义s=k^-1(z+rdA) mod n。等式两边同时乘以k除以s，我们得到：

**这个和我们第二步用签名构造算法得到的P是相等的！**当构造签名和验证签名时我们用一组不同的等式计算出了相同的P。这就是为什么算法时正确的。

玩转ECDSA

当然，我写了一个脚本（a Python script ）来计算签名和签名验证。代码共享了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”），验证失败。最后，它尝试用签名验证正确的消息，但是使用另一个随机的公钥，验证失败。

k的重要性

当我们生成ECDSA签名，确保机密的k真的保密很重要。如果我们对所有签名使用同样的k，或者如果我们的随机数生成器在某些方面可预测，**一种攻击能够找出私钥！

这是索尼几年前犯的一个错误（This is the kind of mistake made by Sony a few years ago）.基本上，PlayStation 3游戏机只能运行ECDSA签名的游戏。这样，如果我想为PlayStation 3开发一个新游戏，在没有索尼的签名的情况下我没办法把它发布出去。问题是：索尼所有的签名都是用用一个静态的k构造的。

（显然索尼的随机数生成器受了XKCD和Dilbert的启发）

这种情况下，只要购买两款索尼签名的游戏我们就能够很容易的恢复出私钥ds，提取它们的散列值（z1和z2）和签名((r1,s1)和(r2,s2))，以及域参数。以下是如何操作：

  • 首先，注意r1=r2(因为r=xp mod n，P=kG对每一个签名都是一样的).
  • 考虑到(s1 - s2)mod n = k^-1(z1 -z2) mod n(这个结果可以直接由s的等式得出).
  • 现在等式两边同时乘以k： k(s1−s2) mod n= (z1−z2) mod n.
  • 除以(s1 -s2)得到k=(z1−z2)(s1−s2)^-1 mod n.
    最后一个等式能够让我们仅仅使用两个散列值和它们对应的签名计算k。现在我们根据s的等式提取出私钥：
s=k^-1(z+rds) mod n => ds=r^-1(sk-z) mod n
一些情况下如果k不是静态的但是是可预测的，同样的技术也能使用。

周末愉快

我真心希望你们能喜欢我写的这些。和往常一样，毫不犹豫的留下你们的评论，或者需要任何帮助可以戳我。（译者注：怎么戳？？？）

下周我将发布第四篇也就是这个系列的最后一篇文章。它将涉及解决离散对数问题的技术，椭圆曲线密码学的一些重要问题，以及ECC和RSA的对比。不要错过哦！！

哇，翻译真心比码代码累呀！！


FEATURED TAGS
FRIENDS