第2章密碼技術2.1密碼學概述2.2傳統密碼體制2.3現代對稱密碼體制2.4非對稱密碼體制2.5密碼學的新進展例：設明文是一串二進制序列，加密和解密算法都采用模2運算，即異或運算⊕，加密密鑰和解密密鑰相同。若明文P=11001100加密和解密密鑰K=11000111則加密后的密文C=P⊕K=00001011解密后的密文P=C⊕K=11001100密碼學的發展歷史自人類社會出現戰爭便產生了密碼

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

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

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

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

2.2.2代換密碼

2.2.3傳統密碼的分析

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

明文M=“pleaseconfirmreceipt”

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

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

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

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

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

DES（三）DES工作模式

ElectronicCodebook(ECB)模式

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

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

AES(Rijndael)算法結構與DES類似：將分組明文M與輪密鑰K0進行異或,作為第1輪的輸入。每輪迭代由函數變換E(M’)和異或運算構成，其中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加密循環（除最后一輪外）均包含4個步驟:(1)輪密鑰加運算(AddRoundKey)矩陣中的每一個字節都與該次輪密鑰（Roundkey）做XOR運算；每個子密鑰由密鑰生成方案產生。(2)字節代換(SubBytes)通過一個非線性的替換函數，用查找表的方式把每個字節替換成對應的字節。(3)行位移變換(ShiftRows)將矩陣中的每個橫列進行循環式移位。

(4)列混合變換(MixColumns)為了充分混合矩陣中各個直行的操作。這個步驟使用線性轉換來混合每組內聯的四個字節。AES(1)輪密鑰加運算(AddRoundKey)在每次的加密循環中，都會由主密鑰產生一把輪密鑰，這把密鑰大小會跟原矩陣一樣，然后與原矩陣中每個對應的字節作異或（⊕）加法。AES(2)字節代換(SubBytes)矩陣中的各字節通過一個8位的S-box進行轉換。S-box與GF(28)上的乘法逆有關。為了避免簡單代數性質的攻擊，S-box結合了乘法逆及一個可逆的仿射變換矩陣建構而成。此外在建構S-box時，刻意避開了固定點與反固定點，即以S-box替換字節的結果會相當于錯排的結果。AES（3）行位移變換(ShiftRows)每一行都向左循環位移某個偏移量。在AES中（區塊大小128位），第一行維持不變，第二行里的每個字節都向左循環移動一格。同理，第三行及第四行向左循環位移的偏移量就分別是2和3。經過ShiftRows之后，矩陣中每一豎列，都是由輸入矩陣中的每個不同列中的元素組成。AESAES(4)列混合變換(MixColumns)每行的四個字節通過線性變換互相結合。每一行的四個元素分別作為1,x,x2,x3的系數，合并即為GF(28)中的一個多項式，然后將此多項式和一個固定的多項式：c(x)=3x3+x2+x+2在模取x4+1下相乘。MixColumns函數接受4個字節的輸入，輸出4個字節，每一個輸入的字節都會對輸出的四個字節造成影響。因此ShiftRows和MixColumns兩步驟為這個密碼系統提供了擴散性。AES(4)列混合變換(MixColumns)每行的四個字節通過線性變換互相結合。每一行的四個元素分別作為1,x,x2,x3的系數，合并即為GF(28)中的一個多項式，然后將此多項式和一個固定的多項式c(x)=3x3+x2+x+2在模取x4+1下相乘。MixColumns函數接受4個字節的輸入，輸出4個字節，每一個輸入的字節都會對輸出的四個字節造成影響。因此ShiftRows和MixColumns兩步驟為這個密碼系統提供了擴散性。AES（二）密鑰擴展（ExpandedKey）算法（1）當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）當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年成為有效標準（旁道攻擊成功一次）AES算法的安全性目前是可靠的；針對AES密碼系統，不斷有新的攻擊方法提出，包括功耗分析、積分攻擊和旁道攻擊等，尚不能對AES構成實際的威脅；旁道攻擊不攻擊密碼本身，而是攻擊那些實現于不安全系統上的加密系統。RC4RC4是由麻省理工學院RonRivest開發的可變密鑰長度的流密碼，是世界上普遍使用的流密碼之一。RC4是一種基于非線性數據表變換的流密碼，它以一個足夠大的數據表S為基礎，對表進行非線性變換，產生非線性的密鑰流序列。RC4RC4密鑰調度算法初始化數據表S

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

、P2···Pn是r的質因子。例：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個整數中8個與20互質:1，3，7，9，11，13，17，19。定義4：兩個整數a、b分別被m除，如果所得余數相同，則稱a與b對模m是同余的，記作：a≡b（modm）2.4.1RSA非對稱密碼體制算法描述：(1)選擇一對不同的、足夠大的素數p，q,計算n=pq;(2）計算Φ(n)=(p-1)(q-1);(3)找一個與Φ(n)互質的數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的一個整數mi。若明文較長，可先分割成適當的組，然后再進行加密。設密文為Ci，則加密過程為：(7)解密過程為：RSA加密和解密的例子：在以下實例中只選取小數值的素數p,q,以及e.假設用戶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互質）則e×d≡1modΦ

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

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

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

擴展的Eulid算法：如果gcd(a,n)=1，a關于模n的乘法逆元a-1存在，如何求出a-1？intExtended_Eulid(inta,intn)//a、n為正整數，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乘的運算性質：(a×b)modn=((amodn)×(bmodn))modn計算z=(ammodn)，考慮m的二進制表示：(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

指數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英文數字化：用戶A需要將明文“key”通過RSA加密后傳遞給用戶B。

。

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

用戶加密密鑰(3,33)將數字化明文分組信息加密成密文。由C≡Me(modn)得：得到相應的密文信息為：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。根據上面的編碼表將其轉換為英文，我們又得到了恢復后的原文“key”。26實際運用時，要比這復雜得多。由于RSA算法的公鑰私鑰的長度（模長度）要到1024位甚至2048位才能保證安全，因此，p、q、e的選取、公鑰私鑰的生成，加密解密模指數運算都有一定的計算程序，需要仰仗計算機的高速計算來完成。

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

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

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

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

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

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

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

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

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

ax

≡bmodn由a,x,n求b容易，已知a,b,n求x難1.密鑰產生任選一個大素數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.簽名過程假設對消息m簽名，任選一個隨機數k，使k∈[0,p-1]計算簽名為(5)簽名驗證過程

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

Diffie-Hell