第3章 分組密碼理論

1古典密碼和現(xiàn)代密碼（Cont.）現(xiàn)代密碼算法把算法和密鑰分開(kāi)

密碼算法可以公開(kāi)，密鑰保密密碼系統(tǒng)的安全性在于保持密鑰的保密性發(fā)送方接收方mm加密E解密Dc=Ek(m)m=Ek(c)密碼分析密鑰分配（秘密信道）kk第三章分組密碼理論分組密碼概述數(shù)據(jù)加密標(biāo)準(zhǔn)公開(kāi)密鑰算法3.1分組密碼概述分組密碼，就是一個(gè)明文分組被當(dāng)作一個(gè)整體來(lái)產(chǎn)生一個(gè)等長(zhǎng)（通常）的密文分組的密碼，通常使用的是128位分組大小。分組密碼的實(shí)質(zhì)是，設(shè)計(jì)一種算法，能在密鑰控制下，把n比特明文簡(jiǎn)單而又迅速地置換成唯一n比特密文，并且這種變換是可逆的（解密）。3.1分組密碼概述(Cont.)分組密碼的設(shè)計(jì)思想（C.E.Shannon)：擴(kuò)散(diffusion)將明文及密鑰的影響盡可能迅速地散布到較多個(gè)輸出的密文中（將明文冗余度分散到密文中）。產(chǎn)生擴(kuò)散的最簡(jiǎn)單方法是通過(guò)“置換(Permutation)”（比如：重新排列字符）。信息論的創(chuàng)始人克勞德·艾爾伍德·香農(nóng)(ClaudeElwoodShannon)

分組密碼的設(shè)計(jì)思想(Cont.)混淆(confusion)其目的在于使作用于明文的密鑰和密文之間的關(guān)系復(fù)雜化，是明文和密文之間、密文和密鑰之間的統(tǒng)計(jì)相關(guān)特性極小化，從而使統(tǒng)計(jì)分析攻擊不能奏效。通常的方法是“代換（Substitution)”（回憶愷撒密碼）。3.1分組密碼概述(Cont.)分組密碼設(shè)計(jì)的要求：分組長(zhǎng)度足夠大（64~128比特）密鑰量要足夠大（64~128）算法足夠復(fù)雜（包括子密鑰產(chǎn)生算法）加密、解密算法簡(jiǎn)單，易軟、硬件實(shí)現(xiàn)便于分析（破譯是困難的，但算法卻簡(jiǎn)潔清晰）73.2DES算法原理IBM公司，70年代初提出，80年代成為國(guó)家標(biāo)準(zhǔn)DES是一種對(duì)稱密鑰算法，密鑰長(zhǎng)度為56bits(加上奇偶校驗(yàn)，通常寫(xiě)成64bits)是一種分組加密算法，64bits為一個(gè)分組基本思想：混亂（Confusion）和擴(kuò)散（Diffusion）使用標(biāo)準(zhǔn)的算術(shù)和邏輯運(yùn)算成為標(biāo)準(zhǔn)的過(guò)程發(fā)明人：IBM公司W(wǎng).Tuchman和C.Meyer1971-72年研制。產(chǎn)生：美國(guó)商業(yè)部的國(guó)家標(biāo)準(zhǔn)局NBS1973年5月到1974年8月兩次發(fā)布通告，公開(kāi)征求用于電子計(jì)算機(jī)的加密算法。經(jīng)評(píng)選從一大批算法中采納了IBM的LUCIFER方案。標(biāo)準(zhǔn)化：于1976年11月被美國(guó)政府采用，DES隨后被美國(guó)國(guó)家標(biāo)準(zhǔn)局和美國(guó)國(guó)家標(biāo)準(zhǔn)協(xié)會(huì)(AmericanNationalStandardInstitute，ANSI)承認(rèn)。1977年1月以數(shù)據(jù)加密標(biāo)準(zhǔn)DES（DataEncryptionStandard）的名稱正式向社會(huì)公布。于1977年7月15日生效。3.2數(shù)據(jù)加密標(biāo)準(zhǔn)（Cont.)3.2.1簡(jiǎn)化的DES

SimplifiedDES方案，簡(jiǎn)稱S-DES方案。它是一個(gè)供教學(xué)而非安全的加密算法，它與DES的特性和結(jié)構(gòu)類似，但參數(shù)小。注：1.*加密算法涉及五個(gè)函數(shù)：

(1)初始置換IP(initialpermutation)

(2)復(fù)合函數(shù)fk1，它是由密鑰K確定的，具有置換和代換的運(yùn)算。(3)置換函數(shù)SW

(4)復(fù)合函數(shù)fk2

(5)初始置換IP的逆置換IP-1

加密10bit密鑰

解密8bit明文P108bit明文IP移位IP-1P8fkfkSWSW移位P8fkfkIPIP-18bit密文8bit密文K2K2K1K1S-DES方案示意圖2*.加密算法的數(shù)學(xué)表示：

IP-1*fk2*SW*fk1*IP

也可寫(xiě)為

密文=IP-1（fk2(SW(fk1(IP(明文)))))

其中K1=P8(移位(P10(密鑰K)))

K2=P8(移位(移位(P10(密鑰K))))

解密算法的數(shù)學(xué)表示：

明文=IP-1（fk1(SW(fk2(IP(密文)))))對(duì)S-DES的深入描述（1）S-DES的密鑰生成：設(shè)10bit的密鑰為（k1,k2,…,k10)置換P10是這樣定義的P10(k1,k2,…,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6)LS-1為循環(huán)左移1位，LS-2為循環(huán)左移2位P8=(k1,k2,…,k10)=(k6,k3,k7,k4,k8,k5,k10,k9)

按照上述條件,若K選為(1010000010),產(chǎn)生的兩個(gè)子密鑰分別為K1=(10100100),K2=(01000011)S-DES的密鑰生成

10-bit密鑰P10LS-1LS-1LS-2LS-2P8P8K18K255558(2)S-DES的加密運(yùn)算:

初始置換用IP函數(shù):IP=12345678 26314857

末端算法的置換為IP的逆置換:

IP-1=1234567841357286

易見(jiàn)IP-1(IP(X))=XS-DES加密圖

8-bit明文IPE/P+S0S1P4+LR4K1844fkF4E/P+S0S18K2P4+IP-18-bit密文4844fkF44228SW中間各級(jí)算法說(shuō)明Ki：每級(jí)密鑰不同

數(shù)據(jù)加密標(biāo)準(zhǔn)Li-1LiRi-1Ri

Li-1

f(Ri-1,Ki)19一個(gè)簡(jiǎn)單的加密算法—異或20一個(gè)簡(jiǎn)單的加密算法—異或異或

密文：0110解密：密鑰：

0101

明文：0011

已知明文、密文，怎樣求得密鑰？C=PKP=CK異或運(yùn)算（不帶進(jìn)位加法）： 明文:

0011

加密： 密鑰:

0101

密文：0110K=CP只知道密文，如何求得密文和密鑰？函數(shù)fk，是加密方案中的最重要部分，它可表示為：fk(L,R)=(LF(R,SK),R)

其中L，R為8位輸入,左右各為4位,F為從4位集到4位集的一個(gè)映射,并不要求是1-1的。SK為子密鑰。對(duì)映射F來(lái)說(shuō)：首先輸入是一個(gè)4-位數(shù)（n1,n2,n3,n4），第一步運(yùn)算是擴(kuò)張/置換（E/P）運(yùn)算：

E/P 41232341事實(shí)上，它的直觀表現(xiàn)形式為：n4n1n2n3n2n3n4n18-bit子密鑰：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后與E/P的結(jié)果作異或運(yùn)算得：

n4+k11n1+k12 n2+k13 n3+k14 n2+k15n3+k16 n4+k17 n1+k18把它們重記為8位：

