現(xiàn)代密碼學(xué)理論與實(shí)踐第10章密鑰管理和其他公鑰密碼體制

現(xiàn)代密碼學(xué)理論與實(shí)踐

第10章密鑰管理和其他公鑰密碼體制FourthEditionbyWilliamStallingsSlidesby楊壽保syang@http:///~syang2012年10月2023/3/51/59現(xiàn)代密碼學(xué)理論與實(shí)踐-10本章要點(diǎn)公鑰密碼方案是安全的，僅當(dāng)公鑰的真實(shí)性能夠得到保證。公鑰證書方案提供了必要的安全性。一個(gè)簡(jiǎn)單的公鑰算法是Diffie-Hellman密鑰交換協(xié)議。這個(gè)協(xié)議使得通信雙方利用基于離散對(duì)數(shù)問題的公鑰算法建立秘密密鑰。這個(gè)協(xié)議是安全的，僅當(dāng)通信雙方的真實(shí)性能夠得到保證。橢圓曲線算術(shù)可以用來開發(fā)許多橢圓曲線密碼ECC方案，包括密鑰交換，加密和數(shù)字簽名。就ECC而言，橢圓曲線算術(shù)是指使用定義在有限域上的橢圓曲線方程。方程里的系數(shù)和變量都是域里的元素。已經(jīng)開發(fā)了很多使用Zp和GF(2m)的方案。2023/3/52現(xiàn)代密碼學(xué)理論與實(shí)踐-10公開密碼的主要作用之一就是解決密鑰分配問題，公鑰密碼實(shí)際上可以用于以下兩個(gè)不同的方面公鑰的分配公鑰密碼用于傳統(tǒng)密碼體制的密鑰分配幾種公鑰分配方法公開發(fā)布、公開可訪問的目錄公鑰授權(quán)、公鑰證書公鑰的公開發(fā)布用戶將他的公鑰發(fā)送給另一通信方，或者廣播給通信各方，比如在電子郵件后附上PGP密鑰，或者發(fā)布到郵件列表上最大問題在于任何人都可以偽造這種公鑰的發(fā)布10.1.1密鑰管理之公鑰的分配2023/3/53現(xiàn)代密碼學(xué)理論與實(shí)踐-10自由的公鑰發(fā)布2023/3/54現(xiàn)代密碼學(xué)理論與實(shí)踐-10維護(hù)一個(gè)動(dòng)態(tài)可訪問的公鑰目錄可以獲得更大程度的安全性一個(gè)可信實(shí)體或組織負(fù)責(zé)這個(gè)公開目錄的維護(hù)和分配目錄包含{name,public-key}等項(xiàng)每一通信方通過目錄管理員以安全的方式注冊(cè)一個(gè)公鑰通信方在任何時(shí)刻可以用新的密鑰替代當(dāng)前的密鑰目錄定期更新目錄可通過電子方式訪問一旦攻擊者獲得目錄管理員私鑰，則可傳遞偽造的公鑰，可以假冒任何通信方以竊取消息，或者修改已有的記錄公開可訪問的目錄2023/3/55現(xiàn)代密碼學(xué)理論與實(shí)踐-10公開可訪問的目錄2023/3/56現(xiàn)代密碼學(xué)理論與實(shí)踐-10A發(fā)送帶有時(shí)間戳的消息給公鑰管理員,請(qǐng)求B的當(dāng)前公鑰管理員給A發(fā)送用其私鑰KRauth加密的消息,A用管理員的公鑰解密，可以確信該消息來自管理員：B的公鑰KUb，用來加密；原始請(qǐng)求，A可以驗(yàn)證其請(qǐng)求未被修改；原始時(shí)間戳,A可以確定收到的不是來自管理員的舊消息。A保存B的公鑰,并用它對(duì)包含A的標(biāo)識(shí)IDA和Nonce1的消息加密,然后發(fā)送給BB以同樣方式從管理員處得到A的公鑰B用KUa對(duì)A的N1和B的N2加密,發(fā)送給AA用B的公鑰對(duì)N2加密并發(fā)送給B,使B相信其通信伙伴是A公鑰授權(quán)2023/3/57現(xiàn)代密碼學(xué)理論與實(shí)踐-10公鑰分配方案2023/3/58現(xiàn)代密碼學(xué)理論與實(shí)踐-10有了公鑰證書使得不通過實(shí)時(shí)訪問公鑰授權(quán)部門而實(shí)現(xiàn)公鑰交換成為可能公鑰證書將一個(gè)通信方的身份與他的公開密鑰綁定在一起，通常還包括有效期和使用方法等證書的所有內(nèi)容必須經(jīng)由可信公鑰授權(quán)方或者證書授權(quán)方簽名后方可生效知道公鑰授權(quán)當(dāng)局公開密鑰的任何人都可以驗(yàn)證一個(gè)用戶的公開密鑰證書的有效性

對(duì)于申請(qǐng)者A，管理員提供的證書為：CA=

EKRauth

[T,IDA,KUa]其他人讀取并驗(yàn)證：DKUauth[CA]=DKUauth

[EKRauth

[T,IDA,KUa]]=(T,IDA,KUa)10.1.2公鑰證書2023/3/59現(xiàn)代密碼學(xué)理論與實(shí)踐-10公鑰證書的交換2023/3/510現(xiàn)代密碼學(xué)理論與實(shí)踐-10采用前述方法獲得的公開密鑰可以用于保密和認(rèn)證之需公鑰密碼算法速度較慢，因此更適合作為傳統(tǒng)密碼中實(shí)現(xiàn)秘密密鑰分配的一種手段因此，需要產(chǎn)生會(huì)話密碼來加密已經(jīng)有一些方法用來協(xié)商適當(dāng)?shù)臅?huì)話密鑰10.1.3利用公鑰密碼分配傳統(tǒng)密碼體制的密鑰2023/3/511現(xiàn)代密碼學(xué)理論與實(shí)踐-10一種簡(jiǎn)單的秘密密鑰分配方法Merkle在1979提出一種簡(jiǎn)單的方法A產(chǎn)生公/私鑰對(duì){PUa,PRa},將含有PUa和標(biāo)識(shí)IDA的消息發(fā)給BB產(chǎn)生秘密密鑰(會(huì)話密鑰)Ks,并用A的公鑰加密后發(fā)給AA解密D(PRa,E(PUa,Ks),得到Ks,這樣雙方即可通信這個(gè)協(xié)議不安全，因?yàn)闀?huì)受到中間人攻擊2023/3/512現(xiàn)代密碼學(xué)理論與實(shí)踐-10具有保密性和真實(shí)性的密鑰分配2023/3/513現(xiàn)代密碼學(xué)理論與實(shí)踐-1010.2Diffie-Hellman密鑰交換Diffie和Hellman在1976年首次提出了公鑰算法，給出了公鑰密碼學(xué)的定義，該算法通常被稱為Diffie-Hellman密鑰交換算法Diffie-Hellman密鑰交換算法是一種公鑰分發(fā)機(jī)制它不是用來加密消息的所生成的是通信雙方共享的會(huì)話密鑰，必須保密，其值取決于通信雙方的私鑰和公鑰信息Diffie-Hellman密鑰交換算法是基于有限域GF中的指數(shù)運(yùn)算的(模一素?cái)?shù)或多項(xiàng)式)Diffie-Hellman密鑰交換算法的安全性依賴于求解離散對(duì)數(shù)問題DLP2023/3/514現(xiàn)代密碼學(xué)理論與實(shí)踐-10離散對(duì)數(shù)問題DiscreteLogarithmProblem如果a是素?cái)?shù)p的一個(gè)原根(本原元素)，則amodp,a2modp,......,ap-1modp，生成模p的完全剩余集{1,2,......,p-1}對(duì)于所有素?cái)?shù)，其原根必定存在，即對(duì)于一個(gè)整數(shù)b和素?cái)?shù)p的一個(gè)原根a，可以找到唯一的指數(shù)i,使得b=aimodp,其中0<=i<=p-1指數(shù)i稱為b的以a為基數(shù)的模p的離散對(duì)數(shù)或者指數(shù)。離散對(duì)數(shù)密碼體制的安全性基于DLP問題,在已知C和P的情況下,由d求M很容易,由M求d很困難,d=logCMinGF(P),最快的算法需要T=exp((ln(P)lnln(P)1/2)次運(yùn)算。當(dāng)P是200位時(shí),T=2.7x1011,如果1μs解一次,需要2~3天；如果P=664位,則T=1.2x1023,約1012天或2.739x109年,約2.7億年.只要P足夠大,可以達(dá)到足夠安全。2023/3/515現(xiàn)代密碼學(xué)理論與實(shí)踐-10Diffie-HellmanKeyExchange通信雙方約定一個(gè)大素?cái)?shù)(或多項(xiàng)式)p,和模p的一個(gè)素根α各方產(chǎn)生公開密鑰選擇一個(gè)秘密鑰(數(shù)值)，如xA<p，xB<p

計(jì)算公鑰,如yA=αxAmodp,yB=αxBmodp,并相互交換雙方共享的會(huì)話密鑰KAB可以如下算出KAB=αxA.xBmodp=yAxBmodp(whichBcancompute)=yBxAmodp(whichAcancompute)KAB是雙方用對(duì)稱密碼通信時(shí)共享的密鑰如果雙方繼續(xù)通信，可以繼續(xù)使用這個(gè)密鑰，除非他們要選擇新的密鑰攻擊者如果想要獲得x,則必須解決DLP問題2023/3/516現(xiàn)代密碼學(xué)理論與實(shí)踐-10Diffie-HellmanExampleUsersAlice&BobwhowishtoswapkeysAgreeonprimep=353andα

=3Selectrandomsecretkeys:AchoosesxA=97,BchoosesxB=233Computepublickeys:yA=397mod353=40 (Alice)yB=3233mod353=248 (Bob)Computesharedsessionkeyas:KAB=yBxAmod353=24897mod353=160 (Alice)KAB=yAxBmod353=40233mod353=160 (Bob)2023/3/517現(xiàn)代密碼學(xué)理論與實(shí)踐-1010.2.2Diffie-Hellman密鑰交換協(xié)議本協(xié)議不能抵抗中間人攻擊2023/3/518現(xiàn)代密碼學(xué)理論與實(shí)踐-10假設(shè)A和B互相通信，共享大素?cái)?shù)p，本原元素α，0≤m≤p-1加密：A選擇k∈[0,p-1],k的作用其實(shí)即為xA,A訪問公共區(qū)域找到B的公開密鑰YB=αxBmodp,計(jì)算：K=(YB)kmodp,即K=αxBkmodpc1=αk

modpc2=mKmodp密文即為(c1,c2)解密：B首先恢復(fù)K：K=c1xB

modP=αkxBmodp然后恢復(fù)m：m=c2/KmodP=c2K-1modp基于DLP的概率密碼系統(tǒng)

