密碼學課件 公開密鑰密碼

密碼學導論IntroductiontoCryptology主講教師：李衛(wèi)海、胡紅鋼第8章公開密鑰密碼公開密鑰密碼RSA密碼其它公鑰密碼ElGamal密碼橢圓曲線密碼公開密鑰密碼RSA密碼其它公鑰密碼ElGamal密碼橢圓曲線密碼單向函數(shù)舉例公開密鑰密碼的設計關鍵：將單向函數(shù)構(gòu)造為單向陷門函數(shù)因數(shù)分解問題(IntegerFactorization)給定大素數(shù)p和q，求n=p×q,只要一次乘法給定n，求p和q，即為因數(shù)分解問題IF，最快方法需要T(n)=exp{c((lnn)1/3ln(lnn))2/3}次運算，其中c為大于1的正整數(shù)。離散對數(shù)問題(DiscreteLogarithmProblem)令素數(shù)p滿足p-1含有另一大質(zhì)數(shù)q(q整除p-1)，及一整數(shù)g,1<g<p-1。若給定整數(shù)x，求y=gxmodp是簡單的但是若給定p,g及y，求x，則為DLP問題，是困難的。背包問題(KnapsackProblem)給定有限個自然數(shù)序列集合B=(b1,b2,…bn)及二進制序列x=(x1,x2,…xn),xi∈(0,1),求S＝∑xibi最多只需n-1次加法；但若給定B和S，求x則非常困難。窮舉時有2n種可能，當n很大時為計算上不可行。RSA設計思路1977年，Rivest、Shamir、Adleman基于大數(shù)分解難題，提出RSA密碼體制RSA專利于2000年9月20日到期RSA算法滿足公開密鑰加密的要求，基本思路：找到適當?shù)膃,d,n，使得對所有m<n有medmodn=m對于所有m<n的值，要計算me和Cd是相對容易的在給定e和n時，計算出d是不可行的算法依據(jù)mp-1modp=1，mk(p-1)+1modp=med=k(p-1)+1?ed=1mod(p-1)p必須公開，由e計算d是容易的。不滿足公開密鑰條件mΦ(n)modn=1，mkΦ(n)+1modn=med=kΦ(n)+1?ed=1modΦ(n)n是公開的，但將n分解并計算Φ(n)是困難的RSA算法流程隨機選擇兩個秘密大質(zhì)數(shù)p和q計算公開模數(shù)n=p*q計算秘密的歐拉指數(shù)函數(shù)Φ(n)=(p-1)(q-1)選擇一個與Φ(n)互素的數(shù)，作為e計算e模Φ(n)的乘法逆元素，作為d公開密鑰PU={e,n}；私有密鑰PR={d,n}加密：C=memodn解密：m=Cdmodn=medmodn=m例：RSA，p=17,q=11,e=7，加密消息m=88并解密解：n=pq=17×11=187Φ(n)=(p-1)(q-1)=16×10=160gcd(7,160)=1,d=7-1mod

160=23公鑰PU={7,187}，私鑰PR={23,187}加密計算C=887mod187=11解密計算m=1123mod187=88實現(xiàn)方面的考慮前面已證明，當m是p或q的倍數(shù)時，仍可以正確加解密m不能是0、±1，否則密文就是明文（e必為奇數(shù)）加密與解密模指數(shù)運算，可通過下面兩個手段減少運算量模運算特性[(amodn)op(bmodn)]modn=(aopb)modn快速指數(shù)算法公鑰的有效運算e常選65537(即216+1)：僅有兩個比特為1，乘法次數(shù)最小應用中也可以先選擇e，再選擇p,q。為保證gcd(e,Φ(n))=1，選擇p,q時應保證gcd(e,p-1)=gcd(e,q-1)=1實現(xiàn)方面的考慮：小公鑰的危險e有時也選3或17。但過小的e可能受到攻擊例如：假設有三個用戶的e都選擇3，但模數(shù)分別為n1,n2,n3若要向他們發(fā)送m，密文分別為

C1=m3

modn1,C2=m3modn2,C3=m3modn3各用戶的素數(shù)是隨機生成的，因此模數(shù)n1,n2,n3兩兩互素的可能很大由中國剩余定理可以計算C=CRT(n1,n2,n3,C1,C2,C3)顯然有C=m3modn1n2n3由RSA算法規(guī)則，m<ni，

