計(jì)算機(jī)安全與保密-第4章

計(jì)算機(jī)安全與保密-第4章第1頁內(nèi)容ELGAMAL公鑰密碼系統(tǒng) 橢圓曲線密碼體制 橢圓曲線標(biāo)量乘法 GF(2m)域橢圓曲線 離散對數(shù)問題求解計(jì)算機(jī)安全與保密-第4章第2頁ELGAMAL公鑰密碼系統(tǒng)另一個(gè)NP問題離散對數(shù)問題（DiscreteLogarithmProblem，簡稱DLP）當(dāng)前還沒有找到離散對數(shù)問題多項(xiàng)式時(shí)間算法T.Elgamal于1985年率先提出Elgamal公鑰密碼系統(tǒng)在有限群G（Zp*）中，尋找唯一指數(shù)0≤x≤|H|-1，H是由α?G產(chǎn)生子群，使得β=αx.相當(dāng)于log

αβ.計(jì)算機(jī)安全與保密-第4章第3頁Elgamal公鑰密碼系統(tǒng)計(jì)算機(jī)安全與保密-第4章第4頁實(shí)例Elgamal公鑰密碼體制引入了一個(gè)輔助參數(shù)k即使明文和密鑰都相同，密文也會伴隨k不一樣取值而各不相同計(jì)算機(jī)安全與保密-第4章第5頁橢圓曲線密碼體制橢圓曲線定義在域F上橢圓曲線E指是由韋爾斯特拉斯（Weierstrass）方程所確定平面曲線。滿足上述方程點(diǎn)（x,y）稱為F域上橢圓曲線上點(diǎn)，除了上面點(diǎn)，還有一個(gè)特殊點(diǎn)——無窮遠(yuǎn)點(diǎn)O。橢圓曲線簡化形式：計(jì)算機(jī)安全與保密-第4章第6頁有限域GF(p)上橢圓曲線設(shè)p是素?cái)?shù)，且p>3，在有限域上橢圓曲線由滿足：點(diǎn)(x,y)和一個(gè)特殊無窮遠(yuǎn)點(diǎn)O組成，記作Ep（a,b）計(jì)算機(jī)安全與保密-第4章第7頁xz是否是平方剩下y010否100215否34是17,2411是7,1254是17,268否710否816是4,15913否107是11,8114是17,21210否1312否1416是4,15159是16,31616是4,15175是9,10181是1,18{1,0}，{3,2}，{3,17}，{4,7}，{4,12}{5,2}，{5,17}，{8,4}，{8,15}，{10,8}{10,11}，{11,2}，{11,17}，{14,4}，{14,15}{15,3}，{15,16}，{16,4}，{16,15}，{17,9}{17,10}，{18,1}， {18,18}計(jì)算機(jī)安全與保密-第4章第8頁橢圓曲線E19（8,10）點(diǎn)分布圖計(jì)算機(jī)安全與保密-第4章第9頁定義加法PQRQ計(jì)算機(jī)安全與保密-第4章第10頁定義幺元和逆元逆元：P+

(-P)

=O

-P(x,y)=P(x,-y)幺元：P+