P0,0P0,1P0,2 P0,3P1,0P1,1P1,2P1,3上述第一行4位輸入進(jìn)S-盒S0，產(chǎn)生2-位的輸出；第二行的4位輸入進(jìn)S盒S1，產(chǎn)生2-位的輸出。兩個(gè)S盒按如下定義：S盒按下述規(guī)則運(yùn)算：將第1和第4的輸入比特做為2-bit數(shù)，指示為S盒的一個(gè)行；將第2和第3的輸入比特做為S盒的一個(gè)列。如此確定為S盒矩陣的（i,j）數(shù)。例如：（P0,0,P0,3）=(00),并且(P0,1,P0,2)=(10)確定了S0中的第0行2列（0，2）的系數(shù)為3，記為（11）輸出。由S0,S1輸出4-bit經(jīng)置換

P4

243 1

它的輸出就是F函數(shù)的輸出。數(shù)據(jù)加密標(biāo)準(zhǔn)使用選擇函數(shù)S將以上第j個(gè)(1≤j≤6)二進(jìn)制的塊（記為Zj=zj1zj2zj3zj4zj5zj6）輸入第j個(gè)選擇函數(shù)Sj。各選擇函數(shù)Sj的功能是把6位數(shù)變換成4位數(shù)，做法是以zj1zj6為行號(hào)，zj2zj3zj4zj5為列號(hào)，查找Sj，行列交叉處即是要輸出的4位數(shù)。在此以S1為例說(shuō)明其功能，我們可以看到：在S1中，共有4行數(shù)據(jù)，命名為0，1、2、3行；每行有16列，命名為0、1、2、3，......，14、15列?，F(xiàn)設(shè)輸入為：

D＝101100令：列＝0110行＝10坐標(biāo)為（2，6），然后在S1表中查得對(duì)應(yīng)的數(shù)為2，以4位二進(jìn)制表示為0010，此即選擇函數(shù)S1的輸出。數(shù)據(jù)加密標(biāo)準(zhǔn)012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S11011001020010輸入6位輸出4位使用選擇函數(shù)S的例子DES概述分組加密算法：明文和密文為64位分組長(zhǎng)度對(duì)稱算法：加密和解密除密鑰編排不同外，使用同一算法密鑰長(zhǎng)度：56位，但每個(gè)第8位為奇偶校驗(yàn)位，可忽略密鑰可為任意的56位數(shù)，但存在弱密鑰，容易避開(kāi)采用混亂和擴(kuò)散的組合，每個(gè)組合先替代后置換，共16輪只使用了標(biāo)準(zhǔn)的算術(shù)和邏輯運(yùn)算，易于實(shí)現(xiàn)DES加密算法的一般描述輸入64比特明文數(shù)據(jù)初始置換IP在密鑰控制下16輪迭代初始逆置換IP-1輸出64比特密文數(shù)據(jù)交換左右32比特DES加密過(guò)程初始置換IP和初始逆置換IP—1

逆初始變換。用IP-1表示，它和IP互逆。例如，第58位經(jīng)過(guò)初始置換后，處于第1位，而通過(guò)逆置換，又將第1位換回到第58位。可見(jiàn)輸入組m和IP(IP-1(m))是一樣的。IP和IP—1IPIP—1Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器選擇擴(kuò)展運(yùn)算E48比特寄存器子密鑰Ki（48比特）32比特寄存器選擇壓縮運(yùn)算S置換運(yùn)算PRi（32比特）Li=Ri-1DES的一輪迭代擴(kuò)展置換Ｅ-盒－32位擴(kuò)展到48位擴(kuò)展壓縮替代S-盒－48位壓縮到32位共8個(gè)S盒S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒的構(gòu)造S-盒的構(gòu)造DES中其它算法都是線性的，而S-盒運(yùn)算則是非線性的S-盒不易于分析，它提供了更好的安全性所以S-盒是算法的關(guān)鍵所在S-盒的構(gòu)造準(zhǔn)則S盒的每一行是整數(shù)0，…，15的一個(gè)置換沒(méi)有一個(gè)S盒是它輸入變量的線性函數(shù)改變S盒的一個(gè)輸入位至少要引起兩位的輸出改變對(duì)任何一個(gè)S盒和任何一個(gè)輸入X，S（X）和

