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

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

第11周

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

2023/1/81

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

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

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

愷撒（Caesar）密碼是k＝3的情況。即通過(guò)簡(jiǎn)單的向右移動(dòng)源字母表3個(gè)字母則形成如下代換字母表若明文為：pleaseconfirmreceipt則密文為：SOHDVEFRQILUPUHFHLSWM:a0b1c2d3e4f5g6h7i8j9k10l11m12C:DEFGHIJKLMNOPn13o14p15q16r17s18t19u20v21w22x23y24z25QRSTUVWXYZABC2023/1/84Caesar密碼表例2．1愷撒（Caesar）密碼是k＝3Playfair密碼體制Playfair密碼表

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

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

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

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

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

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

c≡memodn3.解密對(duì)密文分組的解密運(yùn)算為：

m≡cdmodn2023/1/8192.加密2023/1/719例2：選p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，滿(mǎn)足1<e<φ(n)，且gcd(φ(n),e)=1。確定滿(mǎn)足d·e=1mod96且小于96的d，因?yàn)?7×5=385=4×96+1，所以d為77，因此公開(kāi)鑰為{5，119}，秘密鑰為{77，119}。設(shè)明文m=19，則由加密過(guò)程得密文為

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

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

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

RSA算法中的計(jì)算問(wèn)題1.RSA的加密與解密過(guò)程RSA的加密、解密過(guò)程都為求一個(gè)整數(shù)的整數(shù)次冪，再取模。如果按其含義直接計(jì)算，則中間結(jié)果非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。如上例中解密運(yùn)算6677mod119，先求6677再取模，則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)允許的整數(shù)取值范圍。而用模運(yùn)算的性質(zhì)：(a×b)modn=[(amodn)×(bmodn)]modn就可減小中間結(jié)果。2023/1/822RSA算法中的計(jì)算問(wèn)題1.RSA的加密與解密過(guò)程2023再者，考慮如何提高加、解密運(yùn)算中指數(shù)運(yùn)算的有效性。例如求x16，直接計(jì)算的話(huà)需做15次乘法。然而如果重復(fù)對(duì)每個(gè)部分結(jié)果做平方運(yùn)算即求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因此2023/1/823再者，考慮如何提高加、解密運(yùn)算中指數(shù)運(yùn)算的有效性。例如求x1例4求7560mod561。將560表示為1000110000，算法的中間結(jié)果如表所示。所以7560mod561=1。2023/1/824例4求7560mod561。2023/1/724背包密碼體制例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后，對(duì)明文分組x=(x1x2…xn)的加密運(yùn)算為c=f(x)=B·Bx≡t·A·Bxmodk對(duì)單向函數(shù)f(x)，t、t-1和k可作為其秘密的陷門(mén)信息，即解密密鑰。解密時(shí)首先由s≡t-1cmodk，求出s作為超遞增背包向量A的容積，再解背包問(wèn)題即得x=(x1x2…xn)。這是因?yàn)閠-1cmodk≡t-1tABxmodk≡ABxmodk，而由k>∑ai，知ABx<k，所以t-1cmodk=ABx，是惟一的。2023/1/825背包密碼體制例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è)用戶(hù)收到的密文是(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)。2023/1/826例6接例5，A=(1,3,5,11,21,44,取s=734，由734>701，得x10=1；令s=734-701=33，由33<349，得x9=0；重復(fù)該過(guò)程得第一個(gè)明文分組是1001100001，它對(duì)應(yīng)的英文文本是SA；類(lèi)似地得其他明文分組，解密結(jié)果為SAUNAANDHEALTH。2023/1/827取s=734，由734>701，得x10=1；令s=734-Diffie-Hellman密鑰交換是W.Diffie和M.Hellman于1976年提出的第一個(gè)公鑰密碼算法，已在很多商業(yè)產(chǎn)品中得以應(yīng)用。算法的惟一目的是使得兩個(gè)用戶(hù)能夠安全地交換密鑰，得到一個(gè)共享的會(huì)話(huà)密鑰，算法本身不能用于加、解密。算法的安全性基于求離散對(duì)數(shù)的困難性。Diffie-Hellman密鑰交換2023/1/828Diffie-Hellman密鑰交換是W.Diffie和M圖2表示Diffie-Hellman密鑰交換過(guò)程，其中p是大素?cái)?shù)，a是p的本原根，p和a作為公開(kāi)的全程元素。用戶(hù)A選擇一保密的隨機(jī)整數(shù)XA，并將YA=aXAmodp發(fā)送給用戶(hù)B。類(lèi)似地，用戶(hù)B選擇一保密的隨機(jī)整數(shù)XB，并將YB=aXBmodp發(fā)送給用戶(hù)A。然后A和B分別由K=(YB)XAmodp和K=(YA)XBmodp計(jì)算出的就是共享密鑰，這是因?yàn)?YB)XAmodp=(aXBmodp)XAmodp=(aXB)XAmodp=aXB

