第2章 密碼技術(shù)1

第2章密碼技術(shù)2.1密碼學(xué)概述2.2傳統(tǒng)密碼體制2.3現(xiàn)代對稱密碼體制2.4非對稱密碼體制2.5密碼學(xué)的新進(jìn)展例：設(shè)明文是一串二進(jìn)制序列，加密和解密算法都采用模2運(yùn)算，即異或運(yùn)算⊕，加密密鑰和解密密鑰相同。若明文P=11001100加密和解密密鑰K=11000111則加密后的密文C=P⊕K=00001011解密后的密文P=C⊕K=11001100密碼學(xué)的發(fā)展歷史自人類社會出現(xiàn)戰(zhàn)爭便產(chǎn)生了密碼

Phaistos圓盤，一種直徑約為160mm的Cretan-Mnoan粘土圓盤，始于公元前17世紀(jì)。表面有明顯字間空格的字母，至今還沒有破解。JuliusCaesar發(fā)明了凱撒密碼密碼學(xué)的發(fā)展歷史1834年，英國人庫克和倫敦大學(xué)的實驗物理學(xué)教授惠斯頓合作發(fā)明了電報機(jī)(第1個具有專利），這是通信向機(jī)械化、電氣化躍進(jìn)的開始，為密碼通信采用在線加密技術(shù)提供了前提條件。1920年，美國電報電話公司的弗納姆發(fā)明了弗納姆密碼。其原理是利用電傳打字機(jī)的五位碼與密鑰字母進(jìn)行模2相加。密碼學(xué)的發(fā)展歷史兩次世界大戰(zhàn)大大促進(jìn)了密碼學(xué)的發(fā)展。一戰(zhàn)中美國陸軍和海軍使用的條形密碼設(shè)備M-138-T4。根據(jù)1914年P(guān)arkerHitt的提議而設(shè)計。25個可選取的紙條按照預(yù)先編排的順序編號和使用，主要用于低級的軍事通信。Kryha密碼機(jī)：約在1926年由AlexandervoKryha發(fā)明。這是一個多表加密設(shè)備，密鑰長度為442，周期固定。由數(shù)量不等的齒輪引導(dǎo)密文輪不規(guī)則運(yùn)動。密碼學(xué)的發(fā)展歷史兩次世界大戰(zhàn)大大促進(jìn)了密碼學(xué)的發(fā)展。轉(zhuǎn)輪密碼機(jī)ENIGMA，由ArthurScherbius于1919年發(fā)明，面板前有燈泡和插接板；4輪ENIGMA在1942年裝備德國海軍，英國從1942年2月到12月都沒能解讀德國潛艇的信號。英國的TYPEX打字密碼機(jī)，是德國3輪ENIGMA的改進(jìn)型密碼機(jī)。它在英國通信中使用廣泛，且在破譯密鑰后幫助破解德國信號。密碼學(xué)的發(fā)展歷史1949年香農(nóng)發(fā)表了一篇題為《保密系統(tǒng)的通信理論》的著名論文，該文首先將信息論引入了密碼，從而把已有數(shù)千年歷史的密碼學(xué)推向了科學(xué)的軌道，奠定了密碼學(xué)的理論基礎(chǔ)。1976年，美國密碼學(xué)家W.Diffie和M.Hellman在一篇題為《密碼學(xué)的新方向》一文中提出了一個嶄新的思想，不僅加密算法本身可以公開，甚至加密用的密鑰也可以公開。1977年美國國家標(biāo)準(zhǔn)局頒布了數(shù)據(jù)加密標(biāo)準(zhǔn)DES2001年11月26日，正式頒布AES為美國國家標(biāo)準(zhǔn)。

2.1密碼學(xué)概述密碼體制的模型2.1密碼學(xué)概述2.密碼體制的分類（1）對稱密碼體制：K1=K2或K2=f（K1）優(yōu)點：（a）加密和解密的速度都比較快，具有較高的數(shù)據(jù)吞吐率；（b）對稱密碼體制中所使用的密鑰相對較短；（c）密文的長度往往與明文長度相同。缺點：（a）密鑰分發(fā)需要安全通道，需要付出的代價較高；（b）密鑰量大，難于管理。2.1密碼學(xué)概述（2）非對稱密碼體制：K1和K2不相同，且不能從公鑰推出私鑰，或者說從公鑰推出私鑰在計算上是不可行的。優(yōu)點：a）密鑰的分發(fā)相對容易。b）密鑰管理簡單。c）可以有效地實現(xiàn)數(shù)字簽名。缺點：a）與對稱密碼體制相比，非對稱密碼體制加解密速度較慢；b）同等安全強(qiáng)度下，非對稱密碼體制要求的密鑰長度要長一些；c）密文的長度往往大于明文長度。2.1密碼學(xué)概述柯克霍夫準(zhǔn)則（KerckhoffsPrinciple）： 即使密碼系統(tǒng)的任何細(xì)節(jié)已為人悉知，只要密鑰未泄漏，它也應(yīng)是安全的。換言之：密碼算法是公開的，所有秘密都在密鑰中。2.1密碼學(xué)概述3.密碼體制的攻擊（1）唯密文攻擊（CiphertextonlyAttack）密碼攻擊者截獲了消息的密文，從中盡可能多的恢復(fù)對應(yīng)明文，甚至推導(dǎo)出加密信息的密鑰。抽象描述：已知:Ci=Ek(Pi),i=1,2,..,n試圖推導(dǎo):P1,..,Pn，密鑰k；或者構(gòu)造一個算法從Ci+1=Ek(Pi+1)中推導(dǎo)Pi+1（2）已知明文攻擊（KnownPlaintextAttack）攻擊者已知若干明文-密文對，試圖推導(dǎo)密鑰，或者根據(jù)密文推導(dǎo)未知明文2.1密碼學(xué)概述（3）選擇明文攻擊（ChosenPlaintextAttack）攻擊者不僅能夠得到若干明文-密文對，而且可以選擇任何明文及其密文對，從而推導(dǎo)密鑰或者從密文推導(dǎo)明文通過暫時控制加密器，實現(xiàn)對公鑰密碼體制的攻擊（4）選擇密文攻擊（ChosenCiphertextAttack）攻擊者可以選擇任何密文及其對應(yīng)明文，從而推導(dǎo)密鑰——通過暫時控制解密器，（5）選擇文本攻擊(ChosenTextAttack)（3）、（4）的結(jié)合。

以上五類攻擊強(qiáng)度逐級遞增。例如一個密碼系統(tǒng)能夠抵御選擇明文攻擊則就能夠抵御選擇密文攻擊和唯密文攻擊2.1密碼學(xué)概述4.密碼算法的評價1）安全性。安全是最重要的評價因素；2）計算的效率。即算法的速度，算法在不同的工作平臺上的速度都應(yīng)該考慮到；3）存儲條件；4）軟件和硬件的適應(yīng)性，即算法在軟件和硬件上都應(yīng)該能夠被有效的實現(xiàn)；5）簡潔性。即要求算法應(yīng)該容易實現(xiàn)；6）適應(yīng)性。即算法應(yīng)與大多數(shù)的工作平臺相適應(yīng)，能在廣泛的范圍內(nèi)應(yīng)用，具有可變的密鑰長度。加密算法的有效性Unconditionallysecure，絕對安全？永不可破，是理想情況，理論上不可破，密鑰空間無限，在已知密文條件下，方程無解。但是我們可以考慮：破解的代價超過了加密信息本身的價值破解的時間超過了加密信息本身的有效期Computationallysecure，計算安全滿足上述兩個條件Veritifiablesecure,可證明安全（歸約安全）將密碼體制的安全性歸約為某個數(shù)學(xué)問題，其安全性等價于該數(shù)學(xué)問題的可解性直覺：什么是好的加密算法假設(shè)密鑰(password)k是固定的明文和密文是一個映射關(guān)系：單射，即

Ek(x1)!=Ek(x2)ifx1!=x2通常情況是：明文非常有序好的密碼條件下，我們期望得到什么樣的密文隨機(jī)性如何理解隨機(jī)性小的擾動帶來的變化不可知考慮設(shè)計一個加密算法打破明文本身的規(guī)律性隨機(jī)性(可望不可及)非線性(一定要)統(tǒng)計意義上的規(guī)律多次迭代迭代是否會增加變換的復(fù)雜性是否存在通用的框架，用于迭代復(fù)雜性帶來密碼分析的困難和不可知性實踐的檢驗和考驗2.2傳統(tǒng)密碼體制2.2.1置換密碼

2.2.2代換密碼

2.2.3傳統(tǒng)密碼的分析

古典加密方法2.2.1置換密碼假定m=6，密鑰是以下置換：123456--------——————————351642則逆置換為：123456—————————361524假定給出明文：shesellsseashellsbytheseashore首先把明文分為6個字母一組：shesellsseashellsbytheseashore每6個字母按置換函數(shù)進(jìn)行重排，得到相應(yīng)的密文：EESLSHSALSESLSHBLEHSYEETHRAEOS2.2.2代換密碼將明文中的每一個字符被替換成密文中的另一個字符。接收者對密文做反向替換就可以恢復(fù)出明文。單表代換密碼多表代換密碼單表代換密碼（移位密碼）ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425例如：Caesar密碼，k=3

明文M=“pleaseconfirmreceipt”

密文C=“sohdvhfrqilupuhfhlsw”單表代換密碼（替換密碼）單表代換密碼（仿射密碼）例：假定k=(7,3)，7-1mod26=15，加密函數(shù)為ek(x)=7x+3，則相應(yīng)的解密函數(shù)為dk(y)=7-1*(y-3)=15y-19，其中所有的運(yùn)算都是在Z26中。 容易驗證，dk(ek(x))=dk(7x+3)=15(7x+3)-19=x+45-19=x。假設(shè)待加密的明文為HOT。 首先轉(zhuǎn)化這三個字母分別為數(shù)字7，14和19?？傻妹芪拇疄锳XG。多表代換密碼多表代換密碼是以一系列(兩個以上)代換表依次對明文消息的字母進(jìn)行代換的加密方法。例：設(shè)m=6，且密鑰字是CIPHER，這相應(yīng)于密鑰k=(2,8,15,7,4,17)。假定明文串是 thiscryptosystemisnotsecure。首先將明文串轉(zhuǎn)化為數(shù)字串，按6個一組分段，然后模26“加”上密鑰字可得相應(yīng)的密文串： VPXZGIAXIVWPUBTTMJPWIZITWZT單表代換密碼的分析語言的統(tǒng)計特性：語言的頻率特征連接特征重復(fù)特征頻率特征在各種語言中,各個字母的使用次數(shù)是不一樣的,有的偏高,有的偏低,這種現(xiàn)象叫偏用現(xiàn)象.對英文的任何一篇文章，一個字母在該文章中出現(xiàn)的次數(shù)稱作這個字母（在這篇文章中）的頻數(shù)。一個字母的頻數(shù)除以文章的字母總數(shù)，就得到字母的使用頻率。英文字母的普遍使用頻率美國密碼學(xué)家W.F.Friedman在調(diào)查了大量英文資料后,得出英文字母的普遍使用規(guī)律.英文字母普遍的頻率特征英文單字母的相對頻率表(參看表2.3)英文單字母使用頻率分類統(tǒng)計分析示例例2.6假設(shè)從仿射密碼獲得的密文為：FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHR最高頻的密文字母是：R(8次)，D(7次)，E，H，K(各5次)，F(xiàn)，S，V(各4次)假定:R是e的加密，D是t的加密。數(shù)值化有ek(4)=17，且ek

(19)=3。得到線性方程組：4a+b=1719a+b=3這個方程組有惟一解a=6，b=19(在Z26上)。但這是一個非法的密鑰，因為gcd(a，26)=2>1，所以上面的假設(shè)有誤。統(tǒng)計分析示例下一個猜想：R是e的加密，E是t的加密，得a=13，又是不可能的。(gcd(13,26)=13>1)繼續(xù)假定:R是e的加密，且K是t的加密。于是產(chǎn)生了a=3，b=5，這至少是一個合法的密鑰。(gcd(3,26)=1)最后計算相應(yīng)于k=(3，5)的解密函數(shù)，然后解密密文看是否得到了有意義的英文串。得到明文：algorithmsarequitegeneraldefinitionsofarithmeticprocesses單表密碼破譯小結(jié)假定，推翻，再假定，再推翻，直至破譯①對密文字母的頻數(shù)、使用頻率和連接次數(shù)進(jìn)行統(tǒng)計②根據(jù)了解到的密碼編制人員的語言修養(yǎng)，以及手中掌握的密文的統(tǒng)計規(guī)律，多方比較，對明文的語種和密碼種類作出假定③將假定語種的字母頻率與密文字母頻率進(jìn)行比較④首先找出密文中頻率最高的字母⑤根據(jù)字母的頻率特征、連接特征、重復(fù)特征，從最明顯的單詞或字母開始，試探進(jìn)行⑥總結(jié)對抗頻率分析的辦法多名或同音代換密碼多表代換密碼多字母代換密碼多名代換密碼與簡單代換密碼類似，只是映射是一對多的，每個明文字母可以加密成多個密文字母。例如，A可能對應(yīng)于5、13、25B可能對應(yīng)于7、9、31、42當(dāng)對字母的賦值個數(shù)與字母出現(xiàn)頻率成比例時。這時因為密文符號的相關(guān)分布會近似于平均的，可以挫敗頻率分析。然而，若明文字母的其它統(tǒng)計信息在密文中仍很明顯時，同音代替密碼仍然是可破譯的。2.3現(xiàn)代對稱密碼體制現(xiàn)代密碼學(xué)已發(fā)展成兩個重要的分支：（1）對稱加密體制

其典型代表是數(shù)據(jù)加密標(biāo)準(zhǔn)DES（數(shù)據(jù)加密標(biāo)準(zhǔn)）、IDEA（國際數(shù)據(jù)加密算法）、AES（高級加密標(biāo)準(zhǔn)）等算法。（2）公開密鑰加密體制其典型代表是RSA、橢圓曲線加密等。2.3現(xiàn)代對稱密碼體制按照代碼處理組織分類：分組密碼體制:數(shù)據(jù)在密鑰的作用下，一組一組、等長地被處理，且通常情況是明、密文等長。以DES和AES為代表。序列密碼體制：序列密碼將明文消息序列m=m1，m

2，…，mn用密鑰流序列k=k1，k2，…，kn逐位加密,得密文序列c=c1，c2，…，cn。以RC4為代表。DES概覽（一）DES概覽

初始置換IP和逆置換IP-1f(A,J)的運(yùn)算過程DES（二）子密鑰計算

DES（三）DES工作模式

ElectronicCodebook(ECB)模式

DESCipherBlockChaining(CBC)模式OutputFeedback(OFB)模式DESCipherFeedback(CFB)模式DESOutputFeedback(OFB)模式DES（四）DES安全性

對DES的批評主要集中在以下幾點：(1)DES的密鑰長度(56位)可能太短；(2)DES的迭代次數(shù)可能太少；(3)S-盒中可能有不安全因素；(4)DES的一些關(guān)鍵部分不應(yīng)當(dāng)保密.AES算法1997年4月15日美國國家標(biāo)準(zhǔn)和技術(shù)研究所NIST發(fā)起了征集AES算法的活動并成立了專門的AES工作組對AES的基本要求：比三重DES快；但至少和三重DES同樣安全；所有設(shè)計必須公開；必須支持128、192和256位密鑰長度；必須是既可用硬件或又可用軟件實現(xiàn)；算法必須公開或無歧視許可。1997年9月12日在聯(lián)邦登記處公布了征集AES候選算法的通告1998年8月20日NIST召開了第一次候選大會并公布了15個候選算法1999年3月22日舉行了第二次AES候選會議從中選出5個AES將成為新的公開的聯(lián)邦信息處理標(biāo)準(zhǔn)入選AES的五種算法是MARS、RC6、Serpent、Twofish、Rijndael2000年10月2日美國商務(wù)部部長NormanY.Mineta宣布經(jīng)過三年來世界著名密碼專家之間的競爭,“Rijndael數(shù)據(jù)加密算法”最終獲勝為此而在全球范圍內(nèi)角逐了數(shù)年的激烈競爭宣告結(jié)束這一新加密標(biāo)準(zhǔn)的問世將取代DES數(shù)據(jù)加密標(biāo)準(zhǔn)成為21世紀(jì)保護(hù)國家敏感信息的高級算法.AES(Rijndael)算法：帶有可變塊長和可變密鑰長度的多輪迭代塊密碼算法。塊長和密鑰長度可以分別指定為128、192或256位。算法執(zhí)行的迭代輪數(shù)Nr由以32位字為單位的分組長度Nb和密鑰長度Nk決定。（參看P39:圖2.19）例如，設(shè)分組長度為128,M=(b0,b1,…b127)

=(B00,B01,B02,B03,B10,B11,B12,B13,B20,B21,B22,B23,B30,B31,B32,B33)=(W0,W1,W2,W3)這里Bij為字節(jié),Wk為32位字，則Nb=4。取密鑰字長Nk=4，則迭代輪數(shù)Nr=10。Rijndael算法中Nr的取值算法過程概述

AES(Rijndael)算法結(jié)構(gòu)與DES類似：將分組明文M與輪密鑰K0進(jìn)行異或,作為第1輪的輸入。每輪迭代由函數(shù)變換E(M’)和異或運(yùn)算構(gòu)成，其中Ki為各輪的輪密鑰。各輪迭代變換如下：CODE_Round(M,RoundKey){C=ByteSub(M);C=ShiftRow(C);C=MixColumn(C);Return(C⊕RoundKey);}最后一輪的處理稍有不同：CODE_Last_Round(M1,RoundKey){C=ByteSub(M1);C=ShiftRow(C);Return(C⊕RoundKey);}Rijndael加密流程AES各輪AES加密循環(huán)（除最后一輪外）均包含4個步驟:(1)輪密鑰加運(yùn)算(AddRoundKey)矩陣中的每一個字節(jié)都與該次輪密鑰（Roundkey）做XOR運(yùn)算；每個子密鑰由密鑰生成方案產(chǎn)生。(2)字節(jié)代換(SubBytes)通過一個非線性的替換函數(shù)，用查找表的方式把每個字節(jié)替換成對應(yīng)的字節(jié)。(3)行位移變換(ShiftRows)將矩陣中的每個橫列進(jìn)行循環(huán)式移位。

(4)列混合變換(MixColumns)為了充分混合矩陣中各個直行的操作。這個步驟使用線性轉(zhuǎn)換來混合每組內(nèi)聯(lián)的四個字節(jié)。AES(1)輪密鑰加運(yùn)算(AddRoundKey)在每次的加密循環(huán)中，都會由主密鑰產(chǎn)生一把輪密鑰，這把密鑰大小會跟原矩陣一樣，然后與原矩陣中每個對應(yīng)的字節(jié)作異或（⊕）加法。AES(2)字節(jié)代換(SubBytes)矩陣中的各字節(jié)通過一個8位的S-box進(jìn)行轉(zhuǎn)換。S-box與GF(28)上的乘法逆有關(guān)。為了避免簡單代數(shù)性質(zhì)的攻擊，S-box結(jié)合了乘法逆及一個可逆的仿射變換矩陣建構(gòu)而成。此外在建構(gòu)S-box時，刻意避開了固定點與反固定點，即以S-box替換字節(jié)的結(jié)果會相當(dāng)于錯排的結(jié)果。AES（3）行位移變換(ShiftRows)每一行都向左循環(huán)位移某個偏移量。在AES中（區(qū)塊大小128位），第一行維持不變，第二行里的每個字節(jié)都向左循環(huán)移動一格。同理，第三行及第四行向左循環(huán)位移的偏移量就分別是2和3。經(jīng)過ShiftRows之后，矩陣中每一豎列，都是由輸入矩陣中的每個不同列中的元素組成。AESAES(4)列混合變換(MixColumns)每行的四個字節(jié)通過線性變換互相結(jié)合。每一行的四個元素分別作為1,x,x2,x3的系數(shù)，合并即為GF(28)中的一個多項式，然后將此多項式和一個固定的多項式：c(x)=3x3+x2+x+2在模取x4+1下相乘。MixColumns函數(shù)接受4個字節(jié)的輸入，輸出4個字節(jié)，每一個輸入的字節(jié)都會對輸出的四個字節(jié)造成影響。因此ShiftRows和MixColumns兩步驟為這個密碼系統(tǒng)提供了擴(kuò)散性。AES(4)列混合變換(MixColumns)每行的四個字節(jié)通過線性變換互相結(jié)合。每一行的四個元素分別作為1,x,x2,x3的系數(shù)，合并即為GF(28)中的一個多項式，然后將此多項式和一個固定的多項式c(x)=3x3+x2+x+2在模取x4+1下相乘。MixColumns函數(shù)接受4個字節(jié)的輸入，輸出4個字節(jié)，每一個輸入的字節(jié)都會對輸出的四個字節(jié)造成影響。因此ShiftRows和MixColumns兩步驟為這個密碼系統(tǒng)提供了擴(kuò)散性。AES（二）密鑰擴(kuò)展（ExpandedKey）算法（1）當(dāng)Nk≤6時（即AES算法密鑰長度為128和192比特時）KeyExpansion(byteKey[4*Nk,w[Nb*(Nr+1)]){for(i=0;i<Nk;i++)W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);

for(i=Nk;i<Nb*(Nr+1);i++){temp=W[i-1];if(i%Nk==0)temp=SubByte(RotByte(temp))^Rcon[i/Nk];

W[i]=W[i-Nk]^temp;}}（2）當(dāng)Nk＞6時（即AES算法密鑰長度為256比特時）KeyExpansion(byteKey[4*Nk,w[Nb*(Nr+1)]){for(i=0;i<Nk;i++)W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);

for(i=Nk;i<Nb*(Nr+1);i++){temp=W[i-1];if(i%Nk==0)temp=SubByte(RotByte(temp))^Rcon[i/Nk];elseif(i%Nk==4)

temp=SubByte(temp);W[i]=W[i-Nk]^temp;}}AES（三）AES安全性2002年成為有效標(biāo)準(zhǔn)（旁道攻擊成功一次）AES算法的安全性目前是可靠的；針對AES密碼系統(tǒng)，不斷有新的攻擊方法提出，包括功耗分析、積分攻擊和旁道攻擊等，尚不能對AES構(gòu)成實際的威脅；旁道攻擊不攻擊密碼本身，而是攻擊那些實現(xiàn)于不安全系統(tǒng)上的加密系統(tǒng)。RC4RC4是由麻省理工學(xué)院RonRivest開發(fā)的可變密鑰長度的流密碼，是世界上普遍使用的流密碼之一。RC4是一種基于非線性數(shù)據(jù)表變換的流密碼，它以一個足夠大的數(shù)據(jù)表S為基礎(chǔ)，對表進(jìn)行非線性變換，產(chǎn)生非線性的密鑰流序列。RC4RC4密鑰調(diào)度算法初始化數(shù)據(jù)表S

forifrom0to255 S[i]:=iendforj:=0forifrom0to255 j:=(j+S[i]+K[imodkeylength])mod256 swapvaluesofS[i]andS[j]endforRC4RC4密鑰流的每個輸出都是數(shù)據(jù)表S中的一個隨機(jī)元素。密鑰流的生成需要兩個過程：密鑰調(diào)度算法用于設(shè)置數(shù)據(jù)表S的初始排列；偽隨機(jī)生成算法．用于選取隨機(jī)元素并修改S的原始排列順序。優(yōu)點:軟件實現(xiàn)容易，已經(jīng)應(yīng)用于Microsoftwindows、LotusNotes等軟件，用于安全套接字層SSL(SecureSocketLayer)保護(hù)因特網(wǎng)的信息流。2.4非對稱密碼體制特點：在非對稱密碼體制中，有一對密鑰，其中pk是公開的，即公開密鑰，也就是說，這個密鑰可以讓每個人都知道。另一個密鑰sk是保密的，這個密鑰稱為私人密鑰，簡稱私鑰。在非對稱密碼體制中，進(jìn)行加密和解密時使用不同的加密密鑰和解密密鑰，這里要求加密密鑰和解密密鑰不能相互推導(dǎo)出來或者很難推導(dǎo)出來。一般來說，非對稱密碼體制都是建立在嚴(yán)格的數(shù)學(xué)基礎(chǔ)上，公開密鑰和私人密鑰的產(chǎn)生是通過數(shù)學(xué)方法產(chǎn)生的，公鑰算法的安全性是建立在某個數(shù)學(xué)問題很難解決的基礎(chǔ)上。2.4.1RSA非對稱密碼體制RSA發(fā)明人,從左到右RonRivest,AdiShamir,LeonardAdleman.照片攝于1978年2.4.1RSA非對稱密碼體制它的安全性一直未從理論上得到證明，但至今未被完全攻破。RSA具有的優(yōu)勢：為實現(xiàn)數(shù)字簽名和數(shù)字認(rèn)證提供了合適的手段，解決了DES不能解決的問題；在具有多個節(jié)點的網(wǎng)絡(luò)中，大大減輕了密鑰分配與管理的壓力（在N個節(jié)點的網(wǎng)絡(luò)中，用DES算法進(jìn)行加密，需要N(N-1)/2對密鑰，而RSA僅需要N對）RSA的數(shù)學(xué)基礎(chǔ)定義1：對一個自然數(shù)P，如果P只能被1和自身除盡時，則稱P為素數(shù)（或質(zhì)數(shù)），否則為合數(shù)。定義2：如果整數(shù)a與整數(shù)b的最大公約數(shù)是1，則稱a與b是互為質(zhì)數(shù)。例如：2和3，5和7等都是互為質(zhì)數(shù)。定義3：歐拉函數(shù)定義為：φ(r)={1、2、3、···、r}與r互為質(zhì)數(shù)的整數(shù)個數(shù)。例如：φ(5)=4,φ(6)=2可以證明：φ(r)=r（1－1/P1）（1－1/P2）···（1－1/Pn）P1

、P2···Pn是r的質(zhì)因子。例：6=2*3,φ(6)=6(1-1/2)(1-1/3)=2r=20，20=2×2×5，

φ(20)=20*(1-1/2)*(1-1/5)=8即在1～20個整數(shù)中8個與20互質(zhì):1，3，7，9，11，13，17，19。定義4：兩個整數(shù)a、b分別被m除，如果所得余數(shù)相同，則稱a與b對模m是同余的，記作：a≡b（modm）2.4.1RSA非對稱密碼體制算法描述：(1)選擇一對不同的、足夠大的素數(shù)p，q,計算n=pq;(2）計算Φ(n)=(p-1)(q-1);(3)找一個與Φ(n)互質(zhì)的數(shù)e(gcd(e,Φ(n))=1)且1<e<Φ(n),令sk=e;(4)計算pk，使得pk*sk≡1modΦ(n)。(pk=sk-1modΦ(n))(5)公鑰KU=(sk,n)，私鑰KR=(pk,n)。(6)加密時，先將明文變換成0至n-1的一個整數(shù)mi。若明文較長，可先分割成適當(dāng)?shù)慕M，然后再進(jìn)行加密。設(shè)密文為Ci，則加密過程為：(7)解密過程為：RSA加密和解密的例子：在以下實例中只選取小數(shù)值的素數(shù)p,q,以及e.假設(shè)用戶A需要將明文“key”通過RSA加密后傳遞給用戶B。

（1）生成公私密鑰(e,n)和(d,n)。

令p=3，q=11，得出n=p×q=3×11=33；

Φ

(n)=(p-1)(q-1)=2×10=20；取e=3，（3與20互質(zhì)）則e×d≡1modΦ

(n)，即3×d≡1mod20。

pk怎樣取值呢？可以用試算的辦法來尋找。試算結(jié)果見下表：當(dāng)d=7時，e×d≡1modΦ

(n)同余等式成立。因此，可令pk=7。從而可以設(shè)計出一對公私密鑰，加密密鑰（公鑰）為：KU=(e,n)=(3,33)，解密密鑰（私鑰）為：KR=(d,n)=(7,33)。

擴(kuò)展的Eulid算法：如果gcd(a,n)=1，a關(guān)于模n的乘法逆元a-1存在，如何求出a-1？intExtended_Eulid(inta,intn)//a、n為正整數(shù)，0<a<n-1{intx1,x2,x3,y1,y2,y3,t1,t2,t3,q;x1=1;x2=0;x3=n;y1=0,y2=1,y3=a;while(y3>1){q=x3divy3;t1=(x1-q*y1)(modn);t2=(x2-q*y2)(modn);t3=(x3-q*y3)(modn);x1=y1;x2=y2;x3=y3;y1=t1;y2=t2;y3=t3;}if(y3==0)return(-1);//x3=gcd(a,n)>0,a-1不存在elsereturn(y2);//這時y3=gcd(a,n)=1,y2=a-1(modn)}計算：7-1(mod24)，9-1(mod24)x1x2x3y1y2y3qt1t2t31023017312020171202320101120220101

n=23,a=7,10=7-1(mod23).

利用模n乘的運(yùn)算性質(zhì)：(a×b)modn=((amodn)×(bmodn))modn計算z=(ammodn)，考慮m的二進(jìn)制表示：(bk-1,bk-2,..b1,b0)：有：

例計算z=(6677mod119)77=(1001101)2=26+23+22+20=64+8+4+1

(6677mod119)=((6664mod119)×(668mod119)×(664mod119)×66)mod119=

(6664mod119×((668mod119)×((664mod119)×66)mod119)mod119)mod119

指數(shù)i66itz=1166166662662724664=72267198668=6728687166616=862183266328621819因為：77=(1001101)=26+

28+24+20所以：z=(6677mod119)

=(18×(86×(67×66)mod119)mod119)mod119=(18×(86×19)mod119)mod119=(18×87)mod119=19由此得快速求冪算法：intpower(inta,intn,intm)//求an(modm){intz=1,t;for(t=a;n>0;n/=2){if(n%2==1)z=(z*t)%m;t=(t*t)%m;}return(z);}例取p=7,q=17。計算n=p×q=7×17=119，φ(n)=(p-1)(q-1)=6×16=96。選e=77,滿足gcd(e,φ(n))=gcd(77,96)=1，得公鑰Kc={77,119}d=e-1(modφ(n))=77-1(mod96)=5，得私鑰Kp={5,119}已知明文M=19，加密：C=(Memoden)=(195mode119)=66解密：M=(Cdmoden)=(6677mode119)=19例2英文數(shù)字化：用戶A需要將明文“key”通過RSA加密后傳遞給用戶B。

。

將明文信息數(shù)字化，并將每塊兩個數(shù)字分組。假定明文英文字母編碼表為按字母順序排列數(shù)值則得到分組后的key的明文信息為：11，05，25。（3）明文加密

用戶加密密鑰(3,33)將數(shù)字化明文分組信息加密成密文。由C≡Me(modn)得：得到相應(yīng)的密文信息為：11，26，16。C1≡(M1)e(modn)=113(mod33)=11C2≡(M2)e(modn)=53(mod33)=26C3≡(M3)e(modn)=253(mod33)=16（4）密文解密。

用戶B收到密文，若將其解密，只需要計算，即：用戶B得到明文信息為：11，05，25。根據(jù)上面的編碼表將其轉(zhuǎn)換為英文，我們又得到了恢復(fù)后的原文“key”。26實際運(yùn)用時，要比這復(fù)雜得多。由于RSA算法的公鑰私鑰的長度（模長度）要到1024位甚至2048位才能保證安全，因此，p、q、e的選取、公鑰私鑰的生成，加密解密模指數(shù)運(yùn)算都有一定的計算程序，需要仰仗計算機(jī)的高速計算來完成。

RSA的安全性：RSA-129的故事

鶚鳥（ossifrage），又名髭兀鷹（lammergeier），是阿爾卑斯山上一種稀有的肉食禿鷹。它的翅膀展開將近十米寬。鳥名的字面含義是“碎骨”。顧名思義，其習(xí)性令人毛骨悚然。MirtinGardner在1977年“ScientificAmerican”的專欄文章中介紹了RSA碼。為了顯示這一技術(shù)的威力，RSA公司的研究人員用一個129位的數(shù)N和一個4位數(shù)e對這個關(guān)于禿鷹的消息作了編碼。Gardner刊登了那個密文，同時給出了N和e。RSA公司還懸賞100美元，獎給第一個破譯這密碼的人。一批因子分解迷(約有六百余人，分布在二十幾個國家）經(jīng)過八個月的努力最后于1994年4月為RSA-129找到了64位數(shù)和65位數(shù)兩個素數(shù)因子。N=114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541=3490529510847650949147849619903898133417764638493387843990820577*32769132993266709549961988190834461413177642967992942539798288533RSA的安全性由n求(n)等價于分解n，如果分解n=p×q，則立即獲得(n)=(p－1)(q－1)，從而能夠確定e的模(n)乘法逆dRSA的安全性基于分解大整數(shù)的困難性假定RSA-129歷時8個月(曾經(jīng)預(yù)言需要4*1016年)被于1996年4月被成功分解來自兩個方面的威脅人類計算能力的不斷提高分解算法的進(jìn)一步改進(jìn)。分解算法過去都采用二次篩法，如對RSA-129的分解。而對RSA-130的分解則采用了一個新算法，稱為推廣的數(shù)域篩法，該算法在分解RSA130時所做的計算僅比分解RSA-129多10%。將來也可能還有更好的分解算法，因此在使用RSA算法時對其密鑰的選取要特別注意其大小。估計在未來一段比較長的時期，密鑰長度介于1024比特至2048比特之間的RSA是安全的。幾個建議為了防止可以很容易地分解n，RSA算法的發(fā)明者建議p和q還應(yīng)滿足下列限制條件：P和q的長度應(yīng)僅相差幾位。對于1024位的密鑰而言，p和q都應(yīng)在1075到10100之間。(p-1)和(q-1)都應(yīng)有一個大的素因子。gcd(p-1,q-1)應(yīng)該較小。RSA的缺點RSA的缺點：a)產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。b)分組長度太大，為保證安全性，n至少也要600bits以上，使運(yùn)算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。因此，使用RSA只能加密少量數(shù)據(jù)，大量的數(shù)據(jù)加密還要靠對稱密碼算法。ElGamal密碼