S(X001100）至少有兩個(gè)比特不同（這里X是長(zhǎng)度為6的比特串）對(duì)任何一個(gè)S盒，對(duì)任何一個(gè)輸入對(duì)e,f屬于{0,1},

S(X)S(X11ef00)

對(duì)任何一個(gè)S盒，如果固定一個(gè)輸入比特，來(lái)看一個(gè)固定輸出比特的值，這個(gè)輸出比特為0的輸入數(shù)目將接近于這個(gè)輸出比特為1的輸入數(shù)目S-盒的構(gòu)造要求S-盒是許多密碼算法的唯一非線性部件,因此,它的密碼強(qiáng)度決定了整個(gè)算法的安全強(qiáng)度提供了密碼算法所必須的混亂作用如何全面準(zhǔn)確地度量S-盒的密碼強(qiáng)度和設(shè)計(jì)有效的S-盒是分組密碼設(shè)計(jì)和分析中的難題非線性度、差分均勻性、嚴(yán)格雪崩準(zhǔn)則、可逆性、沒(méi)有陷門(mén)置換p-盒的構(gòu)造p-盒的構(gòu)造準(zhǔn)則P置換的目的是提供雪崩效應(yīng)明文或密鑰的一點(diǎn)小的變動(dòng)都引起密文的較大變化DES中的子密鑰的生成密鑰置換算法的構(gòu)造準(zhǔn)則設(shè)計(jì)目標(biāo)：子密鑰的統(tǒng)計(jì)獨(dú)立性和靈活性實(shí)現(xiàn)簡(jiǎn)單速度不存在簡(jiǎn)單關(guān)系：(給定兩個(gè)有某種關(guān)系的種子密鑰,能預(yù)測(cè)它們輪子密鑰之間的關(guān)系)種子密鑰的所有比特對(duì)每個(gè)子密鑰比特的影響大致相同從一些子密鑰比特獲得其他的子密鑰比特在計(jì)算上是難的沒(méi)有弱密鑰Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器選擇擴(kuò)展運(yùn)算E48比特寄存器子密鑰Ki（48比特）32比特寄存器選擇壓縮運(yùn)算S置換運(yùn)算PRi（32比特）Li=Ri-1DES的一輪迭代DES加密算法的一般描述DES的工作模式電子密碼本ECB(electroniccodebookmode)密碼分組鏈接CBC(cipherblockchaining)密碼反饋CFB(cipherfeedback)輸出反饋OFB(outputfeedback)兩重DES50雙密鑰的三重DES

（TripleDESwithTwoKeys)C=EK1(DK2(EK1(P)))P=DK1(EK2(DK1(C)))51三密鑰的三重DES

（TripleDESwithThreeKeys)C=EK3(DK2(EK1(P)))=DK3(EK2(DK1(C)))DES的安全性

F函數(shù)(S-Box)設(shè)計(jì)原理未知密鑰長(zhǎng)度的爭(zhēng)論

DES的破譯

弱密鑰與半弱密鑰DES密鑰長(zhǎng)度關(guān)于DES算法的另一個(gè)最有爭(zhēng)議的問(wèn)題就是擔(dān)心實(shí)際56比特的密鑰長(zhǎng)度不足以抵御窮舉式攻擊，因?yàn)槊荑€量只有個(gè)

早在1977年，Diffie和Hellman已建議制造一個(gè)每秒能測(cè)試100萬(wàn)個(gè)密鑰的VLSI芯片。每秒測(cè)試100萬(wàn)個(gè)密鑰的機(jī)器大約需要一天就可以搜索整個(gè)密鑰空間。他們估計(jì)制造這樣的機(jī)器大約需要2000萬(wàn)美元VLSI:very-large-scale-integration

（超大規(guī)模集成電路）DES密鑰長(zhǎng)度在CRYPTO’93上，Session和Wiener給出了一個(gè)非常詳細(xì)的密鑰搜索機(jī)器的設(shè)計(jì)方案，這個(gè)機(jī)器基于并行運(yùn)算的密鑰搜索芯片，所以16次加密能同時(shí)完成?；ㄙM(fèi)10萬(wàn)美元，平均用1.5天左右就可找到DES密鑰.CRYPTO是國(guó)際密碼討論年會(huì)(AnnualInternationalCryptologyConference)的常用英文縮寫(xiě)。它是密碼學(xué)中最大的研討會(huì)

