椭圆曲线:有限域上的离散对数问题

Posted by Mr小军 on 2018-10-26

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

在上一篇文章,我们知道了怎样利用椭圆曲线在实数域上定义一个群.特别的,我们定义了点的加法(point addition)规则:给定三个对齐点,它们的和为0(P + Q +R = 0).我们衍生出了计算点的加法的代数方法(geometric method )和几何方法(algebraic method).

我们还介绍了标量乘法 (nP = P + P + … + P),并且我们还找出了计算标量乘法的“简单”方法:加倍(double)与相加(add)

现在我们要限定椭圆曲线到有限域上,而不是实数集合,我们看看会有哪些变化

整数模P域

首先,一个有限域就是一个拥有有限个元素的集合.整数模P就是一个有限域的例子,这里P是一个素数.通常表示为ℤ/p,GF§或者𝔽p.我们将使用最后的这种标记.

在域中我们有二元操作:加法(+)和乘法(·).都是满足封闭性,结合律,交换律.对这两种操作都存在唯一的单位元,并且域中每个元素都存在一个相反数.最后满足乘法分配律: x⋅(y+z)=x⋅y+x⋅z.

集合整数模P由0到p-1之间的所有整数构成.加法和乘法都基于模数运算(又称为“时钟运算”).以下是𝔽23上一些运算的例子.

  • 加法: (18+9) mod 23 = 4
  • 减法: (7-14) mod 23 = 16
  • 乘法: 4·7 mod 23 = 5
  • 加法逆元: -5 mod 23 = 18
  • 特别的: (5+(-5)) mod 23 = (5+18) mod 23 = 0
  • 乘法逆元: 9^{-1} mod 23 = 18
  • 特别的: 9·9^{-1} mod 23 = 9·18 mod 23 = 1

如果这些操作你看起来很陌生的话你应该看看模数运算的入门书籍,可以看看这个Khan Academy

正如我们之前说的,整数模P是一个域,并且满足上面列出的所有属性.注意,P是素数这个要求非常重要!集合整数模4就不是一个域:2没有乘法逆元(例如 等式 2·x mod 4 = 1 没有解)

模P除法

我们将很快定义𝔽p上的椭圆曲线,但是在这之前我们得搞清楚𝔽p上x/y的含义.简单的说: x/y= x·y^{-1},或者更直白的说,x除以y等于x倍的y的乘法逆元.事实令人惊讶,但是给了我们一个简单的方法去执行除法操作:找到一个数的的乘法逆元然后执行简单的乘法操作

计算乘法逆元可以使用扩展欧几里德(extended Euclidean algorithm)算法,这个算法的最坏时间复杂度为O(logP)(当我们考虑二进制长度时为O(k)).

