[译] 椭圆曲线密码学: 安全强度及对比RSA

本文翻译自爱尔兰AWS工程师 ANDREA CORBELLINI 关于椭圆曲线密码学四篇博客中的最后一篇, 原文采用 CC-BY 4.0 协议 进行授权
原文链接 : https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/
原作者: ANDREA CORBELLINI
译者: chxj1992

本文是 ECC:入门 系列文章的第四篇也是最后一篇.

上一篇文章中我们学习了两种算法: ECDH 和 ECDSA, 并且了解到了椭圆曲线上的离散对数难题在保证算法安全性上扮演的重要角色. 但是如果你还没忘的话, 我们并没有对离散对数难题的复杂性在数学上的证明: 我们相信它是"困难的", 但是我们还不能肯定. 在本文的第一个部分中, 我们将试着去了解在今天的技术条件下要解决它到底有多"难".

然后在第二个部分里, 我们将尝试解答以下问题: 既然已经有了 RSA 为什么我们需要椭圆曲线加密.

破解离散对数难题

下面我们将会看到两种解决椭圆曲线上离散对数难题最高效的算法: 大步小步法(Baby-Step, Giant-Step Algorithm) 以及 Pollard's rho 算法.

在正式开始之前, 让我们再来回顾一下什么是离散对数难题: 已知两点 P 和 Q, 找出令等式 Q = xP 成立的整数 x. 这些点属于椭圆曲线的某个子群, 该子群的基点为 G 阶为 n.

大步小步法

在学习算法之前让我们先快速思考一下: 我们可以将任意整数 x 写成 x = am + b 的形式, 其中 a, m 和 b 为任意的三个整数. 例如, 我们可以写出 10 = 2 × 3 + 4.

以此为基础, 我们可以把离散对数难题的方程重写为如下形式: $$ \begin{array}{rl} Q & = xP \\ Q & = (am + b) P \\ Q & = am P + b P \\ Q - am P & = b P \end{array} $$ 大步小步法是一种"中途相遇"算法. 相较于暴力破解攻击(尝试用所有 x 计算 xP 直到算出正确的 Q), 我们只需计算"少量" bP 和"少量" Q - amP 即可找到答案. 算法原理如下:

  1. 计算出$m = \left\lceil{\sqrt{n}}\right\rceil$
  2. 依次将 ${0, \dots, m}$ 中的每个元素作为 b 计算出 bP 并将计算结果保存到一个哈希表中
  3. 依次将 ${0, \dots, m}$ 中的每个元素作为 a:
    1. 计算出 amP
    2. 计算出 Q - amP
    3. 检查 Q - amP 的结果是否存在于点 bP 的哈希表中
    4. 如果点存在, 我们就找到了正确的 x = am + b

如你所见, 我们先一点一点地(小步)增加系数 b (1P, 2P, 3P, ...) 计算出点 bP. 然后, 我们大幅(大步)增加 am (1mP, 2mP, 3mP, ... 其中 m 是一个很大的数) 并计算点 amP.

大步小步法: 首先我们小步计算少量的点并将结果保存在一个哈希表中. 然后我们大步地计算出新的点并和在哈希表中保存的点比较. 一旦找到匹配的值, 解决离散对数难题就只剩简化方程了.

要理解算法的原理, 让我们先暂时忘记点 bP 被缓存在哈希表中从方程 Q = amP + bP 入手.

  • 当 a = 0 时, 我们将验证 Q 等于 bP, 其中 b 为0 到 m 中的整数. 这样我们相当于用 Q 跟 0P 到 mP 之间的所有点做了比较
  • 当 a = 1 时, 我们将验证 Q 等于 mP + bP. 相当于用 Q 跟 mP 到 2mP 之间的所有点做了比较( 译者注: 考虑到所有的 bP 已缓存在哈希表中, 对 m 个点的检查只需一次计算即可完成)
  • 当 a = 2, 我们相当于用 Q 跟 2mP 到 3mP 之间的点做了比较
  • ...
  • 当 a = m - 1, 我们相当于用 Q 检验了 (m-1)mP 到 $m^2 P = nP$ 之间的所有点

