雪花臺灣

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是素數），可表示為 或 ,我們一般用後者。

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

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

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

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

模p的除法

我們即將定義在 上的橢圓曲線，但是在這之前我們需要弄清在 上 代表什麼？可以簡單表示為： ， 等於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

在 上的橢圓曲線

現在，所有的必要元素都已就位，用來在 上定義橢圓曲線，它的形式是點集，在上一篇文章中我們是這樣寫的：

現在，可以寫成：

這裡的0仍然是無限遠的點，a和b是 上的兩個整數。

圖1

圖1：曲線 且 . 請注意，對於每一個 ，至多有兩個對稱的點滿足： .

圖2

圖2：曲線 是一個奇點，並且在 處有三個點，這是一個無效的橢圓曲線。

圖1是連續的橢圓曲線在xy軸平面上表現為不相交的點集。在 上的橢圓曲線仍然可以形成阿貝爾羣。（elliptic curves in still form an abelian group.）

點加

顯然，我們需要改變一點點關於加法的定義，為了使它能更好的工作在 。 在實數域上，我們約定俗成三個對齊的點的和是0（ ）。在實數域上這個定義沒有問題，就是共線。但是在 上，我們如何定義三個點的對齊？

我們可以說，如果一條直線連接了三個點，這三個點就是對齊的。當然， 上的直線不同於 上的直線。也就是說， 上的直線就是點集( )，這個點集滿足 (這是帶有" "的標準的線性方程式)

請見注釋1（方程式在這裡長的不標準...）

注釋1: 上圖的所有點都在 ， 請注意連接某些點的一次方程 在圖中不停的「重複（因為有mod 127...）」自己。

鑒於這已經是一個羣，所以點加具備一些通用的屬性:

  • (單位元的定義)
  • 給定一個非零點Q, 逆元-Q和它具有相同的橫坐標，但是縱坐標相反。或者還有一種方式， 。舉個例子，如果曲線在 上有一個點 ，逆元是 。
  • （相反數的定義）

代數和

點加的計算和上篇文章中基本差不多，除了要在每個等式後加上「 」。因此，鑒於 和 ，我們可以計算 ，如下：

如果 ，假設斜率是：

如果 ，斜率是：

這個式子長的和在實數域的點加差不多吧，這不是個巧合，事實上，以上的方程式適用於任一域，無論是有限域還是無限域（除了 和 ）。有個問題是：證明這些法則通常要引入一些複雜的數學概念。但是我發現Stefan Friedl給出的證明淺顯易懂。如果你對「為什麼這個方程式幾乎適用於所有環境」很感興趣，read it!

言歸正傳，由於在幾何方法上有一些問題，所以我們不會定義一個幾何方法。比如，在第一篇稿子中，我們說 要計算 我們需要在曲線 上正切，但是如果不是一條線的話（without continuity, 即沒有連續性），「正切」沒有任何意義。確實我們可以權衡利弊後做一些變通，但是這種純幾何方法太複雜而且不實用。

橢圓曲線的階

我們之前說到每個在有限域上的橢圓曲線都由有限個點組成。那麼我們不禁要問：到底是多少個點？

首先，我們要定義一下 在一個羣有多少個點就叫做這個羣的「階」（order）【在此放上wiki關於order的解釋】。

羣舉從 到 所有可能的值去數有多少個點不太可行，因為它的時間複雜度是 ，當 很大的時候，這算下來就很慢很慢。

還好，有一個更快的演算法來計算階：Schoof演算法。在此不展細節，我們只需要知道他的複雜度是多項式時間(大名鼎鼎的Polynomial-Time.在此奉上wiki)

數乘和循環子羣

在實數域乘法的定義是：

我們可以用倍加演算法（請見上一篇）去做乘法，時間複雜度是 （或者 ，這裡的 是 的二進位倍數）。

在 上的橢圓曲線的乘法有個很有意思的屬性。取一個曲線： 和點 ，現在來計算P的所有倍數：

p=(3,6)的所有倍乘的取值只有5個點(0, P, 2P, 3P, 4P )然後不停的循環重複。我們能很容易的發現橢圓曲線上的數乘和模運算的加法非常相似。
  • ...

到此，我們發現了兩個事情：第一，P的倍乘只有5個取值，永遠不會出現第6個。第二，他們是循環重複的。我們可以寫成這樣： （ 取任意整數）

所以呢，這五個式子可以被「壓縮」成一個（模運算）： 。

不僅如此，我們可以立即驗證：P的加法是個閉環。（These five points are closed under addition. ）這意味著：不論我加的是0, P, 2P, 3P 還是 4P， 結果永遠都是這五個點中的一個。Again, 其他點永遠不會出現在這根橢圓曲線的結果裏。

這個規則同樣適用於所有的點，不僅僅是對 。事實上，對於任意的 :

