第3章 密碼學(xué)基礎(chǔ)

第3章密碼學(xué)基礎(chǔ)l

密碼學(xué)的基本概念和術(shù)語l

對稱和非對稱密碼的區(qū)別l

古典密碼學(xué)的基本方法l

掌握DES算法、AES算法RSA算法的基本原理13.1密碼學(xué)概述3.1.1密碼學(xué)的發(fā)展史愷撒（Caesar）密碼一種簡單易行的單字母替代密碼

維吉尼亞密碼（Vigenere

cypher）多表加密的替代密碼

“恩格瑪（Enigma）”密碼機(jī)

DES（數(shù)據(jù)加密標(biāo)準(zhǔn)）美國國家標(biāo)準(zhǔn)局頒布的國家標(biāo)準(zhǔn)密碼學(xué)歷史上一個具有里程碑意義的事件

23.1.1密碼學(xué)的發(fā)展史（續(xù)）公開密鑰密碼

密碼學(xué)的一場革命量子密碼學(xué)

3密碼學(xué)的發(fā)展史大體上可以歸結(jié)為三個階段

第一階段：1949年之前，密碼學(xué)還不是科學(xué),而是藝術(shù)。

第二階段：1949～1975年，密碼學(xué)成為科學(xué)。

第三階段：1976年以后，密碼學(xué)的新方向——公鑰密碼學(xué)。（公鑰密碼使得發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡?。?/p>

43.1.2密碼系統(tǒng)一個密碼系統(tǒng)被定義為一對數(shù)據(jù)變換：加密變換：將明文和加密密鑰作為輸入，輸出密文；解密變換：將密文和解密密鑰作為輸入，輸出明文；密鑰是變換中的一個參數(shù)。5簡單加密系統(tǒng)模型簡單地說它就是一組含有參數(shù)K的變換E。設(shè)已知消息m，通過變換Ek得密文C，即，這個過程稱為加密，E為加密算法，k不同，密文C亦不同。傳統(tǒng)的保密通信機(jī)制：EncipherPlaintextCiphertextKeysDecipherC=Ek(m)發(fā)方：m收方：mkk（公共信道）加密E解密D（秘密信道）6理論安全和實際安全

TheoreticalSecurity(orPerfectSecurity)andPracticalSecure(orComputationallySecure)理論安全，或無條件安全：攻擊者無論截獲多少密文，都無法得到足夠的信息來唯一地決定明文。Shannon用理論證明：欲達(dá)理論安全，加密密鑰長度必須大于等于明文長度，密鑰只用一次，用完即丟，即一次一密，One-timePad，不實用。實際安全，或計算上安全：如果攻擊者擁有無限資源，任何密碼系統(tǒng)都是可以被破譯的；但是，在有限的資源范圍內(nèi)，攻擊者都不能通過系統(tǒng)地分析方法來破解系統(tǒng)，則稱這個系統(tǒng)是計算上安全的或破譯這個系統(tǒng)是計算上不可行（ComputationallyInfeasible）。

78密碼體制

加密系統(tǒng)采用的基本工作方式稱為密碼體制。密碼體制的基本要素是密碼算法和密鑰。密碼算法是一些公式、法則或程序；密鑰是密碼算法中的控制參數(shù)。通常一個密碼體制可以表達(dá)為一個五元組（P，C，K，E，D），其中：（1）P是可能明文的有限集稱為明文空間（2）C是可能密文的有限集稱為密文空間（3）K是一切可能密鑰構(gòu)成的有限集稱為密鑰空間（4）對于密鑰空間的任一密鑰有一個k∈K，則有C＝Ek(P)，P＝Dk(C)＝Dk(Ek(P))，或者Dk＝Ek－1，且Ek＝Dk－1。93.1.3密碼的分類1、按應(yīng)用的技術(shù)或歷史發(fā)展階段劃分：手工密碼機(jī)械密碼電子機(jī)內(nèi)亂密碼計算機(jī)密碼2、按保密程度劃分：理論上保密的密碼實際上保密的密碼不保密的密碼103.1.3密碼的分類（續(xù)）