总结一下, 我们可以通过最多通过 2m 次加法和乘法完成了 0P 到 nP 之间的点(即所有可能的点)进行了检查(m 次小步, 以及最多 m 次大步).

考虑到通过哈希表进行检查只需要 $O(1)$ 的时间复杂度, 我们可以容易地得出该算法的时间复杂度和空间复杂度均为 $O(\sqrt{n})$ (或者按位长算 $O(2^{k / 2})$). 这依然是多项式时间级别的, 不过这比暴力破解要好得多了.

大步小步法实践

现在我们得看看 $O(\sqrt{n})$ 的复杂度在实践中意味着什么. 我们先选择一条标准曲线: prime192v1 (也叫 secp192r1, ansiX9p192r1). 曲线的阶为 n = 0xffffffff ffffffff ffffffff 99def836 146bc9b1 b4d22831. n 的开方大约等于 $7.922816251426434 · 10^28$.

现在想象一下 $\sqrt{n}$ 个点缓存在哈希表中. 假设每个点需要 32 个字节的空间: 这样我们的哈希表需要大约 $2.5 · 10^30$ 字节的内存. 而全世界的存储体量大于是 $10^21$ 字节. 这差不多比我们哈希表需要的空间还要少10个数量级! 即使我们一个点只占用 1 个字节的内存空间, 这依然比我们需要的少了很多.

这太惊人了, 更惊人的是我们刚刚提到的 prime192v1 只是一条最低阶的标准曲线. secp521r1(另一条 NIST 标准曲线)的阶约为 $6.9 · 10^156$ !

试验大步小步法

我写了一个用大步小步法计算离散对数难题的 Python脚本. 显然, 这个算法只能用于求解阶数很低的曲线: 千万别用来求解 secp521r1, 除非你想得到一个 MemoryError.

Curve: y^2 = (x^3 + 1x - 1) mod 10177
Curve order: 10331
p = (0x1, 0x1)
q = (0x1a28, 0x8fb)
325 * p = q
log(p, q) = 325
Took 105 steps

Pollard's ρ 算法

Pollard's ρ 是另一种用于计算离散对数难题的算法. 它和大步小步法有一样的时间复杂度 $O(\sqrt{n})$, 但仅需要 $O(1)$ 的空间复杂度. 如果大步小步法不能解决离散对数难题是因为巨大的空间需求, 那么 Pollard's ρ 算法能做到吗? 我们拭目以待 ...

首先还是再回顾一下离散对数难题: 已知 P 和 Q 找出令 Q = xP 成立的 x. 基于 Pollard's ρ 算法, 我们需要解决的问题稍有不同: 已知 P 和 Q, 找到整数 a,b 和 A,B (译者注: A , B 需要和 a, b 不同) 令 aP + bQ = AP + BQ 成立.

一旦找到满足条件的四个数, 我们可以通过方程 Q = xP 找出 x: $$ \begin{array}{rl} aP + bQ & = AP + BQ \\ aP + bxP & = AP + BxP \\ (a + bx) P & = (A + Bx) P \\ (a - A) P & = (B - b) xP \end{array} $$ 现在我们可以消去 P, 但在此之前别忘了循环子群的阶是 n, 所以点乘的系数要以 n 为模: $$ \begin{array}{rl} a - A & \equiv (B - b) x \pmod{n} \\ x & = (a - A)(B - b)^{-1} \bmod{n} \end{array} $$ Pollard's ρ 算法运算的基本原则很简单: 我们生成一个伪随机点序列 $X_1, X_2, ...$ 其中每个 X 都可表示为 $X = a_i P + b_i Q$. 序列通过如下如下伪随机方程生成: $$ \begin{array}{rl} (a_{i + 1}, b_{i + 1}) = f(X_i) \end{array} $$ 即: 上述方程 f 以当前序列中最后一个点的系数 $(a_i, b_i)$ 作为输入得出新的点 $X_{i + 1}$. 由此, 我们可以算出 $X_{i + 1} = a_{i + 1} P + b_{i + 1} Q$. 然后我们继续以 $a_{i+1}$ 和 $b_{i+1}$ 作为输入再生成后面的点.