XAmodp=(aXA)XBmodp=(aXAmodp)XBmodp =(YA)XBmodp2023/1/829圖2表示Diffie-Hellman密鑰交換過(guò)程，其中p是大圖2Diffie-Hellman密鑰交換2023/1/830圖2Diffie-Hellman密鑰交換2023/1/73因XA，XB是保密的，敵手只能得到p，a，YA

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

a=gk(modp)

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

M=xa+kb(modp-1)

實(shí)際用

b=yk*Mmodp

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

驗(yàn)證時(shí)要驗(yàn)證下式：

ya*ab(modp)=gM(modp)

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

a=gk(modp)

b=ykM(modp)

(a,b)為密文，是明文的兩倍長(zhǎng)。解密時(shí)計(jì)算

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

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

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

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

*p：Lbits長(zhǎng)的素?cái)?shù)。L是64的倍數(shù)，范圍是512到1024；

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

*g：g=h^((p-1)/q)modp，h滿(mǎn)足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ù)。注："^"為冪運(yùn)算符2023/1/836DSA算法DigitalSignatureAlgorit簽名過(guò)程DSA中選用SHA(SecureHashAlgorithm)。p,q,g可由一組用戶(hù)共享，y是公開(kāi)鑰，x是私鑰，簽名過(guò)程如下：

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

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

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

r，s即簽名結(jié)果。2023/1/837簽名過(guò)程DSA中選用SHA(SecureHashAlg驗(yàn)證過(guò)程驗(yàn)證過(guò)程：簽名結(jié)果是(m,r,s)。

3.驗(yàn)證時(shí)計(jì)算w=s-1modq

u1=(H(m)*w)modq

u2=(r*w)modq

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

若v=r，則認(rèn)為簽名有效。驗(yàn)證通過(guò)說(shuō)明：簽名(r,s)有效，即(r,s,M)確為發(fā)送方的真實(shí)簽名結(jié)果，M未被竄改，為有效信息。驗(yàn)證失敗說(shuō)明：簽名(r,s)無(wú)效，即(r,s,M)不可靠，或者M(jìn)被竄改過(guò)，或者簽名是偽造的，M為無(wú)效信息。2023/1/838驗(yàn)證過(guò)程驗(yàn)證過(guò)程：簽名結(jié)果是(m,r,s)。

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

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

第11周

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

2023/1/844

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

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

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

愷撒（Caesar）密碼是k＝3的情況。即通過(guò)簡(jiǎn)單的向右移動(dòng)源字母表3個(gè)字母則形成如下代換字母表若明文為：pleaseconfirmreceipt則密文為：SOHDVEFRQILUPUHFHLSWM:a0b1c2d3e4f5g6h7i8j9k10l11m12C:DEFGHIJKLMNOPn13o14p15q16r17s18t19u20v21w22x23y24z25QRSTUVWXYZABC2023/1/847Caesar密碼表例2．1愷撒（Caesar）密碼是k＝3Playfair密碼體制Playfair密碼表

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

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

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

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

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

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

c≡memodn3.解密對(duì)密文分組的解密運(yùn)算為：

m≡cdmodn2023/1/8622.加密2023/1/719例2：選p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，滿(mǎn)足1<e<φ(n)，且gcd(φ(n),e)=1。確定滿(mǎn)足d·e=1mod96且小于96的d，因?yàn)?7×5=385=4×96+1，所以d為77，因此公開(kāi)鑰為{5，119}，秘密鑰為{77，119}。設(shè)明文m=19，則由加密過(guò)程得密文為

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

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

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