因此m3<n1n2n3因而可以直接計算m=C1/3實現(xiàn)方面的考慮：共模攻擊為簡化問題，可能會給多個用戶分配相同的n（p和q由密鑰管理中心保管，不公開），但給不同用戶分配不同的e和d若明文m用不同的公鑰e1,e2加密，公共模數(shù)為n則密文c1=me1(modn),c2=me2(modn)不同用戶的指數(shù)e往往是互素的，由擴展歐幾里德算法可以找到r和s，滿足re1+se2=1有c1r

c2s=mre1+se2=mr和s必有一個是負數(shù)，不妨設是r，則(c1-1)-r

c2s=m不應使用公共的模數(shù)n實現(xiàn)方面的考慮私鑰d應不小于1/3n1/4若d<1/3n1/4，則可以用Wiener攻擊在多項式時間內(nèi)分解n“CryptanalysisofshortRSAsecretexponents”,1990私鑰的有效運算運用中國剩余定理簡化運算：求m=Cdmodn計算：Xp=q×(q-1modp),Xq=p×(p-1modq)定義：Vp=Cdmodp=Cdmod(p-1)modp Vq=Cdmodq=Cdmod(q-1)modq則m=CRT(n,p,q,Vp,Vq)=(VpXp+VqXq)modn比直接運算m=Cdmodn快4倍RSA的安全性四種潛在的攻擊方法窮舉攻擊：嘗試所有可能的密鑰數(shù)學攻擊：對兩個素數(shù)乘積的因子分解(IF問題)計時攻擊：依賴于解密算法的運行時間選擇密文攻擊：利用了RSA體制的性質(zhì)數(shù)學攻擊數(shù)學攻擊：分解n為兩個素數(shù)p,q，并進而求出d主要的大數(shù)分解算法二次篩選法一般數(shù)域篩選法對116位以上的大數(shù)分解比二次篩

選法快得多特殊數(shù)域篩選法分解一些特殊形式的數(shù)數(shù)學攻擊RSA的安全性問題依賴于大合數(shù)的素因子分解，即FactorizationProblem(IF)2005年分解了200位十進制（約664bits）大合數(shù)2009年分解了232位十進制（768bits）大合數(shù)（數(shù)百臺設備運行2年）p、q應選取1024或2048位數(shù)學攻擊選擇適當?shù)拇笏財?shù)，避免被已知方法分解大素數(shù)應該是隨機的，且不包含在素數(shù)表中查表或遍歷特殊形式的素數(shù)總是容易的選擇強素數(shù)，素數(shù)p應滿足：p-1有一個大的素因子rp+1有一個大的素因子r-1有一個大的素因子p和q大小不能太接近否則p和q接近n1/2，容易被窮舉攻擊選擇p和q在長度上有幾個比特差異是可行的(p-1)和(q-1)都應有一個不相等的大素因子可能存在基于重復加密的攻擊：ce,(ce)e,…若cet≡c

