網(wǎng)絡(luò)安全密碼學(xué)基礎(chǔ)

網(wǎng)絡(luò)信息安全

---第3章密碼學(xué)基礎(chǔ)電子信息工程學(xué)院計(jì)算機(jī)與科學(xué)技術(shù)系第3章密碼學(xué)基礎(chǔ)

本章主要討論以下幾方面的問(wèn)題密碼學(xué)的基本概念和術(shù)語(yǔ)對(duì)稱和非對(duì)稱密碼及其區(qū)別古典密碼學(xué)的基本方法DES算法、RSA算法的基本原理

懸賞：如果你能讀懂這個(gè)消息，你就是一個(gè)成功的密碼

破譯者了，考試可以給你加點(diǎn)分。分這是密可加懂就的了試讀你功者考能息成譯你消個(gè)破給果個(gè)一碼以如點(diǎn)農(nóng)戶與雞快吃吧，這是你最后一頓！雞躺倒并留遺書(shū)：爺已吃老鼠藥，你們別想吃爺了，爺也不是好惹的！

當(dāng)對(duì)手知道了你的決定之后，就能做出對(duì)自己最有利的決定?！{什均衡理論保密、信息安全很重要！3.1密碼學(xué)概述密碼學(xué)是一門(mén)古老而深?yuàn)W的學(xué)科，對(duì)一般人來(lái)說(shuō)是非常陌生的。長(zhǎng)期以來(lái)，只在很小的范圍內(nèi)使用，如軍事、外交、情報(bào)等部門(mén)。計(jì)算機(jī)密碼學(xué)是研究使用計(jì)算機(jī)進(jìn)行信息加密、解密及其變換的科學(xué)，是數(shù)學(xué)和計(jì)算機(jī)的交叉學(xué)科，是一門(mén)新興的學(xué)科。隨著計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)通信技術(shù)的發(fā)展，計(jì)算機(jī)密碼學(xué)得到前所未有的重視并迅速普及和發(fā)展起來(lái)。3.1.1密碼學(xué)的發(fā)展史密碼學(xué)的歷史比較悠久，在四千年前，古希臘人就開(kāi)始使用密碼來(lái)保密傳遞消息。兩千多年前，羅馬國(guó)王JuliusCaesar（愷撒）就開(kāi)始使用目前稱為“愷撒密碼”的密碼系統(tǒng)，用來(lái)、傳遞保護(hù)重要軍事情報(bào)。但是密碼技術(shù)直到20世紀(jì)40年代以后才有重大突破和發(fā)展。特別是20世紀(jì)70年代后期，由于計(jì)算機(jī)、電子通信的廣泛使用，現(xiàn)代密碼學(xué)得到了空前的發(fā)展。3.1.1密碼學(xué)的發(fā)展史幾個(gè)著名的加密系統(tǒng)愷撒（Caesar）密碼維吉尼亞密碼（Vigenerecypher）

恩格瑪（Enigma）密碼機(jī)數(shù)據(jù)加密標(biāo)準(zhǔn)：DES公開(kāi)密鑰密碼：RAS萊斯·德·維吉尼亞（BlaisedeVigenère，1523-1596），一名法國(guó)的外交官，同時(shí)也是一位密碼學(xué)家。1586年在維吉尼亞密碼原基礎(chǔ)上進(jìn)行了改進(jìn)。

愷撒大帝是羅馬共和國(guó)末期杰出的軍事統(tǒng)帥、政治家。他公元前60年與龐培、克拉蘇秘密結(jié)成前三巨頭同盟，隨后出任高盧總督，花了八年時(shí)

間征服了高盧全境（大約是現(xiàn)在的法國(guó)），還襲擊了日耳曼和不列顛

恩格瑪（Enigma）密碼機(jī)密碼學(xué)的發(fā)展史大體上可以歸結(jié)為三個(gè)階段第一階段：1949年之前。這階段的密碼學(xué)的特點(diǎn)是：

密碼學(xué)還不是科學(xué)，而是藝術(shù)

出現(xiàn)一些密碼算法和加密設(shè)備

密碼算法的基本手段出現(xiàn)，主要針對(duì)字符

簡(jiǎn)單的密碼分析手段出現(xiàn)

數(shù)據(jù)的安全性基于算法的保密代表性的事件是：1883年荷蘭密碼學(xué)家Kerchoffs提出了密碼學(xué)的一個(gè)基本原則：加密算法應(yīng)建立在算法的公開(kāi)，密碼系統(tǒng)的安全性應(yīng)該完全依賴于密鑰的安全性。這個(gè)原則得到廣泛承認(rèn)，成為判定密碼強(qiáng)度的衡量標(biāo)準(zhǔn)，實(shí)際上也成為傳統(tǒng)密碼和現(xiàn)代密碼的分界線。密碼學(xué)的發(fā)展史大體上可以歸結(jié)為三個(gè)階段第二階段是1949-1975年，密碼學(xué)成為一門(mén)獨(dú)立的科學(xué)，計(jì)算機(jī)的出現(xiàn)使基于復(fù)雜計(jì)算的密碼成為可能。主要研究特點(diǎn)是：數(shù)據(jù)安全性基于密鑰而不是算法的保密。第三階段是1976年以后密碼學(xué)中公鑰密碼學(xué)成為主要研究方向，該階段具有代表性的事件是：1976年，斯坦福大學(xué)的Diffie和Hellman提出了不對(duì)稱密鑰1977年，Rivest，Shamir和Adleman提出了RSA公鑰算法1977年，DES算法出現(xiàn)80年代，出現(xiàn)IDEA和CAST等算法90年代，對(duì)稱密鑰密碼算法進(jìn)一步成熟，Rijndael，RC6等出現(xiàn)，逐步出現(xiàn)橢圓曲線等其他公鑰算法2001年，Rijndael成為DES算法的替代者2004年8月，山東大學(xué)信息安全研究所所長(zhǎng)王小云，在國(guó)際會(huì)議上首次宣布了她及她的研究小組對(duì)MD5、HAVAL-128、MD4和RIPEMD等四個(gè)著名密碼算法的破譯結(jié)果，引起世界轟動(dòng)。這階段的主要特點(diǎn)是：公鑰密碼學(xué)使數(shù)據(jù)的安全性是基于密鑰而不是算法。Caesar（愷撒）密碼（一）：（換位加密法）明文集合：abcdefghijklmnopqwstunwxyz密文集合：DEFGHIGKLMNOPQRSTUVWXYZABC明文(m)：Caesarwas

agreatsoldier密文(c)：

FDHVDU

ZDVD

JUHDW

VROGLHU

密文集合是明文集合中的字母向后移動(dòng)3位得到的3.1.1密碼學(xué)的發(fā)展歷史

Caesar（愷撒）

密碼（二）：為26個(gè)英文字母依次分配一個(gè)序號(hào)CAESAR密碼算法或變換（E）：c=(m+

k)mod26k=3CAESAR密碼的密鑰集合（K）：（1，2，3，4，…，25）26英文字母與數(shù)字對(duì)照表進(jìn)行加密維吉尼亞（Vigenere）密碼表

ABCDEFGHIJKLMNOPQRSTUVWXYZ

A

ABCDEFGHIJKLMNOPQRSTUVWXYZ