实际上函数 f 内部到底是怎么实现的并不重要(获取某些方程可以更快的返回结果), 重点在于方程 f 能基于前一个点的系数生成序列中的下一个点, 这就是关于 $a_i$ 和 $b_i$ 我们知道这么多就足够了.

一个包含圆圈的序列图看起来可能就像上面那样: 有一些初始的点 ($X_0, X_1, X_2$), 然后由点 $X_3$ 到点 $X_8$ 构成的圆圈, 还有 $X_9 = X_3, X_10 = X_4$. 图形看起来像希腊字母 ρ, 由此得名.

我们一定会看到出现一个圆圈的理由非常简单: 点的总数是有限的, 因此他们迟早会发生重复. 只要我们看到圆圈出现, 我们就可以用上面的方程来解决离散对数难题.

现在的问题是: 我们怎么才能高效的找出这个圆圈? (译者注: 我的理解是这里的重点并不在于找到圆圈, 详见下一小节结尾的注解)

乌龟和兔子

为了找出圆圈, 我们有一种高效的方法: 那就是龟兔算法(也叫做弗洛伊德判圈算法). 下面这张动图展示了龟兔算法的原理, 这也是 Pollard's ρ 算法的核心.

已知曲线 $y^2 \equiv x^3 + 2x + 3 \pmod{97}$ 及曲线上的两点 $P = (3, 6)$ 和 $Q = (80, 87)$. 点属于一个 5 阶的循环子群.

我们用不同的速度遍历这个序列直到找出某个相同点有两对有不同的系数 (a,b) 和 (A,B). 在这个例子中, 我们找出了系数 (3,3) 和 (2,0), 据此我们可以算出对数 $x = (3 - 2)(0 - 3)^{-1} \bmod{5} = 3$. 这样我们就得出了正确结果 $Q = 3P$

我们有两个宠物: 乌龟和兔子, 让他们从左到右遍历我们的序列. 乌龟(图中绿色表示)速度慢, 一次遍历一个点; 兔子(红色表示)速度快, 每次跳过一个点.

过一会乌龟和兔子就会找到两个系数不同的相同点. 通过方程表达, 乌龟会找到系数(a,b), 兔子会找到系数(A,B) 即 $aP + bQ = AP + BQ$.

容易看出此算法只需要常数量的内存($O(1)$ 的空间复杂度). 计算渐进时间复杂度不是太容易, 但是我们可以构造一个概率性的证明来说明为什么其时间复杂度为 $O(\sqrt{n})$, 如我们之前说的那样. 此证明建立在"生日问题"的基础之上, 即关于两个人有相同生日的问题. 而这里我们关注的是两对系数(a,b)生成相同的点.

译者注: 实际上, 原作者关于 Pollard's ρ 算法的部分讲解是不够准确的. 根据作者的前面的说法系数(a,b)总由它前面点决定, 这也就是说, 相同点一定生成相同的系数, 而 GIF 动图中的点(3,6)第一次生成了 a=3,b=3 但第二次生成了 a=2, b=0. 这与前面的说法是矛盾的.

经过跟原作者讨论以及对照其提供的Python 脚本示例得知, 在作者提供的例子中, 下一个点的系数并非由前一个点生成, 而是由前一个点和前一个点的系数共同决定. 而下一个点又能由前一个点决定, 系数和点的不同循环周期创造了找到问题的解的可能. 如果想了解上述算法的实现细节, 建议阅读原作者提供的Python 脚本示例, 相信会有帮助.

试验 Pollard's ρ 算法

我写了一个利用 Pollard's ρ 算法计算离散对数难题的Python脚本. 脚本没有使用原始的 Pollard's ρ 算法, 而是做了一点轻微的修改(我采用了一种更高效的方法来生成伪随机序列). 脚本中包含了一些帮助理解的注释, 如果你对算法的细节感兴趣可以尝试去阅读它们.

