第一章信息安全概述ECC算法計(jì)算機(jī)系統(tǒng)與網(wǎng)絡(luò)安全技術(shù)橢圓曲線算法（ECC:EllipticCurveCryptography）1985年，N.Koblitz及V.S.Miller分別提出了橢圓曲線密碼體制（ECC）。已經(jīng)開(kāi)發(fā)出的橢圓曲線標(biāo)準(zhǔn)的文檔有：IEEEP1363P1363a、ANSIX9.62X9.63、ISO/IEC14888等。近年來(lái)，ECC已走向工程實(shí)現(xiàn)和實(shí)際應(yīng)用階段。ECC算法橢圓曲線算法簡(jiǎn)介信息安全概論RSA主要問(wèn)題之一：為了保證必要的安全強(qiáng)度，其密鑰必須很長(zhǎng)ECC的優(yōu)勢(shì)：在同等安全強(qiáng)度下，ECC所需密鑰比RSA短為什么要提出ECC？ECC算法信息安全概論什么是橢圓曲線？橢圓曲線指的是由韋爾斯特拉斯（Weierstrass）方程所確定的平面曲線。其中，系數(shù)ai（i=1，2，…，6）定義在基域K上（K可以是有理數(shù)域、實(shí)數(shù)域、復(fù)數(shù)域，還可以是有限域，橢圓曲線密碼體制中用到的橢圓曲線都定義在有限域上）。橢圓曲線并非橢圓ECC算法信息安全概論代數(shù)相關(guān)概念群：對(duì)于非空集合G，其上的一個(gè)二元運(yùn)算（.）滿足：封閉性、結(jié)合率、單位元和可逆性環(huán)：對(duì)于R上的兩個(gè)二元運(yùn)算（+，x）滿足：關(guān)于＋是一個(gè)交換群（群的條件＋交換率）對(duì)于乘法x滿足：封閉性＋結(jié)合率＋分配率域：對(duì)于F上的兩個(gè)運(yùn)算（+，x）滿足：F是一個(gè)整環(huán)：交換環(huán)＋乘法逆元＋無(wú)零因子乘法逆元存在ECC算法信息安全概論橢圓曲線的運(yùn)算規(guī)則O是加法的單位元，O＝－O；對(duì)于橢圓曲線上的任一點(diǎn)P，有P＋O＝P點(diǎn)P的負(fù)元是與P具有現(xiàn)同x坐標(biāo)和相反y坐標(biāo)的點(diǎn)，即若P＝（x，y），則-P＝（x，-y）；P＋（P)=O若P＝（x1，y），Q＝（x2，z），則P＋Q＝-R。其中R是直線PQ與橢圓曲線的第三個(gè)交點(diǎn)。若P和Q的x坐標(biāo)相同，則為無(wú)窮遠(yuǎn)點(diǎn)O若Q＝（x，y），則Q＋Q＝2Q＝－S，其中S為橢圓曲線在Q點(diǎn)的切線與橢圓曲線的另一交點(diǎn)。ECC算法信息安全概論有限域上橢圓曲線：y2

x3+ax+bmodpp是奇素?cái)?shù),且4a3+27b2

0modp（構(gòu)成Abel群的條件，證明過(guò)程略）y2+xy

x3+ax2+bmod2m(Galois域的橢圓曲線）有限域上的橢圓曲線ECC算法信息安全概論有限域上橢圓曲線

y2

x3+ax+bmodp

（3）加法公式:P=(xp,yp),Q=(xQ,yQ)若xP=xQ且yP=-yQ則P+Q=O否則P+Q=(xR,yR)xR=

2-xP-xQyR=

(xP-xR)-yP其中

=(yQ-yP)/(xQ-xP),如果P

Q=(3xP2+a)/（2yP），如果P=Q（1）P+O=P（2）P=(x,y)P＋(x,-y)=O其中（x,-y)是P的負(fù)元－P(4)重復(fù)相加：nP=P+…+P按照上述定義構(gòu)成了一個(gè)橢圓曲線上的Abel群橢圓曲線的運(yùn)算規(guī)則ECC算法信息安全概論示例：有限域上橢圓曲線