B

BCDEFGHIJKLMNOPQRSTUVWXYZA

C

CDEFGHIJKLMNOPQRSTUVWXYZAB………

O

OPQRSTUVWXYZABCDEFGHIJKLMN………

X

XYZABCDEFGHIJKLMNOPQRSTUVW

Y

YZABCDEFGHIJKLMNOPQRSTUVWX

Z

ZABCDEFGHIJKLMNOPQRSTUVWXY

維吉尼亞加密法：置換加密法給出一個(gè)用于加密的密鑰（單詞），比如:welcome加密過(guò)程：以明文字母選擇列，以密鑰字母選擇行，兩者的交點(diǎn)就

是加密生成的密文。

解密過(guò)程：以密鑰字母選擇行，從中找到密文字母，密文字母所在

列的列名即為明文字母。

例：以your為密鑰，加密明文howareyou 明文P=

howareyou

密鑰K=

youryoury 密文C=

fcqrpssfs維吉尼亞加密法：密鑰控制下的矩陣加密法矩陣加密法的操作過(guò)程：給出1個(gè)密鑰單詞，其字符數(shù)假如為：9，并根據(jù)其每個(gè)字符在字母表中位置給出其序號(hào)。把明文按9列排成一個(gè)矩陣在明文矩陣的上方寫(xiě)密鑰及其序號(hào)根據(jù)密鑰中字符的序號(hào)，按列讀出明文，即為加密的密文解密：根據(jù)密鑰、密文算得行寬，寫(xiě)出矩陣，得到明文例如，用密鑰單詞compute，對(duì)明文MATHEMATICALMODELINGISUSEFUL加密：根據(jù)密鑰的字符數(shù)7，把明文看成一個(gè)n行7列的矩陣

根據(jù)密鑰字符的序號(hào)，依次按列讀出就得到密文MTDSAIEUTCLSHAIEELEFMMNUAOIL

1、密碼學(xué)的幾個(gè)術(shù)語(yǔ)明文(PlainText)：

準(zhǔn)備加密的消息(Message)；加密（Encryption）：

用某種方法偽裝消息以隱藏它的內(nèi)容的過(guò)程；密文(Cipher)：

被加密的消息；解密（Decryption）：

把密文轉(zhuǎn)變?yōu)槊魑牡倪^(guò)程；加密算法：

用來(lái)加密和解密的數(shù)學(xué)函數(shù)（變換函數(shù)）

比如：c=E(m),m=D(c),D(E(m))=m3.1.2

密碼系統(tǒng)密鑰(key):參與變換的參數(shù)，算法中的一個(gè)變量，或一些關(guān)鍵信息比如：c=EK(m)，m=DK(c)，DK(EK(m))=m密鑰：加密密鑰與解密密鑰

密碼學(xué)（Cryptology）：

密碼學(xué)可看作數(shù)學(xué)的一個(gè)分支，包括：密碼編碼學(xué)密碼分析學(xué)密碼編碼技術(shù)和密碼分析技術(shù)是相互依存、相互支持、密不可分的兩個(gè)方面。2、加密和解密的過(guò)程3一個(gè)密碼系統(tǒng)或密碼體制的組成：通常一個(gè)密碼體制表示成一個(gè)五元組:（M，C，K，E，D）其中：

⑴M：是可能明文的有限集，稱為明文空間⑵C：是可能密文的有限集，稱為密文空間⑶K：是一切可能密鑰構(gòu)成的有限集，稱為密鑰空間⑷E：加密算法或加密函數(shù)：

Ek：M->C，或EK（M）=C

比如，Caesar密碼中：C=EK（M）=（M+K）MOD26⑸D：解密算法或解密函數(shù)：

Dk:C->M，或DK（C）=M

比如，Caesar密碼中：M=DK(C)=(C-K)MOD26

滿足：Dk（Ek（M））=M密碼系統(tǒng)的安全性基于密鑰的安全性，而不是基于算法安全性，即密鑰要保密，算法可以公開(kāi)！3.1.3密碼的分類1、按應(yīng)用的技術(shù)或歷史發(fā)展階段劃分：

密碼的發(fā)展經(jīng)歷了：（1）手工密碼（2）機(jī)械密碼（3）電子機(jī)內(nèi)亂密碼（4）計(jì)算機(jī)密碼2、按保密程度劃分：

⑴理論上保密的密碼；⑵實(shí)際上保密的密碼；⑶不保密的密碼

3.1.3密碼的分類3、按密鑰方式劃分：⑴對(duì)稱密碼體制（如DES、AES）；⑵公開(kāi)密鑰密碼體制（RSA、ECC）。4、按明文形態(tài)：⑴

模擬型密碼⑵數(shù)字型密碼5、按編制原理劃分：⑴替換；⑵置換3.1.4近代加密技術(shù)1、對(duì)稱加密算法對(duì)稱加密算法（symmetricalgorithm），也稱為傳統(tǒng)密碼算法或單鑰算法。對(duì)稱加密算法的主要特征：

其加密密鑰與解密密鑰相同或很容易相互推算出來(lái)。

整個(gè)通訊的安全性依賴于密鑰的保密，而不是算法的保密對(duì)稱加密算法的優(yōu)缺點(diǎn)：主要優(yōu)點(diǎn):

加密速度快，計(jì)算量小、加密效率高，硬件容

易實(shí)現(xiàn)和大規(guī)模生產(chǎn)；

主要缺點(diǎn)：密鑰的分發(fā)與管理比較困難，當(dāng)通信的人數(shù)

增加時(shí)，密鑰數(shù)目急劇膨脹：n(n-1)/2，100人50003.1.4近代加密技術(shù)對(duì)稱加密過(guò)程發(fā)送方用自己的私有密鑰對(duì)要發(fā)送的信息進(jìn)行加密；發(fā)送方將加密后的信息通過(guò)網(wǎng)絡(luò)傳送給接收方；接收方用發(fā)送方進(jìn)行加密的那把密鑰，對(duì)接收到的加密信息進(jìn)行解密，得到信息明文。秘密渠道對(duì)稱加密算法分類：

序列密碼算法分組密碼算法對(duì)稱加密算法用到的兩種技術(shù)：混亂擴(kuò)散非對(duì)稱加密算法（AsynmetricAlgorithm）也稱公開(kāi)密鑰算法。主要特征：公開(kāi)密鑰體制把加密密鑰和解密密鑰分離，并且通信的每一方都擁有這樣的一對(duì)密鑰；加密密鑰可以像電話號(hào)碼一樣對(duì)外公開(kāi)，由發(fā)送方用來(lái)加密要發(fā)送的原始數(shù)據(jù)；稱為公鑰解密密鑰則由接收方秘密保存，作為解密時(shí)的私用密鑰。加、解密過(guò)程發(fā)送方用接收方公開(kāi)密鑰對(duì)要發(fā)送的信息進(jìn)行加密；發(fā)送方將加密后的信息通過(guò)網(wǎng)絡(luò)傳送給接收方；接收方用自己的私有密鑰對(duì)接收到的加密信息進(jìn)行解密，得到信息明文。2、非對(duì)稱加密體制（公開(kāi)密鑰體制）公開(kāi)密鑰體制優(yōu)缺點(diǎn)：主要優(yōu)點(diǎn)：就是不需要對(duì)密鑰通信進(jìn)行保密，所需傳輸?shù)闹挥泄_(kāi)密鑰；主要缺陷：在于其加密和解密的運(yùn)算時(shí)間比較長(zhǎng)，這在一定程度上限制了它的應(yīng)用范圍。2、非對(duì)稱加密體制公開(kāi)密鑰體制主要用途：