ElGamalCryptosystem2023/3/519現(xiàn)代密碼學(xué)理論與實(shí)踐-10這里特別注意，k不能重復(fù)使用，如果(1)c1,1=αkmodp c2,1=m1Kmodp(2)c1,2=αkmodp c2,2=m2Kmodp得：m1/m2=c2,1/c2,2modp.如果m1已知，m2即可算出。ElGamal密碼體制是概率密碼體制，同樣的明文每次加密得到不同的密文,因?yàn)槊看坞S機(jī)選擇k。ElGamal密碼體制加密效率是50%，因?yàn)槊芪拇笮∈敲魑牡膬杀丁lGamal密碼體制的破譯難度同Diffie-Hellman的方法,即基于DLP，離散對(duì)數(shù)問題，最快的算法需要T=exp((ln(p)lnln(p)1/2)次運(yùn)算。ElGamalCryptosystem2023/3/520現(xiàn)代密碼學(xué)理論與實(shí)踐-10例：P=17,α=3,xA=2,xB=5,m=11,m從A發(fā)送到B,A選擇k=7.求：密文(c1,c2)并解密加密：YA=αxAmodP=32mod17=9 YB=αxBmodP=35mod17=5 K=(YB)kmodP=57mod17=10 c1=αkmodP=37mod17=11 c2=mKmodP=10x11mod17=8 所以，密文C=(c1,c2)=(11,8)解密：K=c1xBmodP=115mod17=10 c2=mKmodP=10mmod17=8 m=c2/KmodP=c2K-1modP KK-1modP=1，即10K-1mod17=1，得K-1=12

所以，明文m=c2K-1modP=8x12mod17=11ElGamalCryptosystem2023/3/521現(xiàn)代密碼學(xué)理論與實(shí)踐-1010.3橢圓曲線算術(shù)橢圓曲線密碼編碼學(xué)ECC使用橢圓曲線密碼系統(tǒng)ECC,可以達(dá)到如RSA,D-H同樣的安全但位數(shù)要小得多。橢圓曲線并非橢圓,它指的是由Weierstrass威爾斯特拉斯方程所確定的平面曲線：y2+axy+by=x3+cx2+dx+e一般形式：y2=x3+ax+b滿足上述方程的數(shù)偶(x,y)稱為橢圓曲線E上的點(diǎn)。同時(shí)定義無窮點(diǎn)(pointatinfinity)或零點(diǎn)(zeropoint)的O。2023/3/522現(xiàn)代密碼學(xué)理論與實(shí)踐-10實(shí)數(shù)域上的橢圓曲線一般形式具有不同根的條件例子2023/3/523現(xiàn)代密碼學(xué)理論與實(shí)踐-10橢圓曲線舉例(a)y2=x3-x(b)y2=x3+x+12023/3/524現(xiàn)代密碼學(xué)理論與實(shí)踐-10單位元和逆元逆元：

P’(x,-y)=P(x,y)關(guān)于X軸對(duì)稱點(diǎn)。P+P’=O單位元P+O=P2023/3/525現(xiàn)代密碼學(xué)理論與實(shí)踐-10如果橢圓曲線上的三個(gè)點(diǎn)處于一條直線上,那么它們的和為O。加法規(guī)則：O是加法的單位元(additiveidentity),O=－O；對(duì)于橢圓曲線上的任一點(diǎn)P,有P+O=P。一條垂直線與曲線相交于P1=(x,y)和P2=(x,－y),也相交于無窮點(diǎn)O,有P1+P2+O=O和P1=－P2。對(duì)具有不同的x坐標(biāo)的Q和R相加,在它們之間畫一條直線求出第三個(gè)交點(diǎn)P1,這種交點(diǎn)是唯一的。因?yàn)镼+R+P1=O,因此Q+R=－P1對(duì)點(diǎn)Q加倍,畫一切線求出另一交點(diǎn)S,則Q+Q=2Q=－S一條橢圓曲線上的一點(diǎn)P被一個(gè)正整數(shù)k相乘的乘法被定義為k個(gè)P的相加橢圓曲線上的形式加法2023/3/526現(xiàn)代密碼學(xué)理論與實(shí)踐-10橢圓曲線的加法橢圓曲線上的點(diǎn)集及其上的加法操作構(gòu)成一個(gè)群點(diǎn)集橢圓曲線上的所有點(diǎn)和無窮點(diǎn)操作點(diǎn)加法R=P+Q（或R=P*Q）2023/3/527現(xiàn)代密碼學(xué)理論與實(shí)踐-10點(diǎn)的累加二倍過點(diǎn)P(x,y)的切線R=P+P2023/3/528現(xiàn)代密碼學(xué)理論與實(shí)踐-10反復(fù)累加kP=P+…+P或?qū)憺椋?023/3/529現(xiàn)代密碼學(xué)理論與實(shí)踐-10數(shù)學(xué)描述直線g:y=sx+y0其中：與曲線相交：(sx+y0)2=x3+ax+bR點(diǎn)坐標(biāo)：2023/3/530現(xiàn)代密碼學(xué)理論與實(shí)踐-10數(shù)學(xué)描述切線g：y=sx+y0與曲線相交：(sx+y0)2=x3+ax+bR點(diǎn)坐標(biāo)：2023/3/531現(xiàn)代密碼學(xué)理論與實(shí)踐-10有限域上的橢圓曲線

FiniteEllipticCurves可以將橢圓曲線定義于有限域GFP上

y2=x3+ax+bmodpp是一個(gè)素?cái)?shù),并且{0,1,…,p-1}是模p加的交換群(Abelian)；{1,…,p-1}是模p乘的交換群橢圓曲線密碼系統(tǒng)采用變量和系數(shù)有限的曲線來實(shí)現(xiàn)2023/3/532現(xiàn)代密碼學(xué)理論與實(shí)踐-10定義在Zp上的素曲線(primecurves)Ep(a,b)使用三次方程，變量和系數(shù)取自集合{0,1,…,p-1},模p運(yùn)算最適合用軟件實(shí)現(xiàn)定義在GF(2n)上的二元曲線E2n(a,b)變量和系數(shù)取自GF(2n),模素多項(xiàng)式(二進(jìn)制多項(xiàng)式)最適合硬件實(shí)現(xiàn)Ep(a,b)表示滿足下列條件的模p橢圓群,群中元素(x,y)是滿足如下方程的小于p的非負(fù)整數(shù)另外加上無窮點(diǎn)O：y2modp=(x3+ax+b)modp.例如：p=23,有4a3+27b2=4x13+27x12mod23=8≠0,滿足條件(這里a,b=1)兩種有限域上的橢圓曲線2023/3/533現(xiàn)代密碼學(xué)理論與實(shí)踐-10橢圓曲線E23(1,1)上的點(diǎn)對(duì)于每個(gè)滿足0≤x<p的x,計(jì)算y2=x3+x+1modp對(duì)于上一步得到的每個(gè)結(jié)果確定它是否有一個(gè)模p的平方根,如果沒有,在E23(1,1)中就沒有具有這個(gè)x值的點(diǎn)；如果有,就有兩個(gè)滿足平方根運(yùn)算的y值(除非這個(gè)值是單個(gè)的y值0)。這些(x,y)就是E23(1,1)上的點(diǎn)2023/3/534現(xiàn)代密碼學(xué)理論與實(shí)踐-10橢圓曲線E23(1,1)上的點(diǎn)2023/3/535現(xiàn)代密碼學(xué)理論與實(shí)踐-10橢圓曲線上的點(diǎn)在GF11上找出滿足橢圓曲線方程的點(diǎn)P(x,y):

y2=x3+x+6mod11有12個(gè)點(diǎn),加上無窮遠(yuǎn)點(diǎn)O共有n=13個(gè)元素2023/3/536現(xiàn)代密碼學(xué)理論與實(shí)踐-10橢圓曲線點(diǎn)加運(yùn)算將y2=x3+x+6mod11上的點(diǎn)(2,4)反復(fù)累加計(jì)算2P=P+P

（或記為P2=P*P)計(jì)算3P=P+P+P=2P+P（或記為P3=P*P*P=P2*P)所有運(yùn)算均在GF11上進(jìn)行2023/3/537現(xiàn)代密碼學(xué)理論與實(shí)踐-10橢圓曲線點(diǎn)加運(yùn)算取P(2,4),計(jì)算2P=P+P

（或記為P2=P*P)再計(jì)算3P=P+P+P=2P+P

（或記為P3=P2*P)2023/3/538現(xiàn)代密碼學(xué)理論與實(shí)踐-10GF(2n)上的橢圓曲線有限域GF(2n)由2n個(gè)元素及定義在多項(xiàng)式上的加法和乘法運(yùn)算組成給定某n,對(duì)于GF(2n)上的橢圓曲線，使用變?cè)拖禂?shù)均在GF(2n)上取值的三次方程，且利用GF(2n)中的算術(shù)運(yùn)算規(guī)則來進(jìn)行計(jì)算可以證明，GF(2n)上適合橢圓曲線密碼應(yīng)用的三次方程與Zp上的三次方程有所不同，形為

y2+xy=x3+ax2+b

其中變?cè)獂和y以及系數(shù)a和b是GF(2n)中的元素，計(jì)算在GF(2n)中進(jìn)行2023/3/539現(xiàn)代密碼學(xué)理論與實(shí)踐-10GF(2n)上的橢圓曲線考慮所有整數(shù)對(duì)(x,y)和無窮遠(yuǎn)點(diǎn)O組成的集合E2n(a,b)例如，使用不可約多項(xiàng)式f(x)=x4+x+1(10011)定義的有限域GF(24)，其生成元g滿足f(g)=0,即g1=0010,

g4=g+1,或二進(jìn)制0011,g5=(g4)(g)=g2+g=0110g0=0001g4=0011g8=0101g12=1111g1=0010g5=0110g9=1010g13=1101g2=0100g6=1100g10=0111g14=1001g3=1000g7=1011g11=1110g15=00012023/3/540現(xiàn)代密碼學(xué)理論與實(shí)踐-10GF(2n)上的橢圓曲線例如，考慮橢圓曲線y2+xy=x3+g4x2+1,a=g4=0011,b=g0=0001,

滿足該方程的一個(gè)點(diǎn)(x,y)為(g5,

g3)：(g3)2+(g5)(g3)=(g5)3+(g4)(g5)2+1g6+g8=g15+g14+11100+0101=0001+1001+00011001=10012023/3/541現(xiàn)代密碼學(xué)理論與實(shí)踐-102023/3/542現(xiàn)代密碼學(xué)理論與實(shí)踐-10大多數(shù)公開密鑰密碼系統(tǒng)如RSA,D-H都使用具有非常大數(shù)目的整數(shù)或多項(xiàng)式，計(jì)算量大，密鑰和報(bào)文存儲(chǔ)量也極大。使用橢圓曲線密碼系統(tǒng)ECC，可以達(dá)到同樣安全但位數(shù)要小得多。ECC的加類似于模乘，ECC的重復(fù)加類似于模指數(shù)ECC需要有對(duì)應(yīng)于DLP的難解問題Q=kP,Q,P屬于Ep(a,b),k<P給定k,P,容易計(jì)算Q=kP但是給定Q,P,求k難這就是橢圓曲線對(duì)數(shù)問題10.4橢圓曲線密碼學(xué)2023/3/543現(xiàn)代密碼學(xué)理論與實(shí)踐-10橢圓曲線對(duì)數(shù)問題給定曲線

y2=x3+ax+bmodp

以及其上一點(diǎn)P，我們可以通過連續(xù)自加k-1次計(jì)算

Q=kP,(或Q=Pk)。目前存在這樣的快速算法。問題：當(dāng)Q已知時(shí)能否計(jì)算k?答案：這是一個(gè)被稱為橢圓曲線對(duì)數(shù)的難題。2023/3/544現(xiàn)代密碼學(xué)理論與實(shí)踐-10橢圓曲線密碼學(xué)例：E23(9,17),即y2=(x3+9x+7)mod23,以P=(16,5)為底的Q=(4,5)的離散對(duì)數(shù)k為多少？可以通過窮舉攻擊方法，多次計(jì)算P的倍數(shù)直至找到Q為止，這樣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)所以,以P=(16,5)為底的Q=(4,5)的離散對(duì)數(shù)k為9實(shí)際應(yīng)用中，k的值非常大，窮舉攻擊不可行2023/3/545現(xiàn)代密碼學(xué)理論與實(shí)踐-10橢圓曲線密碼學(xué)橢圓曲線密碼系統(tǒng)的定義域標(biāo)識(shí)：定義橢圓曲線采用的有限域橢圓曲線：系數(shù)a和b基準(zhǔn)點(diǎn)(base)：指定的橢圓曲線上的點(diǎn)P階(order)：P點(diǎn)的階n，使得nP=O橢圓曲線公鑰系統(tǒng)EP(a,b),GFPBasepointP(x,y)選擇e作為私有密鑰公開密鑰為Q=eP2023/3/546現(xiàn)代密碼學(xué)理論與實(shí)踐-1010.4.1Diffie-Hellman的橢圓曲線實(shí)現(xiàn)選定橢圓曲線上一點(diǎn)GA、B分別隨機(jī)選取a,b并保密AQA=aGBQB=bGA:Q=a(QB)=abG

B:Q=b(QA)=baG=abG

2023/3/547現(xiàn)代密碼學(xué)理論與實(shí)踐-102023/3/548現(xiàn)代密碼學(xué)理論與實(shí)踐-10類似于D-H，ECC也可以實(shí)現(xiàn)密鑰交換用戶選擇合適的ECC,Ep(a,b)選擇基點(diǎn)G=(x1,y1),滿足nG=O的最小n是一個(gè)大素?cái)?shù)A和B之間的密鑰交換如下A和B選擇私鑰nA<n,nB<n計(jì)算公鑰PA=nA×G,PB=nB×GA與B交換PA和PB計(jì)算共享密鑰K=nA×PB=nB×PA,因?yàn)镵=nA×nB×G，所以這兩個(gè)密鑰是一樣的。ECC與Diffie-Hellman密鑰交換的類比2023/3/549現(xiàn)代密碼學(xué)理論與實(shí)踐-10用ECC實(shí)現(xiàn)Diffie-Hellman密鑰交換例如Ep(0,-4),即y2=x3-4,G=(2,2),p=211,n=240;計(jì)算240G=OnA=121,PA=121(2,2)=(115,48)nB=203,PB=203(2,2)=(130,203)K=121(130,203)=203(115,48)=(161,69)2023/3/550現(xiàn)代密碼學(xué)理論與實(shí)踐-10Massey-Omura公鑰體制在GF(q)上,用戶A的加密、解密密鑰為eA,dAgcd(eA,q-1)=1,eAdA=1mod(q-1)同樣,用戶B的加密、解密密鑰為eB,dBgcd(eB,q-1)=1,eBdB=1mod(q-1)A將消息m發(fā)送給B:

AmeA

B

meA

eB(meA

eB)da

=meB

B:

(

meB

)dB=m

2023/3/551現(xiàn)代密碼學(xué)理論與實(shí)踐-10Massey-Omura在橢圓曲線上實(shí)現(xiàn)m嵌入橢圓曲線上的點(diǎn)Pmn：橢圓曲線上的點(diǎn)數(shù)(已知大素?cái)?shù))用戶隨機(jī)選擇e：1<e<n,gcd(e,n)=1,ed=1modnA將消息m發(fā)送給B：

AeAPm

B

eBeAPm

dA(

eBeAPm

)=eBPm

B:dB(

eBPm

)=Pm2023/3/552現(xiàn)代密碼學(xué)理論與實(shí)踐-10ElGamal算法在橢圓曲線上實(shí)現(xiàn)E(a,b),basepointG屬于EA選擇a并保密,0<a<n，n為G的階(order)

aG公開B向A發(fā)送消息m

B將m嵌入點(diǎn)Pm，選擇隨機(jī)數(shù)k,

A(kG,Pm+k(aG))BA：Pm=Pm+k(aG)–a(kG)本質(zhì)上：A,B共享秘密akG2023/3/553現(xiàn)代密碼學(xué)理論與實(shí)踐-10首先將明文消息m編碼為x-y的點(diǎn)Pm,點(diǎn)Pm就是要進(jìn)行加密和解密的,不能簡(jiǎn)單地把消息編碼為點(diǎn)的x坐標(biāo)或y坐標(biāo)，因?yàn)椴⒉皇撬械淖鴺?biāo)都在Eq(a,b)中。