古典算法復(fù)習(xí)課概要課件

數(shù)據(jù)加密與PKI技術(shù)

第11周

數(shù)據(jù)加密涉及算法復(fù)習(xí)課

2022/11/111

數(shù)據(jù)加密與PKI技術(shù)

第11周數(shù)據(jù)學(xué)習(xí)目標(biāo)理解凱撒密碼與Playfair等古典替換密碼掌握DES加密中的IP置換與S盒變換掌握歐幾里德最大公因子算法靈活運用費馬定理與歐拉定理理解RSA加解密算法理解背包密碼體制掌握Diffie—Hellman密鑰交換計算理解Elgamal算法與DSA算法2022/11/112學(xué)習(xí)目標(biāo)理解凱撒密碼與Playfair等古典替換密碼2022古典密碼學(xué)作業(yè)1、愷撒與安東尼要舉行一個秘密會議，他寫了一個密信“ULEHU”,請問地點在什么地方？并寫出推導(dǎo)出它的數(shù)學(xué)求解式。（寫一個就可以了）答：M=C-K（mod26），M=20-3（mod26）=17=R，同理其他字母可解。明文：RIBER2、截獲了一封密信，已知是愷撒變形密信，并知道了兩對明文和相應(yīng)的密文字母，求解K？并寫出數(shù)學(xué)求解式。明文是:vy，密文是AD.答：k=c-m（mod26），k=0-21（mod26）=5。3、用playfair密碼加密：Iseeaplane！這句話，密鑰就是playfair。答：先將明文兩個字母分一組，isexeaplanex，

C=cnkuhplapqku4、用Vigenère密碼加密hereishowitw.這些字母，密鑰是（V-21，E-4，C-2，T-19，O-14，R-17）。（注意全部忽略空格和標(biāo)點符號）答：根據(jù)規(guī)則將密鑰重復(fù)，每個字母相當(dāng)于凱撒加密，C=citxwjcsybtn2022/11/113古典密碼學(xué)作業(yè)1、愷撒與安東尼要舉行一個秘密會議，他寫了一個Caesar密碼表例2．1

愷撒（Caesar）密碼是k＝3的情況。即通過簡單的向右移動源字母表3個字母則形成如下代換字母表若明文為：pleaseconfirmreceipt則密文為：SOHDVEFRQILUPUHFHLSWM:a0b1c2d3e4f5g6h7i8j9k10l11m12C:DEFGHIJKLMNOPn13o14p15q16r17s18t19u20v21w22x23y24z25QRSTUVWXYZABC2022/11/114Caesar密碼表例2．1愷撒（Caesar）密碼是k＝3Playfair密碼體制Playfair密碼表

playfirbcdeghkmnoqstuvwxz1234512345該密碼體制的密鑰是一個單詞，比如playfair，將單詞中后面重復(fù)的字母去掉，只保留不相同的字母，得到playfir，將剩下的字母排列成5×5矩陣的起始部分，矩陣的剩余部分則用26個字母表中未出現(xiàn)的字母填充，并將i與j作為一個字母對待（原因？）2022/11/115Playfair密碼體制Playfair密碼表playfir各種各樣的移位密碼是在16世紀(jì)發(fā)明的，它們大多數(shù)來自于Vigenère方法，它是法國密碼學(xué)家維吉尼亞于1586年提出一種多表替換密碼,但是就加密性而言，Vigenère密碼體制更復(fù)雜和高級，直到20世紀(jì)初，這種加密體制在很多地方仍然被認(rèn)為是安全的，雖然早在19世紀(jì)，Babbage和Kasiski就展示了如何攻擊它們。在1920年，由Fridman開發(fā)了另外一種加密方法，打破了Vigenère及其相關(guān)的密碼方法。第一步：這個加密的密鑰是一個向量，按如下方式選擇。首先，確定一個密鑰長度，如6，然后從0～25個整數(shù)中選擇元素項滿足這個長度的向量，如k＝（21，4，2，19，14，17），將其稱為向量。這樣，系統(tǒng)的安全性所依賴的就是既不能知道密鑰內(nèi)容也不能得知其長度。

Vigenère密碼2022/11/116各種各樣的移位密碼是在16世紀(jì)發(fā)明的，它們大多數(shù)來自Vigenère密碼第二步：下面所舉的例子就是利用k來加密信息，首先，取明文的第1個字母并將之移21位，然后將第2個字母移4位，第3個字母移2位等等，一旦得到了密鑰的結(jié)尾，又從頭開始，這樣第7個字母又移位21位，第8個字母移4位等等，加密過程的密碼流程表如下：（明文）hereishowitworks(密鑰)21421914172142191417214219（密文）CITXWJCSYBHNJVML

這樣對于這么一段明文就可以用Vigenère完全進(jìn)行加密了，注意這里沒有一個字母的頻率比其他大很多，這是因為e在加密的過程中擴(kuò)散成了幾個字母的緣故。

2022/11/117Vigenère密碼第二步：下面所舉的例子就是利用k來加密信其中Mi是二元數(shù)字，為：