數(shù)據(jù)的加、解密：

發(fā)送消息方用接收方的公鑰加密消息；接收方用自己的私鑰解密消息。數(shù)字簽名：

接收方用發(fā)送方的公鑰來(lái)認(rèn)證消息的真實(shí)性和來(lái)源。密鑰交換：

用于通訊雙方進(jìn)行會(huì)話密鑰的交換。3.1.5密碼的破譯密碼分析密碼分析是在不知道密鑰的情況下，利用數(shù)學(xué)方法從密文中恢復(fù)出明文或找到密鑰的方法;密碼分析也可以發(fā)現(xiàn)密碼體制的弱點(diǎn)。攻擊對(duì)密鑰或密文進(jìn)行分析的嘗試稱為攻擊。攻擊方法分類：

密鑰的窮盡搜索；

密碼分析；其它方法。3.1.5密碼的破譯1、密鑰的窮盡搜索破譯密文就是嘗試所有可能的密鑰組合。

雖然大多數(shù)的密鑰嘗試都是失敗的，但最終有一個(gè)密鑰讓破譯者得到原文，這個(gè)過(guò)程稱為密鑰的窮盡搜索。在相同條件下，密鑰越長(zhǎng)，破譯密碼的難度就越大，密碼系統(tǒng)就越可靠。比如，

PGP，使用128位密鑰進(jìn)行加密，所有密鑰排列數(shù)是2128，每秒鐘嘗試1億把密鑰，也需要1014年完成。

3.1.5密碼的破譯2、密碼分析

已知明文的破譯方法在某些情況下，攻擊者可能部分或全部地知道加密的明文。這種知情度可能使攻擊者能夠較輕松地使用該協(xié)議確定密鑰和破譯其它消息。典型的已知明文暴露的示例是：攻擊者知道加密的內(nèi)容是由包含標(biāo)準(zhǔn)頭的文件類型組成的，或者攻擊者知道消息與一個(gè)命名主題相關(guān)。在其它情況下，整個(gè)消息也可能會(huì)以破解密碼以外的方式泄露，這有助于攻擊者破解其它消息。3.1.5密碼的破譯2、密碼分析已知明文的破譯方法密碼分析者掌握了一段明文和對(duì)應(yīng)的密文，企圖從中找出加密的密鑰。實(shí)際中獲得明文對(duì)應(yīng)的密文是可能的。比如，電子郵件選定明文的破譯方法選定明文的破譯者知道了加密算法；他選定一段明文，設(shè)法讓加密者加密選定的明文，并得到加密結(jié)果，即知道選定的明文和對(duì)應(yīng)的密文。企圖找出加密的密鑰。

3.1.5密碼的破譯2、密碼分析選定密文的破譯方法破譯者已知選定的密文和對(duì)應(yīng)的、已解密的原文，即知道選擇的密文和對(duì)應(yīng)的明文；企圖從中找出加密的密鑰。差別比較分析破譯方法破譯者選定一組相似且差別微小的明文；設(shè)法讓加密進(jìn)行加密，并得到加密結(jié)果；企圖從中找出加密的密鑰；

3．其他密碼破譯方法“窺視”或“偷竊”密鑰內(nèi)容；從用戶生活和工作環(huán)境的中獲得未加密的保密信息，比如進(jìn)行“垃圾分析”；用拷打、威脅、騷擾或其它強(qiáng)迫方式讓用戶而被迫泄露密鑰和秘密。通過(guò)賄賂、收買、勾引或誘惑得到密鑰和秘密。4、密碼的破譯舉例-字母頻率攻擊

古代密碼多數(shù)可以通過(guò)字母頻率攻擊來(lái)破解，以愷撒密碼為例，可以通過(guò)計(jì)算機(jī)字母出現(xiàn)的頻率推測(cè)出密鑰k=3,比如：原文：pandasoftware密文：sdqgdvriwzduh⑴找出密文中出現(xiàn)頻率最高的字母：“d”；⑵英語(yǔ)中最常出現(xiàn)的字母是“a”和“e”，分別進(jìn)行檢驗(yàn)；⑶若“d“是“e”：“d”在“e”的后面第25位，然后用25來(lái)

解密其它密文，即密文向左移動(dòng)25位，得到明文如下：

原文：terhewsjxaevi

這個(gè)字母序列沒(méi)有絲毫意義。⑷若“d”是“a”：因?yàn)椤癲”是“a”后的第3位，然后用3來(lái)解密其它密文，即密文向左移動(dòng)3位，得到明文如下：

密文：sdqgdvriwzduh原文：pandasoftware破譯成功！3.2古典密碼學(xué)古典密碼主要有：代換密碼法與置換密碼法3.2.1代換密碼代換密碼的特點(diǎn)是：依據(jù)一定的規(guī)則，明文字母被不同的密文字母所代替；明文的原有順序在密文中被保留。

1、移位密碼法移位密碼基于數(shù)論中的模運(yùn)算。如下：令m={a,b,c,……，z}，C={A,B,C,……，Z}，K={1，2，……，25}，加密變換：Ek（x）=（x+k）mod26解密變換：Dk（y）=（y-k）mod26Caesar（凱撒）密碼就是當(dāng)K=3時(shí)的代替密碼法維吉尼亞加密法也是代替密碼加密法。2、單表代換密碼單表代換密碼的基本思想是：列出明文字母與密文字母的一一對(duì)應(yīng)關(guān)系。明文abcdefghijklm密文WJANDYUQIBCEF明文nopqrstuvwxyz密文GHKLMOPRSTVXZ例如：明文為:n

e

t

w

o

r

k

s

e

c

u

r

i

t

y,相應(yīng)密文為：

G

D

P

T

H

M

C

O

D

A

R

M

I

P

X3、多表替換密碼Vigenere密碼是一種典型的多表替換密碼算法。算法如下：設(shè)密鑰：K=k1k2……kn，明文M=m1m2……mn,加密變換:ci≡（mi+ki）mod26,i=1,2,……,n解密變換：mi≡（ci-ki）mod26,i=1,2,……,n例如：明文：

M=cipherblock,密鑰為：K=hit

3、多表替換密碼

⑴根據(jù)密鑰序列的個(gè)數(shù)3，把明文劃分成長(zhǎng)度為3的序列：

cipherblock⑵加密算法：每個(gè)序列中的字母分別與密鑰序列中相應(yīng)字母進(jìn)行

模26運(yùn)算，得密文：JQIOMKITHJS比如：⑴cip→2815⑵hit→7819⑶（2＋7）mod26=9→J⑷（8＋8）mod26=16→Q⑸（15＋19）mod26=8→I⑹cip→JQI26英文字母與數(shù)字對(duì)照表3.2.2置換密碼置換密碼的特點(diǎn)：是保持明文的所有字母不變，只是利用置換改變明文原來(lái)字母的排列順序，比如置換密碼體制定義如下：令m為一正整數(shù)，P=C={A,B,C,……Z}，對(duì)任意的置換π（密鑰），定義:加密變換：Eπ（x1,x2,……,xm）=（xπ（1）,xπ（2）……,xπ（m））,解密變換：Dπ（y1,y2,……,ym）=（xπ-1（1）,xπ-1（2）……,xπ-1（m））,密鑰控制下的矩陣換位加密法就是置換加密法

