計算機(jī)信息安全技術(shù) 課件 第2章 密碼技術(shù)

第2章密碼技術(shù)2.1密碼學(xué)概述2.2傳統(tǒng)密碼體制2.3現(xiàn)代對稱密碼體制2.4非對稱密碼體制2.5密碼學(xué)的新進(jìn)展

例：設(shè)明文是一串二進(jìn)制序列，加密和解密算法都采用模2運算，即異或運算⊕，加密密鑰和解密密鑰相同。若明文

P=11001100加密和解密密鑰

K=11000111則加密后的密文

C=P⊕K=00001011解密后的密文

P=C⊕K=110011002.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）

（2）已知明文攻擊（KnownPlaintextAttack）

（3）選擇明文攻擊（ChosenPlaintextAttack）

（4）選擇密文攻擊（ChosenCiphertextAttack）

（5）選擇文本攻擊(ChosenTextAttack)

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，滿足上述兩個條件直覺：什么是好的加密算法假設(shè)密碼(password)k是固定的明文和密文是一個映射關(guān)系：單射，即

通常情況是：明文非常有序好的密碼條件下，我們期望得到什么樣的密文隨機(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單表代換密碼（替換密碼）單表代換密碼（仿射密碼）例：假定k=(7,3)，7-1

mod26=15，加密函數(shù)為ek(x)=7x+3，則相應(yīng)解密函數(shù)為dk(y)=15(y-3)=15y-19，其中所有的運算都是在Z26中。 容易驗證，dk(ek(x))=dk(7x+3)=15(7x+3)-19=x+45-19=x。假設(shè)待加密的明文為hot。 首先轉(zhuǎn)化三個字母分別為數(shù)字7，14和19?？傻妹芪拇疄锳XG。

單表代換密碼的分析語言的統(tǒng)計特性：語言的頻率特征連接特征重復(fù)特征頻率特征在各種語言中,各個字母的使用次數(shù)是不一樣的,有的偏高,有的偏低,這種現(xiàn)象叫偏用現(xiàn)象.對英文的任何一篇文章，一個字母在該文章中出現(xiàn)的次數(shù)稱作這個字母（在這篇文章中）的頻數(shù)。一個字母的頻數(shù)除以文章的字母總數(shù)，就得到字母的使用頻率。英文字母的普遍使用頻率美國密碼學(xué)家W.F.Friedman在調(diào)查了大量英文資料后,得出英文字母的普遍使用規(guī)律.英文字母普遍的頻率特征英文單字母的相對頻率表英文單字母使用頻率分類統(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，又是不可能的。繼續(xù)假定R是e的加密，且K是t的加密。于是產(chǎn)生了a=3，b=5，這至少是一個合法的密鑰。最后計算相應(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é)對抗頻率分析的辦法多名或同音代換密碼多表代換密碼多字母代換密碼多表代換密碼多表代換密碼是以一系列(兩個以上)代換表依次對明文消息的字母進(jìn)行代換的加密方法。例：設(shè)m=6，且密鑰字是CIPHER，這相應(yīng)于密鑰k=(2,8,15,7,4,17)。假定明文串是

thiscryptosystemisnotsecure。首先將明文串轉(zhuǎn)化為數(shù)字串，按6個一組分段，然后模26“加”上密鑰字可得相應(yīng)的密文串：

VPXZGIAXIVWPUBTTMJPWIZITWZT多表代換密碼有名的多表代換密碼有VigenèreBeaufortRunning-KeyVerna轉(zhuǎn)輪機(jī)(RotorMachine)多表代換密碼Vigenère密碼1858年提出的移位代換密碼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、橢圓曲線加密、NTRU算法等。2.3現(xiàn)代對稱密碼體制序列密碼體制和分組密碼體制分組密碼體制:數(shù)據(jù)在密鑰的作用下，一組一組、等長地被處理，且通常情況是明、密文等長。一般以DES和AES為代表。序列密碼體制：序列密碼將明文消息序列m=m1，m

2，…，mn用密鑰流序列k=k1，k2，…，kn逐位加密,得密文序列c=c1，c2，…，cn。以RC4為代表。DES概述數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）是迄今為止使用最為廣泛的加密算法。作為分組密碼的典型代表，它是IBM公司在Lucifer密碼的基礎(chǔ)上改進(jìn)的，已經(jīng)有40多年的歷史。1977年1月，DES被正式批準(zhǔn)為美國聯(lián)邦信息處理標(biāo)準(zhǔn)，直到1998年12月才被AES取代。DES算法描述DES是分組加密算法，它以64位（二進(jìn)制）為一組，64位明文輸入，64位密文輸出。密鑰長度為56位，但密鑰通常表示為64位，并分為8組，每組第8位作為奇偶校驗位，以確保密鑰的正確性，對用戶來說每組密鑰仍是56位。利用密鑰，通過傳統(tǒng)的置換、代換和異或等變換，實現(xiàn)二進(jìn)制明文的加密與解密。代換運算置換運算初始置換IP58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157逆置換IP-140848165614643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725DES框圖（一）DES框圖f(A,J)的運算過程DES（二）子密鑰計算

DES（三）DES工作模式

ElectronicCodebook(ECB)

模式

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

對DES的批評主要集中在以下幾點：

(1)DES的密鑰長度(56位)可能太短；

(2)DES的迭代次數(shù)可能太少；

(3)S-盒中可能有不安全因素；

(4)DES的一些關(guān)鍵部分不應(yīng)當(dāng)保密.DES安全性1977年，迪菲和海爾曼提出了一部造價約2千萬美元的破解器，可以在一天內(nèi)找到一個DES密鑰。1993年，邁克爾·維納設(shè)計了一部造價約1百萬美元的破解器，大約可以在7小時內(nèi)找到一個密鑰。然而，這些早期的設(shè)計并沒有被實現(xiàn)，至少沒有公開的實現(xiàn)。在1990年代晚期，DES開始受到實用的攻擊。1997年，RSA數(shù)據(jù)安全公司贊助了一系列的競賽，獎勵第一個成功破解以DES加密的信息的隊伍1萬美元，洛克·韋爾謝什（RockeVerser），馬特·柯廷（MattCurtin）和賈斯廷·多爾斯基（JustinDolske）領(lǐng)導(dǎo)的DESCHALL計劃獲勝，該計劃使用了數(shù)千臺連接到互聯(lián)網(wǎng)的計算機(jī)的閑置計算能力。1998年，電子前哨基金會（EFF）制造了一臺DES破解器，造價約$250,000。該破解器可以用稍多于2天的時間暴力破解一個密鑰，它顯示了迅速破解DES的可能性。AES（AdvancedEncryptionStandard）AES使用的是置換-組合架構(gòu)。AES在軟件及硬件上都能快速地加解密，相對來說較易于實作，且只需要很少的內(nèi)存。作為一個新的加密標(biāo)準(zhǔn)，目前正被部署應(yīng)用到更廣大的范圍。AES（AdvancedEncryptionStandard）

(一）算法過程概述

AES各輪AES加密循環(huán)（除最后一輪外）均包含4個步驟:(1)輪密鑰加運算(AddRoundKey)矩陣中的每一個字節(jié)都與該次輪密鑰（Roundkey）做XOR運算；每個子密鑰由密鑰生成方案產(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)輪密鑰加運算(AddRoundKey)在每次的加密循環(huán)中，都會由主密鑰產(chǎn)生一把輪密鑰，這把密鑰大小會跟原矩陣一樣，然后與原矩陣中每個對應(yīng)的字節(jié)作異或（⊕）加法。AES(1)輪密鑰加運算(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)而成。

AES11000110=1000111111000111111000111111000111111000011111000011111000011111y0y1y2y3y4y5y6y7.⊕x0x1x2x3x4x5x6x7(2)字節(jié)代換(SubBytes)代換表(即S-盒)是可逆的，由以下兩個變換得到：首先，將每個狀態(tài)字節(jié)看作GF(28)上的元素，映射到自己的乘法逆元。其次，對該字節(jié)轉(zhuǎn)換成二進(jìn)制數(shù)，做如下的(GF(2)上的仿射變換：AES(2)字節(jié)代換(SubBytes)狀態(tài)矩陣按照下面的方式映射成為一個新的字節(jié)：把該字節(jié)的高4位作為行值，低4位作為列值，得到S盒或逆S盒的對應(yīng)元素作為輸出。例如輸入字節(jié)0x12，取S盒的第0x01行盒0x02列，得到0xC9。S盒代換表0123456789ABCDEF0637C777BF26B6FC53001672BFED7AB761CA82C97DFA5947F0ADD4A2AF9CA472C02B7FD9326363FF7CC34A5E5F171D83115304C723C31896059A071280E2EB27B275409832C1A1B6E5AA0523BD6B329E32F84553D100ED20FCB15B6ACBBE394A4C58CF6D0EFAAFB434D338545F9027F503C9FA8751A3408F929D38F5BCB6DA2110FFF3D28CD0C13EC5F974417C4A77E3D645D1973960814FDC222A908846EEB814DE5E0BDBAE0323A0A4906245CC2D3AC6291951479BE7C8376D8DD54EA96C56F4EA657AAE08CBA78252E1CA6B4C6E8DD741F4BBD8B8AD703EB5664803F60E613557B986C11D9EEE1F8981169D98E949B1E87E9CE5528DFF8CA1890DBFE6426841992D0FB054BB16AES(2)字節(jié)代換(SubBytes)此外在建構(gòu)S-box時，刻意避開了固定點與反固定點，即以S-box替換字節(jié)的結(jié)果會相當(dāng)于錯排的結(jié)果。1)S盒變換是AES的唯一非線性變換，是AES安全的關(guān)鍵；2）AES使用16個相同的S盒，DES使用8個不同的S盒；3）AES的S盒有8位輸入，8位輸出；DES的S盒有6位輸入，4位輸出。AESAES（3）行位移變換(ShiftRows)每一行都向左循環(huán)位移某個偏移量。在AES中（區(qū)塊大小128位），第一行維持不變，第二行里的每個字節(jié)都向左循環(huán)移動一格。同理，第三行及第四行向左循環(huán)位移的偏移量就分別是2和3。經(jīng)過ShiftRows之后，矩陣中每一豎列，都是由輸入矩陣中的每個不同列中的元素組成。AES(4)列混合變換(MixColumns)列混合運算將狀態(tài)(State)的列看作是有限域GF(28)上的多項式a(x)，與多項式c(x)=03x3+01x2+01x+02相乘(在模(x4＋1)意義下)。b(x)=c(x)xa(x)(modx4+1)b0b1b2b3=02030101010203010101020303010102a0a1a2a3AES(4)列混合變換(MixColumns)在MixColumns步驟中，每個直行都在modulo之下，和一個固定多項式c(x)作乘法。AES的密鑰調(diào)度密鑰bit的總數(shù)=分組長度x(輪數(shù)Round+1)當(dāng)分組長度為128bit且輪數(shù)為10時，輪密鑰長度為:128x(10+1)=1408bit將初始密鑰擴(kuò)展成擴(kuò)展密鑰輪密鑰從擴(kuò)展密鑰中取，第1輪輪密鑰取擴(kuò)展密鑰的前Nb個字，第2輪輪密鑰取接下來的Nb個字，以此類推。密鑰擴(kuò)展ω[0]ω[1]ω[2]ω[3]k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33密鑰擴(kuò)展以128bit為例，對數(shù)組ω擴(kuò)充40個新列，構(gòu)成總共44列的擴(kuò)展密鑰數(shù)組。新列按照以下的方式遞歸產(chǎn)生：(1)如果i不是4的倍數(shù)，那么第i列由等式ω[i]=ω[i-4]⊕ω[i-1]確定；(2)如果i是4的倍數(shù)，那么第i列由等式ω[i]=ω[i-4]⊕T(ω[i-1])確定；ω[0]ω[1]ω[2]……ω[42]ω[43]ω[0]ω[1]ω[2]ω[3]AES密鑰擴(kuò)展圖ω[4i]ω[4i-3]ω[4i-2]ω[4i-1]⊕ω[4i]ω[4i+1]ω[4i+2]ω[4i+3]T⊕⊕⊕密鑰擴(kuò)展函數(shù)T由三部分組成：字循環(huán)移位、字節(jié)代換和輪常量異或。(1)字循環(huán)移位：將1個字中的4個字節(jié)循環(huán)左移1個字節(jié)，即將輸入字[b0,b1,b2,b3]變換為[b1,b2,b3,b0]。(2)字節(jié)代換：對字循環(huán)的結(jié)果使用S盒進(jìn)行字節(jié)代換。(3)輪常量異或：將前兩步的結(jié)果同輪常量Rcon[j]進(jìn)行異或，其中j表示輪數(shù)。輪常量是一個字，使用輪常量是為了防止不同輪中產(chǎn)生的輪密鑰的對稱性或相似性。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的巧妙之處：雖然解密算法與加密算法不同，但解密算法與加密算法結(jié)構(gòu)相同。把加密算法的基本運算變換成逆變換，便得到解密算法。AES的各個基本變換都是可逆的。AES的基本逆變換輪密鑰加變換的逆就是其本身；行移位變換的逆是狀態(tài)的分別移位對應(yīng)的位數(shù)；列混合變換的逆就是狀態(tài)的每列都乘以c(x)的逆多項式d(x);S盒變換的逆：首先進(jìn)行逆仿射變換，然后再把每個字節(jié)用對應(yīng)的逆來代替，查逆S盒表。

逆S盒代換表0123456789ABCDEF052096AD53036A538BF40A39E81F3D7FB17CE339829B2FFF87348E4344C4DEE9CB2547B9432A6C2233DEE4C950B42FAC34E3082EA16628D924B2765BA2496D8BD125472F8F66486689816D4A45CCC5D65B69256C704850FDEDB9DA5E154657A78D9D84690D8AB008CBCD30AF7E45805B8B345067D02C1E8FCA3F0F02C1AFBD0301138A6B83A9111414F67DCEA97F2CFCEF0B4E673996AC7422E7AD3585E2F937E81C75DF6EA47F11A711D29C5896FB7620EAA18BE1BBFC563E4BC6D279209ADBC0FE78CD5AF4C1FDDA8338807C731B11210592780EC5FD60517FA919B54A0D2DE57A9F93C99CEFEA0E03B4DAE2AF5B0C8EBBB3C83539961F172B047EBA77D626E169146355210C7DAES（三）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]:=i k[i]=key[i%Len]endforj:=0forifrom0to255 j:=(j+S[i]+k[i])mod256 swapvaluesofS[i]andS[j]endforRC4RC4密鑰流的每個輸出都是數(shù)據(jù)表S中的一個隨機(jī)元素。密鑰流的生成需要兩個過程：

1）密鑰調(diào)度算法用于設(shè)置數(shù)據(jù)表S的初始排列；

2）偽隨機(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)=r（1－1/P1）（1－1/P2）···（1－1/Pn）

P1

、P2···Pn是r的質(zhì)因子，即公約數(shù)。

歐拉函數(shù)是用來計算1、2、3、···、r中有多少個數(shù)與r互為質(zhì)數(shù)的。例如：當(dāng)r=20時，由于r=2×2×5，即20的公約數(shù)是2和5

所以：

=20×（1-1/2）×（1-1/5）=8

即在1～20個整數(shù)中有8個與20互質(zhì)的數(shù)，它們是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，且1<e<Φ(n)(令sk=e);(4)計算pk，使得pk*sk≡1modΦ(n)。2.4.1RSA非對稱密碼體制(5)公鑰KU=(pk,n)，私鑰KR=(sk,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）設(shè)計公、私密鑰(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)。

2）明文數(shù)字化。

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

用戶加密密鑰(3,33)將數(shù)字化明文分組信息加密成密文。由得：得到相應(yīng)的密文信息為：11，26，16。（4）密文解密。

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

RSA算法安全性在RSA密碼應(yīng)用中，公鑰KU是被公開的，即pk和n的數(shù)值可以被第三方得到。破解RSA密碼的問題就是從已知的pk和n的數(shù)值（n等于pq），設(shè)法求出sk的數(shù)值，這樣就可以得到私鑰來破解密文。從上文中的公式：d≡e-1(mod((p-1)(q-1)))或de≡1(mod((p-1)(q-1)))可以看出，密碼破解的實質(zhì)問題是：從pq的數(shù)值，求出(p-1)和(q-1)。即，只要求出p和q的值，就能求出d的值而得到私鑰。RSA算法安全性RSA算法的安全性取決于p、q的保密性，以及分解大數(shù)的難度，所以在計算出r后要立即徹底刪除p、q值。通常，在實際應(yīng)用中應(yīng)該注意：1．p與q的取值必須相差很大，有人建議至少要在10倍左右；

2．為了提高加密速度，通常取加密的sk為特定的小整數(shù)，如EDI(電子數(shù)據(jù)交換)國際標(biāo)準(zhǔn)中規(guī)定選擇的，ISO/IEC9796甚至允許取k=3，這樣導(dǎo)致加密速度一般比解密速度快10倍以上。RSA的缺點RSA的缺點：

a)產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。

b)分組長度太大，為保證安全性，n至少也要600bits以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。因此，使用RSA只能加密少量數(shù)據(jù)，大量的數(shù)據(jù)加密還要靠對稱密碼算法。2.4.2橢圓曲線密碼橢圓曲線在密碼學(xué)中的使用是在1985年由NealKoblitz和VictorMiller分別獨立提出。橢圓曲線密碼突出的優(yōu)點：密鑰長度短，抗攻擊性強(qiáng)，單位比特的安全性強(qiáng)度高，比如160比特的ECC與1024比特的RSA有相同的安全強(qiáng)度；ECC的計算量小，處理速度快。在相同的強(qiáng)度下，用160比特的ECC進(jìn)行加密、解密或數(shù)字簽名要比用1024比特的RSA要快大約10倍。