美國(guó)克羅拉多洲的程序員Verser從1997年2月18日起，用了96天時(shí)間，在Internet上數(shù)萬(wàn)名志愿者的協(xié)同工作下，成功地找到了DES的密鑰，贏得了懸賞的1萬(wàn)美元DES密鑰長(zhǎng)度1998年7月電子前沿基金會(huì)（EFF）使用一臺(tái)25萬(wàn)美圓的電腦在56小時(shí)內(nèi)破譯了56比特密鑰的DES1999年1月RSA數(shù)據(jù)安全會(huì)議期間，電子前沿基金會(huì)用22小時(shí)15分鐘就宣告破解了一個(gè)DES的密鑰弱密鑰與半弱密鑰弱密鑰:EKEK=I

，DES存在4個(gè)弱密鑰即：半弱密鑰:EK1=EK2

，至少有12個(gè)半弱密鑰即：弱密鑰?初始密鑰被分成兩部分，每部分都單獨(dú)做移位。如果每一部分的每一位都是0或都是1，則每一圈的子密鑰都相同。這樣的密鑰被稱為弱密鑰。?DES存在4個(gè)弱密鑰半弱密鑰?有些成對(duì)的密鑰會(huì)將明文加密成相同的密文，即一對(duì)密鑰中的一個(gè)能用來(lái)解密由另一個(gè)密鑰加密的消息，這種密鑰稱作半弱密鑰。其它常規(guī)分組加密算法TripleDESIDEARC5RC6AES其他一些較實(shí)用的算法，如Blowfish，CAST，以及RC2等目錄分組密碼概述數(shù)據(jù)加密標(biāo)準(zhǔn)公開(kāi)密鑰算法63密鑰分配（KeyDistribution）保密通信雙方需共享密鑰共享密鑰要經(jīng)常更換A選擇密鑰并手工傳遞給B第三方C選擇密鑰分別手工傳遞給A,B用A,B原有共享密鑰傳送新密鑰與A,B分別有共享密鑰的第三方C傳送新密鑰給A和/或BN個(gè)用戶集需要N(N-1)/2個(gè)共享密鑰密鑰分發(fā)中心(KeyDistributionCenter)64密鑰分發(fā)中心（KDC）每個(gè)用戶與KDC有共享密鑰(MasterKey)N個(gè)用戶,KDC只需分發(fā)N個(gè)MasterKey兩個(gè)用戶間通信用會(huì)話密鑰(SessionKey)用戶必須信任KDCKDC能解密用戶間通信的內(nèi)容（1）密鑰管理量的困難傳統(tǒng)密鑰管理：兩兩分別用一對(duì)密鑰時(shí)，則n個(gè)用戶需要C(n,2)=n(n-1)/2個(gè)密鑰，當(dāng)用戶量增大時(shí)，密鑰空間急劇增大。如:n=100時(shí)，C(100,2)=4,995n=5000時(shí)，C(5000,2)=12,497,500（2）數(shù)字簽名的問(wèn)題傳統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴的需求。問(wèn)題的提出公開(kāi)密鑰算法

公開(kāi)密鑰算法是非對(duì)稱算法，即密鑰分為公鑰和私鑰，因此稱雙密鑰體制雙鑰體制的公鑰可以公開(kāi)，因此也稱公鑰算法公鑰算法的出現(xiàn)，給密碼的發(fā)展開(kāi)辟了新的方向。公鑰算法雖然已經(jīng)歷了20多年的發(fā)展，但仍具有強(qiáng)勁的發(fā)展勢(shì)頭，在鑒別系統(tǒng)和密鑰交換等安全技術(shù)領(lǐng)域起著關(guān)鍵的作用公開(kāi)密鑰算法的提出公鑰密碼學(xué)是1976年由Diffie和Hellman在其“密碼學(xué)新方向”一文中提出的，見(jiàn)文獻(xiàn)：