密鑰控制下的矩陣加密法矩陣加密法的操作過(guò)程：給出1個(gè)密鑰單詞，其字符數(shù)假如為：9，并根據(jù)其每個(gè)字符在字母表中位置給出其序號(hào)。把明文按9列排成一個(gè)矩陣在明文矩陣的上方寫(xiě)密鑰及其序號(hào)根據(jù)密鑰中字符的序號(hào)，按列讀出明文，即為加密的密文解密：根據(jù)密鑰、密文算得行寬，寫(xiě)出矩陣，得到明文例如，用密鑰單詞compute，對(duì)明文MATHEMATICALMODELINGISUSEFUL加密：根據(jù)密鑰的字符數(shù)7，把明文看成一個(gè)n行7列的矩陣

根據(jù)密鑰字符的序號(hào)，依次按列讀出就得到密文MTDSAIEUTCLSHAIEELEFMMNUAOIL置換密碼算法的分析密文字符和明文字符相同，只是順序被打亂密文和明文中的字母出現(xiàn)頻率相同，使得分析者可以很使用多輪置換加密可提高安全性3.3對(duì)稱密碼學(xué)3.3.1對(duì)稱密碼概述加密和解密使用相同的密鑰：KE=KD密鑰必須使用秘密的信道進(jìn)行分配對(duì)稱密碼算法可以分為兩類：分組密碼（BlockCipher）序列密碼（StreamCipher）分組密碼：將明文分成固定長(zhǎng)度的組。典型分組長(zhǎng)度是64位，用同一密鑰和算法對(duì)每一分組加密。加密以分組為單位。序列密碼/流密碼：每次加密一位或一字節(jié)的明文，序列密碼使用盡可能長(zhǎng)的密鑰。加密是以位或字節(jié)為單位。

3.3對(duì)稱密碼學(xué)接收方發(fā)送方mm加密E解密Dc=Ek(m)m=Dk(c)密鑰分配（秘密信道）kk特點(diǎn)：⑴加密密鑰與解密密鑰相同；⑵密鑰要通過(guò)秘密信道轉(zhuǎn)送3.3.2Feistel密碼結(jié)構(gòu)1、擴(kuò)散和混亂擴(kuò)散和混亂是由Shannon提出的設(shè)計(jì)密碼系統(tǒng)的兩個(gè)基本方法。目的：抵抗攻擊者對(duì)密碼的統(tǒng)計(jì)分析。明文的某些統(tǒng)計(jì)特性-如果在密文中反映了出來(lái)-攻擊者就可能得到加密密鑰的一部分或一個(gè)可能的密鑰集合擴(kuò)散：就是將明文的統(tǒng)計(jì)特性擴(kuò)散到密文中去。實(shí)現(xiàn)時(shí)使得密文的每一位由明文中的多位產(chǎn)生。這樣明文的統(tǒng)計(jì)特性就被散布開(kāi)了，攻擊者難以通過(guò)統(tǒng)計(jì)分析得到有用的信息。通常擴(kuò)散的方法：是通過(guò)多次置換或復(fù)雜的置換算法1、擴(kuò)散和混亂混亂：就是使密文和密鑰之間的統(tǒng)計(jì)關(guān)系變得盡可能復(fù)雜，使攻擊者無(wú)法得到密鑰。攻擊者即便得到了密文之間的某些統(tǒng)計(jì)關(guān)系，也難以得到密鑰。

通常的混亂方法：是通過(guò)多次代換或復(fù)雜的代換算法。2、Feistel密碼結(jié)構(gòu)及特點(diǎn)

（1）

將明文的分組分為左右兩個(gè)部分：L0，R0；

數(shù)據(jù)的這兩部分用一個(gè)函數(shù)F，進(jìn)行n輪處理（迭代運(yùn)算）

把經(jīng)過(guò)n輪處理后的兩部分，再結(jié)合起來(lái)生成密文分組；（2）第i輪把其上一輪產(chǎn)生的Li-1和Ri-1，用密碼K產(chǎn)生的子密鑰Ki作為輸入，進(jìn)行處理。一般說(shuō)來(lái)，子密鑰Ki與K不同，Ki是用子密鑰生成算法從密鑰K生成的；其第i輪迭代的函數(shù)為：Li=Ri-1

Ri=Li-1

⊕F(Ri-1,Ki)其中：Ki是第i輪的子密鑰，“⊕”表示異或運(yùn)算，F(xiàn)表示輪函數(shù)。（3）每一輪的處理的結(jié)構(gòu)都相同：每一輪都是先對(duì)數(shù)據(jù)的右半部分應(yīng)用處理函數(shù)F；然后對(duì)函數(shù)輸出結(jié)果和數(shù)據(jù)的左半部分取異或（XOR）。（4）處理函數(shù)F：對(duì)每輪處理都有相同的通用結(jié)構(gòu)；由循環(huán)子密鑰Ki來(lái)區(qū)分。（5）在置換之后，執(zhí)行由數(shù)據(jù)兩部分互換構(gòu)成的交換；（6）解密過(guò)程與加密過(guò)程基本相同。規(guī)則如下：用密文作為算法的輸入，但以相反順序使用子密鑰Ki；（7）加密和解密不需要用兩種不同的方法。異或運(yùn)算（XOR)運(yùn)算規(guī)則：操作數(shù)同，則為0；操作數(shù)異，則為1一個(gè)簡(jiǎn)單的加密算法—異或運(yùn)算：

密文：01

10解密：密鑰：

0101

明文：

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

0011

加密： 密鑰:

0101

密文：

01

10K=CM3.3.3DES算法1、DES算法概述IBM公司于70年代初提出，1977年1月被美國(guó)政府規(guī)定為用來(lái)對(duì)數(shù)據(jù)進(jìn)行加密的國(guó)家標(biāo)準(zhǔn)（DataEncryptionStandard）。目前，DES算法在ATM、磁卡及智能卡（IC卡）、加油站、高速公路收費(fèi)站等領(lǐng)域被廣泛應(yīng)用。DES是一種對(duì)稱密鑰算法，DES的整個(gè)體制是公開(kāi)的，系統(tǒng)的安全性依賴于密鑰，密鑰可以是任意的56bit數(shù)(加上奇偶校驗(yàn)，通常寫(xiě)成64bits)是一種分組加密算法，明文、密文都是按64bits進(jìn)行分組基本思想：混亂（Confusion）和擴(kuò)散（Diffusion）使用標(biāo)準(zhǔn)的算術(shù)和邏輯運(yùn)算。2、DES算法的基本過(guò)程：

初始置換IP

將明文組分為左右兩

部分，每部分32位，以

L0，R0表示進(jìn)行16輪運(yùn)算（）：

將數(shù)據(jù)和密鑰結(jié)合

16輪后，左、右兩部

分連接在一起再進(jìn)行一個(gè)末置換，