3、按密鑰方式劃分：對稱密碼體制(SymmetricSystem,One-keySystem,Secret-keySystem)加密密鑰和解密密鑰相同，或者一個密鑰可以從另一個導(dǎo)出，能加密就能解密，加密能力和解密能力是結(jié)合在一起的，開放性差。非對稱密碼體制(AsymmetricSystem,Two-keySystem,Public-keySystem)加密密鑰和解密密鑰不相同，從一個密鑰導(dǎo)出另一個密鑰是計算上不可行的，加密能力和解密能力是分開的，開放性好。113.1.3密碼的分類（續(xù)）

4、按明文形態(tài)：模擬型密碼數(shù)字型密碼5、按編制原理劃分：移位、代替和置換以及它們的組合形式123.1.4近代加密技術(shù)

1、對稱加密算法對稱加密算法（synmetricalgorithm），也稱為傳統(tǒng)密碼算法，其加密密鑰與解密密鑰相同或很容易相互推算出來，因此也稱之為秘密密鑰算法或單鑰算法。對稱算法分為兩類一類稱為序列密碼算法（streamcipher）：以明文中的單個位（有時是字節(jié)）為單位進(jìn)行運(yùn)算；另一種稱為分組密碼算法（blockcipher）：以明文中的一組位為單位進(jìn)行運(yùn)算。加密過程中會用到兩種技術(shù)：混亂（confusion）：改變信息塊使輸出位和輸入位無明顯的統(tǒng)計關(guān)系。擴(kuò)散（diffusion）：將明文位和密鑰的效應(yīng)傳播到密文的其他位。13對稱加密系統(tǒng)由以下五部分組成:Plaintext：明文Encryptionalgorithm：加密算法SecretKey：密鑰Ciphertext：密文Decryptionalgorithm：解密算法加密算法必須足夠強(qiáng)大，使破譯者不能僅根據(jù)密文破譯消息；Securitydependsonthesecrecyofthekey,notthesecrecyofthealgorithm.對稱密碼的模型141、對稱加密算法（續(xù)）對稱加密算法的主要優(yōu)點是運(yùn)算速度快，硬件容易實現(xiàn)；其缺點是密鑰的分發(fā)與管理比較困難，特別是當(dāng)通信的人數(shù)增加時，密鑰數(shù)目急劇膨脹。如當(dāng)n個人互相之間通信時，需要有n(n-1)/2個密鑰。1516Requirementstworequirementsforsecureuseofsymmetricencryption:astrongencryptionalgorithmasecretkeyknownonlytosender/receiver Y=EK(X) X=DK(Y)assumeencryptionalgorithmisknownimpliesasecurechanneltodistributekey17Y=Ek(X)X=Dk(Y)182、非對稱加密體制非對稱加密算法（AsynmetricAlgorithm）也稱公開密鑰算法（PublicKeyAlgorithm）。公開密鑰體制把信息的加密密鑰和解密密鑰分離，通信的每一方都擁有這樣的一對密鑰。其中加密密鑰可以像電話號碼一樣對外公開，由發(fā)送方用來加密要發(fā)送的原始數(shù)據(jù)；解密密鑰則由接收方秘密保存，作為解密時的私用密鑰。19公開密鑰密碼系統(tǒng)的原理對稱密碼體制的問題加密能力與解密能力是捆綁在一起的密鑰更換、傳遞和交換需要可靠信道如有N用戶，則需要C=N(N-1)/2個密鑰，n=1000時，C(1000,2)≈500000,管理困難無法滿足不相識的人之間通信的保密要求不能實現(xiàn)數(shù)字簽名非對稱密碼體制的基本特點加密能力與解密能力是分開的密鑰分發(fā)簡單需要保存的密鑰量大大減少，N個用戶只需要N個可滿足不相識的人之間保密通信可以實現(xiàn)數(shù)字簽名20公開密鑰加密算法的核心是一種特殊的數(shù)學(xué)函數(shù)——單向陷門函數(shù)（Trap-DoorOneWayFunction），即該函數(shù)從一個方向求值是容易的，但是其逆變換卻是極其困難。其通用表示為：Ek1(M)=CDk2(C)=MDk2(Ek1(M))=M公開秘鑰加密算法可用于加密和認(rèn)證21公開密鑰加密過程22公開密鑰認(rèn)證過程23公開密鑰密碼系統(tǒng):保密24公開密鑰密碼系統(tǒng):認(rèn)證25公開密鑰密碼系統(tǒng):保密和認(rèn)證262、非對稱加密體制（續(xù)）公開密鑰體制最大的優(yōu)點就是不需要對密鑰通信進(jìn)行保密，所需傳輸?shù)闹挥泄_密鑰。這種密鑰體制還可以用于數(shù)字簽名。公開密鑰體制的缺陷在于其加密和解密的運(yùn)算時間比較長，這在一定程度上限制了它的應(yīng)用范圍。272、非對稱加密體制（續(xù)）三個不同方面的用途：數(shù)據(jù)的加密解密：RSA數(shù)字簽名：RSA、DSS密鑰交換：RSA、Diffie-Hellman28密碼編碼學(xué)(Cryptography)密碼編碼系統(tǒng)根據(jù)以下三個獨立方面進(jìn)行分類：用于將明文轉(zhuǎn)換為密文操作的類型：替代和置換所使用的密鑰的數(shù)量：對稱密碼體制，單鑰系統(tǒng)、秘密密鑰系統(tǒng)非對稱密碼體制，雙鑰系統(tǒng)、公開密鑰系統(tǒng)明文處理的方式：分組加密和流加密密碼分析學(xué)(Cryptanalysis)試圖破譯密文得到明文或試圖獲得密鑰的過程為密碼分析，密碼破譯的策略取決于加密方法及可供破譯者使用的信息。Cryptology密碼學(xué)293.1.5密碼的破譯不同的密碼系統(tǒng)可能使用不同長度的鑰匙。在其他條件相同的情況下，鑰匙越長，破譯密碼就越困難，密碼系統(tǒng)就越可靠。303.1.5密碼的破譯（續(xù)）1、密鑰的窮盡搜索嘗試所有可能的鑰匙組合。2、密碼分析利用數(shù)學(xué)方法破譯密文或找到鑰匙的方法稱為密碼分析。有兩個基本目標(biāo)：利用密文發(fā)現(xiàn)明文利用密文發(fā)現(xiàn)鑰匙常見的有：已知明文的破譯方法

選定明文的破譯方法

差別比較分析法

31BruteForceSearchalwayspossibletosimplytryeverykeymostbasicattack,proportionaltokeysizeassumeeitherknow/recogniseplaintext32333.1.5密碼的破譯（續(xù)）真正的加密安全性，必須要建立在公開和廣泛的同行鑒定、檢查的基礎(chǔ)之上。3、其它密碼破譯方法針對人機(jī)系統(tǒng)的弱點進(jìn)行攻擊以達(dá)到其目的。

343.2古典密碼學(xué)3.2.1代換密碼

代換密碼的特點是：改變明文內(nèi)容的表示形式，保持內(nèi)容元素之間相對位置不變。1、移位密碼——凱撒密碼（k=3）移位密碼基于數(shù)論中的模運(yùn)算。因為英文有26個字母，故可將移位密碼定義如下：令P={A,B,C,……Z}，C={A,B,C,……Z},K={0，1，2,……25}，加密變換：Ek（x）=（x+k）mod26解密變換：Dk（y）=（y-k）mod26352、單表代換密碼單表代換密碼的基本思想是：列出明文字母與密文字母的一一對應(yīng)關(guān)系。

明文AbcDefghijklm密文WJANDYUQIBCEF明文nopQrstuvwxyz密文GHKLMOPRSTVXZ例如：明文為networksecurity,則相就的密文為：GDPTHMCODARMIPX。363、多表替換密碼Vigenere密碼是一種典型的多表替換密碼算法。算法如下：設(shè)密鑰K=k1k2……kn,明文M=m1m2……mn,加密變換:ci≡（mi+ki）mod26,i=1,2,……,n解密變換：mi≡（ci-ki）mod26,i=1,2,……,n例如：明文X=cipherblock,密鑰為：hit則把明文劃分成長度為3的序列：cipherblock每個序列中的字母分別與密鑰序列中相應(yīng)字母項加并進(jìn)行模26運(yùn)算，得密文：JQIOMKITHJS373.2.2置換密碼置換密碼的特點是保持明文的所有字母不變，只是利用置換打亂明文字母出現(xiàn)的位置。置換密碼體制定義如下：令m為一正整數(shù)，P=C={A,B,C,……Z}，對任意的置換π（密鑰），定義:

加密變換：Eπ（x1,x2,……,xm）=（xπ（1）,xπ（2）……,xπ（m））,

解密變換：Dπ（y1,y2,……,ym）=（xπ-1（1）,xπ-1

（2）……,xπ-1

（m））,

置換密碼也不能掩蓋字母的統(tǒng)計規(guī)律，因而不能抵御基于統(tǒng)計的密碼分析方法的攻擊。38置換技術(shù)(Transpositionorpermutation)改變明文內(nèi)容元素的相對位置，保持內(nèi)容的表現(xiàn)形式不變。一維變換－矩陣轉(zhuǎn)置二維變換－圖形轉(zhuǎn)置DNATSREDNUUOYNAC明文：canyouunderstand密文：codtaueanurnynsd輸入輸出UUOYNACSREDNNATD密文明文明文：canyouunderstand密文：dnsuaruteodynnac393.3對稱密碼學(xué)3.3.1分組密碼概述分組密碼是將明文消息編碼后的數(shù)字序列：b1b2b3b4…劃分為長度為n的分組，一個分組表示為：mi=(bj,bj+1,…,bj+n-1)，各個分組在密鑰的作用下，變換為等長的數(shù)字輸出序列ci=(xj,xj+1,xj+2,…,xj+n-1)。40設(shè)計分組密碼算法時，需要考慮的因素：分組長度n要足夠大密鑰空間要足夠大算法要足夠復(fù)雜：保證秘鑰和明文的充分?jǐn)U散和混淆加密和解密運(yùn)算簡單，易于實現(xiàn)，差錯傳播盡可能小41分組密碼大多數(shù)分組密碼基于FeistelCipherStructure分組加密器本質(zhì)上就是一個巨大的替換器64位的分組就會有264種輸入采用了乘積加密器的思想3.3.2Feistel網(wǎng)絡(luò)42Feistel密碼ClaudeShannonandSubstitution-PermutationCiphers1949年，ClaudeShannon

引進(jìn)了substitution-permutation(S-P)networks的思想，即現(xiàn)代的乘積加密器modernsubstitution-transpositionproductcipher，形成了現(xiàn)代分組加密的基礎(chǔ)。S-Pnetworks是基于替代substitution(S-box)和置換permutation(P-box)這兩個基本操作的。提供了對明文信息處理所做的confusion和diffusion