W.DiffieandM.E.Hellman,NewDirectrionsinCryptography，

IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654公開(kāi)密鑰算法的提出RSA公鑰算法是由Rivest,Shamir和Adleman在1978年提出來(lái)的參見(jiàn)CommunitionsoftheACM.Vol.21.No.2.Feb.1978,PP.120-126該算法的數(shù)學(xué)基礎(chǔ)是初等數(shù)論中的Euler（歐拉)定理，并建立在大整數(shù)因子的困難性之上加密與解密由不同的密鑰完成加密：解密：知道加密算法，從加密密鑰得到解密密鑰在計(jì)算上是不可行的兩個(gè)密鑰中任何一個(gè)都可以作為加密而另一個(gè)用作解密公開(kāi)密鑰算法的基本要求基于公開(kāi)密鑰的加密過(guò)程用公鑰密碼實(shí)現(xiàn)保密

用戶擁有自己的密鑰對(duì)(KU,KR)

公鑰KU公開(kāi)，私鑰KR保密

基于公開(kāi)密鑰的鑒別過(guò)程用公鑰密碼實(shí)現(xiàn)鑒別

條件：兩個(gè)密鑰中任何一個(gè)都可以用作加密而另外一個(gè)用作解密鑒別：

鑒別＋保密

公開(kāi)密鑰算法公鑰算法的種類很多，具有代表性的三種密碼：

基于整數(shù)分解難題（IFP）的算法體制基于離散對(duì)數(shù)難題（DLP）算法體制基于橢圓曲線離散對(duì)數(shù)難題（ECDLP）的算法體制RSA算法76基本思想和要求涉及到各方：發(fā)送方、接收方、攻擊者涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文公鑰算法的條件：產(chǎn)生一對(duì)密鑰是計(jì)算可行的已知公鑰和明文，產(chǎn)生密文是計(jì)算可行的接收方利用私鑰來(lái)解密密文是計(jì)算可行的對(duì)于攻擊者，利用公鑰來(lái)推斷私鑰是計(jì)算不可行的已知公鑰和密文，恢復(fù)明文是計(jì)算不可行的(可選)加密和解密的順序可交換?1977年由RonRivest、AdiShamir和LenAdleman發(fā)明，1978年公布?是一種分組加密算法。

–明文和密文在0~n-1之間,n是一個(gè)正整數(shù)?應(yīng)用最廣泛的公鑰密碼算法?只在美國(guó)申請(qǐng)專利，且已于2000年9月到期RSA算法RSA算法的實(shí)現(xiàn)實(shí)現(xiàn)的步驟如下：Bob為實(shí)現(xiàn)者