得到密文初始置換IPk1k2k16IP-1L0R0L1=R0R1=L0(R0,K1)L2=R1R2=L1(R1,K2)L15=R14R15=L14(R14,K15)R16=L15(R15,K16)L16=R1564位明文64位密文2、DES算法流程如圖所示第1步：變換明文。對(duì)給定的64位的明文M，首先通過(guò)一個(gè)初始置換IP表來(lái)重新排列M，從而構(gòu)造出64位的M0：

M0=IP(M)=L0＋R0，

其中：L0表示M0的前32位，R0表示M0的后32位。第2步：按照規(guī)則進(jìn)行運(yùn)算，規(guī)則為：Li=Ri-1Ri=Li⊕F(Ri-1,Ki)（i=1,2,3,…,16）其中：F表示一種算法，Ki是第I輪運(yùn)算時(shí)用的子密鑰。第3步：對(duì)L16＋R16，利用IP-1作逆置換，就得到了密文。3DES算法實(shí)現(xiàn)加密需要3個(gè)步驟初始置換IPk1k2k16IP-1L0R0L1=R0R1=L0(R0,K1)L2=R1R2=L1(R1,K2)L15=R14R15=L14(R14,K15)R16=L15(R15,K16)L16=R1564位明文64位密文4、DES的6個(gè)關(guān)鍵點(diǎn)：IP置換表IP-1逆置換表，運(yùn)算過(guò)程，函數(shù)F，子密鑰Ki的生成，⑥S盒的工作原理。

①IP表置換表：4×16

輸入的64位數(shù)據(jù)按IP表置換進(jìn)行重新組合。然后把輸出分成：

L0和R0兩部分。

（1）IP置換表和IP-1逆置換表初始置換將明文的第58位換到第1位；第50位換到第2位第42位換到第3位；第1位換到第40位（1）IP置換表和IP-1逆置換表②IP-1逆置換表：4×16逆置換將16次迭代后得到的L16和R16：

第1位換到第58位；第2位換到第50位第3位換到第42位；第40位換到第1位經(jīng)過(guò)初始置換后，將置換后明文分成兩部分。進(jìn)行16輪完全

相同的運(yùn)算。在運(yùn)算過(guò)程中數(shù)據(jù)與子密鑰ki結(jié)合。下面是第一輪運(yùn)算過(guò)程：k1L0R0L1=R0R1=L0(R0,K1)

函數(shù)的輸出經(jīng)過(guò)一個(gè)異或運(yùn)算，和左半部分結(jié)合，其結(jié)果

成為新的右半部分，原來(lái)的右半部分成為新的左半部分。（2）運(yùn)算過(guò)程第i輪的運(yùn)算過(guò)程：假設(shè)Li和Ri是第i輪

運(yùn)算結(jié)果的左半部

分和右半部分，Ki是第i輪的48位子

密鑰，第i輪迭代過(guò)程可

以如右圖所示。Li-1(32bit)Ri-1(32bit)擴(kuò)展置換ES盒代替P-盒置換Ri(32bit)Li(32bit)Ki48bitRi=Li-1(Ri-1,Ki)Li=Ri-132位48位48位32位32位32位1、函數(shù)f有兩個(gè)輸入：⑴32位的Ri-1

；⑵

48位Ki

，2、函數(shù)f要處理：⑴1個(gè)運(yùn)算；⑵四個(gè)變換；⑶函數(shù)f

f函數(shù)的處理流程圖

①E變換的算法是從Ri-1的32位中選取某些位，加上原32位，構(gòu)成48位，即E將32位擴(kuò)展為48位。變換規(guī)則見(jiàn)下表。

32|1234|54|5678|98|9101112|1312|13141516|1716|17181920|2120|21222324|2524|25262728|2928|29303132|1子密鑰Ki的生成DES算法由64（56）位密鑰產(chǎn)生16輪的48位子密鑰。在每一輪運(yùn)算過(guò)程中，使用不同的子密鑰。每一輪子密鑰生成過(guò)程見(jiàn)右圖：64位密鑰置換選擇1C0(28位)D0(28位)循環(huán)左移循環(huán)左移C1(28位)D1(28位)置換選擇2循環(huán)左移循環(huán)左移Ci(28位)Di(28位)置換選擇256位k148位ki48位56位壓縮置換。將56位輸入置換為48位。將64位密鑰減至56位。然后進(jìn)行一次密鑰置換。各輪循環(huán)移動(dòng)的次數(shù)由輪數(shù)決定。57，49，41，33，25，17，9，1，58，50，42，34，26，18，10，

2，59，51，43，35，27，19，11，3，60，52，44，36，63，55，47，39，31，23，15，7，62，54，46，38，30，22，14，6，61，53，45，37，29，21，13，5，28，20，12，4置換選擇1：4×14由于不考慮每個(gè)字節(jié)的第8位，DES的密鑰由64位減至56位。每個(gè)字節(jié)的第8位可作為奇偶校驗(yàn)以確保密鑰不發(fā)生錯(cuò)誤。64位密鑰置換選擇1

經(jīng)過(guò)置換選擇1，將輸出的56位密鑰分成兩部分，每部分28位。然后，根據(jù)輪數(shù)，將兩部分分別循環(huán)左移1位或2位。如表所示。每輪移動(dòng)的位數(shù)，見(jiàn)下表

輪1

2345678910111213141516位數(shù)1122222212

222

221C0(28位)D0(28位)循環(huán)左移循環(huán)左移C1(28位)D1(28位)64位密鑰置換選擇1第1輪：對(duì)C0作左移1位得到C1，對(duì)D0作左移1位得到D1，對(duì)C1D1應(yīng)用PC2進(jìn)行選位，得到K1。PC2如下

第2輪：對(duì)C1和D1作左移1位得到C2和D2，進(jìn)一步對(duì)C2、D2應(yīng)用進(jìn)行選位，得到K2。如此繼續(xù)，分別得到K3，K4，…，K16。

移動(dòng)后，從56位輸出中選出48位，稱為壓縮換位。如表所示。壓縮換位14，17，11，24，1，5，3，28，15，6，21，10，23，19，12，4，26，8，16，7，27，20，13，2，41，52，31，37，47，55，30，40，51，45，33，48，44，49，39，56，34，53，46，42，50，36，29，32

64位密鑰置換選擇1C0(28位)D0(28位)循環(huán)左移循環(huán)左移C1(28位)D1(28位)置換選擇256位k148位④S盒替換將48-bit輸入轉(zhuǎn)為32-bit的輸出48-位輸入32-位輸出S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8

S代換運(yùn)算由8個(gè)不同的替換盒（S盒）完成。每個(gè)S盒有6位輸入，4位輸出。

48位的輸入被分為8個(gè)6位的分組，每一分組對(duì)應(yīng)一個(gè)S-盒,用來(lái)進(jìn)行代替操作。經(jīng)過(guò)S盒代替，形成8個(gè)4位分組，把48位的輸入變成32位輸出。其過(guò)程如下：48-bit組被分成8個(gè)6-bit組，每一個(gè)6-bit組作為一個(gè)S盒的輸入，輸出為一個(gè)4-bit組。由輸入的位數(shù)計(jì)算機(jī)其輸出結(jié)果：每個(gè)S盒是一個(gè)4×16的矩陣：行號(hào)、列號(hào)由0開(kāi)始由6-bit輸入數(shù)計(jì)算出兩個(gè)數(shù)：用6-bit數(shù)的首、末兩位得到的數(shù)：m，去選擇行用6-bit數(shù)中間的四位得到的數(shù)：n，去選擇列m、n的交叉點(diǎn)即為輸入的數(shù)的變換結(jié)果

