ECC橢圓曲線加密演算法:有限域和離散對數
Hi all,我來翻譯第二篇啦。若大家發現那些翻譯的不夠準確還望指出,不勝感激。首先放上原文鏈接:
http://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/在上一篇文章里,我們已經展示了在實數域上的橢圓曲線在「群」上是如何使用的。尤其是,我們還針對「加」(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的除法
我們即將定義在
用歐幾里得拓展演算法來計算乘法逆元非常的「簡單易做」,它的時間複雜度是
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:曲線
圖2:曲線
圖1是連續的橢圓曲線在xy軸平面上表現為不相交的點集。在
點加
顯然,我們需要改變一點點關於加法的定義,為了使它能更好的工作在
我們可以說,如果一條直線連接了三個點,這三個點就是對齊的。當然,
注釋1: 上圖的所有點都在
鑒於這已經是一個群,所以點加具備一些通用的屬性:
(單位元的定義) - 給定一個非零點Q, 逆元-Q和它具有相同的橫坐標,但是縱坐標相反。或者還有一種方式,
。舉個例子,如果曲線在 上有一個點 ,逆元是 。 (相反數的定義)
代數和
點加的計算和上篇文章中基本差不多,除了要在每個等式後加上「
如果
如果
這個式子長的和在實數域的點加差不多吧,這不是個巧合,事實上,以上的方程式適用於任一域,無論是有限域還是無限域(除了
言歸正傳,由於在幾何方法上有一些問題,所以我們不會定義一個幾何方法。比如,在第一篇稿子中,我們說 要計算
橢圓曲線的階
我們之前說到每個在有限域上的橢圓曲線都由有限個點組成。那麼我們不禁要問:到底是多少個點?
首先,我們要定義一下 在一個群有多少個點就叫做這個群的「階」(order)【在此放上wiki關於order的解釋】。
群舉從
還好,有一個更快的演算法來計算階:Schoof演算法。在此不展細節,我們只需要知道他的複雜度是多項式時間(大名鼎鼎的Polynomial-Time.在此奉上wiki)
數乘和循環子群
在實數域乘法的定義是:
我們可以用倍加演算法(請見上一篇)去做乘法,時間複雜度是
在
- ...
到此,我們發現了兩個事情:第一,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的演算法,因為這個演算法只能在整個的橢圓曲線上生效,在子群上無效。在解決這個問題之前,我們需要打點地基:
- 到現在為止,我們已經定義了:階,就是一個群的點的數量。這個定義仍然是有效的,但是在循環的子群里我們可以下一個新的,與前面的定義相等的定義:
的階是最小的正整數 , 滿足的條件是 。事實上,我們回顧前面的例子, 。 的階和橢圓曲線是有聯繫的,拉格朗日定理告訴我們,子群的階是父群的階的因子。換句話說,如果一個橢圓曲線包含 個點,它的一個子群包含 個點,那麼 是 的因子。
以上兩條規則結合起來給我們指了一條明路,如何根據基點
- 使用Schoof的演算法去計算橢圓曲線的階
。 - 找到
所有的因子。 - 對於
的每一個因子 ,計算 。 - 找到最小的且滿足
的 , 就是子群的階。
舉個栗子,在
請注意,很重要的一點是一定一定要是最小的因子,而不是隨機的一個因子。如果我們隨機處理一下,我們可能取
另一個例子:定義在
找基點
在ECC演算法中,我們想找到一個階數比較大的子群。所以通常呢,我們會選擇一條橢圓曲線,然後去計算它的階(
首先,我們要介紹一個術語。拉格朗日定理說,
現在,思考一下對於橢圓曲線中的每一個點,我們有
假設
現在我們總結一下演算法:
- 計算橢圓曲線的階
。 - 選擇一個階為
的子群。n必須是素數且必須是 的因子。【至於為什麼一定是素數,請見下一篇文章】 - 計算輔因子
。 - 在曲線上選擇一個隨機的點
。 - 計算
。 - 如果
是0,那麼回到步驟4。否則我們就已經找到了階為 和輔因子是 的子群的生成器/基點。
請注意,上面這個演算法僅僅適用於
離散對數
當有一條連續的橢圓曲線,我們現在要討論的問題是:如果我們已知
這個問題,就是橢圓曲線中大名鼎鼎的離散對數問題,它被認為是個很難很難的問題!【插一句,這也是ECC的核心的核心,也是為什麼ECC安全的原因】。到目前為止,沒有找到一個能在多項式時間內解出來的演算法。因此,也沒有數學證明。
這個難題同樣也是其他涉及離散對數問題的加密演算法的難題,比如DSA演算法,D-H密鑰交換演算法,ElGamal演算法。不同點在於,上述演算法使用了模冪演算法而不是數乘。模冪演算法的離散對數問題可以簡述為:當我們知道
這兩個問題中,值都是「離散」的,因為他們都取自於有限的集合(循環的子群)。而且都是「對數」,就是普通意義上的對數運算。
ECC有趣的地方在於,到今天為止,它的離散問題看上去比其他密碼學中的離散問題難多了。這就說明我們可以用更少的位數的整數
其他
下一篇會介紹:鍵值對的生成,ECDH和ECDSA演算法。
【我已經盡量的還原文章了,其中加了一點點個人見解和wiki的簡介。閱讀愉快:)--xiaopei】
推薦閱讀: