信息安全基礎(chǔ)5公開密鑰算法教學(xué)教案

5公開密鑰算法概述RSA算法其他公開密鑰算法公開密鑰數(shù)字簽名算法身份驗(yàn)證體制密鑰交換算法5.1概述成對密鑰的思想：一個(gè)加密密鑰和一個(gè)解密密鑰，而從其中一個(gè)密鑰推導(dǎo)出另外一個(gè)是不能的?；旌厦艽a系統(tǒng)：對稱算法用于加密消息，公開密鑰算法用于加密密鑰。5.2RSA算法第一個(gè)成熟的公開密鑰算法，可以用作加密和數(shù)字簽名算法描述：RSA的安全性基于大整數(shù)的因數(shù)分解的困難性首先隨機(jī)選擇兩個(gè)大素?cái)?shù)p和q，計(jì)算n=pq然后隨機(jī)選擇加密密鑰e，滿足e與(p-1)(q-1)互素。用擴(kuò)展的Euclid算法計(jì)算解密密鑰d，使得ed

1mod(p-1)(q-1)公開密鑰：e和n秘密密鑰：d加密：C=Memodn解密：M=CdmodnRSA算法用于數(shù)字簽名：(見148頁7.1.6)數(shù)字簽名：手寫簽名來證明文件的原作者，或至少證明簽名者同意文件的內(nèi)容簽名的特性：可信性：文件的接收者應(yīng)該相信簽名者慎重簽署了該文件；不可偽造性：能夠證明是簽名者本人，而不是別人慎重簽署了該文件；不可重用性：簽名應(yīng)該作為文件的一部分，任何人不能將該簽名移動(dòng)到別的文件上去；不可更改性：任何人不能對簽名后的文件內(nèi)容進(jìn)行更改；不可否認(rèn)性：簽名及文件是客觀存在的，簽名者不能事后否認(rèn)他簽署過該文件。RSA簽名：S=MdmodnM:要簽名的消息驗(yàn)證簽名：M=Semodne:公開密鑰d:秘密密鑰5.3ElGamal公開密鑰算法ElGamal：安全性基于有限域內(nèi)計(jì)算離散對數(shù)的困難性。數(shù)字簽名加密ElGamal產(chǎn)生密鑰：一個(gè)素?cái)?shù)p和兩個(gè)隨機(jī)數(shù)g，x，使g和x都小于p。計(jì)算y=gxmodp公開密鑰：y,g和p，g和p由一群用戶共享秘密密鑰：xElGamal簽名產(chǎn)生簽名：選擇一個(gè)隨機(jī)數(shù)k，使k與p-1互素。計(jì)算a=gkmodp用擴(kuò)展的Euclid算法求b，使M=(xa+kb)mod(p-1)數(shù)字簽名為a和b，k要保密。驗(yàn)證簽名：確認(rèn)是否有yaabmodp=gMmodp例：選擇p=11,g=2,秘密密鑰x=8,M=5則y=gxmodp=28mod11=3公開密鑰為：y=3,g=2,p=11產(chǎn)生簽名：選擇一個(gè)隨機(jī)數(shù)k=9gcd(k,p-1)=gcd(9,10)=1互素計(jì)算：a=gkmodp=29mod11=6用擴(kuò)展Euclid算法求b:M=(xa+kb)mod(p-1)5=(6*8+9b)mod105=8+9bmod107=9bmod10

b=7*9-1mod10=7*9mod10=3簽名為：a=6,b=3驗(yàn)證簽名：確認(rèn)yaabmodp=gMmodp是否相等yaabmodp=3663mod11=10gMmodp=25mod11=10等式成立ElGamal加密加密M：選擇隨機(jī)數(shù)k，使k與p-1互素計(jì)算a=gkmodp,b=ykMmodp,a和b為密文解密：計(jì)算M=b/axmodpb/axmodp=ykM/axmodp=gkxM/gkxmodp=M上例：y=3,g=2,p=11,x=8,M=5,k=9加密：a=gk

modp=29mod11=6