例如，假設(shè)S-盒6的輸入為：110011。第1位和最后一位組合形成了11，是十進(jìn)制的3，它對(duì)應(yīng)著

S-盒6的第3行。中間的4位組合形成了1001，是十進(jìn)制的9，它對(duì)應(yīng)著S-盒6

的第9列。而S-盒6的第3行第9列處的數(shù)是14，得到輸出值為：1110。輸入6位，如何得到4位？以S-盒6說(shuō)明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⑤P-盒置換

16，7，20，21，29，12，28，17，1，15，23，26，5，18，31，10，

2，8，24，14，32，27，3，9，19，13，30，6，22，11，

4，25例如，第21位移到了第4位，第4位移到了第31位。⑷末置換

末置換是初始置換的逆過(guò)程。

DES在最后一輪迭代過(guò)程后，左半部分和右半部分并不交換，而是將R16和L16并在一起形成一個(gè)分組作為末置換的輸入。末置換40，8，48，16，56，24，64，32，39，7，47，15，55，23，63，31，38，6，46，14，54，22，62，30，37，5，45，13，53，21，61，29，36，4，44，12，52，20，60，28，35，3，43，11，51，19，59，27，34，2，42，10，50，18，58，26，33，1，41，9，49，17，57，25DES解密

DES的解密和加密使用相同的算法。解密過(guò)程中使用的子密鑰順序與加密過(guò)程中使用的密鑰順序相反。Li-1=Ri(Li,Ki)Ri-1=Li2、DES算法的安全性

DES算法正式公開(kāi)發(fā)表以后，引起了一場(chǎng)激烈的爭(zhēng)論。1977年Diffie和Hellman提出,若制造一個(gè)每秒能測(cè)試106個(gè)密鑰的大規(guī)模芯片，這種芯片的機(jī)器大約一天就可以搜索DES算法的整個(gè)密鑰空間；制造這樣的機(jī)器需要兩千萬(wàn)美元。1993年R.Session和M.Wiener給出了一個(gè)非常詳細(xì)的密鑰搜索機(jī)器的設(shè)計(jì)方案，它基于并行的密鑰搜索芯片。此芯片每秒測(cè)試5×107個(gè)密鑰，5760個(gè)這樣的芯片組成的系統(tǒng)平均1.5天即可找到密鑰，如果利用10個(gè)這樣的系統(tǒng)，搜索時(shí)間可以降到2.5小時(shí)。制作10個(gè)這樣的系統(tǒng)大概需要100萬(wàn)元。1997年1月28日，美國(guó)的RSA數(shù)據(jù)安全公司在互聯(lián)網(wǎng)上開(kāi)展了一項(xiàng)名為“密鑰挑戰(zhàn)”的競(jìng)賽：懸賞一萬(wàn)美元，破解一段用56位密鑰加密的DES密文。計(jì)劃公布后引起了網(wǎng)絡(luò)用戶的強(qiáng)烈響應(yīng)。一位名叫RockeVerser的程序員設(shè)計(jì)了一個(gè)可以通過(guò)互聯(lián)網(wǎng)分段運(yùn)行的密鑰窮舉搜索程序，組織一個(gè)稱為DESHALL的搜索行動(dòng)，成千上萬(wàn)的志愿者加入到計(jì)劃中；在計(jì)劃實(shí)施的第96天，即挑戰(zhàn)賽計(jì)劃公布的第140天，1997年6月17日晚上10點(diǎn)39分，美國(guó)鹽湖城Inetz公司的職員MichaelSanders成功地找到了密鑰，在計(jì)算機(jī)上顯示了明文：“Theunknownmessageis:Strongcryptographymakestheworldasaferplace”。世界在Internet面前變得不安全起來(lái)了。Internet僅僅應(yīng)用了閑散的資源，毫無(wú)代價(jià)地破解了DES的密碼，這是對(duì)密碼方法的挑戰(zhàn)，也是Internet超級(jí)計(jì)算能力的顯示。盡管DES有這樣那樣的不足，但是作為第一個(gè)公開(kāi)密碼算法的密碼體制成功地完成了它的使命，它在密碼學(xué)發(fā)展歷史上具有重要的地位。3、增強(qiáng)的DES加密算法DES一個(gè)致命的缺陷就是密鑰長(zhǎng)度短，而DES又不支持變長(zhǎng)密鑰，對(duì)于當(dāng)前的計(jì)算能力，56位的密鑰長(zhǎng)度已經(jīng)抗不住窮舉攻擊。但算法可以一次使用多個(gè)密鑰，從而等同于更長(zhǎng)的密鑰。對(duì)DES進(jìn)行復(fù)合，強(qiáng)化它的抗攻擊能力；3、增強(qiáng)的DES加密算法

C=EK2[EK1[M]]?M=DK1[DK2[C]]MEK1XEK2C(a)加密CDK2XDK1M(b)解密

二重DES

兩個(gè)密鑰的三重DES

C=EK1[DK2[EK1[M]]]?M=DK1[EK2[DK1[C]]]MDK2BEK1C(a)加密(b)解密EK1ACEK2ADK1MDK1B三個(gè)密鑰的三重DES

C=EK3[DK2[EK1[M]]]?M=DK1[EK2[DK3[C]]]MDK2BEK1C(a)加密(b)解密EK3ACEK2ADK3MDK1B4、國(guó)際數(shù)據(jù)加密算法--IDEA1990年瑞士聯(lián)邦技術(shù)學(xué)院的XueJiaLai和著名密碼學(xué)家JamesMassey開(kāi)發(fā)出PES，即建議的加密標(biāo)準(zhǔn)的，是IDEA的雛形1991年設(shè)計(jì)者對(duì)PES強(qiáng)化成為IPES，即改進(jìn)的建議加密標(biāo)準(zhǔn)1992年更名為IDEA，即國(guó)際數(shù)據(jù)加密標(biāo)準(zhǔn)明文分組：64位，密鑰長(zhǎng)度：128位類似于DES，IDEA也是一種數(shù)據(jù)塊加密算法，它設(shè)計(jì)了一系列加密輪次，每輪加密都使用從完整的加密密鑰中生成一個(gè)子密鑰。5、高級(jí)加密標(biāo)準(zhǔn)—AES算法1997年4月15日，NIST（美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)局）征集AES（AdvancedEncryptionStandard）以代替DES算法。1998年8月20日舉辦了首屆AES候選會(huì)議，選出了15個(gè)候選算法。1999年8月9日，NIST宣布了第二輪AES的優(yōu)勝者：MARS，RC6，Rijndael，SERPENT，Twofish。2000年10月2日，NIST最終確定Rijndael作為AES算法。（比利時(shí)密碼專家JoanDaemen和VincentRijmen）