。Shannon認(rèn)為，為了對付基于統(tǒng)計分析的密碼破譯，必須對明文作confusion(擾亂)和diffusion(擴(kuò)散)處理，以減少密文的統(tǒng)計特性，為統(tǒng)計分析制造障礙。diffusion–dissipatesstatisticalstructureofplaintextoverbulkofciphertext，明文統(tǒng)計結(jié)構(gòu)擴(kuò)散消失到大批密文統(tǒng)計特性中，使明文和密文之間統(tǒng)計關(guān)系盡量復(fù)雜；confusion–makesrelationshipbetweenciphertextandkeyascomplexaspossible，使密文和加密密鑰之間的關(guān)系盡量復(fù)雜。431、擴(kuò)散和混亂擴(kuò)散和混亂是由Shannon提出的設(shè)計密碼系統(tǒng)的兩個基本方法，目的是抵抗攻擊者對密碼的統(tǒng)計分析。擴(kuò)散就是指將明文的統(tǒng)計特性散布到密文中去

混亂就是使密文和密鑰之間的統(tǒng)計關(guān)系變得盡可能復(fù)雜

442、Feistel網(wǎng)絡(luò)結(jié)構(gòu)及特點Feistel提出利用乘積密碼可獲得簡單的代換密碼。

（1）將明文分組分為左右兩個部分：L0，R0，數(shù)據(jù)的這兩部分通過n輪（round）處理后，再結(jié)合起來生成密文分組；（2）第i輪處理其上一輪產(chǎn)生的Li-1和Ri-1和K產(chǎn)生的子密鑰Ki作為輸入。一般說來，子密鑰Ki與K不同，相互之間也不同，它是用子密鑰生成算法從密鑰生成的；（3）每一輪的處理的結(jié)構(gòu)都相同，置換在數(shù)據(jù)的左半部分進(jìn)行，其方法是先對數(shù)據(jù)的右半部分應(yīng)用處理函數(shù)F，然后對函數(shù)輸出結(jié)果和數(shù)據(jù)的左半部分取異或（XOR）；（4）處理函數(shù)F對每輪處理都有相同的通用結(jié)構(gòu)，但由循環(huán)子密鑰Ki來區(qū)分；（5）在置換之后，執(zhí)行由數(shù)據(jù)兩部分互換構(gòu)成的交換；（6）解密過程與加密過程基本相同。規(guī)則如下：用密文作為算法的輸入，但以相反順序使用子密鑰Ki；（7）加密和解密不需要用兩種不同的方法。45Feistel密碼結(jié)構(gòu)1973年，HorstFeistel提出了基于可逆乘積加密器概念的FeistelCipher：將輸入分組分成左右兩部分，實施Shannon’s的substitution-permutationnetwork概念對左半部數(shù)據(jù)實施多回合的替代操作(substitution)對右半部數(shù)據(jù)和子密鑰應(yīng)用round函數(shù)F，其輸出與左一半做異或?qū)⑦@兩部分進(jìn)行互換(permutationswapping)

46FeistelCipherEncryptionandDecryption47DES加密算法的一般描述3.3.3DES算法481、算法描述DES算法流程如圖3-4所示。首先把明文分成若干個64-bit的分組，算法以一個分組作為輸入，通過一個初始置換（IP）將明文分組分成左半部分（L0）和右半部分（R0），各為32-bit。然后進(jìn)行16輪完全相同的運(yùn)算，這些運(yùn)算我們稱為函數(shù)f，在運(yùn)算過程中數(shù)據(jù)與密鑰相結(jié)合。經(jīng)過16輪運(yùn)算后，左、右兩部分合在一起經(jīng)過一個末轉(zhuǎn)換（初始轉(zhuǎn)換的逆置換IP-1），輸出一個64-bit的密文分組。495051初始置換IP(InitialPermutation)和逆置換IP-152擴(kuò)展置換和置換函數(shù)53S-盒置換，將48-bit輸入轉(zhuǎn)為32-bit的輸出，過程如下：48-bit組被分成8個6-bit組，每一個6-bit組作為一個S盒的輸入，輸出為一個4-bit組。其方式是：6-bit數(shù)的首、末兩位數(shù)決定輸出項所在的行；中間的四位決定輸出項所在的列。例如：假設(shè)第6個S-盒的輸入為110101，則輸出為第3行第10列的項（行或列的記數(shù)從0開始），即輸出為4-bit組0001。