O=P計(jì)算機(jī)安全與保密-第4章第11頁R'RP倍點(diǎn)運(yùn)算計(jì)算機(jī)安全與保密-第4章第12頁P(yáng)2PP3標(biāo)量乘運(yùn)算計(jì)算機(jī)安全與保密-第4章第13頁加法計(jì)算公式gPQR計(jì)算機(jī)安全與保密-第4章第14頁gPR倍點(diǎn)計(jì)算公式計(jì)算機(jī)安全與保密-第4章第15頁實(shí)例計(jì)算機(jī)安全與保密-第4章第16頁MV-橢圓曲線公鑰密碼系統(tǒng)計(jì)算機(jī)安全與保密-第4章第17頁實(shí)例計(jì)算機(jī)安全與保密-第4章第18頁二進(jìn)制法帶符號二進(jìn)制法Comb標(biāo)量乘算法橢圓曲線標(biāo)量乘法E211(1,1)：y2=x3+x+1,p=211P(2,86)，k=112求：Q=kPk=(1110000)2Q=00：P=2P=(43,209)0：P=2P=(207,12)0：P=2P=(14,4)0：P=2P=(55,116)1：Q=Q+P=(55,116);P=2P=(157,201)1：Q=Q+P=(29,187);P=2P=(151,65)1：Q=Q+P=(32,27)Q=(32,27)從右向左計(jì)算機(jī)安全與保密-第4章第19頁二進(jìn)制法帶符號二進(jìn)制法Comb標(biāo)量乘算法1：Q=2Q=0;Q=Q+P=(2,86)1：Q=2Q=(43,209);Q=Q+P=(175,28)1：Q=2Q=(12,105);Q=Q+P=(93,142)0：Q=2Q=(45,190)0：Q=2Q=(137,178)0：Q=2Q=(13,177)0：Q=2Q=(32,27)從左向右Q=(32,27)計(jì)算機(jī)安全與保密-第4章第20頁二進(jìn)制法帶符號二進(jìn)制法Comb標(biāo)量乘算法i=0k=112是偶數(shù)，k0=0；k=56,i=1k=56是偶數(shù)，k1=0；k=28,i=2k=28是偶數(shù)，k2=0；k=14,i=3k=14是偶數(shù)，k3=0；k=7,i=4k=7是奇數(shù)，k4=-1，k=8；k=4,i=5k=4是偶數(shù)，k5=0；k=2,i=6k=2是偶數(shù)，k6=0；k=1,i=7k=1是奇數(shù)，k7=1，k=0；k=0,i=8k=112K表示成(100-10000)2計(jì)算機(jī)安全與保密-第4章第21頁二進(jìn)制法帶符號二進(jìn)制法Comb標(biāo)量乘算法Q=01：Q=2Q=0;Q=Q+P=(2,86)0：Q=2Q=(43,209)0：Q=2Q=(207,12)-1：Q=2Q=(14,4);Q=Q-P=(93,142)0：Q=2Q=(45,190)0：Q=2Q=(137,178)0：Q=2Q=(13,177)0：Q=2Q=(32,27)計(jì)算機(jī)安全與保密-第4章第22頁GF（2m）表示方法多項(xiàng)式基(Polynomialbasis)表示法正規(guī)基(Normalbasis)表示法GF(2m)域橢圓曲線GF（2m）上橢圓曲線由滿足：點(diǎn)(x,y)和一個(gè)特殊無窮遠(yuǎn)點(diǎn)O組成。其中:a,b?

GF(2m)且b≠0.二進(jìn)制域GF（24）上全部元素計(jì)算機(jī)安全與保密-第4章第23頁GF（24）域上不可約多項(xiàng)式是計(jì)算機(jī)安全與保密-第4章第24頁點(diǎn)運(yùn)算加法計(jì)算公式倍點(diǎn)計(jì)算公式逆元計(jì)算機(jī)安全與保密-第4章第25頁實(shí)例(0000，1011)，(0001，0000)，(0001，0001)(0010，1101)，(0111，1100)，(001l，1100)(001l，1111)，(010l，0000)，(010l，0101)(0111，1011)，(1011，1001)，(1000，0001)(1000，1001)，(1001，0110)，(1001，1111)(1011，0010)，(1100，0000)，(1100，1100)(1111，0100)，(1111，1011)，(0010，1111)GF（24）上不可約多項(xiàng)式橢圓曲線曲線上除無窮遠(yuǎn)點(diǎn)O全部點(diǎn)計(jì)算機(jī)安全與保密-第4章第26頁(0010，1111)+(1100，1100)=(0001，0001)2(0010，1111)=(1011，0010)點(diǎn)加運(yùn)算倍點(diǎn)運(yùn)算計(jì)算機(jī)安全與保密-第4章第27頁離散對數(shù)問題求解窮盡搜索法大步小步法（BabyStep/GiantStep）Polard-ρ方法計(jì)算機(jī)安全與保密-第4章第28頁p=181α=23β=113j04138791012116135223j(mod)18111523404457107108117131152157164167i0123113*23-14*imod181)1138813140x=i*L+j=2*14+11=39計(jì)算機(jī)安全與保密-第4章第29頁離散對數(shù)問題求解窮盡搜索法大步小步法（BabyStep/GiantStep）Polard-ρ方法p=179α=3β=75將群G分為規(guī)模相當(dāng)三個(gè)集合S1，S2，S3S1=[1,59]，S2=[60,118]，S3=[119,178]a0=133，b0=158x0=αa0βb0=57mod(p)計(jì)算機(jī)安全與保密-第4章第30頁ixiaibi02513315818513315926526631831085326364291064127252710641273656106412747831064127588721282550951425651001066425651011160851210202122017024204041368170242040514149340484081015893404940810164568098816201715368098816211810168099816211917713619816324220173136199