[译] 椭圆曲线密码学: 入门

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

如果你们知道什么是椭圆曲线密码学, 那你们应该也听说过 ECC, ECD或者ECDSA. ECC是椭圆曲线密码学(Elliptic Curve Cryptography)的首字母缩写, 而另外两个都是基于ECC实现的算法.

如今, 我们在 TLS, PGPSSH 里都能找到椭圆曲线密码学的身影, 这三种技术可以说是现代互联网和数字世界的基础, 更别提ECC在比特币和其他各种加密货币中发挥的巨大作用了.

在ECC开始流行以前, 绝大多数公钥加密算法都基于 RSA, DSA 和 DH 实现. 和ECC一样, RSA等如今仍然发挥着重要的作用. RSA等算法由于其相对容易解释的原理和可以轻松实现的简化模型, 让很多人都能大概理解RSA是怎么一回事. 而对其中大多数人来说, ECC的实现原理却仍是个谜.

希望通过这一系列的文章我能将你带入椭圆曲线密码学的世界. 我的目标并不是提供一份完整详尽的ECC指南(这样的资料在网上到处都能找到), 而是通过尽量简单的方式说明 什么是ECC以及它为什么是安全的, 而不必在冗长的数学证明和枯燥的实现细节上花费太多的时间.另外, 我还会提供一些交互式的可视化小工具和脚本来帮助你更好的理解内容.

具体来说, 本系列文章将涉及以下内容:

  1. 实数域上的椭圆曲线和群论 (本篇文章将会讨论)
  2. 有限域上的椭圆曲线和离散对数难题
  3. 秘钥对的生成及两种ECC算法: ECDH和ECDSA
  4. ECC破解算法和与RSA的对比

为了更好的理解我们将要讨论的内容, 你需要先学习一点关于集合论, 几何学和模运算的基础, 并熟悉关于对称性和非对称密码学相关的基础知识. 最后, 你需要对什么是"简单"问题, 什么是"复杂"问题以及他们在密码学中锁扮演的角色有一个清晰的认识.

椭圆曲线

首先, 什么是椭圆曲线? Wolfram MathWorld 给出了一个超赞且完善的定义. 但是考虑到本文目标, 可以把椭圆曲线简单的理解成一个满足以下方程式的点的集合:

$$y^2 = x^3 + ax + b$$且满足 $4a^3 + 27b^2 \ne 0$ (以便排除奇点). 上面的方程被称为椭圆曲线的维尔斯特拉斯标准形式(Weierstrass normal form).
不同椭圆曲线的形状 (b=1,  a 从 2 变到 -3).
奇点的类型: 在左图曲线上存在一个尖锐点($y^2 = x^3$), 右图曲线发生了自交($y^2 = x^3 - 3x + 2$), 它们都不是有效的椭圆曲线.

根据a和b值的不同, 椭圆曲线可能在平面上呈现出不同的形状, 我们可以很容易的看出,椭圆曲线是关于x轴对称的. 我们还需要一个无穷远处的点(也叫理想点)作为曲线的组成部分, 从现在起, 我们将用0(数字0)表示这个点.如果要显示的表现这个无穷远处的点, 可以通过下面的方程来完善我们的定义:

$$\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}$ 成为一个群, 就必须先定义一个加法运算并且这个集合应该遵循以下四条特征:

  1. 封闭性: 如果a和b都是 $\mathbb{G}$ 中的元素, 那么 a+b 也应该是 $\mathbb{G}$ 中的元素
  2. 结合律: $(a + b) + c = a + (b + c)$
  3. 存在单位元 0 满足 $a + 0 = 0 + a = a$
  4. 任何元素都有一个与之相对应的逆元, 比如: 任何元素a都存在一个b使之满足 $a + b = 0$
如果我们再加上第五个条件:
交换律: $a + b = b + a$
那么这个群就可以被称作阿贝尔群

根据加法的一般概念, 整数集合 $\mathbb{Z}$ 是一个群 (更准确的说, 是一个阿贝尔群). 而自然数集合就不是一个群, 因为它无法满足第四个特征.