(1)Bob尋找出兩個(gè)大素?cái)?shù)p和q(2)Bob計(jì)算出n=pq和φ(n)=(p-1)(q-1)(3)Bob選擇一個(gè)隨機(jī)數(shù)e(0<e<φ(n))，滿足gcd(e,φ(n))=1(4)Bob使用輾轉(zhuǎn)相除法計(jì)算d=e-1(modφ(n))(5)Bob將n和e設(shè)為公鑰,在目錄中公開(kāi),將p、q、d設(shè)為秘密的Alice將m加密為c≡me(modn)，并將c發(fā)送給Bob；Bob通過(guò)計(jì)算m≡cd(modn)解密。素?cái)?shù)：只能被1和它本身整除的自然數(shù)；否則為合數(shù)。每個(gè)合數(shù)都可以唯一地分解出素?cái)?shù)因子6=2·3999999=3·3·3·7·11·13·3727641=131·121GCD通常表示最大公約數(shù)(greatestcommondivisor，簡(jiǎn)寫(xiě)為gcd

輾轉(zhuǎn)相除法,又名歐幾里得算法（Euclideanalgorithm）乃求兩個(gè)正整數(shù)之最大公因數(shù)的算法。這是已知最古老的算法,其可追溯至前300年。首次出現(xiàn)于歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國(guó)則可以追溯至東漢出現(xiàn)的《九章算術(shù)》。這算法并不需要把二數(shù)作質(zhì)因數(shù)分解。

輾轉(zhuǎn)相除法求最大公約數(shù)，是一種比較好的方法，比較快。對(duì)于52317和75569兩個(gè)數(shù)，你能迅速地求出它們的最大公約數(shù)嗎？一般來(lái)說(shuō)你會(huì)找一找公共的因子，這題可麻煩了，不好找，質(zhì)因子大?，F(xiàn)在教你用輾轉(zhuǎn)相除法來(lái)求最大公約數(shù)。先用較大的75569除以52317，得商1，余數(shù)23252，再以52317除以23252，得商2，余數(shù)是5813，再用23252做被除數(shù)，5813做除數(shù)，正好除盡得商數(shù)4。這樣5813就是5569和52317的最大公約數(shù)。算法描述:

a÷b，令r為所得余數(shù)（0≤r＜b）若r=0，算法結(jié)束；b

即為答案。a

mod

b”是指取a÷b

的余數(shù)。例如，123456和7890的最大公因數(shù)是6,這可由下列步驟看出：

RSA算法編制參數(shù)T={N}；私鑰SK=P,Q,D；公鑰PK=E；設(shè)：明文M，密文C，那么：用公鑰作業(yè)：MEmodN=C

用私鑰作業(yè)：CDmodN=MRSA算法舉例設(shè)p=7,q=17,n=7*17=119;參數(shù)T={n=119};φ(n)=(7-1)(17-1)=96;選擇e=5,gcd(5,96)=1;公鑰pk=5;計(jì)算d,(d*e)mod96=1;d=77;私鑰sk=77;設(shè):明文m=19

加密：（19）5mod119=66

脫密：（66）77mod119=19模p運(yùn)算

給定一個(gè)正整數(shù)p，任意一個(gè)整數(shù)n，一定存在等式

n=kp+r

其中k、r是整數(shù)，且0≤r<p，稱呼k為n除以p的商，r為n除以p的余數(shù)。

對(duì)于正整數(shù)p和整數(shù)a,b，定義如下運(yùn)算：

取模運(yùn)算：amodp表示a除以p的余數(shù)。

模p加法：(a+b)modp，其結(jié)果是a+b算術(shù)和除以p的余數(shù)，也就是說(shuō)，(a+b)=kp+r，則(a+b)modp=r。

模p減法：(a-b)modp，其結(jié)果是a-b算術(shù)差除以p的余數(shù)。

模p乘法：(a×b)modp，其結(jié)果是a×b算術(shù)乘法除以p的余數(shù)。

86RSA:例2選擇兩個(gè)素?cái)?shù):p=17&q=11計(jì)算

n=pq=17×11=187計(jì)算?(n)=(p–1)(q-1)=16×10=160選擇e:gcd(e,160)=1;其中e=787如果待加密的消息M=88(注意：88<187)加密：C=887mod187=11

解密:M=1123mod187=88

RSA：例2RSA：例3Bob選擇p=885320693，q=238855417，則可以計(jì)算

n=p*q=211463707796206571，設(shè)加密系數(shù)為e=9007，將n和e發(fā)送給Alice。假設(shè)Alice傳遞的信息是cat。令a=01c=03t=20，則cat=030120=30120。

Alice計(jì)算：c≡me≡301209007≡113535859035722866(modn)

她將c傳給Bob。RSA：例3Bob已知p和q的值，他用擴(kuò)展歐幾里德算法計(jì)算d：

de≡1(mod(p-1)(q-1))，得到

d=116402471153538991

然后Bob計(jì)算：

cd≡113535859035722866116402471153538991≡30120(modn)

由此他可以得到最初的信息。RSA算法的安全性分析密碼分析者攻擊RSA體制的關(guān)鍵點(diǎn)在于如何分解n若分解成功使n=pq，則可以算出φ(n)＝（p-1)(q-1)，然后由公開(kāi)的e，解出秘密的d若使RSA安全，p與q必為足夠大的素?cái)?shù)，使分析者沒(méi)有辦法在多項(xiàng)式時(shí)間內(nèi)將n分解出來(lái)RSA算法的