S6:12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,54子密鑰的生成

密鑰通常表示為64-bit，但每個第8位用作奇偶校驗，實際的密鑰長度為56-bit。在DES的每一輪運(yùn)算中，從56-bit密鑰產(chǎn)生出不同的48-bit的子密鑰（K1,K2……K16）。首先，由64-bit密鑰經(jīng)過一個置換選擇（PC-1）選出56-bit并分成兩部分（以C、D分別表示這兩部分），每部分28位，然后每部分分別循環(huán)左移1位或2位（從第1輪到第16輪，相應(yīng)左移位數(shù)分別為：1、1、2、2、2、2、2、2、1、2、2、2、2、2、2、1）。再將生成的56-bit組經(jīng)過一個另一個置換選擇（PC-2），舍掉其中的某8個位并按一定方式改變位的位置，生成一個48-bit的子密鑰Ki。

555657DES的解密是加密的逆過程，采用相同算法，但是子密鑰使用的次序正好相反。58密鑰長度問題56-bit密鑰有256=72,057,584,037,927,936≈7.2億億之多強(qiáng)力搜索(bruteforcesearch)似乎很困難，20世紀(jì)70年代估計要1000－2000年技術(shù)進(jìn)步使窮舉搜索成為可能1997年1月29日，RSA公司發(fā)起破譯RC4、RC5、MD2、MD5，以及DES的活動，破譯DES獎勵10000美金。明文是：Strongcryptographymakestheworldasaferplace.結(jié)果僅搜索了24.6%的密鑰空間便得到結(jié)果，耗時96天。1998年在一臺專用機(jī)上(EFF)只要三天時間即可1999年在超級計算機(jī)上只要22小時!DES的安全強(qiáng)度593、三重DES如上所言，DES一個致命的缺陷就是密鑰長度短，并且對于當(dāng)前的計算能力，56位的密鑰長度已經(jīng)抗不住窮舉攻擊，而DES又不支持變長密鑰。但算法可以一次使用多個密鑰，從而等同于更長的密鑰。三重DES算法表示為：C=EK3（DK2（EK1（M）））通常取K3=K1，則上式變?yōu)椋篊=EK1（DK2（EK1（M）））這樣對于三重DES的窮舉攻擊需要2112次，而不是DES的264次了。603.3.5

分組密碼的工作模式611.電子密碼本模式ElectronicCodebook,ECB明文分成64的分組進(jìn)行加密，必要時填充，每個分組用同一密鑰加密，同樣明文分組得相同密文62AdvantagesandLimitationsofECBrepetitionsinmessagemayshowinciphertext

weaknessduetoencryptedmessageblocksbeingindependentmainuseissendingafewblocksofdata632.密碼分組鏈接模式CipherBlockChaining(CBC)加密輸入是當(dāng)前明文分組和前一密文分組的異或，形成一條鏈，使用相同的密鑰，這樣每個明文分組的加密函數(shù)輸入與明文分組之間不再有固定的關(guān)系64AdvantagesandLimitationsofCBCeachciphertextblockdependsonallmessageblocksthusachangeinthemessageaffectsallciphertextblocksafterthechangeaswellastheoriginalblockneedInitialValue(IV)knowntosender&receiverhoweverifIVissentintheclear,anattackercanchangebitsofthefirstblock,andchangeIVtocompensatehenceeitherIVmustbeafixedvalue(asinEFTPOS)oritmustbesentencryptedinECBmodebeforerestofmessageatendofmessage,handlepossiblelastshortblockbypaddingeitherwithknownnon-datavalue(egnulls)orpadlastblockwithcountofpadsizeeg.[b1b2b300005]<-3databytes,then5bytespad+count65加密：Ci=Ek

（Pi⊕Ci-1）解密：Pi=Ci-1⊕Dk