和大步小步法的脚本类似, 这个脚本仅适用于很小的曲线, 并输出类似的结果.

Pollard's ρ 算法实践

我们说大步小步法无法用于实践是因为巨大的内存需要. Pollard's ρ 不同, 只需要很少的内存. 那么它实用吗?

Certicom公司1998年举行了一项计算109到359位的椭圆曲线离散对数难题的挑战. 时至今日, 只有109位的曲线被成功破解过. 最近一次成功的尝试发生于2004年. 引用维基百科:

奖励于2004年4月8日颁发给了一个以 Chris Monico 为代表的由2600人组成的团队. 他们也使用了某种并行 Pollard's ρ 算法, 耗时17个月完成.

正如我们所言, prime192v1 是"最小的"标准椭圆曲线之一. 我们还提到 Pollard's ρ 算法的时间复杂度为 $O(\sqrt{n})$. 如果我们采用跟 Chris Monico 同样的技术(相同的算法, 相同的硬件, 相同的机器), 计算 prime192v1 上的离散对数难题要多长时间呢? $$ 17\ \text{months}\ \times \frac{\sqrt{2^{192}}}{\sqrt{2^{109}}} \approx 5 \cdot 10^{13}\ \text{months} $$ 想要用这样的技术破解离散对数难题将有多困难, 通过上面的数字已经不言而喻了.

Pollard's ρ 算法对比大步小步法

我决定将大步小步法的脚本, Pollard's ρ 算法的脚本以及暴力破解脚本合并写了第四个脚本来比较他们的性能.

第四个脚本用不同的算法计算了某个"小型"曲线上所有点的离散对数难题并输出了各自花费的时间:

Curve order: 10331
Using bruteforce
Computing all logarithms: 100.00% done
Took 2m 31s (5193 steps on average)
Using babygiantstep
Computing all logarithms: 100.00% done
Took 0m 6s (152 steps on average)
Using pollardsrho
Computing all logarithms: 100.00% done
Took 0m 21s (138 steps on average)

如我们所料, 和其他两种算法相比暴力破解法极其缓慢. 大步小步法相比要快一些, 而 Pollard's ρ 算法比大步小步法满了3倍 (但使用的内存要少得多和较少的平均步数).

再看看步数: 用暴力破解法求解离散对数难题平均花费了5193步. 5193 和 10331 / 2 很接近(曲线的阶的一半). 大步小步法和 Pollard's ρ 算法分别花费了152步和138步. 这两个数和10331的平方根(101.64)很接近.

最后的思考

当讨论三种算法时, 我给出了很多数字. 在看这些数时保持谨慎的态度是十分重要的: 算法可以通过很多方法来优化, 硬件性能可以提升, 还可以开发专用的硬件.

而今天的方法不具有可操作性不意味着解决问题的方法无法改进. 更不意味着更好的方法不可能存在(再次提醒, 我们仍缺少关于离散对数难题复杂性的证明).

Shor's 算法

如果今天的技术不适用, 那么未来的技术呢? 嗯, 事情有点令人担忧: 有一种量子算法能够用于在多项式时间里解决离散对数难题: Shor's algorithm, 其时间复杂度为 $O((\log n)^3)$ 而空间复杂度为 $O(\log n)$.

量子计算机的精密程度距离能运行如Shor's这样复杂的算法还很遥远. 而对抗量子算法的需要也是值得我们去研究的. 我们现在加密的数据在未来也许并不安全.

ECC 和 RSA

让我们先忘掉量子计算, 毕竟它现在还产生不了什么威胁. 现在我要回答的问题是: 既然用 RSA 也能达到同样的目的, 为什么我们还需要椭圆曲线?

NIST 提供了一个简明的回答, 从下面这张在满足相同安全级别的条件下[对比 RSA 和 ECC 所需的秘钥长度表]就能看出.

RSA key size (bits) ECC key size (bits)
1024 160
2048 224
3072 256
7680 384
15360 521