群很棒因为如果我们能证明以上四条特征是成立的, 那么我们就可以自动得到群的其他一些特征. 比如: 单位元是唯一的; 逆元也是唯一的, 意思是: 对群中的任何元素a来说, 有且仅有b使 $a + b = 0$ 成立(也可以把b写成-a). 这些关于群的特性稍后将会直接或间接的发挥重要的作用.

椭圆曲线上的群律

我们可以在椭圆曲线上定义一个群, 具体来说:

  • 群里的元素是椭圆曲线上的点
  • 单位元是指在无穷远处的点 0
  • 点P的逆元是指其关于x轴对称的点
  • 加法可以根据以下规则定义: 找到三个在一条线上非零的点P,Q和R, 他们之和满足 $P + Q + R = 0$
在一条直线上的三点之和为0

注意最后一条规则, 我们只要求三个点位于一条直线上, 但是并没有要其顺序. 这意味着如果 P,Q和R在一条直线上, 则有 $P + (Q + R) = Q + (P + R) = R + (P + Q) = \cdots = 0$. 这样, 我们有了一个直观的证明, 我们定义的加法运算也满足结合律和交换律, 这是一个阿贝尔群.

到目前为止, 一切都很顺利. 但我们到底应该如何计算任意两个点之和呢?

几何意义上的加法运算

还好这是一个阿贝尔群, 我们可以把 $P + Q + R = 0$ 写成 $P + Q = -R$. 借助这种形式的方程, 我们可以推导出一种计算P和Q之和的几何方法: 过点P,Q画一条直线, 这条直线将和曲线相交于第三个点R(这意味着P,Q和R位于一条直线上). 点R的逆元-R正是 $P + Q$ 的结果.

过 P 和 Q 画一条直线交于第三点 R, 关于x轴与之对称的点 -R 即为 P+Q 之和.

如果再做一些细化, 这个几何式的方法是行得通的. 具体来说, 我们需要回答以下几个问题:

  • 当 P = 0 且 Q = 0 时会怎么样? 显然我们没法画出这样的直线(因为0根本不在xy平面上), 但是根据我们对单位元 0 的定义, $P + 0 = P$ 和 $0 + Q = Q$ 对任何 P 和 Q 都成立
  • 当 P = -Q 时会怎么样? 在这种情况下, 穿过两点的直线将与x轴垂直且不与其他任何点相交. 但当 P 是 Q 的逆元, 根据逆元的定义则有 $P + Q = P + (-P) = 0$
  • 当 P = Q 时会怎么样? 在这种情况下, 过这个点可以作出无穷多条直线. 这里问题就开始变得有点复杂了. 首先考虑当 $Q' \ne P$, 而让 Q' 逐渐接近 P 时会发生什么?

当两点逐渐靠近, 过这两个点的直线将变成曲线的一条切线
当 Q' 朝着 P 移动时, 穿过 P 和 Q' 的直线将变为曲线的一条切线. 据此我们可以得出解决 $P + P = -R$, R 是 P 点在曲线上的切线与曲线的交点.

  • 如果 $P \ne Q$, 而又不存在第三个点 R 呢? 这种情况和前一种很类似, 事实上这就是一条线经过了 P 和曲线上的一个切点 Q 的情况

如果直线与曲线只相交于两点, 这表明这条线与曲线相切. 
很容易就能看出两点之和为切点关于x轴的对称点.

假设 P 是曲线上的切点, 在前一种情况下我们用 $P + P = -Q$ 表示, 这个方程也可以写成 $P + Q = -P$. 换句话说, 现在如果 Q 是曲线上的切点, 那么上面的等式就变成了 $Q + P = -Q$.

现在, 几何式的方法已经可以覆盖所有的场景了, 只需要一支铅笔和一把尺子我们就能计算出如何椭圆曲线上两个点的和. 如果你有兴趣的话, 也可以看看我做的这个计算椭圆曲线加法的 HTML5/JavaScript版可视化工具 !

代数意义上的加法运算

如果你想用计算机来算两点之和, 我们就需要将几何式的求解方法转换成代数式的方法. 把上面的求解方法翻译成一系列的方程看起来很容易, 但是因为需要求解三次方程实际上也比较枯燥. 所以在这里我会直接给出结果.

译者注: 椭圆曲线加法方程的代数方法推导在 Promgramming BitCoin 的第二章 中给出了详细的演算过程, 有兴趣的同学可以前往阅读

