Sign in Subscribe

椭圆曲线ECC

BryanZhang

• 15 min read

https://zhuanlan.zhihu.com/p/36326221

此篇是翻译，因为写的太好了！！！已经拿到作者授权，就翻译了一下，供大家参考。如有不同见解，欢迎提出，我们一起讨论，学习就是一个成长的过程啊。

http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/​andrea.corbellini.name

图标

现在我们听说过的公钥加密有ECC，ECDH 或者 ECDSA。第一个是椭圆曲线加密（Elliptic Curve Cryptography）的缩写，后两个算法是基于它的算法。

今时今日，我们可以在TLS（Transport Layer Security安全传输层协议）,PGP（Pretty Good Privacy基于RSA的邮件加密系统）和SSH（Secure Shell安全外壳协议）中找到椭圆曲线加密系统，这是三项构建了现代Web和IT世界的重要技术，更不用提比特币和其他数字货币加密技术了。

在ECC盛行之前，基本上所有的公钥加密算法都是基于RSA,DSA和DH的，其他的加密系统也都是基于模运算的。RSA和他的小伙伴们在今天仍然很重要，而且经常和ECC一起伴随使用。但是RSA和他的小伙伴们很容易被解释，也被广泛的理解了，况且看上去很难实现的东西写起来还是很容易的，但是ECC对大多数人来说仍旧是个谜。

在这篇文章中，我的目的并不是提供关于ECC完整且细节的指导，我是想提供一个简单的概略：为什么ECC被认为是安全的？这里也不涉及冗长的数学证明或者实现细节。

接下来我会涉及到的文章有：

  1. 实数域上的椭圆曲线和群论（本文）。
  2. 有限域上的椭圆曲线和离散对数问题。
  3. 密钥对的生成和两种ECC算法：ECDH和ECDSA。
  4. 破解ECC安全性的算法，以及和RSA的对比。

为了理解上述文章，你需要先了解一下基础的集合论，几何和模运算，而且要熟悉对称和非对称加密算法。最后，你需要很清楚，什么是“简单”的问题，什么是“困难”的问题，以及他们在加密中所扮演的角色。

开始了!

椭圆曲线

首先，什么是椭圆曲线？Wolfram MathWorld 给出了非常精准的定义：一条椭圆曲线就是一组被

[公式]

定义的且满足

[公式]

的点集。

[公式]

这个限定条件是为了保证曲线不包含奇点(singularities).

[公式]

这个方程称为椭圆曲线的维尔斯特拉斯标准形式（Weierstrass normal form）。

不同的椭圆曲线对应不同的形状（b=1，a从2到-3）
奇异点：左图，带锐点(式1)；右图，曲线自交（式2）。他们都不是有效的椭圆曲线
式1：
[公式]


式2：

[公式]

随着a和b的不同，椭圆曲线也会在平面上呈现出不同的形状，但他还是很容易辨认的，椭圆曲线始终是关于x轴对称的。

另外，我们还需要一个无穷处的点（point at infinity/ideal point）作为曲线的一部分，从现在开始，我们将用 0 这个符号表示无穷处的点。如果我们将无穷处的点也考虑进来的话，那么椭圆曲线的表达式精炼为：

[公式]

群（Group）

我们在一个集合上定义一个二元运算，这就是数学中的群。比如，二元运算-->“加法”并用符号“+”表示，（可以任意符号任意名字，此处仅为举例。也可以这么理解：一个群，由自身的集合和二元运算符‘+’组成），为了使集合

[公式]

成为一个群，必须满足以下四个条件：

  1. 封闭性（closure）：如果a和b被包含于  ，那么a+b 也一定是  的元素。
  2. 结合律(associativity)。
  3. 存在一个单位元（identity element）0，使得 a+0 = 0+a = a;[单位元：与任意元素运算不改变其值的元素]
  4. 每个数都存在一个相反数(inverse)。

如果我们再加上第五个条件：

5. 交换律(commutativity):a+b = b+a.

这个群就叫做阿贝尔群(abelian group)。

从我们通常的加法概念来看，整数集