ElGamal是1985年由T.EIGamal提出的一個著名的公鑰密碼算法該算法既能用于數(shù)據(jù)加密也能用于數(shù)字簽名其安全性是依賴于計算有限域上離散對數(shù)這一難題預(yù)備知識：離散對數(shù)本原根

假設(shè)gcd(a,n)=1,如果m是使am

≡1modn成立的最小正整數(shù)，則稱它是a對模n的指數(shù)，記為Ordna

若Ordna=φ(n)，則稱a是模n的本原根(primitiveroot)，也稱生成元*如果n是素數(shù)，則φ(n)=n-1求模7和模15的本原根對于模7而言，滿足gcd(a,n)=1的a是{1,2,3,4,5,6}，將它們的指數(shù)列表如下

a123456Ord7a136362從上表可以看到，當(dāng)a是3和5時，Ord7a=φ(7)，因此，3和5是模7的本原根。對于模15而言，滿足gcd(a,n)=1的a是{1,2,4,7,8,11,13,14}，將它們的指數(shù)列表如下：上表中不存在一個a，使Ord15a=φ(15)，所以模15沒有本原根定理2.18模m的本原根存在的必要條件是m=2,4,pa,或者2pa，此處p是奇素數(shù)a12478111314Ord7a14244242離散對數(shù)模運(yùn)算用于指數(shù)計算可以表示為axmodn，我們稱為模指數(shù)運(yùn)算