M58M50M42M34M26M18M10M2 M60M52M44M36M28M20M12M4 M62M54M46M38M30M22M14M6 M64M56M48M40M32M24M16M8 M57M49M41M33M25M17M9M1 M59M51M43M35M27M19M11M3 M61M53M45M37M29M21M13M5 M63M55M47M39M31M23M15M7如果再取逆初始置換Y=IP-1(X)=IP-1(IP(M))，可以看出，M各位的初始順序?qū)⒈换謴?fù)。2022/11/118其中Mi是二元數(shù)字，為：2022/11/108求IP逆置換例如求矩陣-1的逆。即為：4279186355281973642022/11/119求IP逆置換例如求矩陣-圖1函數(shù)F(R,K)的計算過程S盒變換2022/11/1110圖1函數(shù)F(R,K)的計算過程S盒變換2022/11/10F中的代換由8個S盒組成，每個S盒的輸入長為6比特、輸出長為4比特，其變換關(guān)系由表2.7定義，每個S盒給出了4個代換（由一個表的4行給出）。對每個盒Si，其6比特輸入中，第1個和第6個比特形成一個2位二進(jìn)制數(shù)，用來選擇Si的4個代換中的一個。6比特輸入中，中間4位用來選擇列。行和列選定后，得到其交叉位置的十進(jìn)制數(shù)，將這個數(shù)表示為4位二進(jìn)制數(shù)即得這一S盒的輸出。例如，S1

