【正文】 學 ECC ? 為什么要提出 ECC？ 同等安全強度下各算法的密鑰長度 ? RSA 主要問題之一： ? 為了保證必要的安全強度，其密鑰必須很長 ? ECC的優(yōu)勢： ? 在同等安全強度下， ECC所需密鑰比 RSA短 128 密碼學 ECC ? 橢圓曲線指的是由韋爾斯特拉斯（ Weierstrass）方程所確定的平面曲線 。 ? 其中，系數(shù) （ i =1， 2， … ， 6）定義在基 域K上（ K可以是有理數(shù)域、實數(shù)域、復數(shù)域，還可以是 有限域 ，橢圓曲線密碼體制中用到的橢圓曲線都定義在有限域上）。 ? 橢圓曲線并非橢圓 64223312 axaxaxyaxyay ??????ia129 密碼學 ECC ? 群： ? 對于非空集合 G，其上的一個二元運算（ .）滿足：封閉性、結合 律 、單位元和可逆性 ? 環(huán)：對于 R上的兩個二元運算（ +， x）滿足： ? 關于＋是一個交換群（群的條件＋交換律） ? 對于乘法 x滿足： ? 封閉性＋結合律＋分配律 ? 域：對于 F上的兩個運算（ +， x）滿足 ? F是一個 整環(huán)：交換環(huán)＋乘法逆元＋無零因子 ? 乘法逆元存在 2022/1/4 例：證明 n, +n是群，其中 n是正整數(shù)。 分析 需要證明 4點：封閉性；結合律；幺元存在； 逆元存在。 證明 （ 1） 封閉性 ： ?x, y∈ n，令 k = x + y (mod n)，則 0≤k＜ n ? 1，即 k∈ n， 所以封閉性成立。 131 2022/1/4 證明（續(xù)） （ 2） 結合律 ： ?x, y, z∈ n，有 (x +n y) +n z = x + y + z (mod n) = x +n (y +n z), 所以結合律成立。 （ 3） 幺元 ： ?x∈ n，顯然有 0 +n x = x +n 0， 因此， 0是幺元。 132 2022/1/4 證明（續(xù)） （ 4） 逆元存在 ： ?x∈ n，如果 x = 0，顯然 0?1 = 0，如果 x≠0，則有 n ? x∈ n， 顯然 x +n (n?x) = (n?x) +n x = 0， 所以 x?1 = (n?x)， 因此， ?x∈ n， x有逆元。 綜上， n, +n是群。 133 密碼學 ECC ?? ?? ?? ? ? ? ?? ? ? ? ?? ? ? ? ??? ???域 整 環(huán) 可 交 換 環(huán) 環(huán) 可 交 換 群 群134 密碼學 PQR RP + Q ( P + Q )( P + Q )ECC ? 橢圓曲線加法運算規(guī)則： ? O是加法的單位元， O＝－ O；對于橢圓曲線上的任一點 P，有 P＋ O＝ P ? 點 P的負元是與 P具有現(xiàn)同 x坐標和相反 y坐標的點，即若 P＝（ x， y），則 P＝（ x， y）；P＋（ P)=O 135 密碼學 ECC S SQ2 Q? 若 P＝（ x1， y）， Q＝（ x2， z），則 P＋ Q＝ R。其中 R是直線 PQ與橢圓曲線的第三個交點。 ? 若 P和 Q的 x坐標相同，則為無窮遠點 O ? 若 Q＝（ x， y），則 Q＋ Q＝ 2Q＝－ S，其中 S為橢圓曲線在 Q點的切線與橢圓曲線的另一交點。 PQR = ( P + Q ) R = P + QP + Q136 橢圓曲線密碼學 ? 有限域上橢圓曲線 ?y2?x3+ax+b mod p p是奇素數(shù) ,且 4a3+27b2?0 mod p （構成Abel群的條件，證明過程略） ?y2+xy?x3+ax2+b mod 2m(Galois 域的橢圓曲線） ? 有限域上橢圓曲線 ?y2?x3+ax+b mod p （ 3）加法公式 : P=(xp,yp), Q=(xQ,yQ) 若 xP=xQ且 yP=yQ則 P+Q=O， 否則 P+Q=(xR,yR) xR=?2xPxQ yR=?(xPxR)yP 其中 ?=(yQyP)/(xQxP), 如果 P?Q ?=(3xP2+a)/（ 2yP）， 如果 P=Q （ 1） P+O=P （ 2） P=(x,y)， P＋ (x,y)=O， 其中（ x,y)是 P的負元－ P (4)重復相加： nP=P+… +P 按照上述定義構成了一個橢圓曲線上的 Abel群。 138 橢圓曲線密碼學 ? 示例：有限域上橢圓曲線 y2?x3+ax+b mod p ? 條件： a=1, b=1,x=9,y=7,p=23 ? y2 =72 mod 23=3 ? x3+ax+b=(93 +9+1) mod 23=3 ? y2?x3+ax+b mod p 139 ECC示例 ? 示例：有限域上橢圓曲線 y2?x3+ax+b mod p ? 條件： a=1, b=1,x=9,y=7,p=23 ? 問題： ? 求滿足上述方程的所有整數(shù)對（ x， y）以及無窮遠點 O組成的集合 Ep（ a， b） ＝ E23（ 1， 1）？ 橢圓曲線密碼學 ECC示例 (0,1) (6,4) (12,19) (0,22) (6,19) (13,7) (1,7) (7,11) (13,16) (1,16) (7,12) (17,3) (3,10) (9,7) (17,20) (3,13) (9,16) (18,3) ( 4,0) (11,3) (18,20) (5,4) (11,20) (19,5) (5,19) (12,4) (19,18) E23（ 1， 1） 141 ECC示例 (0,1) (6,4) (12,19) (0,22) (6,19) (13,7) (1,7) (7,11) (13,16) (1,16) (7,12) (17,3) (3,10) (9,7) (17,20) (3,13) (9,16) (18,3) ( 4,0) (11,3) (18,20) (5,4) (11,20) (19,5) (5,19) (12,4) (19,18) E23（ 1， 1） 1） P＝（ 0， 1），P+O＝（ 0， 1） 2） P＝（ 13， 7） P=（ 13， 7）=(13,16) 3） P＝ (3， 10)，Q＝ (9， 7) P+Q=(17,20) 4） P＝（ 3， 10） 2P=(7,12) 142 ? P＋ Q計算過程： 22( 3 , 10) , ( 9 , 7 )m od ( )3m od ( )27 10m od 23 1193( ) m od 17( ( ) ) m od 20QPQpPpR P QR P R pPQyyp P Qxxxp P Qyx x x py x x y p???????? ?? ??? ?????? ??? ??? ?????? ????????? ? ??????? ? ? ? ?? ? ? ?x3=?2x1x2 y3=?(x1x3)y1 其中 ?=(y2y1)/(x2x1), 如果 P?Q ?=(3x12+a)/2y1, 如果 P=Q 143 ? 有限域上橢圓曲線 ? y2+xy?x3+ax2+b mod 2m(Galois 域的橢圓曲線） （ 3）加法公式 : P=(xP,yP), Q=(xQ,yQ),且 P≠ Q, P ≠Q 則 P+Q=(xR,yR), xR=?2+ ? +xP+xQ+a yR=?(xP+xR)+xR +yP 其中 ， ?=(yQ+yP)/(xQ+xP) （ 1） P+O=P （ 2） P=(x,y) P＋ (x,y)=O 其中（ x,y)是 P的負元－ P 144 ? 有限域上橢圓曲線 ? y2+xy?x3+ax2+b mod 2m(Galois 域的橢圓曲線） (4) 若 P=(xP,yP), 則 R＝ 2P=(xr,yr) 其中： xR=?2+ ? +a yR=xP2+( ? +1)xR ?=xp+yp/xP 按照上述定義構成了一個橢圓曲線上的 Abel群 145 ? 橢圓曲線上的離散對數(shù) ? 難題 ? ? 對于方程 Q=kP,其中 P， Q屬于 Ep(a,b)。對于給定的 k和 P，計算 Q比較容易，而對于給定的 P和 Q，計算 k比較困難 146 ECC ? 例如： 方程 y2=(x3+9x+17) mod 23所定義的群 E23(9,17)。求： P＝（ 16， 5）和 Q＝（ 4， 5）的離散對數(shù) k？ 窮舉計算： P＝（ 16， 5）， 2P＝ (20,20), 3P=(14,14)， 4P＝（ 19， 20）， 5P＝ 13， 10）； 6P＝（ 7， 3）， 7P＝（ 8， 7）， 8P＝（ 12， 17）， 9P＝（ 4， 5） 因此 k＝ 9 147 ECC加密 /解密實現(xiàn) ? AliceBob ? Step 1： Bob選擇 Ep(a， b)的元素 G， 使得 G的階 n是一個大素數(shù) ,秘密選擇整數(shù) P=kG,公開 (p， a， b， G， P)， 保密 k。 其中Kb＝ kG為 Bob公鑰， Kb?＝ k為 Bob私鑰 ? Step 2：將消息 m編碼為 xy形式的點 Pm 148 ECC加密 /解密實現(xiàn) ? Step 3： Alice隨機選擇一個正整數(shù) r，對 Pm產(chǎn)生密文 Cm＝ {rG， Pm＋ rKb} ? Step 4： Bob解密 ? CmKb?(rG) ? =Pm+rKbkrG ? =Pm+r(kG)rkG=Pm 149 ECC加密 /解密實現(xiàn) ? AliceBob(示例） ? Step 1： Bob選擇 E88331(3， 45)， G＝(4,11), Bob私鑰 Kb?＝ K=3, Bob公布公鑰 Kb＝ (413,1808) ? Step 2： Pm=(5,1734) ? Step 3： Alice隨機選擇一個正整數(shù) r=8，對 Pm產(chǎn)生密文 : ? Cm＝ {rG， Pm＋ rKb} ={(5415,6321),(6626,3576)} 150 ECC加密 /解密實現(xiàn) ? Step 4： Bob解密 ? Kb?(rG)=3(5415,6321)=(673,146) ? Cm Kb?(rG)=(6626,3576)(673,146)=(5,1734) 151 密碼學與安全性總結 第一階段 80年代 第二階段 90年代 第三階段 90年代后期 信息保密 信息保護 信息保障 密碼學 保密學 加解密技術 數(shù)據(jù)完整性 數(shù)據(jù)可用性 數(shù)據(jù)可控性 可信環(huán)境 可信計算 可信存儲 抗抵賴性 + + + + 密碼學 152 密碼學與安全性總結（續(xù)） 密碼學 （數(shù)學基礎） 編碼學 分析學 相輔相成 對立統(tǒng)一 機密性、完整性、可鑒別性、抗抵賴性 信息源目標服務 密碼學 153 密碼實現(xiàn) 數(shù)學發(fā)現(xiàn) 密碼算法 算法論證 復雜性 密鑰配置 算法實現(xiàn) 密碼協(xié)議 加密解密 破譯技術 密鑰技術 密碼應用 領域應用 密碼系統(tǒng) 密碼管理 密鑰管理 交叉融合 基礎 過程 結果 密碼學與安全性總結（續(xù)） 154 計算復雜性 單向函數(shù) 代數(shù)結構 密碼 分析 古典密碼 公鑰密碼 簽名模式 私鑰密碼 散列 函數(shù) 密碼學協(xié)議 密鑰管理 操作式 抗抵賴 機密性 密碼系統(tǒng)的整體設計與分析 完整性 鑒別性 密碼學與安全性總結（續(xù)）