b=ykMmodp=39*5mod11=9解密：M=b/axmodp=9/68mod11=9/4mod11=9*3mod11=55.4公開密鑰數(shù)字簽名算法數(shù)字簽名算法（DSA）DSA變體GOST數(shù)字簽名算法離散對數(shù)簽名體制數(shù)字簽名算法（DSA）算法描述參數(shù)：p：一個(gè)L位長的二進(jìn)制素?cái)?shù)，L從512到1024，是64的整數(shù)倍；q：一個(gè)160位的p-1的素?cái)?shù)因子；g=h(p-1)/qmodp，其中h是小于p-1的任意數(shù)，且h(p-1)/qmodp>1；x：一個(gè)小于q的數(shù)；y=gxmodp。p,q和g公開，可由一群用戶共享秘密密鑰：x，公開密鑰：y一個(gè)單向哈希函數(shù)H(M)，為安全哈希算法（SHA）簽名：A產(chǎn)生一個(gè)比q小的隨機(jī)數(shù)k；A計(jì)算r=(gkmodp)modq,s=(k-1(H(M)+xr))modq,r和s為簽名。A向B發(fā)送r和s；B驗(yàn)證簽名：w=s-1modq,u1=(H(M)*w)modq,u2=(r*w)modq,v=((gu1*yu2)modp)modq,

如果v=r，則簽名有效。用預(yù)先計(jì)算加快速度DSA的素?cái)?shù)產(chǎn)生使用DSA的ElGamal加密用DSA進(jìn)行RSA加密5.5身份驗(yàn)證體制身份驗(yàn)證方法Feige-Fiat-ShamirGuillou-QuisquaterSchnorr身份驗(yàn)證方法身份驗(yàn)證（Authentication）：當(dāng)A登錄進(jìn)入郵件服務(wù)器、網(wǎng)上銀行系統(tǒng)或其他類型的系統(tǒng)，系統(tǒng)需要通過某種方式來驗(yàn)證登錄者的身份。常用的一些身份驗(yàn)證方法：使用物理標(biāo)識：護(hù)照，駕駛執(zhí)照、信用卡等使用人體的生物特征：指紋、視網(wǎng)膜、及其他一些生物特征，或使用人臉識別技術(shù)、步態(tài)識別技術(shù)等使用口令使用單向函數(shù)：系統(tǒng)存儲的是口令的單向函數(shù)值，而不是口令本身。容易受到詞典攻擊的威脅。使用公鑰密碼使用零知識證明協(xié)議零知識證明零知識：設(shè)A和B是網(wǎng)絡(luò)上的兩個(gè)用戶，A只想讓B知道他掌握某件事，而不想讓B知道這件事的內(nèi)容。稱B對這件事具有零知識。零知識證明（Zero-KnowledgeProof）：在協(xié)議中，用P（證明者）和V（驗(yàn)證者）分別代表用戶A和B。P向V證明他確實(shí)具有一條信息，而又不告訴V用什么方法獲取該信息。證明采取相互作用協(xié)議的形式：P聲稱他知道某一條信息，V問P一系列有關(guān)該信息的問題，如果P真的知道這條信息，他就能正確回答所有的問題。如果P不知道這條信息，那么，正確回答問題的概率只有50%?；卮鹑舾蓚€(gè)問題后，V就能確定P是否真的知道這條信息所有這些問題及答案都不能向V提供任何有關(guān)P所具有的信息的內(nèi)容。洞穴圖n次試驗(yàn)：P能夠成功欺騙V的概率為1/2nCDBAFeige-Fiat-Shamir簡化的Feige-Fiat-Shamir身份驗(yàn)證體制：仲裁人選擇一個(gè)隨機(jī)模n，為兩個(gè)大素?cái)?shù)的乘積產(chǎn)生密鑰：仲裁人選擇一個(gè)數(shù)v，令v為模n的一個(gè)二次剩余即x2