[公式]

是一个群（而且是一个阿贝尔群）。自然数集

[公式]

不是一个群，因为它不满足第4条。

群是非常好的，因为如果我们可以证明这四条属性，那么我们可以直接拿来用其他的属性了。比如，有且只有一个单位元，对应的相反数也是独一无二的，那么不论直接还是间接，关于群的所有属性和结论我们都可以随意使用。

椭圆曲线上的群论

我们可以在椭圆曲线上定义一个群：

  1. 群中的元素就是椭圆曲线上的点。
  2. 单位元就是无穷处的点0.
  3. 相反数P，是关于X轴对称的另一边的点。
  4. 加法规则定义如下：取一条直线上的三点（这条直线和椭圆曲线相交的三点），P, Q, R（皆非零），他们的总和等于0，P+Q+R=0。
三个对齐的点的和是0

请注意最后一条规则，我们仅仅说了需要三个在一条直线上的点，并没有规定他们的顺序。这就意味着，如果P, Q, R在一条直线上的话，他们满足

P+(Q+R)=Q+(P+R)=R+(P+Q)=⋯=0。

这样，我们可以直观的证明：+运算符是符合交换律和结合律的，这是一个阿贝尔群。

几何加法

由于椭圆曲线的点集属于一个阿贝尔群，所以我们可以将
P+Q+R=0写成 P+Q=−R。这个方程式让我们派生出了一个几何方法去计算两个点P和Q的和：当我们画一条直线通过P，Q，这条线将会和椭圆曲线相交于第三个点，R（这就暗示着P，Q，R三点是在一条直线上的）。如果我们取它相反的点，-R， 我们就可以找到P+Q 的结果。

画一条线穿过P和Q，则此直线必和曲线相交第三个点R。取R关于x轴的对称点-R，就是P+Q的结果。

这个几何方法非常有用但是还需要再精炼一下。让我们来回答一下以下几个问题：

  • 如果 P = 0或者 Q = 0 呢？很明显，这样我们是画不出线的，无穷远点0 不在xy平面上。但是我们已经定义了0作为单位元。 P + 0 = P 和 Q + 0 = Q，对于任意的P和Q都适用，单位元的作用就是与任意元素运算不改变其值的元素。
  • 如果P = -Q呢？ 在这种情况下，穿过两点的直线是垂直的，没有相交的第三个点。但是呢，如果P是Q的相反数，然后我们将会从相反数的定义中得到 P+Q=P+(−P)=0。
  • 如果P = Q呢？ 在这种情况下，有无数条线会经过这个点。我们假设一个点  . 当Q’越来越接近P的时候会发生什么？
当两点越来越接近，穿过两点的直线将会和曲线相切

【针对这一条我要补充一下：从上文我们知道，P，Q，R三点在一条线上而且没有先后顺序，这是一般情况。当两个点越来越接近的时候，这条线会成为曲线的一条切线，这条切线与曲线相交的另一点就是R。这样的线由于椭圆曲线的有山丘山谷的形状，所以会存在很多条。】

当出现切线这种情况，鉴于此我们可以写成P+P=−R，R是曲线和切线的交点，P是切点。

  • 如果当P!=Q，但是没有第三点R呢？这种情况与上一条非常相似。事实上，这种情况就是一条直线穿过P和Q与曲线相切。
如果直线和曲线仅相交于两点，这意味着直线是曲线的切线。P+Q的结果显而易见是其中一个点关于X轴的对称点。

我们可以假设P是切点，在上一个情况下，我们已经说明了P+P=−Q，这个方程现在可以写成：P+Q=−P。换句话说，Q是切点，标准的写法是：P+Q=−Q。

几何方法已经全部讲完了并且涵盖了所有的情况。原创作者Corbellini, Andrea还做了一些小动画帮助大家理解，链接我以前能打开的，今天试了一下打不开了。。。我放在这里

HTML5/JavaScript visual tool

代数加法

如果我们想要一台计算机能够运行点的加法

[公式]