首先, 我们先排除各种麻烦的边界情况. 我们已经知道 $P + (-P) = 0$, 我们也知道 $P + 0 = 0 + P = P$, 所以在我们的方程式里我们会排除这两种情况, 我们只用考虑 两个非零点, 以及非对称点 $P = (x_P, y_P)$ 和 $Q = (x_Q, y_Q)$.

如果 P 和 Q 不相等 ($x_P \ne x_Q$), 则过两点的直线的斜率为: $$ m = \frac{y_P - y_Q}{x_P - x_Q} $$ 这条直线与椭圆曲线的交点 $R = (x_R, y_R)$ 有: $$ \begin{array}{rcl} x_R & = & m^2 - x_P - x_Q \\ y_R & = & y_P + m(x_R - x_P) \end{array} $$ 或者写成: $$ y_R = y_Q + m(x_R - x_Q) $$ 则有 $(x_P, y_P) + (x_Q, y_Q) = (x_R, -y_R)$ (注意等式中的符号并始终牢记公式 $P + Q = -R$)

如果想要验证结果的正确性, 我们需要检查 R 是否是曲线上的一个点, 以及 P, R 和 Q 是否在一条直线上. 验证 P, R 和 Q 在一条直线上很容易, 但是检查 R 是否是曲线上的一点就没那么容易了, 因为这又需要求解三次方程, 会比较麻烦

作为替代方案, 我们可以用一个可视化工具通过一个例子来说明. 现在有 $P = (1, 2)$ , $Q = (3, 4)$ 在曲线 $y^2 = x^3 - 7x + 10$ 上, 这两点之和为 $P + Q = -R = (-3, 2)$. 我们来看看带入方程是否成立: $$ \begin{array}{rcl} m & = & \frac{y_P - y_Q}{x_P - x_Q} = \frac{2 - 4}{1 - 3} = 1 \\ x_R & = & m^2 - x_P - x_Q = 1^2 - 1 - 3 = -3 \\ y_R & = & y_P + m(x_R - x_P) = 2 + 1 \cdot (-3 - 1) = -2 \\ & = & y_Q + m(x_R - x_Q) = 4 + 1 \cdot (-3 - 3) = -2 \end{array} $$ 很好, 结果是正确的!

注意, 上面的方程在 P 或者 Q 是曲线上的切点时仍然是成立的. 让我们再试试 $P = (-1, 4)$ , $Q = (1, 2)$ 的情况. $$ \begin{array}{rcl} m & = & \frac{y_P - y_Q}{x_P - x_Q} = \frac{4 - 2}{-1 - 1} = -1 \\ x_R & = & m^2 - x_P - x_Q = (-1)^2 - (-1) - 1 = 1 \\ y_R & = & y_P + m(x_R - x_P) = 4 + -1 \cdot (1 - (-1)) = 2 \end{array} $$ 我们得出 $P + Q = (1, -2)$, 这个结果和用可视化工具算出的结果是一样的

当 $P = Q$ 时, 处理起来会有点区别: 求 $x_R$ 和 $y_R$ 的方程是一样的, 不过由于 $x_P = x_Q$, 我们需要用不同的方程来计算斜率: $$ m = \frac{3 x_P^2 + a}{2 y_P} $$ 正如我们所料, m 的表达式是如下方程的一阶导数: $$ y_P = \pm \sqrt{x_P^3 + ax_P + b} $$ 检查 R 点位于椭圆曲线上且穿过 P, R 两点的直线与曲线有且仅有两个交点就能证明结果的正确性, 但和前面一样, 我们还是通过一个例子来验证, 当 P = Q = (1, 2) 时 $$ \begin{array}{rcl} m & = & \frac{3x_P^2 + a}{2 y_P} = \frac{3 \cdot 1^2 - 7}{2 \cdot 2} = -1 \\ x_R & = & m^2 - x_P - x_Q = (-1)^2 - 1 - 1 = -1 \\ y_R & = & y_P + m(x_R - x_P) = 2 + (-1) \cdot (-1 - 1) = 4 \end{array} $$ 可以得出 $P + P = -R = (-1, -4)$, 结果是正确的!

标量乘法