的輸入為011001，行選為01（即第1行），列選為1100（即第12列），行列交叉位置的數(shù)為9，其4位二進(jìn)制表示為1001，所以S1的輸出為1001。2022/11/1111F中的代換由8個S盒組成，每個S盒的輸入長為6比特、輸出長為費爾瑪定理和歐拉定理費爾瑪(Fermat)定理和歐拉(Euler)定理在公鑰密碼體制中起著重要作用。1.費爾瑪定理定理4.2(Fermat)若p是素數(shù)，a是正整數(shù)且gcd(a,p)=1，則ap-1≡1modp。Fermat定理也可寫成如下形式：設(shè)p是素數(shù)，a是任一正整數(shù)，則ap≡amodp。2022/11/1112費爾瑪定理和歐拉定理費爾瑪(Fermat)定理和歐拉(2.歐拉函數(shù)設(shè)n是一正整數(shù)，小于n且與n互素的正整數(shù)的個數(shù)稱為n的歐拉函數(shù)，記為φ(n)。例如：φ(6)=2，φ(7)=6，φ(8)=4。若n是素數(shù)，則顯然有φ(n)=n-1。例如：由21=3×7，得φ(21)=φ(3)×φ(7)=2×6=12。2022/11/11132.歐拉函數(shù)2022/11/1013定理4.3若n是兩個素數(shù)p和q的乘積，則φ(n)=φ(p)×φ(q)=(p-1)×(q-1)。3.歐拉定理定理4.4（Euler）若a和n互素，則aφ(n)≡1modn。2022/11/1114定理4.3若n是兩個素數(shù)p和q的乘積，則φ(n)=φ歐幾里得算法歐幾里得（Euclid）算法是數(shù)論中的一個基本技術(shù)，是求兩個正整數(shù)的最大公因子的簡化過程。而推廣的Euclid算法不僅可求兩個正整數(shù)的最大公因子，而且當(dāng)兩個正整數(shù)互素時，還可求出其中一個數(shù)關(guān)于另一個數(shù)的乘法逆元。2022/11/1115歐幾里得算法歐幾里得（Euclid）算法是數(shù)論中的一個基本技1.求最大公因子Euclid算法是基于下面一個基本結(jié)論：對任意非負(fù)整數(shù)a和正整數(shù)b，有g(shù)cd(a,b)=gcd(b,amodb)。例如：gcd(55,22)=gcd(22,55mod22)=gcd(22,11)=gcd(11,0)=11。在求兩個數(shù)的最大公因子時，可重復(fù)使用以上結(jié)論。例如：gcd(18,12)=gcd(12,6)=gcd(6,0)=6, gcd(11,10)=gcd(10,1)=gcd(1,0)=12022/11/11161.求最大公因子2022/11/1016例1求gcd(1970,1066)。1970=1×1066+904, gcd(1066,904)1066=1×904+162, gcd(904,162)904=5×162+94, gcd(162,94)162=1×94+68, gcd(94,68)94=1×68+26, gcd(68,26)68=2×26+16, gcd(26,16)26=1×16+10, gcd(16,10)16=1×10+6, gcd(10,6)10=1×6+4, gcd(6,4)6=1×4+2, gcd(4,2)4=2×2+0, gcd(2,0)因此gcd(1970,1066)=2。2022/11/1117例1求gcd(1970,1066)。2022/11/101.密鑰的產(chǎn)生①選兩個保密的大素數(shù)p和q(各100～200位十進(jìn)制數(shù)字)。②計算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的歐拉函數(shù)值。③選一整數(shù)e，滿足1<e<φ(n)，且gcd(φ(n),e)=1。④計算d，滿足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元，因e與φ(n)互素，由模運算可知，它的乘法逆元一定存在。⑤以{e,n}為公開鑰,{d,n}為秘密鑰。算法描述2022/11/11181.密鑰的產(chǎn)生算法描述2022/11/10182.加密加密時首先將明文比特串分組，使得每個分組對應(yīng)的十進(jìn)制數(shù)小于n，即分組長度小于log2n。然后對每個明文分組m，作加密運算：

c≡memodn3.解密對密文分組的解密運算為：

m≡cdmodn2022/11/11192.加密2022/11/1019例2：選p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，滿足1<e<φ(n)，且gcd(φ(n),e)=1。確定滿足d·e=1mod96且小于96的d，因為77×5=385=4×96+1，所以d為77，因此公開鑰為{5，119}，秘密鑰為{77，119}。設(shè)明文m=19，則由加密過程得密文為

c≡195mod119≡2476099mod119≡66解密為

6677mod119≡192022/11/1120例2：選p=7，q=17。求n=p×q=119，φ(n)=(例題3：已知明文m=14，pk=（3，55），求密文c和私鑰sk分別為多少？解：因為n=55=5*11，所以p=5（或11），q=11（或者5），（p-1）*（q-1）=40，

e*dmod40≡1，d=e-1=27C=memodn=143mod55=492022/11/1121例題3：已知明文m=14，pk=（3，55），求密文c

RSA算法中的計算問題1.RSA的加密與解密過程RSA的加密、解密過程都為求一個整數(shù)的整數(shù)次冪，再取模。如果按其含義直接計算，則中間結(jié)果非常大，有可能超出計算機(jī)所允許的整數(shù)取值范圍。如上例中解密運算6677mod119，先求6677再取模，則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超出了計算機(jī)允許的整數(shù)取值范圍。而用模運算的性質(zhì)：(a×b)modn=[(amodn)×(bmodn)]modn就可減小中間結(jié)果。2022/11/1122RSA算法中的計算問題1.RSA的加密與解密過程2022再者，考慮如何提高加、解密運算中指數(shù)運算的有效性。例如求x16，直接計算的話需做15次乘法。然而如果重復(fù)對每個部分結(jié)果做平方運算即求x，x2，x4，x8，x16則只需4次乘法。求am可如下進(jìn)行，其中a，m是正整數(shù)：將m表示為二進(jìn)制形式bkbk-1…b0，即m=bk2k+bk-12k-1+…+b12+b0因此2022/11/1123再者，考慮如何提高加、解密運算中指數(shù)運算的有效性。例如求x1例4求7560mod561。將560表示為1000110000，算法的中間結(jié)果如表所示。所以7560mod561=1。2022/11/1124例4求7560mod561。2022/11/1024背包密碼體制例5：A=(1,3,5,11,21,44,87,175,349,701)是一超遞增背包向量，取k=1590，t=43，gcd(43,1590)=1，得B=(43,129,215,473,903,302,561,1165,697,1523)。在得到B后，對明文分組x=(x1x2…xn)的加密運算為c=f(x)=B·Bx≡t·A·Bxmodk對單向函數(shù)f(x)，t、t-1和k可作為其秘密的陷門信息，即解密密鑰。解密時首先由s≡t-1cmodk，求出s作為超遞增背包向量A的容積，再解背包問題即得x=(x1x2…xn)。這是因為t-1cmodk≡t-1tABxmodk≡ABxmodk，而由k>∑ai，知ABx<k，所以t-1cmodk=ABx，是惟一的。2022/11/1125背包密碼體制例5：A=(1,3,5,11,21,4例6接例5，A=(1,3,5,11,21,44,87,175,349,701)是一超遞增背包向量，k=1590，t=43，得t-1≡37mod1590，設(shè)用戶收到的密文是(2942,3584,903,3326,215,2817,2629,819)，由37×2942≡734mod1590,37×3584≡638mod1590,37×903≡21mod1590,37×3326≡632mod1590,37×215≡5mod1590,37×2817≡879mod1590,37×2629≡283mod1590,37×819≡93mod1590,得(734,638,21,632,5,879,283,93)。2022/11/1126例6接例5，A=(1,3,5,11,21,44,取s=734，由734>701，得x10=1；令s=734-701=33，由33<349，得x9=0；重復(fù)該過程得第一個明文分組是1001100001，它對應(yīng)的英文文本是SA；類似地得其他明文分組，解密結(jié)果為SAUNAANDHEALTH。2022/11/1127取s=734，由734>701，得x10=1；令s=734-Diffie-Hellman密鑰交換是W.Diffie和M.Hellman于1976年提出的第一個公鑰密碼算法，已在很多商業(yè)產(chǎn)品中得以應(yīng)用。算法的惟一目的是使得兩個用戶能夠安全地交換密鑰，得到一個共享的會話密鑰，算法本身不能用于加、解密。算法的安全性基于求離散對數(shù)的困難性。Diffie-Hellman密鑰交換2022/11/1128Diffie-Hellman密鑰交換是W.Diffie和M圖2表示Diffie-Hellman密鑰交換過程，其中p是大素數(shù)，a是p的本原根，p和a作為公開的全程元素。用戶A選擇一保密的隨機(jī)整數(shù)XA，并將YA=aXAmodp發(fā)送給用戶B。類似地，用戶B選擇一保密的隨機(jī)整數(shù)XB，并將YB=aXBmodp發(fā)送給用戶A。然后A和B分別由K=(YB)XAmodp和K=(YA)XBmodp計算出的就是共享密鑰，這是因為(YB)XAmodp=(aXBmodp)XAmodp=(aXB)XAmodp=aXB

XAmodp=(aXA)XBmodp=(aXAmodp)XBmodp =(YA)XBmodp2022/11/1129圖2表示Diffie-Hellman密鑰交換過程，其中p是大圖2Diffie-Hellman密鑰交換2022/11/1130圖2Diffie-Hellman密鑰交換2022/11/1因XA，XB是保密的，敵手只能得到p，a，YA

，YB，要想得到K，則必須得到XA，XB中的一個，這意味著需要求離散對數(shù)。因此敵手求K是不可行的。例如：p=97，a=5，A和B分別秘密選XA=36，XB=58，并分別計算YA=536mod97=50，YB=558mod97=44。在交換YA，YB后，分別計算K=(YB)XAmod97=4436mod97=75,K=(YA)XBmod97=5058mod97=752022/11/1131因XA，XB是保密的，敵手只能得到p，a，YA，YB，要想Elgamal算法密鑰對產(chǎn)生辦法。首先選擇一個素數(shù)p，兩個隨機(jī)數(shù)，g和x，g與x<p，計算y=gx(modp)，則其公鑰為y,g和p。私鑰是x。其中g(shù)和p可由一組用戶共享。ElGamal用于數(shù)字簽名。被簽信息為M，首先選擇一個隨機(jī)數(shù)k,k與p-1互質(zhì)，計算

a=gk(modp)

再用擴(kuò)展Euclidean算法對下面方程求解b：

M=xa+kb(modp-1)

實際用

b=yk*Mmodp

簽名就是(a,b)。隨機(jī)數(shù)k須丟棄。

驗證時要驗證下式：

ya*ab(modp)=gM(modp)

同時一定要檢驗是否滿足1<=a<p。否則簽名容易偽造。2022/11/1132Elgamal算法密鑰對產(chǎn)生辦法。首先選擇一個素數(shù)p，兩個ElGamal用于加密被加密信息為M，首先選擇一個隨機(jī)數(shù)k，k與p-1互質(zhì)，計算

a=gk(modp)

b=ykM(modp)

(a,b)為密文，是明文的兩倍長。解密時計算

M=b/ax(modp)=b*（ax）-1modp

2022/11/1133ElGamal用于加密被加密信息為M，首先選擇一個隨機(jī)數(shù)k，例題：鮑勃把11選擇為p。然后他選擇g=e1=2。他再選擇x=d=3并且計算出y=e2=e1d=8。所以公鑰就是（g，y，p）=(2,8,11)，私鑰是x=3。愛麗絲選擇k=r=4并且計算出明文7的C1和C2。鮑勃收到密文c(a=5和b=6)并且計算出明文。

2022/11/1134例題：鮑勃把11選擇為p。然后他選擇g=e1=2。他再選我們不用P=[C2*(C1d)-1]modp解密，就可以避免乘法逆元的計算并且還可以運用P=[C2*C1（p-1-d）]modp。在例10.10中，我們可以算出P=[6*5（11-1-3）]mod11=7mod11。

2022/11/1135我們不用P=[C2*(C1d)-1]modp解DSA算法DigitalSignatureAlgorithm(DSA)是Schnorr和ElGamal簽名算法的變種，被美國NIST作為DSS(DigitalSignatureStandard)數(shù)字簽名標(biāo)準(zhǔn)，DSS是由美國國家標(biāo)準(zhǔn)化研究院和國家安全局共同開發(fā)的。由于它是由美國政府頒布實施的，主要用于與美國政府做生意的公司，其他公司則較少使用，而且美國政府不提倡使用任何削弱政府竊聽能力的加密軟件。算法中應(yīng)用了下述參數(shù)：

*p：Lbits長的素數(shù)。L是64的倍數(shù)，范圍是512到1024；

*q：是p-1的160bits的素因子；

*g：g=h^((p-1)/q)modp，h滿足h<p-1,h^((p-1)/q)modp>1；

*x：為秘密密鑰，正整數(shù)，x<q；

*y：y=g^xmodp，(p,q,g,y)為公鑰；

*k為隨機(jī)數(shù)，0〈k〈q；

*H(x)：One-WayHash函數(shù)。注："^"為冪運算符2022/11/1136DSA算法DigitalSignatureAlgorit簽名過程DSA中選用SHA(SecureHashAlgorithm)。p,q,g可由一組用戶共享，y是公開鑰，x是私鑰，簽名過程如下：

1.產(chǎn)生隨機(jī)數(shù)k，k<q；

2.計算r=(g^kmodp)modq

s=(k-1(H(m)+xr))modq

r，s即簽名結(jié)果。2022/11/1137簽名過程DSA中選用SHA(SecureHashAlg驗證過程驗證過程：簽名結(jié)果是(m,r,s)。

3.驗證時計算w=s-1modq

u1=(H(m)*w)modq

u2=(r*w)modq

v=((g^u1*y^u2)modp)modq

若v=r，則認(rèn)為簽名有效。驗證通過說明：簽名(r,s)有效，即(r,s,M)確為發(fā)送方的真實簽名結(jié)果，M未被竄改，為有效信息。驗證失敗說明：簽名(r,s)無效，即(r,s,M)不可靠，或者M(jìn)被竄改過，或者簽名是偽造的，M為無效信息。2022/11/1138驗證過程驗證過程：簽名結(jié)果是(m,r,s)。

3舉例如果對照我們CIW的教材：p=3011q=301g=α=114x=e=68h(m)=x=2310K=t=71y=β=1993r=γ=216s=δ=2e1=u1=252e2=u2=1082022/11/1139舉例如果對照我們CIW的教材：p=3011q=301思考題1.設(shè)通信雙方使用RSA加密體制，接收方的公開鑰是（e，n）=（5，35），接收到的密文是C=10，求明文M？2.設(shè)背包密碼系統(tǒng)的超遞增序列為（3，4，9，17，35），乘數(shù)t=19，模數(shù)k=73，試對goodnight加密。3.設(shè)背包密碼系統(tǒng)的超遞增序列為（3，4，8，17，35），乘數(shù)t=17，模數(shù)k=67，試對密文24，2，72，92解密。4.在Diffie-hellman密鑰交換中，p=11，a=2，（1）用戶A的公開鑰Ya=9，求私鑰Xa？（2）用戶B的公開鑰Yb=3，求共享密鑰K？2022/11/1140思考題2022/11/1040思考題：5.在ELGamal加密體制中，設(shè)素數(shù)p=71，本原根g=7，1）如果接收方b的公開鑰是y=3，發(fā)送方選中的隨機(jī)數(shù)k=2，求明文M=30所對應(yīng)的密文。2）如果發(fā)送方a選擇另外一個隨機(jī)數(shù)k，使得明文M=30加密后的密文是C=（59，c2），求c2。2022/11/1141思考題：2022/11/10416.已知ELGamal加密算法中，P=7，g=4，x=5，k=1，M=2，1)求出公鑰PK和私鑰SK的值；2）求出密文并驗證之。2022/11/11426.已知ELGamal加密算法中，P=7，g=4，x=5，謝謝！2022/11/1143謝謝！2022/11/1043

數(shù)據(jù)加密與PKI技術(shù)

第11周

數(shù)據(jù)加密涉及算法復(fù)習(xí)課

2022/11/1144

數(shù)據(jù)加密與PKI技術(shù)

第11周數(shù)據(jù)學(xué)習(xí)目標(biāo)理解凱撒密碼與Playfair等古典替換密碼掌握DES加密中的IP置換與S盒變換掌握歐幾里德最大公因子算法靈活運用費馬定理與歐拉定理理解RSA加解密算法理解背包密碼體制掌握Diffie—Hellman密鑰交換計算理解Elgamal算法與DSA算法2022/11/1145學(xué)習(xí)目標(biāo)理解凱撒密碼與Playfair等古典替換密碼2022古典密碼學(xué)作業(yè)1、愷撒與安東尼要舉行一個秘密會議，他寫了一個密信“ULEHU”,請問地點在什么地方？并寫出推導(dǎo)出它的數(shù)學(xué)求解式。（寫一個就可以了）答：M=C-K（mod26），M=20-3（mod26）=17=R，同理其他字母可解。明文：RIBER2、截獲了一封密信，已知是愷撒變形密信，并知道了兩對明文和相應(yīng)的密文字母，求解K？并寫出數(shù)學(xué)求解式。明文是:vy，密文是AD.答：k=c-m（mod26），k=0-21（mod26）=5。3、用playfair密碼加密：Iseeaplane！這句話，密鑰就是playfair。答：先將明文兩個字母分一組，isexeaplanex，

C=cnkuhplapqku4、用Vigenère密碼加密hereishowitw.這些字母，密鑰是（V-21，E-4，C-2，T-19，O-14，R-17）。（注意全部忽略空格和標(biāo)點符號）答：根據(jù)規(guī)則將密鑰重復(fù)，每個字母相當(dāng)于凱撒加密，C=citxwjcsybtn2022/11/1146古典密碼學(xué)作業(yè)1、愷撒與安東尼要舉行一個秘密會議，他寫了一個Caesar密碼表例2．1

愷撒（Caesar）密碼是k＝3的情況。即通過簡單的向右移動源字母表3個字母則形成如下代換字母表若明文為：pleaseconfirmreceipt則密文為：SOHDVEFRQILUPUHFHLSWM:a0b1c2d3e4f5g6h7i8j9k10l11m12C:DEFGHIJKLMNOPn13o14p15q16r17s18t19u20v21w22x23y24z25QRSTUVWXYZABC2022/11/1147Caesar密碼表例2．1愷撒（Caesar）密碼是k＝3Playfair密碼體制Playfair密碼表

playfirbcdeghkmnoqstuvwxz1234512345該密碼體制的密鑰是一個單詞，比如playfair，將單詞中后面重復(fù)的字母去掉，只保留不相同的字母，得到playfir，將剩下的字母排列成5×5矩陣的起始部分，矩陣的剩余部分則用26個字母表中未出現(xiàn)的字母填充，并將i與j作為一個字母對待（原因？）2022/11/1148Playfair密碼體制Playfair密碼表playfir各種各樣的移位密碼是在16世紀(jì)發(fā)明的，它們大多數(shù)來自于Vigenère方法，它是法國密碼學(xué)家維吉尼亞于1586年提出一種多表替換密碼,但是就加密性而言，Vigenère密碼體制更復(fù)雜和高級，直到20世紀(jì)初，這種加密體制在很多地方仍然被認(rèn)為是安全的，雖然早在19世紀(jì)，Babbage和Kasiski就展示了如何攻擊它們。在1920年，由Fridman開發(fā)了另外一種加密方法，打破了Vigenère及其相關(guān)的密碼方法。第一步：這個加密的密鑰是一個向量，按如下方式選擇。首先，確定一個密鑰長度，如6，然后從0～25個整數(shù)中選擇元素項滿足這個長度的向量，如k＝（21，4，2，19，14，17），將其稱為向量。這樣，系統(tǒng)的安全性所依賴的就是既不能知道密鑰內(nèi)容也不能得知其長度。

Vigenère密碼2022/11/1149各種各樣的移位密碼是在16世紀(jì)發(fā)明的，它們大多數(shù)來自Vigenère密碼第二步：下面所舉的例子就是利用k來加密信息，首先，取明文的第1個字母并將之移21位，然后將第2個字母移4位，第3個字母移2位等等，一旦得到了密鑰的結(jié)尾，又從頭開始，這樣第7個字母又移位21位，第8個字母移4位等等，加密過程的密碼流程表如下：（明文）hereishowitworks(密鑰)21421914172142191417214219（密文）CITXWJCSYBHNJVML

這樣對于這么一段明文就可以用Vigenère完全進(jìn)行加密了，注意這里沒有一個字母的頻率比其他大很多，這是因為e在加密的過程中擴(kuò)散成了幾個字母的緣故。

2022/11/1150Vigenère密碼第二步：下面所舉的例子就是利用k來加密信其中Mi是二元數(shù)字，為：

M58M50M42M34M26M18M10M2 M60M52M44M36M28M20M12M4 M62M54M46M38M30M22M14M6 M64M56M48M40M32M24M16M8 M57M49M41M33M25M17M9M1 M59M51M43M35M27M19M11M3 M61M53M45M37M29M21M13M5 M63M55M47M39M31M23M15M7如果再取逆初始置換Y=IP-1(X)=IP-1(IP(M))，可以看出，M各位的初始順序?qū)⒈换謴?fù)。2022/11/1151其中Mi是二元數(shù)字，為：2022/11/108求IP逆置換例如求矩陣-1的逆。即為：4279186355281973642022/11/1152求IP逆置換例如求矩陣-圖1函數(shù)F(R,K)的計算過程S盒變換2022/11/1153圖1函數(shù)F(R,K)的計算過程S盒變換2022/11/10F中的代換由8個S盒組成，每個S盒的輸入長為6比特、輸出長為4比特，其變換關(guān)系由表2.7定義，每個S盒給出了4個代換（由一個表的4行給出）。對每個盒Si，其6比特輸入中，第1個和第6個比特形成一個2位二進(jìn)制數(shù)，用來選擇Si的4個代換中的一個。6比特輸入中，中間4位用來選擇列。行和列選定后，得到其交叉位置的十進(jìn)制數(shù)，將這個數(shù)表示為4位二進(jìn)制數(shù)即得這一S盒的輸出。例如，S1

的輸入為011001，行選為01（即第1行），列選為1100（即第12列），行列交叉位置的數(shù)為9，其4位二進(jìn)制表示為1001，所以S1的輸出為1001。2022/11/1154F中的代換由8個S盒組成，每個S盒的輸入長為6比特、輸出長為費爾瑪定理和歐拉定理費爾瑪(Fermat)定理和歐拉(Euler)定理在公鑰密碼體制中起著重要作用。1.費爾瑪定理定理4.2(Fermat)若p是素數(shù)，a是正整數(shù)且gcd(a,p)=1，則ap-1≡1modp。Fermat定理也可寫成如下形式：設(shè)p是素數(shù)，a是任一正整數(shù)，則ap≡amodp。2022/11/1155費爾瑪定理和歐拉定理費爾瑪(Fermat)定理和歐拉(2.歐拉函數(shù)設(shè)n是一正整數(shù)，小于n且與n互素的正整數(shù)的個數(shù)稱為n的歐拉函數(shù)，記為φ(n)。例如：φ(6)=2，φ(7)=6，φ(8)=4。若n是素數(shù)，則顯然有φ(n)=n-1。例如：由21=3×7，得φ(21)=φ(3)×φ(7)=2×6=12。2022/11/11562.歐拉函數(shù)2022/11/1013定理4.3若n是兩個素數(shù)p和q的乘積，則φ(n)=φ(p)×φ(q)=(p-1)×(q-1)。3.歐拉定理定理4.4（Euler）若a和n互素，則aφ(n)≡1modn。2022/11/1157定理4.3若n是兩個素數(shù)p和q的乘積，則φ(n)=φ歐幾里得算法歐幾里得（Euclid）算法是數(shù)論中的一個基本技術(shù)，是求兩個正整數(shù)的最大公因子的簡化過程。而推廣的Euclid算法不僅可求兩個正整數(shù)的最大公因子，而且當(dāng)兩個正整數(shù)互素時，還可求出其中一個數(shù)關(guān)于另一個數(shù)的乘法逆元。2022/11/1158歐幾里得算法歐幾里得（Euclid）算法是數(shù)論中的一個基本技1.求最大公因子Euclid算法是基于下面一個基本結(jié)論：對任意非負(fù)整數(shù)a和正整數(shù)b，有g(shù)cd(a,b)=gcd(b,amodb)。例如：gcd(55,22)=gcd(22,55mod22)=gcd(22,11)=gcd(11,0)=11。在求兩個數(shù)的最大公因子時，可重復(fù)使用以上結(jié)論。例如：gcd(18,12)=gcd(12,6)=gcd(6,0)=6, gcd(11,10)=gcd(10,1)=gcd(1,0)=12022/11/11591.求最大公因子2022/11/1016例1求gcd(1970,1066)。1970=1×1066+904, gcd(1066,904)1066=1×904+162, gcd(904,162)904=5×162+94, gcd(162,94)162=1×94+68, gcd(94,68)94=1×68+26, gcd(68,26)68=2×26+16, gcd(26,16)26=1×16+10, gcd(16,10)16=1×10+6, gcd(10,6)10=1×6+4, gcd(6,4)6=1×4+2, gcd(4,2)4=2×2+0, gcd(2,0)因此gcd(1970,1066)=2。2022/11/1160例1求gcd(1970,1066)。2022/11/101.密鑰的產(chǎn)生①選兩個保密的大素數(shù)p和q(各100～200位十進(jìn)制數(shù)字)。②計算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的歐拉函數(shù)值。③選一整數(shù)e，滿足1<e<φ(n)，且gcd(φ(n),e)=1。④計算d，滿足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元，因e與φ(n)互素，由模運算可知，它的乘法逆元一定存在。⑤以{e,n}為公開鑰,{d,n}為秘密鑰。算法描述2022/11/11611.密鑰的產(chǎn)生算法描述2022/11/10182.加密加密時首先將明文比特串分組，使得每個分組對應(yīng)的十進(jìn)制數(shù)小于n，即分組長度小于log2n。然后對每個明文分組m，作加密運算：

c≡memodn3.解密對密文分組的解密運算為：

m≡cdmodn2022/11/11622.加密2022/11/1019例2：選p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，滿足1<e<φ(n)，且gcd(φ(n),e)=1。確定滿足d·e=1mod96且小于96的d，因為77×5=385=4×96+1，所以d為77，因此公開鑰為{5，119}，秘密鑰為{77，119}。設(shè)明文m=19，則由加密過程得密文為

c≡195mod119≡2476099mod119≡66解密為

6677mod119≡192022/11/1163例2：選p=7，q=17。求n=p×q=119，φ(n)=(例題3：已知明文m=14，pk=（3，55），求密文c和私鑰sk分別為多少？解：因為n=55=5*11，所以p=5（或11），q=11（或者5），（p-1）*（q-1）=40，

e*dmod40≡1，d=e-1=27C=memodn=143mod55=492022/11/1164例題3：已知明文m=14，pk=（3，55），求密文c

RSA算法中的計算問題1.RSA的加密與解密過程RSA的加密、解密過程都為求一個整數(shù)的整數(shù)次冪，再取模。如果按其含義直接計算，則中間結(jié)果非常大，有可能超出計算機(jī)所允許的整數(shù)取值范圍。如上例中解密運算6677mod119，先求6677再取模，則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超出了計算機(jī)允許的整數(shù)取值范圍。而用模運算的性質(zhì)：(a×b)modn=[(amodn)×(bmodn)]modn就可減小中間結(jié)果。2022/11/1165RSA算法中的計算問題1.RSA的加密與解密過程2022再者，考慮如何提高加、解密運算中指數(shù)運算的有效性。例如求x16，直接計算的話需做15次乘法。然而如果重復(fù)對每個部分結(jié)果做平方運算即求x，x2，x4，x8，x16則只需4次乘法。求am可如下進(jìn)行，其中a，m是正整數(shù)：將m表示為二進(jìn)制形式bkbk-1…b0，即m=bk2k+bk-12k-1+…+b12+b0因此2022/11/1166再者，考慮如何提高加、解密運算中指數(shù)運算的有效性。例如求x1例4求7560mod561。將560表示為1000110000，算法的中間結(jié)果如表所示。所以7560mod561=1。2022/11/1167例4求7560mod561。2022/11/1024背包密碼體制例5：A=(1,3,5,11,21,44,87,175,349,701)是一超遞增背包向量，取k=1590，t=43，gcd(43,1590)=1，得B=(43,129,215,473,903,302,561,1165,697,1523)。在得到B后，對明文分組x=(x1x2…xn)的加密運算為c=f(x)=B·Bx≡t·A·Bxmodk對單向函數(shù)f(x)，t、t-1和k可作為其秘密的陷門信息，即解密密鑰。解密時首先由s≡t-1cmodk，求出s作為超遞增背包向量A的容積，再解背包問題即得x=(x1x2…xn)。這是因為t-1cmodk≡t-1tABxmodk≡ABxmodk，而由k>∑ai，知ABx<k，所以t-1cmodk=ABx，是惟一的。2022/11/1168背包密碼體制例5：A=(1,3,5,11,21,4例6接例5，A=(1,3,5,11,21,44,87,175,349,701)是一超遞增背包向量，k=1590，t=43，得t-1≡37mod1590，設(shè)用戶收到的密文是(2942,3584,903,3326,215,2817,2629,819)，由37×2942≡734mod1590,37×3584≡638mod1590,37×903≡21mod1590,37×3326≡632mod1590,37×215≡5mod1590,37×2817≡879mod1590,37×2629≡283mod1590,37×819≡93mod1590,得(734,638,21,632,5,879,283,93)。2022/11/1169例6接例5，A=(1,3,5,11,21,44,取s=734，由734>701，得x10=1；令s=734-701=33，由33<349，得x9=0；重復(fù)該過程得第一個明文分組是1001100001，它對應(yīng)的英文文本是SA；類似地得其他明文分組，解密結(jié)果為SAUNAANDHEALTH。2022/11/1170取s=734，由734>701，得x10=1；令s=734-Diffie-Hellman密鑰交換是W.Diffie和M.Hellman于1976年提出的第一個公鑰密碼算法，已在很多商業(yè)產(chǎn)品中得以應(yīng)用。算法的惟一目的是使得兩個用戶能夠安全地交換密鑰，得到一個共享的會話密鑰，算法本身不能用于加、解密。算法的安全性基于求離散對數(shù)的困難性。Diffie-Hellman密鑰交換2022/11/1171Diffie-Hellman密鑰交換是W.Diffie和M圖2表示Diffie-Hellman密鑰交換過程，其中p是大素數(shù)，a是p的本原根，p和a作為公開的全程元素。用戶A選擇一保密的隨機(jī)整數(shù)XA，并將YA=aXAmodp發(fā)送給用戶B。類似地，用戶B選擇一保密的隨機(jī)整數(shù)XB，并將YB=aXBmodp發(fā)送給用戶A。然后A和B分別由K=(YB)XAmodp和K=(YA)XBmodp計算出的就是共享密鑰，這是因為(YB)XAmodp=(aXBmodp)XAmodp=(aXB)XAmodp=aXB

XAmodp=(aXA)XBmodp=(aXAmodp)XBmodp =(YA)XBmodp2022/11/1172圖2表示Diffie-Hellman密鑰交換過程，其中p是大圖2Diffie-Hellman密鑰交換2022/11/1173圖2Diffie-Hellman密鑰交換2022/11/1因XA，XB是保密的，敵手只能得到p，a，YA

，YB，要想得到K，則必須得到XA，XB中的一個，這意味著需要求離散對數(shù)。因此敵手求K是不可行的。例如：p=97，a=5，A和B分別秘密選XA=36，XB=58，并分別計算YA=536mod97=50，YB=558mod97=44。在交換YA，YB后，分別計算K=(YB)XAmod97=4436mod97=75,K=(YA)XBmod97=5058mod97=752022/11/1174因XA，XB是保密的，敵手只能得到p，a，YA，YB，要想Elgamal算法密鑰對產(chǎn)生辦法。首先選擇一個素數(shù)p，兩個隨機(jī)數(shù)，g和x，g與x<p，計算y=gx(modp)，則其公鑰為y,g和p。私鑰是x。其中g(shù)和p可由一組用戶共享。ElGamal用于數(shù)字簽名。被簽信息為M，首先選擇一個隨機(jī)數(shù)k,k與p-1互質(zhì)，計算

a=gk(modp)

再用擴(kuò)展Euclidean算法對下面方程求解b：

M=xa+kb(modp-1)

實際用

b=yk*Mmodp

簽名就是(a,b)。隨機(jī)數(shù)k須丟棄。

驗證時要驗證下式：

ya*ab(modp)=gM(modp)

同時一定要檢驗是否滿足1<=a<p。否則簽名容易偽造。2022/11/1175Elgamal算法密鑰對產(chǎn)生辦法。首先選擇一個素數(shù)p，兩個ElGamal用于加密被加密信息為M，首先選擇一個隨機(jī)數(shù)k，k與p-1互質(zhì)，計算

a=gk(modp)

b=ykM(modp)

(a,b)為密文，是明文的兩倍長。解密時計算

M=b/ax(modp)=b*（ax）-1modp

2022/11/1176ElGamal用于加密被加密信息為M，首先選擇一個隨機(jī)數(shù)k，例題：鮑勃把11選擇為p。然后他選擇g=e1=2。他再選擇x=d=3并且計算出y=e2=e1