（Ci）66密碼反饋模式CipherFeedBack(CFB)是一種將DES轉(zhuǎn)化成流密碼的技術(shù)，不再要求報文被填充成整個分組，可以實時運(yùn)行，如果要傳輸一個字符流，每個字符都可以使用面向字符的流密碼立刻加密和傳輸。加密：加密函數(shù)的輸入是一個64位的移位寄存器，產(chǎn)生初始向量IV。加密函數(shù)高端j位與明文P1的第一單元異或，產(chǎn)生j位密文C1進(jìn)入移位寄存器低端，繼續(xù)加密，與P2輸入異或，如此重復(fù)直到所有明文單元都完成加密。解密：采用相同方案，但是使用加密函數(shù)而非解密函數(shù)。3.密碼反饋模式CipherFeedBack(CFB)6768AdvantagesandLimitationsofCFBappropriatewhendataarrivesinbits/bytesmostcommonstreammodelimitationisneedtostallwhiledoblockencryptionaftereveryn-bitsnotethattheblockcipherisusedinencryptionmodeatbothendserrorspropagateforseveralblocksaftertheerror694、出反饋模式OFBOFB模式實際上就是一個同步流密碼，通過反復(fù)加密一個初始向量IV來產(chǎn)生一個密鑰流，將此密鑰流和明文流進(jìn)行異或可得密文流。仍然需要一個初始向量（IV）。IV應(yīng)當(dāng)唯一但不須保密。加密和解密可表示為：加密：S0=IV；Si=Ek（Si-1）；Ci=Pi⊕Si解密：Pi=Ci⊕Si；Si=Ek（Si-1）70（5）計數(shù)模式CTR該模式使用一個計數(shù)ctr（也是一個初始向量）。如圖3-17所示。加密：Ci=Ek（ctr+i）⊕Pi解密：Pi=Ek（ctr+i）⊕Ci71Counter(CTR)723.4非對稱密碼體制

RSAandDiffie-HellmanRSA-RonRives,AdiShamirandLenAdlemanatMIT,in1977.RSAisablockcipherThemostwidelyimplementedDiffie-Hellman

EchangeasecretkeysecurelyComputediscretelogarithms(離散對數(shù))

73RSAAlgorithm概述

1977年，Rivest、Shamir、Adleman提出的非對稱密碼體制，是基于大合數(shù)的質(zhì)因子分解問題的困難性。目前人類已能分解十進(jìn)制150位的特殊類型的大合數(shù)第9個費(fèi)馬數(shù)，1994年4月一個小組通過Internet合作，8個月時間成功分解129位的數(shù)，大約428比特，最新的記錄是1996年分解130位合數(shù)。RSA專利于2000年9月20日到期。743.4.1RSARSA算法的思路如下：為了產(chǎn)生兩個密鑰，先取兩個大素數(shù)，p和q。為了獲得最大程度的安全性，兩數(shù)的長度一樣。計算乘積n=p*q，然后隨機(jī)選取加密密鑰e，使e和（p-1）*（q-1）互素。最后用歐幾里得（Euclidean）擴(kuò)展算法計算解密密鑰d，d滿足ed≡1mod（p-1）（q-1），即d≡e-1mod（p-1）（q-1）。則e和n為公開密鑰，d是私人密鑰。兩個大數(shù)p和q75算法流程隨機(jī)選擇兩個秘密大質(zhì)數(shù)p和q；計算公開模數(shù)n=p*q；計算秘密的歐拉指數(shù)函數(shù)φ(n)=(p-1)(q-1)選擇一個與φ(n)互素的數(shù)K，作為e或d；用Euclid算法計算模φ(n)的K的乘法逆元素，即依edmodφ(n)=1,求d或e；加密：C=Memodn解密：M=Cdmodn=(Memodn)dmodn=M