除加法外, 我们还可以定义另一种运算: 标量乘法, 如下: $$ nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}} $$ 这里的 n 是一个自然数. 我也做了一个计算标量乘法的可视化工具, 有兴趣的话可以看看.

写成上面的形式, 看起来计算 nP 需要进行 n 次加法. 当 n 是一个k位(二进制)的数字, 我们的算法复杂度将会是 $O(2^k)$, 这太差了. 但实际上我们可以有更快的算法.

其中一种叫做倍加法(double and add algorithm). 通过一个例子我们可以更好地解释它的原理. 当 n = 151, 表示为二进制 $10010111_2$, 借助其二进制形式我们可以用以下表达式来表示: $$ \begin{array}{rcl} 151 & = & 1 \cdot 2^7 + 0 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 \\ & = & 2^7 + 2^4 + 2^2 + 2^1 + 2^0 \end{array} $$ (将n转换成二进制并表示为多个2的指数次之和) 通过上面的表达式, 我们可以写出: $$ 151 \cdot P = 2^7 P + 2^4 P + 2^2 P + 2^1 P + 2^0 P $$ 倍加法的具体实现步骤如下:

  • 找到点 P
  • 翻倍, 得到 2P
  • 用 2P 加 P (得到 $2^1P + 2^0P$ 的结果)
  • 2P 翻倍, 得到 2^2P
  • 将其加入之前的结果中 (得到 $2^2P + 2^1P + 2^0P$ 的结果)
  • $2^2P$ 翻倍得到 $2^3P$
  • 别加$2^3P$
  • $2^3P$ 翻倍得到 $2^4P$
  • 加入之前的结果(得到 $2^4P + 2^2P + 2^1P + 2^0P$)
  • ...
最后, 只需要通过7次翻倍(自己加自己)和4次累加就可以计算出 $151 \cdot P$ 的结果. 要是还说得不够清楚, 这里有一个 Python脚本实现了这个算法

def bits(n):
    """
    Generates the binary digits of n, starting
    from the least significant bit.

    bits(151) -> 1, 1, 1, 0, 1, 0, 0, 1
    """
    while n:
        yield n & 1
        n >>= 1

def double_and_add(n, x):
    """
    Returns the result of n * x, computed using
    the double and add algorithm.
    """
    result = 0
    addend = x

    for bit in bits(n):
        if bit == 1:
            result += addend
        addend *= 2

    return result

因为翻倍和叠加都是 $O(1)$ 复杂度的运算, 那么这个算法的复杂度就是 $O(\log n)$ (或者说 $O(k)$, k是数字的位长), 这样就挺好了. 至少比最开始复杂度为 $O(n)$ 的算法要好得多!

对数

已知 n 和 P, 现在我们至少有一种方法可以在多项式时间算法可以算出 $Q = nP$. 但是如果反过来会怎么样? 如果我们已知 Q 和 P 想要找出 n 呢.? 这个就是所谓的 对数难题. 我们把这个问题称作"对数"而不是"除法"主要是为了和其他密码学系统在概念上保持一致(在其他密码学系统中一般用指数而不是乘法).

我没听说过任何"简单"的算法可以用于解决对数难题, 不过通过尝试乘法倒是可以找到一些规律. 比如, 已知曲线 $y^2 = x^3 - 3x + 1$ 和点 $P = (0, 1)$, 我们可以立刻验证出, 当 n 是一个奇数时, $nP$ 会位于曲线的左侧平面, 如果 n 是一个偶数, $nP$ 会位于曲线的右侧平面. 如果我们做更多实验, 我们也许能够找出更多这样的规律, 也许可以帮助我们找到高效计算椭圆曲线上对数难题的方法.

不过对数难题还有一个变体: 离散对数难题. 在下一篇文章里我们将会看到, 如果我们缩小椭圆曲线的域, 计算标量乘法仍然是"容易的", 不过求解离散对数将会成为一个"十分困难"的问题. 这个特性将成为椭圆曲线密码学的关键.

未完待续

这就是今天的全部内容, 希望你能喜欢这篇博客! 下周我们将会通过一些例子和小工具探索 有限域 以及 离散对数难题. 如果这些内容听起来还不错, 那么就敬请期待吧!

Show Comments