注意看, RSA 的秘钥大小和 ECC 的秘钥大小之间并不存在线性关系(换句话说, 如果我们把 RSA 秘钥大小翻倍, ECC 的秘钥大小并不用翻倍). 这个表格告诉我们 ECC 不仅消耗的内存更少, 其生成秘钥和签名的速度也要快得多.

但为什么呢? 答案是相比于面向椭圆曲线上离散对数难题的 Pollard's ρ 和 大步小步法, 我们有针对 RSA 的更快的算法. 普通数域筛选法就是其中之一: 这是一种用于整数因式分解的方法, 该方法也可用于解决 RSA 的离散对数难题. 普通数域筛选法是截至目前求解整数因式分解最快的算法.

以上也适用于其他任何基于模运算的密码系统, 包括 DSA, D-H 和 ElGamal.

来自NSA的潜在威胁

译者注: NSA 全称 National Security Agency, 即美国国家安全局.

最难的地方到了. 现在我们已经讨论了算法和数学, 该谈谈人了, 涉及到人问题总是很复杂.

如果你还记得, 在前一篇文章中我们曾说过某些特定的椭圆曲线是很脆弱的, 为了解决来源可疑的椭圆曲线的信任问题我们为域参数增加了一个随机种子. 如果去看 NIST 提供的那些标准曲线, 我们可以发现他们全都是可验证随机的.

如果我们去看看维基百科的 "nothing up my sleeve" (译者注: 详见上篇文章)就能知道:

  • MD5 算法利用整数的 sine(正弦函数)生成其需要用到的随机数.
  • Blowfish 算法用 $\pi$ 的开始部分作为其随机数.
  • RC5 利用 $e$ 和黄金分割点生成其随机数.

这些数是随机的是因为它们的数字是均匀分布的. 它们也是没有疑点的, 因为它们是可以证明的.

现在问题来了: NIST 曲线里的随机种子是从哪来的? 很遗憾, 答案是: 我们不知道, 这些种子完全没有用于公正的依据.

存在这样的可能吗: NIST 研究了"有足够多量的"一类弱椭圆曲线并且尝试了很多可能的种子直到他们找到一个有漏洞的曲线? 我无法回答这个问题, 但这确实是一个合理且重要的问题. 我们知道 NIST 已经可以将[某种存在漏洞的随机数生成器]标准化(某种基于椭圆曲线实现的生成器). 也许他们也已经将某类弱椭圆曲线标准化. 我们怎么能确定呢? 我们不能.

理解"可验证的随机"和"安全"并非完全等价是很重要的. 重点不在于离散对数有多困难或者我们的秘钥有多长, 如果我们的算法存在漏洞, 那我们做什么也没用.

从这个角度上看 RSA 更好, 因为它并不需要可能被精心设计的特别的域参数. 如果我们不能信任算法的提供者或者我们不能自定义域参数的话, RSA(以及其他基于模运算的系统) 或许是一个不错的替代方案. 提前回答一个问题: 是的, TLS 可能也用了 NIST 的曲线. 如果你访问 https://google.com/, 你会看到连接使用了 ECDHE 和 ECDSA 算法, 和基于 prime256v1 (也叫 secp256p1) 的证书.

译者注: 作者提及风险并非危言耸听, 在2013年的"棱镜门"中, 斯诺登就曾披露 NSA 研发了一种随机数生成方法能够在加密产品中充当"后门", 并通过贿赂 RSA 公司高管利用其公司产品进行传播.

结束了!

我希望大家能喜欢这个系列文章. 我写这些文章的目的是希望大家能对椭圆曲线密码学的基础知识, 术语和概念有一个基本的理解. 如果我的目的达到了, 那么你现在应该能理解已有的基于 ECC 的密码系统并通过阅读那些"不太友好"的文档扩展你的知识. 在写这个系列文章时, 我可能跳过了很多技术细节并且采用了较为简单的术语, 但我觉得这样做你们可以更容易理解文章想要表达的意思. 我相信我在精简型和完整性之间做了一个不错的取舍.