這里，φ(n)為EulerTotientFunction，歐拉商數(shù)，即模n的完全剩余集合(0,1,2,...,n-1)中與n互素的數(shù)的個數(shù)。76加密消息時，首先將消息分成比n小的數(shù)據(jù)分組（采用二進(jìn)制數(shù)，選到小于n的2的最大次冪），設(shè)mi表示消息分組，ci表示加密后的密文，它與mi具有相同的長度。加密過程：ci=mie（modn）解密過程：mi=cid（modn）77TheRSAAlgorithm-Encryption

Plaintext: M<nCiphertext: C=Me(modn)78TheRSAAlgorithm-Decryption

Ciphertext: CPlaintext: M=Cd

(modn)79RSA算法滿足公開密鑰加密的要求，必須符合下列條件有可能找到e,d,n的值，使得對所有M<n有

Medmodn=M對于所有M<n的值，要計算Me和Cd是相對容易的在給定e和n時，計算出d是不可行的幾個關(guān)系φ(n)=φ(pq)=φ(p)φ(q)=(p-1)(q-1),p,qareprimeedmodφ(n)=1,ed=kφ(n)+1,即ed≡1modφ(n),d≡e-1modφ(n)80一個實際的例子來幫助理解RSA算法。①選擇素數(shù):p=17&q=11②計算n=pq

=17×11=187③計算?（n）=（p–1）（q-1）=16×10=160④選擇e:gcd（e,160）=1;選擇e=7⑤確定d:de=1mod160且d<160，d=23因為23×7=161=1×160+1⑥公鑰KU={7,187}⑦私鑰KR={23,187}假設(shè)給定的消息為：M=88，則?加密:C=887mod187=11?解密:M=1123mod187=8881DiscreteLogarithmProblem(DLP)離散對數(shù)問題DiscreteLogarithmProblem(DLP)

如果a是素數(shù)p的一個原根(本原元素)，則amodp,a2modp,......,ap-1modp，生成模p的完全剩余集{1,2,......,p-1}對于所有素數(shù)，其原根必定存在，即對于一個整數(shù)b和素數(shù)p的一個原根，可以找到唯一的指數(shù)i，使得b=aimodp其中0<=i<=p-1指數(shù)i稱為b的以a為基數(shù)的模p的離散對數(shù)或者指數(shù)。給定整數(shù)x，求y=axmodp容易；若給定p,a及y，求x，則為DLP問題，最快方法需要L(p)=exp{(lnpln(lnp))?}次運(yùn)算。3.4.2Diffie—Hellman算法82例：p=11,a=2,<Ex(a)>={20,21,22,…,210}={1,2,4,8,5,10,9,7,3,6,1}

即：20=1mod11 26=9mod11 21=2mod11 27=7mod11 22=4mod11 28=3mod11 23=8mod11 29=6mod11 24=5mod11 210=1mod1125=10mod11給定整數(shù)x，求y=axmodp,最多需要[log2x]+w(x)-1次乘法，w(x)為x中所有1的個數(shù)。如x

=15，即x

=(1111)2，w(x)=4，則a15=((a2)a)2·a)2·amodp，只需要3+4-1=6次乘法。但是若給定p,a及y，求x，則為DLP問題。最快方法需要L(p)=exp{(lnpln(lnp))?}次運(yùn)算。當(dāng)p=512位時，L(p)約為2256≈1077，計算上不可行。因為2100≈1030，計算要1016年。83Diffie-HellmanSetupAllusersagreeonglobalparameters:largeprimeintegerorpolynomialqαaprimitiverootmodqEachuser(e.g.A)generatestheirkeychoosesasecretkey(number):xA<qcomputetheirpublickey:yA=αxAmodqEachusermakespublicthatkeyyA84Diffie-HellmanKeyExchangeSharedsessionkeyforusersA&BisKAB:KAB=αxA.xBmodq=yAxBmodq(whichBcancompute)=yBxAmodq(whichAcancompute)KABisusedassessionkeyinprivate-keyencryptionschemebetweenAlic