v(modn)，且v-1也存在。v為甲的公開密鑰。計(jì)算s=sqrt(v-1)modn的最小的s，為甲的秘密密鑰。協(xié)議：甲方隨機(jī)選取一個(gè)r，使r<n。然后計(jì)算x=r2modn，將x發(fā)送給乙方；乙方向甲方發(fā)送一個(gè)隨機(jī)位b；如果b=0，則甲向乙發(fā)送r。如果b=1，則甲向乙發(fā)送y=r*smodn；如果b=0，則乙驗(yàn)證x=r2modn，表明甲知道sqrt(x)。如果b=1,則乙驗(yàn)證x=y2*vmodn，表明甲知道sqrt(v-1)。以上為一次鑒定。該協(xié)議重復(fù)t次，直到乙相信甲知道s為止。甲能欺騙乙一次的機(jī)會(huì)為50%，能欺騙乙t次的機(jī)會(huì)為1/2t。甲永遠(yuǎn)不能重復(fù)使用一個(gè)r值。Feige-Fiat-Shamir身份驗(yàn)證體制：產(chǎn)生模n，為兩個(gè)大素?cái)?shù)的乘積。產(chǎn)生密鑰：選擇k個(gè)不同的數(shù)v1,v2,…,vk，其中各個(gè)vi為一個(gè)模n的二次剩余即存在x，x2

v(modn)，且vi-1存在。這串v1,v2,…,vk為公開密鑰。計(jì)算滿足si=sqrt(vi-1)modn的最小的si，這一串s1,s2,…,sk為秘密密鑰。協(xié)議：甲選擇一個(gè)隨機(jī)數(shù)r，r<n。計(jì)算x=r2modn，將x發(fā)送給乙；乙向甲發(fā)送一個(gè)隨機(jī)的k位串：b1,b2,…,bk；甲計(jì)算y=r*(s1b1*s2b2*…*skbk)modn，將y發(fā)送給乙；乙驗(yàn)證是否有x=y2*(v1b1*v2b2*…*vkbk)modn。甲乙將這個(gè)協(xié)議重復(fù)t次，每次用一個(gè)不同的隨機(jī)值r直到乙相信甲知道s1,s2,…,sk為止。甲能欺騙乙的機(jī)會(huì)為1/2kt。建議至少取k=5和t=4。舉例：設(shè)模n=35，k=4。公開密鑰：{4，11，16，29}，秘密密鑰：{3，4，9，8}。協(xié)議的一圈：甲選擇一個(gè)隨機(jī)數(shù)r=16，計(jì)算x=162mod35=11，將11發(fā)送給乙；乙向甲發(fā)送一個(gè)隨機(jī)的二進(jìn)制串：{1，1，0，1}；甲計(jì)算y=16*(31*41*90*81)mod35=31，將31發(fā)送給乙；乙驗(yàn)證是否有312*(41*111*160*291)mod35=11。5.6密鑰交換算法Diffie-Hellman點(diǎn)對點(diǎn)協(xié)議Shamir的三次通過協(xié)議加密的密鑰交換Diffie-Hellman是最早的公開密鑰算法用于分配密鑰，但不能用于加密和解密甲乙約定一個(gè)大素?cái)?shù)n和一個(gè)數(shù)g，g為模n的生成元。g，n公開，可以共享。協(xié)議：甲選擇一個(gè)隨機(jī)大整數(shù)x，并向乙發(fā)送：X=gxmodn乙選擇一個(gè)隨機(jī)大整數(shù)y，并向甲發(fā)送：Y=gymodn甲計(jì)算：k=Yxmodn乙計(jì)算：k’=Xymodnk=k’=gxymodn，為秘密的密鑰三方或多方的Diffie-Hellman體制Hughes不用交換密鑰的密鑰交換點(diǎn)對點(diǎn)協(xié)議甲產(chǎn)生一個(gè)隨機(jī)數(shù)x，將它發(fā)送給乙；乙產(chǎn)生一個(gè)隨機(jī)數(shù)y，用Diffie-Hellman協(xié)議計(jì)算基于x和y的共享密鑰k。乙對x和y簽名，并用k加密簽名。然后將簽名和y一起發(fā)送給甲：y,Ek(SB(x,y))；甲也計(jì)算k。將乙的消息的后面部分解密，并驗(yàn)證乙的簽名。然后對一個(gè)由x,y組成的消息簽名，并用共享密鑰對簽名進(jìn)行加密，再發(fā)送給乙：Ek(SA(x,y))；乙解密消息，并驗(yàn)證甲的簽名。Shamir的三次通過協(xié)議甲乙雙方不用交換任何秘密密鑰或公開密鑰就可安全通信一個(gè)可交換的對稱密碼：EA(EB(M))=EB(EA(