2001年11月26日NIST正式宣布AES為美國(guó)政府的新加密標(biāo)準(zhǔn)，該決定在2002年5月26日生效。AES算法特點(diǎn)

(1)密鑰長(zhǎng)度可變：Rijndael的信息塊長(zhǎng)度和加密密鑰長(zhǎng)度都是可變的，都可以是128位，192位和256位(2)混合的運(yùn)算：AES每輪要經(jīng)過(guò)四次變換：

ByteSub()字節(jié)代換

ShiftRows()行移位

MixColumns()列混合

AddRoundKey()輪密鑰的添加

(3)能有效抵制目前已知的攻擊算法

3.4非對(duì)稱密碼體制3.4.1、公開(kāi)密鑰加密算法（RSA）概述 非對(duì)稱密碼體制的算法中最著名的代表是RSA系統(tǒng)。公開(kāi)密鑰加密算法RSA，于1978年，由美國(guó)麻省理工學(xué)院(MIT)的Rivest(李維斯特)、Shamir(沙米爾)、Adleman(艾德曼)在題為《獲得數(shù)字簽名和公開(kāi)鑰密碼系統(tǒng)的方法》的論文中提出。RSA一種分組密碼體制。其名稱RSA來(lái)自于三個(gè)發(fā)明者的姓名首字母。公開(kāi)密鑰加密算法（RSA）的安全性它的安全性是基于大整數(shù)素因子分解的困難性，而大整數(shù)因子分解問(wèn)題是數(shù)學(xué)上的著名難題，至今沒(méi)有有效的方法予以解決。

RSA算法設(shè)計(jì)者

公鑰和私鑰是一對(duì)大素?cái)?shù)P、Q的函數(shù)，從一個(gè)公鑰和密文中恢復(fù)出明文的難度等價(jià)于分解兩個(gè)大素?cái)?shù)之積。

RSA得到了世界上的最廣泛的應(yīng)用，ISO在1992年頒布的國(guó)際標(biāo)準(zhǔn)X.509中,將RSA算法正式納入國(guó)際標(biāo)準(zhǔn)。RSA的安全性一直未能得到理論上的證明。但它經(jīng)歷了各種攻擊，至今未被完全攻破。因此可以確定RSA算法的安全性3.4.2RSA算法的實(shí)現(xiàn)步驟RSA算法描述如下：（1）選取不同且足夠大的兩個(gè)素?cái)?shù)：p和q；（2）計(jì)算這兩個(gè)素?cái)?shù)的乘積：n

=p×q；（3）計(jì)算：φ（n）=(P－1)(q－1)；（4）選擇一個(gè)隨機(jī)數(shù)e，滿足：1＜e＜φ(n)，并且e

和φ(n)互質(zhì)，即gcd（e,φ(n)）=1。e即為加密密鑰（5）計(jì)算：d×e≡1modφ(n)，可得到數(shù)d，d即為解密密鑰（6）公鑰PK={n,e}，私鑰SK={n,d}(7)加密：用（n,e）計(jì)算：c=memodn

（8）解密：用（n,d)

計(jì)算：m=cdmodn

關(guān)于：d×e≡1modφ(n)的說(shuō)明"≡"是數(shù)論中表示同余的符號(hào)。公式中，"≡"符號(hào)的左邊必須和符號(hào)右邊同余，也就是兩邊模運(yùn)算結(jié)果相同。顯而易見(jiàn)，不管φ(n)取什么值，"≡"的右邊：1modφ(n)的結(jié)果都等于1；因此，"≡"的左邊d×e的積做模運(yùn)算后的結(jié)果也必須等于1。計(jì)算出d的值，讓這個(gè)同余等式能夠成立。RSA算法流程圖

密鑰的生成選擇p,q為互異素?cái)?shù)計(jì)算n=p*q，(n)=(p-1)*(q-1)選擇整數(shù)e使e與(n)互質(zhì)計(jì)算d，使?jié)M足d*e=1mod(n)公鑰PK={n,e}私鑰SK={n,d}RSA算法舉例：取P=47,q=71,則n=p*q=3337,(n)=(p-1)*(q-1)=46*70=3220隨機(jī)選取e，使e與(n)互質(zhì)，取e=79,

則由：e*d

mod(n)=1，79*dmod3220

=1得d=1019則可得：公鑰pk={n,e}={3337,79}私鑰sk={n,d}={3337,1019}取：p=3，q=11，得出：n=p×q=3×11=33；φ(n)=(p-1)(q-1)=2×10=20；可以用試算的辦法來(lái)尋找d：由e×d≡1modφ(n)→e×d=k×ф（n）＋1取e=3，則有：

3d=k×20＋1，將1，2，3，…，依次代入k，求出d。當(dāng)取k=1，得d=7（當(dāng)取k=4，得d=27)即，當(dāng)e=3，d=7時(shí)，e×d≡1modφ(n)同余等式成立。從而我們可以設(shè)計(jì)出一對(duì)公私密鑰：加密密鑰（公鑰）為：(e,n)=(3,33)；解密密鑰（私鑰）為：(d,n)=(7,33)。如何計(jì)算d

?1、計(jì)算公鑰與私鑰①選擇素?cái)?shù)：

p=17q=11②計(jì)算：n=pq=17×11=187③計(jì)算：?（n）=（p–1）（q-1）=16×10=160④選擇e：

gcd（e,160）=1;選擇e=7⑤確定d：

d×e≡1mod160且d<160，d=23

因?yàn)?3×7=161=1×160+1⑥公鑰：KU={7,187}⑦私鑰：KR={23,187}假設(shè)給定的消息為：M=88，則加密:C=887mod187=11解密:M=1123mod187=88一個(gè)實(shí)際的例子來(lái)幫助理解RSA算法2、英文數(shù)字化。將明文信息數(shù)字化，并將明文按兩個(gè)數(shù)字分組。假定明文英文字母編碼表為按字母順序排列數(shù)值，即：若要對(duì)sias加密，則分組后的明文信息：19，09，01，193、明文加密用戶B的加密密鑰{7,187},將數(shù)字化明文分組信息加密成密文。s,i,a,s=19，09，01，19由C=Memodn得：4、密文解密

用戶B的解密密鑰{23,187}，收到密文，若將其解密，只需要計(jì)算：M≡Cdmodn，即：用戶B得到明文信息為：19，09，01，19。根據(jù)上面的編碼表將其轉(zhuǎn)換為英文，我們又得到了恢復(fù)后的原文“sias”。當(dāng)然，RSA的實(shí)際運(yùn)用要比這復(fù)雜得多，由于RSA算法的公鑰、私鑰的長(zhǎng)度（模長(zhǎng)度）要到1024位甚至2048位才能保證安全，因此，p、q、e的選取、公鑰私鑰的生成，加密解密模指數(shù)運(yùn)算都有一定的計(jì)算程序，需要仰仗計(jì)算機(jī)高速完成。思考1：對(duì)英文字母能用其它方法編碼嗎？思考2：如何對(duì)漢字信息使用RSA加密算法加密？