這意味著：如果我們將n倍的P進行想加，我們獲得的仍然是P的倍數(If we add two multiples of P, we obtain a multiple of P)【由於這個定理太重要了，我把英文也放上來】。（比如，nP的相加是個閉環。）這足夠來證明：nP的集合是橢圓曲線形成的羣裏的一個具有循環性質的子羣（the set of the multiples of P is a cyclic subgroup of the group formed by the elliptic curve.）。這裡的點 叫做循環子羣的 生成器 或者 基點。

子羣的階

我們可以捫心自問下，由P生成子羣的階到底是什麼？（或者，P的階是什麼？）為了回答這個問題，我們不能使用Schoolf的演算法，因為這個演算法只能在整個的橢圓曲線上生效，在子羣上無效。在解決這個問題之前，我們需要打點地基：

  • 到現在為止，我們已經定義了：階，就是一個羣的點的數量。這個定義仍然是有效的，但是在循環的子羣裏我們可以下一個新的，與前面的定義相等的定義： 的階是最小的正整數 ， 滿足的條件是 。事實上，我們回顧前面的例子， 。
  • 的階和橢圓曲線是有聯繫的，拉格朗日定理告訴我們，子羣的階是父羣的階的因子。換句話說，如果一個橢圓曲線包含 個點，它的一個子羣包含 個點，那麼 是 的因子。

以上兩條規則結合起來給我們指了一條明路，如何根據基點 找到子羣的階：

  1. 使用Schoof的演算法去計算橢圓曲線的階 。
  2. 找到 所有的因子。
  3. 對於 的每一個因子 ,計算 。
  4. 找到最小的且滿足 的 , 就是子羣的階。

舉個栗子，在 上的曲線 的階是 。它的子羣的階可能是 。如果我們代入曲線上的點 我們可以發現 。因此， 的階是7。

請注意，很重要的一點是一定一定要是最小的因子，而不是隨機的一個因子。如果我們隨機處理一下，我們可能取 ，但它不是子羣的階，僅僅是一個倍數。

另一個例子：定義在 橢圓曲線上的方程式 的階是 ，這是一個素數，所以它的子羣的階可能只含有1和37. 很容易我們就可以猜出來，當 的時候，子羣僅包含一個點，就是0（參考上篇文章的point at infinity）。當 時，子羣包含橢圓曲線的所有的點。

找基點

在ECC演算法中，我們想找到一個階數比較大的子羣。所以通常呢，我們會選擇一條橢圓曲線，然後去計算它的階（ ）, 選擇一個以較大的因子作為子羣的階（ ），最終，依此找到一個合適的基點。也就是說，我們不會選擇一個基點然後去計算它的階，我們會反著來操作一波。

首先，我們要介紹一個術語。拉格朗日定理說， 裏的 永遠是一個整數（因為 是 的因子）。這裡的 有個名字：輔因子（cofactor of the subgroup）。

現在，思考一下對於橢圓曲線中的每一個點，我們有 ，且 是任意一個 的倍數。藉助輔因子的概念，我們可以寫成： 。

假設 是素數，這個方程式告訴我們：點 生成了一個階為 的子羣（除了當 ，在這個例子中子羣的階是1）。

現在我們總結一下演算法：

  1. 計算橢圓曲線的階 。
  2. 選擇一個階為 的子羣。n必須是素數且必須是 的因子。【至於為什麼一定是素數，請見下一篇文章】
  3. 計算輔因子 。
  4. 在曲線上選擇一個隨機的點 。
  5. 計算 。
  6. 如果 是0，那麼回到步驟4。否則我們就已經找到了階為 和輔因子是 的子羣的生成器/基點。

請注意，上面這個演算法僅僅適用於 是素數的情況下。如果 不是素數，那麼 的階可以是 的任何一個因子。

離散對數

當有一條連續的橢圓曲線，我們現在要討論的問題是：如果我們已知 ，要想得到 ，我們應該怎麼去計算這個 ?

這個問題，就是橢圓曲線中大名鼎鼎的離散對數問題，它被認為是個很難很難的問題！【插一句，這也是ECC的核心的核心，也是為什麼ECC安全的原因】。到目前為止，沒有找到一個能在多項式時間內解出來的演算法。因此，也沒有數學證明。

這個難題同樣也是其他涉及離散對數問題的加密演算法的難題，比如DSA演算法，D-H密鑰交換演算法，ElGamal演算法。不同點在於，上述演算法使用了模冪演算法而不是數乘。模冪演算法的離散對數問題可以簡述為：當我們知道 ， ，那麼如何求 ?

這兩個問題中，值都是「離散」的，因為他們都取自於有限的集合（循環的子羣）。而且都是「對數」，就是普通意義上的對數運算。

ECC有趣的地方在於，到今天為止，它的離散問題看上去比其他密碼學中的離散問題難多了。這就說明我們可以用更少的位數的整數 做到和其他加密演算法一樣安全級別的加密效果。

其他

下一篇會介紹：鍵值對的生成，ECDH和ECDSA演算法。

【我已經盡量的還原文章了，其中加了一點點個人見解和wiki的簡介。閱讀愉快:)--xiaopei】

推薦閱讀：

相關文章