定義2.17（離散對數(shù)）對于一個整數(shù)b和素數(shù)n的一個本原根a，可以找到唯一的指數(shù)x，使得b≡ax

modn，其中0≤x≤n-1，指數(shù)x稱為b的以a為基數(shù)的模n的離散對數(shù)模指數(shù)運(yùn)算的逆問題就是找出一個數(shù)的離散對數(shù)，即求解x，使得

ax

≡bmodn由a,x,n求b容易，已知a,b,n求x難1.密鑰產(chǎn)生任選一個大素數(shù)p，使得p-1有大素因子，g是模p的一個本原根，公開p與g。使用者任選一私鑰x，x∈[0,p-1]計算公鑰公開公鑰：y,p,g保密私鑰：x,p2.加密過程對于明文m，選取一個r，r∈[0,p-1]計算則密文為3.解密過程先計算再計算出明文4.簽名過程假設(shè)對消息m簽名，任選一個隨機(jī)數(shù)k，使k∈[0,p-1]計算簽名為(5)簽名驗證過程

需要說明的是，為了避免選擇密文攻擊，ElGamal是對消息m的hash值進(jìn)行簽名，而不是對m簽名與RSA方法比較，ElGamal方法具有以下優(yōu)點：(1)系統(tǒng)不需要保存秘密參數(shù)，所有的系統(tǒng)參數(shù)均可公開；(2)同一個明文在不同的時間由相同加密者加密會產(chǎn)生不同的密文ElGamal方法的計算復(fù)雜度比RSA方法要大。Diffie-Hellman密鑰交換Diffie-Hellman密鑰交換是W.Diffie和M.Hellman于1976年提出的第一個公開密鑰算法已在很多商業(yè)產(chǎn)品中得以應(yīng)用算法的惟一目的是使得兩個用戶能夠安全地交換密鑰，得到一個共享的會話密鑰算法本身不能用于加、解密該算法的安全性基于求離散對數(shù)的困難性。假定p是一個素數(shù)，α是其本原根，將p和α公開。假設(shè)A和B之間希望交換會話鑰。--用戶A：--用戶B：

Diffie-Hell