RSA算法的安全性在RSA密碼應(yīng)用中，公鑰KU是被公開(kāi)的，即e和n的數(shù)值可以被分析者得到。破解RSA密碼的問(wèn)題就是從已知的e和n（n等于pq），想法求出d，這樣就可以得到私鑰來(lái)破解密文。從公式：d*e≡1mod((p-1)(q-1))，可以看出，密碼破解的實(shí)質(zhì)問(wèn)題是：從pq的數(shù)值，去求出(p-1)和(q-1)。換句話說(shuō)，只要求出p和q的值，我們就能求出d的值而得到私鑰。當(dāng)p和q是一個(gè)大素?cái)?shù)的時(shí)候，從它們的積pq去分解因子p和q，這是一個(gè)公認(rèn)的數(shù)學(xué)難題。比如當(dāng)pq大到1024位時(shí)，迄今為止還沒(méi)有人能夠利用任何計(jì)算工具去完成分解因子的任務(wù)。RSA從提出到現(xiàn)在三十余年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。然而，雖然RSA的安全性依賴于大數(shù)的因子分解，但并沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)。即RSA的重大缺陷是無(wú)法從理論上把握它的保密性能如何。此外，RSA的缺點(diǎn)還有：A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長(zhǎng)度太大，為保證安全性，n至少也要600bits以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí)；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長(zhǎng)度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。因此，使用RSA只能加密少量數(shù)據(jù)，大量的數(shù)據(jù)加密還要靠對(duì)稱密碼算法。2009年12月12日，編號(hào)為RSA-768（768bits）數(shù)被成功分解。這一事件威脅了現(xiàn)通行的1024-bit密鑰的安全性，普遍認(rèn)為用戶應(yīng)盡快升級(jí)到2048-bit或以上。RSA-768表示如下：1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

=

3347807169895689878604416984821269081770479498371376856891

2431388982883793878002287614711652531743087737814467999489

×

3674604366679959042824463379962795263227915816434308764267

60322838157396665112792333734171433968102700927987363089173.6.2算法攻擊舉例

常見(jiàn)的攻擊包括：1.字母頻率攻擊；2.對(duì)RSA算法的攻擊；3.對(duì)單向散列算法的“生日”攻擊；4.字典攻擊和重放攻擊。3.6.2.2對(duì)RSA算法的攻擊這些算法代表了人們對(duì)大數(shù)分解（也就是對(duì)RSA攻擊）的探索歷程。最好的算法具有超多項(xiàng)式率（次指數(shù)率）的時(shí)間復(fù)雜度，NFS具有最接近于多項(xiàng)式率的表現(xiàn)。大數(shù)分解仍然是困難的，可是隨著數(shù)論和計(jì)算能力的發(fā)展，它變得容易了。1977年，RonRivest說(shuō)過(guò)分解一個(gè)125位的數(shù)需要花費(fèi)4*1013年。在1994年RSA129被分解了，是利用internet上一些計(jì)算機(jī)的空閑CPU周期一共花了8個(gè)月完成的。1995年，Blacknet密鑰被分解，用了幾十臺(tái)工作站和一臺(tái)MarPar，歷時(shí)3個(gè)月。隨著時(shí)間的推移，可能被分解的密鑰長(zhǎng)度還會(huì)增加。下面是幾種針對(duì)RSA有效的攻擊方法，攻擊的是加密協(xié)議環(huán)節(jié)上的漏洞，而不是RSA本身的。

對(duì)RSA算法的攻擊選擇密文攻擊由于RSA密文是通過(guò)公開(kāi)渠道傳播的，攻擊者可以獲取密文。我們假設(shè)攻擊者為A，密文收件人為T(mén)，A得到了發(fā)往T的一份密文c，他想不通過(guò)分解質(zhì)因數(shù)的方法得到明文。換句話說(shuō)，他需要m=cd。為了恢復(fù)m，他找一個(gè)隨機(jī)數(shù)r，r<n，當(dāng)然他有T的公匙(e,n)。他計(jì)算：x=remodn（用T的公匙加密r）y=x*cmodn（將臨時(shí)密文x與c相乘）t=r-1modn

A知道RSA具有下面的一個(gè)特性：如果x=remodn，那么r=xdmodn選擇密文攻擊 因此他想辦法讓T對(duì)y用T自己的私鑰簽名（實(shí)際上就是把y解密了），然后將結(jié)果u=ydmodn寄回給A。A只要簡(jiǎn)單地計(jì)算：m=t*umodn上面結(jié)論的推導(dǎo)是這樣的：t*umodn=(r-1)*(xd)(cd)modn=(cd)modn=m 要防止這種攻擊的辦法就是不要對(duì)外來(lái)的隨機(jī)信息簽名，或者只對(duì)信息的MD5特征值簽名。在這里就很容易明白為什么要強(qiáng)調(diào)MD5的單向性了，因?yàn)镸D5的結(jié)果是不能預(yù)定的，就是說(shuō)A難以湊出一份剛好能產(chǎn)生y這樣的MD5特征值的明文來(lái)讓T簽名。

對(duì)RSA算法的攻擊過(guò)小的加密指數(shù)e e是一個(gè)小數(shù)并不降低RSA的安全性。從計(jì)算速度考慮，e越小越好?？墒?，當(dāng)明文也是一個(gè)很小的數(shù)時(shí)就會(huì)出現(xiàn)問(wèn)題。例如我們?nèi)=3，而且我們的明文m比n的三次方根要小，那么密文c=memodn就會(huì)等于m3。這樣只要對(duì)密文開(kāi)三次方就可以得到明文。公共模數(shù)攻擊 還有一些對(duì)RSA的攻擊，像公共模數(shù)攻擊。它是指幾個(gè)用戶公用一個(gè)模數(shù)n，各自有自己的e和d，在幾個(gè)用戶之間公用n會(huì)使攻擊者能夠不用分解n而恢復(fù)明文。

對(duì)RSA算法的攻擊RSA的計(jì)時(shí)攻擊法 這是一種另辟蹊徑的方法，是由PaulKocher發(fā)表的。可以發(fā)現(xiàn)，RSA的基本運(yùn)算是乘方取模，這種運(yùn)算的特點(diǎn)是耗費(fèi)時(shí)間，精確取決于乘方次數(shù)。這樣如果A能夠監(jiān)視到RSA解密的過(guò)程，并對(duì)它計(jì)時(shí)，他就能算出d來(lái)。Rivest說(shuō)，抵御這種攻擊最簡(jiǎn)單的方法就是使RSA在基本運(yùn)算上花費(fèi)均等的時(shí)間，而與操作數(shù)無(wú)關(guān)。其次在加密前對(duì)數(shù)據(jù)做一個(gè)變換（花費(fèi)恒定時(shí)間），在解密端做逆變換，這樣總時(shí)間就不再依賴于操作數(shù)了。字典攻擊和重放攻擊字典攻擊 對(duì)于用單向函數(shù)加密的口令文件而言，攻擊者可以編制一個(gè)包括100萬(wàn)個(gè)常用口令的口令表，然后用單向函數(shù)對(duì)這100萬(wàn)個(gè)口令進(jìn)行運(yùn)算，并將結(jié)果保存起來(lái)。只要攻擊者偷出加密后的口令文件，將它與自己的可能的口令文件進(jìn)行比較，再觀察哪個(gè)能匹配，就可以成功破解口令了。重放攻擊 重放攻擊指的是收集特定的IP包，篡改其數(shù)據(jù)，然后再一一重新發(fā)送，欺騙接收的