，那我们就需要把几何方法转换成代数方法。将一些规则转换成一系列的方程式看上去是非常直观的，但是实际上是很枯燥的，因为要算三次方程。出于这个原因，这里我只放结果。

首先，我们先去掉一些特殊情况，已知：P+(−P)=0，且P+0=0+P=P，因此，在方程式中，我们将会避免出现这两种情况，只会考虑两个非零，非对称的点

[公式]

和

[公式]

。

如果P和Q是不同的(

[公式]

)，这条线的斜率是：

[公式]

这条直线和椭圆曲线的交点R = (

[公式]

)：

[公式]

也可以写成：

[公式]

于是：

[公式]

(请注意符号，并且记住：P+Q=−R。)

如果我们想检查一下这个结果是否是正确的，我们必须先检查R是否在这条曲线上且P,Q,R这三个点是否共线。检查这些点是否在一条线不算什么，但是检查R是否属于这条曲线就很麻烦了，因为解决一个三次方程，一点乐趣都没有。

我们来看一个例子：

在曲线

[公式]

上定义两个点P=(1,2)和Q=(3,4).他们的和是P+Q = -R = (-3,2)。让我们看一下这个方程是否满足：

[公式]

是对的。

请注意，这个公式在P和Q其中一个是切点的时候也成立，我们再试一下P=(-1,4)和Q=(1,2)。

[公式]

我们可以得到结果P+Q = (1,-2)。

但是当P=Q的时候有一点点不同，方程中的x_R和y_R是一样的，但是

[公式]

,这时我们要用不同的斜率公式：

[公式]

因此，就像我们期望的那样，m的表达式就是下式的一阶导数：

[公式]

证明这个结果的有效性已经足够去说明R点是否属于这个曲线，且P，Q所在的直线和这条曲线仅有两个交点。但是，我们没法正面突破去证明这个情况，从侧面下手，我们用实例检验：

P = Q = (1,2)。

[公式]

最后，P + P = -R = (-1,-4)，对的！

尽管，推导这个答案的过程是无趣的，我们的方程还是很紧凑的。这幸得Weierstrass标准形式：没有它，这些方程会又复杂又长。

标量积（Scalar multiplication）

除了加法，我们还需定义另一个运算:标量积（数乘），如下：

[公式]

在这里，n是一个自然数。

写成上述式子，可以看出计算nP需要做n次加法。如果n有k位二进制的话，我们的算法时间复杂度是O(

[公式]

)，这不是一个好的结果。还好还有更好的算法。

其中一个比较好的算法是倍加算法，它的原理用例子解释如下：

n = 151, 二进制表示：

[公式]

，这个二进制也可以表示成幂次加和：

[公式]

简化一下：

[公式]

倍加算法告诉我们的是：

  • 取一个P
  • 倍乘，我们得到2P
  • 2P加P（为了得到  ）
  • 2*2P，我们得到
  • 加到结果上，（  ）
  • 2* ,得到
  • 扔掉，  不参加任何加法运算
  • 2* ,得到
  • 加到结果上，
  • …

最后，我们计算151P只用了7次倍乘和4次加法。

Python code如下：

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(logn)。（或者是O(k)，如果我们考虑到比特长度的话），这个结果还是非常好的。

对数

对于给定的n和p，我们现在至少有一个多项式最高次幂的算法来计算Q=nP.那么反过来呢？如果我们已知Q和P，需要找到n呢？这个问题就是出名的对数问题，我们称它为“对数”而不是“除”是为了和其他密码系统保持一致性（用幂来代替乘）。

我不清楚对于这个对数问题是否有“简单”的算法。比如，有了曲线

[公式]

和点P=(0,1)，我们可以很快验证。如果n是奇数，nP在左半平面上；如果n是偶数，nP在右半平面上。当我们测试了更多的点的时候，我们就能找到更多的样本和经验，可以带领我们写下更有效的解决对数问题的算法。

还有很多对数问题的变体：离散对数问题。当我们减少椭圆曲线的域，数乘还算是“简单”，而离散对数问题变成了“难题”。这是椭圆曲线加密算法的二元性的核心。

Sign up for more like this.

Enter your email
Subscribe