RSA算法中的計(jì)算問(wèn)題1.RSA的加密與解密過(guò)程RSA的加密、解密過(guò)程都為求一個(gè)整數(shù)的整數(shù)次冪，再取模。如果按其含義直接計(jì)算，則中間結(jié)果非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。如上例中解密運(yùn)算6677mod119，先求6677再取模，則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)允許的整數(shù)取值范圍。而用模運(yùn)算的性質(zhì)：(a×b)modn=[(amodn)×(bmodn)]modn就可減小中間結(jié)果。2023/1/865RSA算法中的計(jì)算問(wèn)題1.RSA的加密與解密過(guò)程2023再者，考慮如何提高加、解密運(yùn)算中指數(shù)運(yùn)算的有效性。例如求x16，直接計(jì)算的話(huà)需做15次乘法。然而如果重復(fù)對(duì)每個(gè)部分結(jié)果做平方運(yùn)算即求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因此2023/1/866再者，考慮如何提高加、解密運(yùn)算中指數(shù)運(yùn)算的有效性。例如求x1例4求7560mod561。將560表示為1000110000，算法的中間結(jié)果如表所示。所以7560mod561=1。2023/1/867例4求7560mod561。2023/1/724背包密碼體制例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后，對(duì)明文分組x=(x1x2…xn)的加密運(yùn)算為c=f(x)=B·Bx≡t·A·Bxmodk對(duì)單向函數(shù)f(x)，t、t-1和k可作為其秘密的陷門(mén)信息，即解密密鑰。解密時(shí)首先由s≡t-1cmodk，求出s作為超遞增背包向量A的容積，再解背包問(wèn)題即得x=(x1x2…xn)。這是因?yàn)閠-1cmodk≡t-1tABxmodk≡ABxmodk，而由k>∑ai，知ABx<k，所以t-1cmodk=ABx，是惟一的。2023/1/868背包密碼體制例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è)用戶(hù)收到的密文是(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)。2023/1/869例6接例5，A=(1,3,5,11,21,44,取s=734，由734>701，得x10=1；令s=734-701=33，由33<349，得x9=0；重復(fù)該過(guò)程得第一個(gè)明文分組是1001100001，它對(duì)應(yīng)的英文文本是SA；類(lèi)似地得其他明文分組，解密結(jié)果為SAUNAANDHEALTH。2023/1/870取s=734，由734>701，得x10=1；令s=734-Diffie-Hellman密鑰交換是W.Diffie和M.Hellman于1976年提出的第一個(gè)公鑰密碼算法，已在很多商業(yè)產(chǎn)品中得以應(yīng)用。算法的惟一目的是使得兩個(gè)用戶(hù)能夠安全地交換密鑰，得到一個(gè)共享的會(huì)話(huà)密鑰，算法本身不能用于加、解密。算法的安全性基于求離散對(duì)數(shù)的困難性。Diffie-Hellman密鑰交換2023/1/871Diffie-Hellman密鑰交換是W.Diffie和M圖2表示Diffie-Hellman密鑰交換過(guò)程，其中p是大素?cái)?shù)，a是p的本原根，p和a作為公開(kāi)的全程元素。用戶(hù)A選擇一保密的隨機(jī)整數(shù)XA，并將YA=aXAmodp發(fā)送給用戶(hù)B。類(lèi)似地，用戶(hù)B選擇一保密的隨機(jī)整數(shù)XB，并將YB=aXBmodp發(fā)送給用戶(hù)A。然后A和B分別由K=(YB)XAmodp和K=(YA)XBmodp計(jì)算出的就是共享密鑰，這是因?yàn)?YB)XAmodp=(aXBmodp)XAmodp=(aXB)XAmodp=aXB

XAmodp=(aXA)XBmodp=(aXAmodp)XBmodp =(YA)XBmodp2023/1/872圖2表示Diffie-Hellman密鑰交換過(guò)程，其中p是大圖2Diffie-Hellman密鑰交換2023/1/873圖2Diffie-Hellman密鑰交換2023/1/73因XA，XB是保密的，敵手只能得到p，a，YA

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

a=gk(modp)

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

M=xa+kb(modp-1)

實(shí)際用

b=yk*Mmodp

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

驗(yàn)證時(shí)要驗(yàn)證下式：

ya*ab(modp)=gM(modp)

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

a=gk(modp)

b=ykM(modp)

(a,b)為密文，是明文的兩倍長(zhǎng)。解密時(shí)計(jì)算

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

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