(modn)，則cet-1≡m(modn)，即met-1=m(modn)當(p-1)和(q-1)都有一個不相等的大素因子時，這種攻擊可以忽略GCD(p-1,q-1)應該較小計時攻擊計時攻擊依據(jù)加密或解密算法對于不同輸入所花的時間上的細微差別，進行分析類似通過觀察轉(zhuǎn)動老式電話撥號盤的時間長短來猜測密碼可能的解決辦法快速指數(shù)算法也會泄露部分信息不變的冪運行時間，可能會降低性能在求冪運算中加入隨機延時干擾：在執(zhí)行冪運算之前先將密文乘上一個隨機數(shù)RSA數(shù)據(jù)安全公司在產(chǎn)品中實現(xiàn)M=Cdmodn的過程：產(chǎn)生0～n-1之間的秘密隨機數(shù)s計算C'=C×(se)modn,e是公開的指數(shù)計算M'=(C')dmodn計算M=M's-1modn,其中s-1是r模n的乘法逆元通過s來干擾運算中的耗時，同一個密文解密時間也會發(fā)生變化明文分解的中間相遇攻擊

選擇密文攻擊對RSA算法，有E(PU,M1)×E(PU,M2)=E(PU,M1×M2)若有密文C=Memodn，則攻擊過程如下：選取隨機數(shù)s計算X=(C×se)modn=(Ms)emodn誘使用戶解密X，并返回Y=Xdmodn=(Ms)modn攻擊者計算M=Ys-1

modn封裝攻擊：攻擊者做為協(xié)議參與一方，將他所需要的消息封裝為合法消息的一部分，誘使另一方解密、簽名等。例如：“我用你的公鑰加密了一個隨機數(shù)，你解密發(fā)還給我，來證實你的身份”永遠不要對一個陌生人提交的隨機文件直接進行私鑰運算（數(shù)字簽名）可以在加密之前對明文隨機填充最優(yōu)非對稱加密填充OAEP，使明文符合一定規(guī)則，解密后可以檢驗消息的合法性對于不符合格式的消息，拒絕給出解密結(jié)果乘法同態(tài)最優(yōu)非對稱加密填充M消息；L可選的標簽公開密鑰密碼RSA密碼其它公鑰密碼ElGamal密碼橢圓曲線密碼離散對數(shù)密碼示例離散對數(shù)密碼例：Pohlig-HellmanScheme加密：C=MemodP解密：M=Cd=(Me)dmodPedmodΦ(P)

=1，P為大素數(shù)，Φ(P)為歐拉函數(shù)因為P是素數(shù)，Φ(P)容易獲得，因此e和d都需要保密顯然，并非公開密鑰密碼ElGamal密碼屬于離散對數(shù)密碼體制安全性基于DLP問題ElGamal密碼算法公共模數(shù)素數(shù)P，本原元素α，私鑰x，公鑰Y=αxmodP加密，消息1≤m≤P-1：A隨機選擇k∈(1,P-1)A訪問公共區(qū)域獲取B的公鑰YB=αxBmodP。計算： K=(YB)kmodP，即K=αxBkmodP c1=αkmodP，c2=mKmodP密文即為(c1,c2)解密：B首先恢復K：K=c1xBmodP=αkxBmodP然后恢復m：m=c2/KmodP=c2K-1modPElGamal密碼體制是概率密碼體制，相同明文每次加密得到不同的密文加密效率是50％，因為密文大小是明文的兩倍例：P=17,α=3,xA=2,xB=5,AB:m=11公鑰計算：YB=αxBmodP=35mod17=5加密：A選擇k=7K=(YB)kmodP=57mod17=10c1=αkmodP=37mod17=11c2=mKmodP=11×10mod17=8所以，密文C=(c1,c2)=(11,8)解密：K=c1xBmodP=115mod17=10K-1modP=10-1mod17=12m=c2K-1modP=8×12mod17=11實現(xiàn)方面的考慮特別注意，k不能重復使用，如果 (1)c1,1=αkmodP c2,1=m1KmodP (2)c1,2=αkmodP c2,2=m2KmodP

得m1/m2=c2,1/c2,2modP

如果m1已知，m2即可算出公開密鑰密碼RSA密碼其它公鑰密碼ElGamal密碼橢圓曲線密碼橢圓曲線密碼ECCECC與RSA的對比ECC中的加法運算與RSA中的乘法運算相對應ECC中的數(shù)乘運算與RSA中的模冪運算相對應同等密碼強度下，ECC所需密鑰量和計算量都小于RSA算法同等密鑰長度下，ECC計算量與RSA相當給定曲線y2=x3+ax+bmodp以及其上一點P，我們可以通過連續(xù)自加k-1次計算Q=kP存在與快速指數(shù)運算類似的快速算法問題：當Q已知時能否計算k?這是一個被稱為橢圓曲線離散對數(shù)的難題“Pollardrho方法”是目前最快的方法橢圓曲線公鑰系統(tǒng)橢圓曲線公鑰密碼系統(tǒng)域標識GF(p)：定義橢圓曲線采用的有限域橢圓曲線E(a,b)：系數(shù)a和b基準點(base)G：指定的橢圓曲線上的一點階(order):G點的階N，使得：NG=O選擇正整數(shù)e作為私有密鑰公開密鑰為Q=eGMenozes-Vanstone橢圓曲線密碼利用ECC實現(xiàn)加/解密的技術有多種Menozes-Vanstone是其中一種令E是GF(p)上的橢圓曲線，選取基點G，階為N私鑰：e<N公鑰：E，GF(p)，Q=eG加密：明文m=(x1,x2)，x1,x2<p任取v<N，vQ=(c1,c2)密文(y0,y1,y2)，y0=vG,y1=c1x1

modp,y2=c2x2modp解密：用私鑰e計算：ey0=evG=vQ=(c1,c2)m=(x1,x2)=(y1c1-1modp,y2c2-1modp)ElGamal算法在橢圓曲線上實現(xiàn)E(a,b)，基點G∈EB選擇a并保密,0<a<N，N為G的階(order)，公鑰為aGA向B發(fā)送消息m:

A將m嵌入點Pm，選擇隨機數(shù)k,

AB(kG,Pm+k(aG))B：Pm=(Pm+k(aG))–a(kG)一種將消息m映射到點Pm的算法編碼：將域p劃分為長256的小段對明文進行分組：使得每個分組0≤m≤

p/256

對明文分組進行編碼，使之成為由域參數(shù)給出的橢圓曲線上的點Pm在256m≤x<256(m+1)中找到一個x，使得橢圓曲線方程有解一般地，對所有的滿足256m≤x<256(m+l)的x，橢圓曲線方程都無解的概率是很小的。從而可以完成編碼。解碼：若解密橫坐標落在256m≤x<256(m+1)中，則解碼為m0123402565127681024xmMassey-Omura公鑰體制不需要交換公鑰。GF(q)上用戶A加密、解密密鑰：eA,dA

gcd(eA,q-1)=1,eAdA=1mod(q-1)用戶B加密、解密密鑰：eB,dB

gcd(eB,q-1)=1,eBdB=1mod(q-1)A將消息m發(fā)送給BABmeAmeAeB(meAeB)dA=meBB:

(

meB)dB=mE(a,b)上m編碼為橢圓曲線上的點PmN:橢圓曲線上的點數(shù)用戶隨機選擇e:1<e<N,gcd(e,N)=1,ed=1modNA將消息m發(fā)送給B：A將m嵌入點PmABeAPmB:dB(eBPm)=PmeBeAPmdA(eBeAPm)=eBPm公開密鑰密碼RSA密碼其它公鑰密碼ElGamal密碼橢圓曲線密碼Rabin密碼人們相信破譯RSA密碼和大數(shù)分解問題同等困難，但缺乏嚴格的證明Rabin密碼是第一個證明了的安全公鑰加密方案破譯它和大數(shù)分解問題同等困難密鑰生成：隨機生成兩個不同但大小相近的大素數(shù)p和q計算n=pq（p和q模4余3時，利于計算）公鑰為n，私鑰為(p,q)加密：B為A加密消息將消息分組表示成{0,1,…,n-1}中的整數(shù)m，n是A的公鑰計算c=m2modn作為密文解密：求解c的四個平方根從四個平方根中選取正確的一個Rabin密碼的安全性安全性n的因子分解問題和計算模n的平方根在計算上是等價的，因此破譯Rabin算法與大數(shù)分解是同等困難的不能抵抗選擇密文攻擊敵手隨機選擇x，計算c=x2modn提交c去正常解密，得到明文y此時有1/2的幾率使得gcd(x+y,n)就是n的一個素因子冗余方案：加密前一般在m中嵌入冗余，據(jù)此從四個解中選擇正確的解。若四個解中均無特定冗余，則拒絕返回答案使用冗余方案時的安全性：若敵手在x中嵌入了冗余，則解密器會以極大的概率返回x（其它三個平方根不大可能也碰巧具有該冗余）。此時破譯攻擊失敗若敵手在x中不嵌入冗余，則解密器會以極大的概率拒絕接受密文。此時破譯攻擊失敗可以抵抗選擇密文攻擊gcd(z1＋z1,n)=？gcd(z1＋z2,n)=qgcd(z1＋z3,n)=pgcd(z1＋z4,n)=n背包公鑰加密背包公鑰加密基于子集和問題基本思想：選擇一個容易求解的子集和問題實例（私鑰），然后將它偽裝成一個很難求解的一般子集和問題實例（公鑰）Merkle-Hellman背包加密方案是第一個具體實現(xiàn)了的公鑰加密方案有著重要的歷史意義已有一個攻擊它的多項式時間算法超遞增序列超遞增序列(b1,b2,…,bn)是一個正整數(shù)序列，其中每個元素都大于前面所有元素之和求解超遞增序列子集和問題輸入(b1,b2,…,bn)，整數(shù)s輸出(x1,x2,…,xn)，其中xi=1表示選中bii=n當i≥

1時，執(zhí)行若s≥bi，則xi=1,s=s

-bi。否則xi=0i=i-1返回(x1,x2,…,xn)Merkle-Hellman背包加密公/私鑰生成：公共參數(shù)n選擇一個超遞增序列(b1,b2,…,bn)和模數(shù)M，使得M>sum(bi)隨機選擇一個整數(shù)W，1≤W≤M-1，gcd(W,M)=1隨機選擇整數(shù){1,2,…,n}的一個置換π計算ai=Wbπ(i)modM,i=1,2,…,n公鑰為(a1,a2,…,an)，私鑰為(π,M,W,(b1,b2,…,bn))加密：消息m將消息表示為二進制串，m=m1,m2,…,mn計算c=m1a1+m2a2+…+mnan，作為密文解密：計算d=W-1cmodM求滿足d=r1b1+r2b2+…+rnbn的二進制數(shù)r1,r2,…,rn消息比特是mi=rπ(i),i=1,2,…,n概率公鑰密碼確定性的密碼體制存在缺點：密碼體制對消息空間的所有概率分布未必是安全的例如：RSA中，消息0或1總是加密成其本身同一消息發(fā)送兩次時，密文重復，容易被檢測有利于密碼分析概率密碼利用隨機性得到一個可證的高強度安全性在對稱密碼體制中實現(xiàn)概率密碼:在消息中嵌入隨機數(shù)通過可逆變換使得該隨機數(shù)影響到所有比特位加密Blum-Goldwasser概率加密是已知的最有效的概率加密方案在速度和消息擴展方面可以與RSA相比若大數(shù)分解是困難的，則它是理想安全的易受選擇密文攻擊，在實際應用中受限密鑰生成：隨機選擇兩個大素數(shù)p,q，p≡q≡3mod4計算n=pq用擴展歐幾里得算法計算整數(shù)a和b，使得ap+bq=1公鑰是n，私鑰是(p,q,a,b)Blum-Goldwasser概率密碼加密：n為接收方公鑰令k=

log2n

,h=

log2k，將消息表示為長度為t的串m=m1m2…mt，其中mi是長度為h的二進制串

//用BBS生成器產(chǎn)生密鑰流加密m隨機選擇r，并計算x0=r2modn對i=1…t執(zhí)行：計算xi=xi-12modn記pi為xi的最低h位比特計算ci=pi⊕mi計算xt+1=xt2modn發(fā)送密文c=(c1,c2,…,ct,xt+1)Blum-Goldwasser概率密碼解密：計算d1=((p+1)/4)t+1mod(p-1)計算d2=((q+1)/4)t+1mod(q-1)計算u=xt+1d1modp,v=xt+1d2modq計算x0=vap+ubqmodn對于i=1…t，執(zhí)行計算xi=xi-12

modn記pi為xi的最低h位比特計算mi=pi⊕ci解密的證明：注意到xt+1(p+1)/4modp=xt重復計算t+1次，u≡xt+1d1≡x0(modp)同理v≡x0(modq)∵ap+bq=1∴vap+ubq≡x0(modp),vap+ubq≡x0(modq)∴x0=vap+ubq(modn)x0解出，即可逐個恢復明文SM2橢圓曲線公鑰密碼

SM2橢圓曲線公鑰密碼私鑰：1<d<n-1公鑰：P=dGS=hP，h為余因子，是橢圓曲線上所有點的個數(shù)與n相除的整數(shù)部分若S是無窮遠點，則需要重新設置私鑰加密算法：消息為m，len為m的長度隨機選取k，1<k<n-1C1=kG