【文章內(nèi)容簡介】 了基本介紹，密鑰流的生成是密碼有效性的關(guān)鍵。目前密鑰流生成器多為用第四章 公鑰密碼體制 公鑰密碼體制概述 指數(shù)加密算法 背包算法 RSA算法 橢圓曲線密碼算法 概率加密 小結(jié) 公鑰密碼體制概述 （ 1）密鑰加密 （ 2）公鑰加密 （ 3）單項函數(shù) 公鑰加密技術(shù)的主要思想 :在公鑰加密技術(shù)中 ,有一對密鑰 :一個私鑰和一個公鑰。一個密鑰鎖上的公鑰用另一個私鑰可以打開。其方法是如果發(fā)送方要發(fā)送一個加密的信息，應(yīng)先得到公鑰的一個副本，然后用它加密信息。但接收方收到這個消息時，用自己的私鑰解密。公鑰密碼體制有五個組成部分： （ 1）明文 （ 2）加密算法 （ 3）公鑰和私鑰 （ 4）密文 （ 5）解密算法 公鑰密碼體制實現(xiàn)的關(guān)鍵問題是如何確定公鑰和私鑰及加密、解密的算法。 指數(shù)加密算法 這種密碼本身并不是公鑰系統(tǒng)，而是為介紹一種重要的 公鑰作準(zhǔn)備。假如 p是一大素數(shù)， e是與 p1互素的正整數(shù)。令 26個英文字母對應(yīng)于 0到 25的整數(shù)，即 a00 b01 c02 d03 e04 f05 g06 h07 i08 j09 k10 l11 m12 n13 o14 p15 q16 r17 s18 t19 u20 v21 w22 x23 y24 z25 在對明文加密之前，先將要發(fā)送的信息字母數(shù)字化成數(shù)字串。取個數(shù)字（即個字母）構(gòu)成一組作為明文塊，表示以加密時做的冪運算： c=me mod p, o≤cp (e,p1)=1 例如， p=2633,e=29,明文 M=public key RS A 先將 M=pu bl ic ke yr sa數(shù)字化得 1520 0111 0802 1004 2417 1800 若明文長度為奇數(shù)，可以補上一空字母?，F(xiàn)將它按下面公式 c=m29 mod 2633 加密得密文 0104 0676 0244 2619 1411 2135 要解密需要獲得解密的密鑰 d，使得 de≡1 mod (p1) 由于 e和 p1互素，所以必存在整數(shù) b和 d，使得 deb(p1)=1 de≡1 mod (p1) 從而 cd=(me)d=med=mb(p1)+1 =[(m)p1]bm =m mod p 這里用到 Fermat定理： mp1≡1 mod p 在本例中， e=29， p=2633， d=2269。 求解的 xr mod p快速算法流程圖如圖 41所示。 （ 1） a←2,b←22,c←1。 （ 2）由 b≡0 mod 2, 得 b←11,a←2 2(即 a←4)。 （ 3）由 11≡1 mod 2, 得 b←10,c←4。 （ 4）由 b=10≡0 mod 2, 得 b←5,a←4 2 mod 11(即 a←5)。 （ 5）由 5≡1 mod 2, 得 b←4,c←54 mod 11(c←9)。 （ 6）由 b=4≡0 mod 2, 得 b←2,a←5 2 mod 11(a←3)。 （ 7）由 b≡0 mod 2, 得 b←1,a←9?！　　。ǎ福?b←0,c←99 mod 11, 即 c←4 。變量初始化a=x,b=r,c=1b=b1c=c*a mod pNb=b/2a=a*a mod p圖４ １　 xp mod p 快速算法流程圖b=0?輸出 cYb mod 2=0?N 背包算法 這種密碼系統(tǒng)的設(shè)計是基于有名的背包問題：設(shè)有長為 i的 背包，一組直徑相同的圓盤共 n個，其厚度分別為 a1, a2,…,a n。 問能否從中選取一部分盤子，正好裝滿這背包，如果能，應(yīng)如何做，這問題導(dǎo)致由已知 b求解 a1x1+a2x2+…+a nxn=b xi=0 或 1,i=1,2, … ,n 目前還沒有有效的算法，且已證明屬于 NP完全題。取 a=(a1,a2, …,a n)作為加密密鑰加以公開。信息 m設(shè)為 n比特的二進制數(shù) m1m2 … mn。發(fā)送的密文 c為 c=a1x1+a2x2+…+a nxn 對方接收到的是一組數(shù) c1,c2, …,c n從已知的公開的加密密鑰（a1,a2, …,a n）及密文 c，要解出明文 m1m2…m n相當(dāng)于一個背包問題?！　　∩鲜鱿到y(tǒng)的安全性取決于解背包問題的困難程度。例如，　　　 a=(28 32 11 08 71 51 43 67) m1=0 1 0 0 1 1 0 1 m2=1 1 0 1 0 1 1 0 m3=1 1 1 0 0 0 1 0 可加密得　　　　 c1=32+71+51+67=221 c2=28+32+08+51+43=162 c3=28+32+11+43=114 于是得一組密文： 221， 162， 114， … 。　　　第三者無法從收到的這些密文推出 m1,m2,m3,… 。對于特殊的一組 a1,a2, …,a n若滿足條件： ai∑a i,j=2,3, …,n 則求解要容易得多。滿足上面條件的序列 a1, a2, …, a 2n 稱為超遞增序列。例如 2,4,9,17,36 　　　　　　　　 j1i=1 便是超遞增序列，因 42,92+4,172+4+9,362+4+9+17 對于超遞增序列 2,4,9,17,36求解 2x1+4x2+9x3+17x4+36x5=59 故必有 x5=1。這樣 2x1+4x2+9x3+17x4=23 而 2+4+9=15＜ 23 故 x4=1 從而 2x1=4x2+9x3=6 又因 9＞ 6，故必有 x3=0 2x1=4x2=6， x2=x1=1 最后解得 x1=1， x2=1， x3=0， x4=1， x5=1 或?qū)憺? x1x2x3x4x5=11011 一般來說，對于滿足不等式 aj∑a j,j=2,3, …,n 的超遞增序列 a1， a2， …,a n，解 ax1x1=a2x2+…+a nxn=b比較容易。首先 xn={ 因若 b≥a n時， xn=0，則 ∑a ixi≤∑a i＜ an≤b 與要求 ∑a ixi=b相矛盾。一般有 i=1j11，0，若 b≥a n若 b＜ ani=1ni=1ni=1 1, 若 b ∑a ixi≥a ini=j+10, 若 b ∑a ixi＜ aini=j+1Xj={ 因若 b∑a ixi≥a i時， xi=0，則 ∑a ixi≤∑a i+∑a ixi＜ aj +∑a ixi≤b 導(dǎo)致矛盾。 當(dāng)然，不能采用超遞增序列本身作為公鑰予以公開，因為對方截獲了密文也同樣容易破譯得到明文。設(shè)法將超遞增序列轉(zhuǎn)換成足夠復(fù)雜的序列，將后者公開。而真正的接收者可以通過該變換的逆變換將它還原為超遞增序列的形式，從而求出解。第三者無法知道變換及其逆變換，在多項式的時間內(nèi)也無法導(dǎo)出這種變換。i=j+1nn ni=1i=j+1ni=j+1ni=j+1 RSA算法 （ 1） 任意選取兩個不同的大質(zhì)數(shù) p和 q，計算乘機 r= pq （ 2）任意選取一個大整數(shù) e, e與 (p1)(q1)互質(zhì)，整數(shù) e用做加密密鑰 （ 3）確定解密密鑰 d: ed ≡1 mod (p1)(q1) 根據(jù) e 、 p 和 q 可以容易地計算出 d=e1 mod (p1)(q1) （ 4）公開整數(shù) r和 e, r和 e是公開密鑰，但是不公開 d是私人密鑰 （ 5）將明文 p（假設(shè) p 是一個小于 r 的整數(shù)）加密為密文 C,計算方法為： C=Pe(mod r) （ 6）將密文 C解密為明文 P，計算方法為： P=Cd(mod r) 然而只根據(jù) r和 e（不是 p和 q）要計算出 d是不可能的。因此，任何人都可對明文進行加密，但只有授權(quán)用戶（知道 d）才可對密文解密。 RSA的安全性依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因為沒有證明破解 RSA就一定需要做大數(shù)分解。 由于進行的都是大數(shù)計算 ,使得 RSA最快的情況也比 DES慢上 100倍 ,無論是軟件還是硬件實現(xiàn)。一般來說只用于少量數(shù)據(jù)加密。 RSA在選擇密文攻擊面前很脆弱。這個固有的問題來自于公鑰密碼系統(tǒng)的最有用的特征 — 每個人都能使用公鑰。 若系統(tǒng)中有一個模數(shù) ,只是不同的人擁有不同的 e和 d,系統(tǒng)將是危險的。 橢圓曲線密碼算法 目前，橢圓曲線密碼體制是公認的比較安全實用的公鑰密碼體制。其基本思想是在基于有限域的橢圓曲線上對信息進行加密解密。 橢圓曲線密碼體制來源于對橢圓曲線的研究，所謂橢圓曲線指的是由 Weierstrass方程： 設(shè) k表示一個有限域 E是域 k上的橢圓曲線，則 E是一個點的集合 E/k={(x,y)|y2+a1xy+a3y=x3+a2x2+a4x+a6,x,y,k}{0} 其中， 0表示無窮遠點所確定的平面曲線。其中系數(shù) ai(i=1,2,…,6)定義在某個域上，可以是有理數(shù)域、實數(shù)域、復(fù)數(shù)域，還可以是有限域 GF（ pr)，橢圓曲線密碼體制中用到的橢圓曲線都是定義在有限域上的。 橢圓曲線上所有的點外加一個叫做無窮遠點的特殊點構(gòu)成一個集合，再連同一個定義的加法運算構(gòu)成一個 Abel群。在等式 mP=P+P+…+P=Q 中，已知 m和點 P求點 Q比較容易，反之，已知點 Q和點 P求 m卻是相當(dāng) 困難的，這個問題稱為橢圓曲線上點群的離散對數(shù)問題。橢圓曲線密碼體制正是利用這個困難問題設(shè)計而來。橢圓曲線應(yīng)用到密碼學(xué)上最早是由 Neal Koblitz和 Victor Miller在 1985年分別獨立提出來的。 橢圓曲線上的離散對數(shù)，可以認為是：給定有限域 Fq(q=pr為素數(shù)冪)上的一條橢圓曲線 y2=x3+ax+b，并給定這條曲線上的兩點 P和 Q，求出正整數(shù) C（如果存在），使之滿足 Q=kP，目前關(guān)于橢圓曲線離散對數(shù)問題還沒有找到一種甚至是子指數(shù)復(fù)雜性的算法（對于整數(shù)分解與離散對數(shù)，已有子指數(shù)復(fù)雜性的算法）。 尋求快速實用的計算橢圓曲線離散對數(shù)的算法是當(dāng)前計算數(shù)論中的一項研究課題。 在 ECC中，關(guān)心的是某種形式的橢圓曲線，即定義在有限域上的橢圓曲線。其方程是： y2≡x 3+ax+b(mod p) （ 1） 這里 p是素數(shù)， a和 b為兩個小于 p的非負整數(shù)，它們滿足： 4a3+27b2(mod p)≠0 滿足方程（ 1）的橢圓曲線如圖 42所示。 用 E