我们不会深入扩展欧几里德算法的细节,这超出了本文的范围,但是下面给出了一个Python的实现.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def extended_euclidean_algorithm(a, b):
    """
    Returns a three-tuple (gcd, x, y) such that
    a * x + b * y == gcd, where gcd is the greatest
    common divisor of a and b.

    This function implements the extended Euclidean
    algorithm and runs in O(log b) in the worst case.
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    return old_r, old_s, old_t


def inverse_of(n, p):
    """
    Returns the multiplicative inverse of
    n modulo p.

    This function returns an integer m such that
    (n * m) % p == 1.
    """
    gcd, x, y = extended_euclidean_algorithm(n, p)
    assert (n * x + p * y) % p == gcd

    if gcd != 1:
        # Either n is 0, or p is not a prime number.
        raise ValueError(
            '{} has no multiplicative inverse '
            'modulo {}'.format(n, p))
    else:
        return x % p

𝔽p上的椭圆曲线

现在我们有了能够限制椭圆曲线在𝔽p上的所有必要元素.上一篇文章中椭圆曲线的点集合为:

现在变成:

0点依然在无穷远,a和b是𝔽上的整数p

曲线 y2≡x3−7x+10(mod p), p = 19,97,127,487.注意,对于每一个x,最多有两个点.并且关于y = p/2对称.

曲线y2≡x3(mod 29)是非凡的并且在(0,0)有一个三倍点.这不是一个有效的椭圆曲线

之前连续的曲线现在变成了xy平面的不相交的点集合.但是我们可以证明,就算限制了域,𝔽p上的椭圆曲线依然满足阿贝尔群.

点加法

很明显,我们需要改变一下加法的定义让其能在𝔽p上工作.按照之前,我们说三个对齐的点的和为0(P+Q+R=0).我们可以继续这样定义,但是在𝔽p上三个对齐的点如何表示?

我们可以说当三个点被一条直线连接它们就是对齐的.当然,现在𝔽p上的直线和ℝ上的不同.我们可以通俗的说,𝔽p上的直线是一组点,满足等式ax+by+c≡0(mod p)(这是增加了“(mod p)”之后标准的直线等式).

在曲线y2≡x3−x+3(mod 127)上点的加法,P=(16,20),Q=(41,120).注意连接点的直线y≡4x+83(mod 127)如何在平面中“重复”它自己.(译者注:以上所有黄色的线都是y≡4x+83(mod 127)在xy平面中的轨迹,它不是完全连续的)

鉴于我们在一个群中,点的加法保留了我们已知的属性

  • Q+0=0+Q=Q(单位元的定义)
  • 给定一个非零点Q,相反数-Q就是有相同横坐标相反纵坐标的点.或者,如果你喜欢可以表示成,−Q=(xQ,−yQ mod p).比如,一个曲线在𝔽29上有一个点Q=(2,5),相反数就是-Q=(2,-5mod29)=(2,24).
  • 并且,p+(-P)=0(根据相反数的定义)

代数相加

计算点的加法的问题和上一节完全一样,只是我们需要在每个表达式后面加上“mod p”.因此,给P=(xP,yP),Q=(xQ,yQ)和R=(xR,yR),我们可以用如下的方法计算P+Q=−R:

如果P≠Q,斜率m可以如下表示:

另外,如果P=Q,我们有:

等式并没有改变着并不是一个巧合.事实上,这些等式适用于所有的域,有限的或者无限的(除了𝔽2和𝔽3,这是特殊情况).现在我觉得我必须为这个事实提供一个理由.问题是:群理论的证明通常牵扯到复杂的数学概念.然而,我发现一个证明(proof from Stefan Friedl)只用到了初级概念.如果你对为什么这些等式适用于(几乎)所有域,可以读一读这个.

回到主题-我们没有定义几何方法:事实上,这里有一些问题.比如,在上一篇文章中,我们说要计算P+P我们需要获取曲线在P点的切线.但是一旦不连续,单词“切线”没有任何意义.我们能够解决这个问题,然后一个纯粹的几何方法仅仅会变得很复杂并且一点都不实用.

相反,你可以使用我编写的计算点的加法的交互工具(interactive tool).

一个椭圆曲线群的阶

我们说一个定义在有限域上的椭圆曲线有有限个数量的点.我们需要回答的一个重要问题是:确切的说有多少个点?

首先,我们说一个群的点的数量可以被称为这个群的阶.

尝试0到p-1上所有x的可能值并不是计算点的数量的可行方法,这需要O§步,并且当p是很大的素数时这会变得“困难”.

幸运的是,存在更快的算法来计算阶:Schoof’s algorithm.我将不会深入这个算法的细节-重要的是它运行在多项式时间内,这就是我们需要的.

标量乘法和循环子组

和实数域一样,点的乘法可以定义为:

并且我们可以再一次使用加倍(double)和相加(add)算法在O(logn)(或者O(k),k是n的二进制位数)完成乘法的计算.我依然写了一个交互工具来**计算标量乘法**.

域𝔽p上的椭圆曲线的点的乘法有一个有意思的属性.取曲线y2≡x3+2x+3(mod9 7)和点P=(3,6).现在计算P的所有倍数.

P=(3,6)的倍数只有五个不同的点(0,2P,3P,4P)并且它们周期性重复.很容易看出椭圆曲线在模数运算下的标量乘法和加法的相似之处.

  • 0P=0
  • 1P=(3,6)
  • 2P=(80,10)
  • 3P=(80,87)
  • 4P=(3,91)
  • 5P=0
  • 6P=(3,6)
  • 7P=(80,10)
  • 8P=(80,87)
  • 9P=(3,91)
  • …

现在我们可以立即知道两件事:第一,P的倍数只有五:椭圆曲线的其他点将不会出现.第二,这些点周期重复.我们可以这样写:

  • 5kP=0
  • (5k+1)P=P
  • (5k+2)P=2P
  • (5k+3)P=3P
  • (5k+4)P=4P

注意,对于任何整数k,这五个等式可以“压缩”成一个,感谢模数运算:
kP=(k mod 5)P

不仅如此,我们可以立即证实这五个点对于加法封闭.这意味着:不管我加0,P,2P,3P或者4P,结果总是这五个点之一.再一次,椭圆曲线的其他点永远不会出现在这个结果中.

每个点的属性都是如此,不仅仅对于点P=(3,6).事实上,如果我们采用一个通用P:

意味着:如果我们加两个P的倍数,我们得到一个P的倍数(i.e. P的倍数关于加法封闭).
这个足够证明P的倍数的集合是一个椭圆曲线形成的群的子群.

一个“子群”是另一个群的子集组成的群.一个“循环子群”是元素周期重复的子群,就像我们之前给出的例子那样.点P叫做循环子群初始化器或者基点.

循环子群是ECC和其他加密系统的基础.我们将在下一篇看到原因.

子群阶

我们可以问自己一个由点P构造的子群的阶是什么(或者,等价的,P的阶是多少).
要回到这个问题,我们不能用Schoof的算法,因为这个算法只有在整个椭圆曲线有效,而不是在子群.在解决问题前,我们需要更多的内容:

  • 到目前为止,我们定义阶为一个群的点的数量.这个定义依然是有效的,但是在一个子群内我们可以给出一个新的等价的定义:P的阶为nP=0的最小的正整数n.事实上,如果你看之前的例子,我们的子群包含五个点,并且5P=0.
  • P的阶和椭圆曲线的阶由拉格朗日定理(Lagrange’s theorem)联系起来,定理表明子群的阶是父群的阶的一个因子.换一种说法,如果一个椭圆曲线包含N个点并且它的一个子群包含n个点,则n是N的一个因子.

这两点结合在一起就可以给我们一个方法来计算基点为P的子群的阶:

  1. 用Schoof算法计算一个椭圆曲线的阶N.
  2. 找到N的所有因子.
  3. 对于每一个N的因子n,计算nP.
  4. 满足nP=0的最小n就是子群的阶

例如,定义在域𝔽37上的曲线y2=x3−x+3的阶为N=42.它的子群可能的阶n=1,2,3,6,7,14,21或者42.如果我们尝试P=(2,3)我们可以看到P≠0,2P≠0,…,7P=0,因此P的阶是n=7.

注意,取最小的因子非常重要,而不是任意的一个.如果我们随机计算,我们可能得到n=14,这不是子群的阶,但是是它的一个倍数.

另一个例子:由等式y2=x3−x+1定义在域𝔽29的曲线的阶为N=37,这是一个素数.它的子群可能的阶是1或者37.正如你轻易猜到的,当n=1,子群只包含了无穷远处的点;当n=N,子群包含了椭圆曲线的所有点.

找一个基点

对于我们的ECC算法,我们想要子群有一个很大的阶.所以通常我们会选择一个椭圆曲线,计算它的阶(N),选择一个很大的因子作为子群的阶(n)最后找到一个合适的基点.这就是,我们不会选择一个基点然后计算它的阶,并且相反的:我们会先选一个看起来不错的因子然后搜索一个合适的基点.我们该如何做这件事?

首先,我们需要介绍一条术语.拉格朗日定理暗示着数字h=N/n永远是一个正整数(因为n是N的一个因子).数字h有一个名字:它是子群的辅助因子.

现在考虑对于椭圆曲线的每一个点我们有NP=0.这个能够成立,因为N是每一个候选n的倍数.使用辅助因子的定义,我们可以这样写:

n(hp)=0

现在我们假设n是一个素数(下一篇我们将解释原因,我们更喜欢素数阶).这个等式,以这样的格式书写是告诉我们点G=hP构造一个阶为n的子群(除了当G=hP=0,这种情况导致子群的阶是1).

鉴于此,我们能够概括出下面的算法:

  1. 计算椭圆曲线的阶N.
  2. 选择子群的阶n.为了让算法有效,这个数字必须是一个素数并且必须是N的一个因子.
  3. 计算辅助因子h=N/n.
  4. 选择曲线上的一个随机点P.
  5. 计算G=hP.
  6. 如果G是0,则回到第四步.否则我们已经找到了一个阶为n辅助因子为h的子群构造器.

注意,这个算法只有在n是素数时才有效.如果n不是一个素数,那么G的阶可能是n的一个因子.

离散对数

正如我们在连续的椭圆曲线做的那样,我们现在要讨论这个问题: 如果我们知道P和Q,满足Q=Pk的k是什么? 然而,对这个确信没有数学证明.

这个问题和其他密码学系统中使用的离散对数问题类似,例如数字签名算法(DSA),Diffie-Hellman密钥交换(D-H),和ElGamal算法-它们有一样的名字并不是巧合.不同点是,对于这些算法,我们使用模数求幂而不是标量乘法.它们的离散对数问题可以表述如下:如果我们一直a和b,满足b=a^k mod p?的k是什么

这些问题都是离散的因为它们包含有限的集合(更精确的,循环子群).
并且它们是“对数”因为它们和平常的对数类似.

让ECC令人感兴趣的是,目前,椭圆曲线的离散对数问题相比于其他的密码学系统中的类似的问题更加“困难”.这意味着我们需要更少字节的k去实现和其他密码学系统同等级的安全水平,正如我们将在第四篇和最后一篇要深入介绍的(译者注:应该是第三篇和最后一篇,作者写错了).

这个问题是已知的椭圆曲线上的离散对数问题,这被确信是一个在经典计算机中不能被多项式时间内解决的“难“题.

下周更多!

今天就到这里!我真心希望你喜欢这篇文章.如果不喜欢你可以留下评论.

下周的文章将是这个系列的第三篇并且是关于ECC算法:密钥对的生成,ECDH和ECDSA.这将是这一系列文章中最有意思的一篇.不要错过!

第一篇终于翻译完了,好多术语,翻译起来有些吃力,可能不完全精确.博主力求能够以作者表述的风格翻译,但是能力有限,不准确的地方望指正!
翻译的文章可以随意转载,但是请注明原翻译作者:Mr小军;以及原翻译博客地址:https://mr-xiaojun.github.io/article/椭圆曲线-有限域上的离散对数问题/
原文地址:http://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/


FEATURED TAGS
FRIENDS