记住, 如果仅仅是阅读了这个系列的文章, 你还不具备去实现一个 ECC 密码系统的能力: 安全性要求我们必须去了解更多微妙但重要的细节. 记住 Smart's attack 的前提和索尼犯过的错误 -- 这两个例子应该可以让你明白开发一个不安全的算法和利用其中的漏洞是多么的容易.

那么, 如果你有志于更深入地探索 ECC 的世界, 应该从哪里开始呢?

首先, 我们已经了解了质数域上的维尔斯特拉斯曲线, 但是你应该知道还有其他类型的曲线和域的存在, 具体来说:

  • 二元域上的 Koblitz 曲线. 它们是形如 $y^2 + xy = x^3 + ax^2 + 1$ (a 可能为0或1) 且有限域包含 $2^m$ (其中 m 为质数)个元素的曲线. 它可以实现特别高效的点加和标量乘法. 标准化的 Koblitz 曲线有 nistk163,nistk283,nistk571(这三条曲线分别定义在 163, 283 和 571 位的域上)
  • 二元曲线. 这类曲线和 Koblitz 曲线有类似的形式 $x^2 + xy = x^3 + x^2 + b$ (其中 b 是从随机种子生成的整数). 正如名字听上去那样, 二元曲线也被限制在二元域上. 标准化的二元曲线有 nistb163, nistb283 和 nistb571. 必须要说的是, 有越来越多的担忧认为 Koblitz 曲线和二元曲线可能并没有质数曲线那么安全.
  • Edwards 曲线, 可以写作 $x^2 + y^2 = 1 + d x^2 y^2$(其中 d 可以是0或1). 这类曲线特别有趣不仅是因为它们的点加和标量乘法特别快, 还因为其计算点加的公式在任何情况下($P \ne Q, P = Q, P = -Q$)都是一样的. 该特性充分考虑了旁路攻击的可能性, 它测量标量乘法计算花费的时间并基于该时间生成其标量参数. Edwards 相对比较新(2007年出现的)且尚未有如 Certicom 或 NIST 之类的权威机构将其标准化.
  • Curve25519 和 Ed25519 是两种分别为 ECDH 和 ECDSA 的某种变体特别设计的椭圆曲线. 和 Edwards 曲线一样, 这两种曲线也很快速并且能够抵御旁路攻击. 也和 Edwards 曲线一样, 这两种曲线也尚未被标准化所以我们不能再流行软件中看到它们的身影(除了 OpenSSH, 它从 2014 年起支持了 Ed25519 秘钥对).

如果你对 ECC 的实现细节感兴趣, 那么我建议你阅读 OpenSSL 和 GnuTLS 的源码.

最后, 如果你对其中的数学细节感兴趣而非其算法的安全性和效率, 那么你必须知道:

  • 椭圆曲线是亏格(genus)为 1 的代数变体
  • 无限远处的点的概念来源于影射几何(projective geometry) 并可以通过齐次坐标(homogeneous coordinates)来表现 (尽管椭圆曲线并不需要影射几何中的绝大部分特性).

另外, 别忘了研究有限域和场理论.

如果你对这些主题有兴趣的话可以通过上面的关键词去了解.

现在这个系列文章就正式完结了. 感谢所有人友好的评论, 私信以及邮件. 很多人问我会不会写一些其他类似主题的系列文章, 答案是: 也许吧. 我会接受建议, 但我不能做出任何承诺.

感谢各位的阅读, 下次再见!

译者后记

Andrea Corbellini 是一个善于总结和表达的工程师, 同时他还是一个友好且有耐心的人. 对于我在评论区提出的若干问题, 他总能为我提供快速而详细的解答, 令我受益颇多, 我想对 Andrea 的热心和分享精神表示感谢. 另外, 翻译这几篇文章的过程也让我对椭圆曲线密码学有了更清晰的理解(当然只是在基础层面上的). 同时, 希望我自己也能写出如此优秀的技术文章, 为技术社区的进步尽一份力.

Show Comments