ECC橢圓曲線加密演算法：有限域和離散對數

Hi all，我來翻譯第二篇啦。若大家發現那些翻譯的不夠準確還望指出，不勝感激。首先放上原文鏈接：

http://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/?

andrea.corbellini.name

在上一篇文章裏，我們已經展示了在實數域上的橢圓曲線在「羣」上是如何使用的。尤其是，我們還針對「加」(point addition) 定義了一個規則：對於在一條線上的三個點，他們的和是0（P+Q+R=0）. 我們也推出了一個幾何方法和代數方法去計算這些點的加法。

然後呢，我們介紹了標量積(scalar multiplication) （nP=P+P+...+P），我們還發現了一個「簡單的」演算法去計算這些標量積。double and add

整數域模p

首先，有限域是一個帶有有限元素的集合。比如，有一個有限域是整數模p的集合（integers mod p,p是素數），可表示為或 $mathbb {F}_{p}$ ,我們一般用後者。

在這個有限域中，我們有兩個二元操作：加（+）和乘( * )。這兩種操作都是封閉的，滿足結合律和交換律，[這塊的封閉應當這樣理解：在有限域中，兩個數的加和乘的結果仍然在這個有限域中。--譯者注] 且含有一個獨一無二的單位元，對於所有的有限域裏的元素，都有一個獨一無二的相反數。最後，乘法還滿足分配律：。

整數模p的集合包含所有從0到的整數。加法和乘法都按模數運算規則去計算。這裡有一些 $mathbb{F}_{23}$ 的例子：

加：
減：
乘：
加法逆元：的確：
乘法逆元： $9^{-1},mod,23,=,18$ 的確： $9*9^{-1},mod,23,=,9*18,mod,23,=,1$

如果這些式子你覺得不太能理解，那麼你可能需要一些關於模運算的入門指導，請參考：Khan Academy.

就如我前面提到的，整數模p是一個域，因此上面列的所有屬性都是滿足的。請注意p是素數這個條件很重要！比如整數模4的集合就不是域：2沒有乘法逆元（無解）。

模p的除法

我們即將定義在 $mathbb {F}_{p}$ 上的橢圓曲線，但是在這之前我們需要弄清在 $mathbb {F}_{p}$ 上代表什麼？可以簡單表示為： $x/y,=,x*y^{-1}$ ，等於x 乘上 y的逆元。這個解釋給了我們基本的做除法的方法：1.求逆元，2.做乘法。

用歐幾裏得拓展演算法來計算乘法逆元非常的「簡單易做」，它的時間複雜度是 (或者是如果考慮bit長度的話) 在最壞的情況下。這裡不會給出歐幾裏得拓展演算法的細節，但是放上Python的代碼：

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