橢圓曲線加密(ECC)最大的優點就是使用比RSA短得多的密鑰得到相同的安全性,是以可以減少處理負荷,使公鑰密碼的應用領域得到拓展。
基本原理:
橢圓曲線密碼體制使用了在有限Abel群(Zp或者GF(2m))上構造的橢圓曲線,橢圓曲線在有限群的加法符号定義下成為一個單向陷門函數。
在有限群上的橢圓曲線在計算上沒有顯而易見的幾何解釋,但是可以将實數域上的橢圓曲線的幾何解釋移植過來。為了友善了解,先從實數域上的橢圓曲線開始講解
1. 實數域上的橢圓曲線
橢圓曲線并不是橢圓,而是與橢圓周長的方程相似的三次方程。一般,橢圓曲線方程形為:
y2 + axy + by = x3 + cx2 + dx + e
對我們而言将方程限制為以下形式就已足夠:
y2 = x3 + ax + b (10.1)
對于給定的a和b,對x的每一個值,需畫出y的正值和負值。
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cGcq5CO5MjNyIWOkhDZ2EmNxYGOyYzX0UjN1MTM2IzLcVDMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.jpg)
構造Abel群
将滿足式(10.1)的所有點(x , y)和元素O(稱為無窮遠點或者零點的元素,後面會讨論這個概念)所組成的點集E(a , b)。上圖中兩條曲線分别可用集合E(-1 , 0)和E(1 , 1)表示。
若式(10.1)裡的參數a和b滿足
4a3 + 27b2 ≠ 0 (10.2)
則基于集合E(a , b)可以定義一個可交換群(Abel群),其加法的運算規則如下:
1、O是加法的機關元,有O = -O;對橢圓曲線上任何一點P,有P + O = P
2、點P (x , y)的負元-P = (x , -y)。注意這兩點可以用一條垂直的線連接配接起來,并且P + (-P) = P - P = O
3、要計算坐标不同的P和Q之和,則在P和Q間作一條直線并找到與曲線的第三個交點R(顯然存在唯一的交點R,除非這條直線與P或者Q相切,此時分别取R = P或者R = Q,與下述5相一緻)。并定義如下三點上的加法:P + Q = -R。也就是,定義P + Q 為第三個交點相對于x軸的鏡像
4、上述術語的幾何解釋也适用于具有相同x坐标的兩個點P和 -P的情形。用一條垂直的線連接配接這兩點,這可視為在無窮遠點與曲線相交,是以有P + (-P) = O,與上述2相一緻。
5、為計算點Q的兩倍,畫一條切線并找到另一交點S,則Q + Q = 2Q = -S。
加法的結論
1、對于不是互為負元的兩個不同點P = (xP , yP) 和 Q = (xQ , yQ),連接配接它們的直線的斜率Δ= (yQ - yP)/(xQ - xP),我們可用如下表示和R = P + Q
xR =Δ2 - xP - xQ
yR =Δ(xP - xR) - yP (10.3)
2、計算一個點與它自身相加:P + P = 2P = R,則表達式為
2. Zp上的橢圓曲線
對于Zp上的素曲線,我們使用三次方程,p為素數,其中的變量和系數自集合{0,1,···,p-1}取值,運算為模p運算。
對Zp上的橢圓曲線,如同實數情形一樣,方程如下:
y2 mod p = (x3 + ax + b) mod p (10.5)
可以證明,若(x3 + ax + b) mod p無重複因子,則基于集合Ep(a , b)可定義一個有限Abel群,這等價于以下條件:
(4a3 + 27b2) mod p ≠ 0 (10.6)
注意,(10.6)與(10.2)具有相同的形式
Ep(a , b)上的加法運算構造與定義在實數上的橢圓曲線中的描述的代數方法是一緻的。對任何點P , Q∈Ep(a , b)
1、P + O = P
2、若P = (xP , yP),則點(xP , -yP)是P的負元,記為 -P。例如對E23(1 , 1)上的點P = (13 , 7),有 -P = (13 , -7),而 -7 mod 23 = 16,是以,-P = (13 , 16),該點也在E23(1 , 1)上。
3、若P = (xP , yP),Q = (xQ , yQ),且P ≠ -Q則R = P + Q = (xR , yR)由下列規則确定:
xR =λ2 - xP - xQ
yR =λ(xP - xR) - yP
其中
4、乘法定義為重複相加。如4P = P + P + P + P
為了确定各種橢圓曲線密碼的安全性,需要知道定義在橢圓曲線上的有限Abel群中點的個數。在有限群Ep(a , b)中,點的個數N的範圍是
p + 1 - 2p1/2 ≤ N ≤ p + 1 + 2p1/2
是以,Ep(a , b)上點的個數約等于Zp中元素的個數,即p個元素。
3. GF(2m)上的橢圓曲線
對于GF(2m)上的橢圓曲線,其變量和系數在GF(2m)内取值,且運算為GF(2m)裡的運算。可以證明,GF(2m)上适合于橢圓曲線密碼應用的三次方程與Zp上的三次方程有所不同,其形為:
y2 + xy = x3 + ax2 + b (10.7)
可以證明,隻要b ≠ 0,則可基于集合E2m(a , b)可定義一個有限Abel群。對任何點P , Q∈E2m(a , b),加法的運算規則如下:
1、P + O = P
2、若P = (xP , yP),則P + (xP , xP + yP) = O。點(xP , xP + yP)是P的負元,記為 -P。
3、若P = (xP , yP),Q = (xQ , yQ),且P ≠ -Q,P ≠ Q則R = P + Q = (xR , yR)由下列規則确定:
xR =λ2 +λ+ xP + xQ + a
yR =λ(xP + xR) + xR + yP
其中
4、若P = (xP , yP),則R = 2P = (xR , yR)由下列規則确定:
xR =λ2 + λ+ a
yR =xP2 + (λ + 1)xR
其中
λ= xP + yP/xP
橢圓曲線密碼學
考慮方程Q = kP,其中Q,P∈Ep(a , b),對給定的k和P計算Q比較容易,而對給定的Q和P計算k則很困難,這就是橢圓曲線的離散對數問題。
用橢圓曲線實作Diffie-Hellman密鑰交換
首先,挑選一個大整數q以及式(10.5)或式(10.7)中的橢圓曲線參數a和b,這裡q為素數p或者是形為2m的整數。由此可以定義出點的橢圓群Eq(a , b)
其次,在Eq(a , b)中挑選基點G = (x1 , y1),G的階為一個非常大的數n。橢圓曲線上的點G的階n是使nG = 0 成立的最小正整數。Eq(a , b)和G是該密碼體制中通信各方均已知的參數
使用者A和使用者B之間完成密鑰交換過程如下:
1、A選擇一個小于n的整數nA作為其私鑰,然後産生其公鑰PA = nA × G。該公鑰是Eq(a , b)中的一個點。B也類似地選擇私鑰nB并計算公鑰PB
2、A産生秘密鑰k = nA × PB,B産生秘密鑰k = nB × PA
nA × PB = nA × (nB × G) = nB × (nA × G) = nB × PA
要破譯這種體制,攻擊者必須由G和kG計算k,這被認為很難。
橢圓曲線加/解密
首先,我們必須将要發送的消息明文m編碼為形為(x , y)的點Pm,并對點Pm進行加密和其後的解密。注意,不能簡單地将消息編碼為點的x坐标或y坐标,因為并不是左右的坐标都在Eq(a , b)中。将消息m編碼為點Pm的方法有很多種,存在比較直接的編碼方法。
像密鑰交換系統一樣,加/解密系統也需要點G和橢圓群Eq(a , b)這些參數。每個使用者選擇一個私鑰n,并産生公鑰P = n × G
若A要将消息Pm加密後發送給B,則A随機選擇一個正整數k,并産生密文Cm,該密文是一個點對:
Cm = {kG , Pm + kPB}
注意,此處A使用了B的公鑰PB,B要對密文解密,則需用第二個點減去第一個點與B的私鑰之積:
Pm + kPB - nB(kG) = Pm + k(nBG) - nB(kG) = Pm
橢圓曲線密碼的安全性
ECC的安全性是建立在由kP和P确定k的困難程度之上的,這個問題稱為橢圓曲線對數問題。Pollard rho方法是已知的求橢圓曲線對數最快的方法。下表從密碼分析所需計算量的角度,通過給出可比較的密鑰大小,比較了各種算法。在密鑰長度相同時,ECC和RSA所執行的計算量差不多。是以,與具有同等安全性的RSA相比,由于ECC使用的密鑰更短,是以ECC所需的計算量比RSA更小。
基于非對稱密碼的僞随機數生成器
由于非對稱算法的速度比對稱算法明顯慢一些,是以非對稱算法不用于生成可擴充的PRNG流,但是,對于生成短的僞随機序列,建立僞随機函數(PRT),非對稱的方法還是很有用的。
Micali-Schnorr PRNG
該PRNG定義如下:
建立 選擇素數p,q;n = pq;φ(n) = (p - 1)(q - 1),選擇e使得gcd(e ,φ(n)) = 1。此外N =└log2n┘ + 1(n的位長度)。選擇r,k使得r + k = N
種子 選擇位長度為r的随機種子x0
生成 生成一個長為k × n的僞随機序列,将i從1到m,計算
yi = xi-1e mod n
xi = r , yi的最高有效位
zi = k , yi的最低有效位
輸出 輸出序列為z1 || z2 || ··· || zm
參數n,r,e,k的選擇要遵循下面6個要求:
1、n = pq n是兩個素數的乘積,在RSA中則是密碼長度
2、1 < e < φ(n) ;gcd(e ,φ(n) ) = 1 確定映射s -> se mod n是一對一的
3、re ≥ 2N 確定求幂運算是有取模過程
4、r ≥ 2 防止密碼攻擊
5、k,r是8的倍數 應用友善
6、k ≥ 8;r + k = N 所有位都有效