y2

x3+ax+bmodp條件：a=1,b=1,x=9,y=7,p=23y2

=72mod23=3x3+ax+b=(93+9+1)mod23=3y2

x3+ax+bmodp橢圓曲線的運(yùn)算規(guī)則ECC算法信息安全概論示例：有限域上橢圓曲線

y2

x3+ax+bmodp條件：a=1,b=1,x=9,y=7,p=23問(wèn)題：求滿足上述方程的所有整數(shù)對(duì)（x，y）以及無(wú)窮遠(yuǎn)點(diǎn)O組成的集合Ep（a，b）＝E23（1，1）？橢圓曲線的運(yùn)算規(guī)則ECC算法信息安全概論橢圓曲線的運(yùn)算規(guī)則E23（1，1）(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)ECC算法信息安全概論橢圓曲線的運(yùn)算規(guī)則E23（1，1）(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)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)ECC算法信息安全概論橢圓曲線的運(yùn)算規(guī)則P＋Q計(jì)算過(guò)程：x3=

2-x1-x2y3=

(x1-x3)-y1其中

=(y2-y1)/(x2-x1),如果PQ=(3x12+a)/2y1,如果P=QECC算法信息安全概論有限域上橢圓曲線y2+xy

x3+ax2+bmod2m(Galois域的橢圓曲線）（3）加法公式:P=(xP,yP),Q=(xQ,yQ),且P≠-Q,P≠Q(mào)則P+Q=(xR,yR)xR=

2+

+xP+xQ+ayR=

(xP+xR)+xR+yP其中

=(yQ+yP)/(xQ+xP)（1）P+O=P（2）P=(x,y)P＋(x,-y)=O其中（x,-y)是P的負(fù)元－P(4)若P=(xP,yP),則R＝2P=(xr,yr)其中：xR=

2+

+ayR=xP2+(

+1)xR=xp+yp/xP按照上述定義構(gòu)成了一個(gè)橢圓曲線上的Abel群橢圓曲線的運(yùn)算規(guī)則ECC算法信息安全概論橢圓曲線上的離散對(duì)數(shù)“難題”對(duì)于方程Q=kP,其中P，Q屬于Ep(a,b)。對(duì)于給定的k和P，計(jì)算Q比較容易，而對(duì)于給定的P和Q，計(jì)算k比較困難例如：方程y2=(x3+9x+17)mod23所定義的群E23(9,17)。求：P＝（16，5）和Q＝（4，5）的離散對(duì)數(shù)k？窮舉計(jì)算：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橢圓曲線上的離散對(duì)數(shù)困難問(wèn)題ECC算法信息安全概論Alice->BobStep1：Bob選擇Ep(a，b)的元素G，使得G的階n是一個(gè)大素?cái)?shù),秘密選擇整數(shù)k.計(jì)算P=kG,公開(kāi)(p，a，b，G，P)，保密k。其中Kb＝kG為Bob公鑰，Kb‘＝k為Bob私鑰Step2：將消息m編碼為x-y形式的點(diǎn)PmECC加密/解密實(shí)現(xiàn)（續(xù)）ECC算法信息安全概論Alice->BobStep3：Alice隨機(jī)選擇一個(gè)正整數(shù)r，對(duì)Pm產(chǎn)生密文Cm＝{rG，Pm＋rKb}Step4：Bob解密Cm-Kb’(rG)=Pm+rKb-krG=Pm+r(kG)-rkG=PmECC加密/解密實(shí)現(xiàn)ECC算法信息安全概論Alice->BobStep1：Bob選擇E88331(3，45)，G＝(4,11),Bob私鑰Kb‘＝K=3,Bob公布公鑰Kb＝(413,1808)Step2：Pm=(5,1734)

ECC加密/解密實(shí)現(xiàn)示例（續(xù)）ECC算法信息安全概論Alice->BobStep3：Alice隨機(jī)選擇一個(gè)正