第3章密碼學基礎(chǔ)lll密碼學的基本概念和術(shù)語對稱和非對稱密碼的區(qū)別古典密碼學的基本方法掌握DES算法、AES算法RSA算法的基本原理3.1密碼學概述3.1.1密碼學的發(fā)展史愷撒（Caesar）密碼維吉尼亞密碼（Vigenere

cypher）“恩格瑪（Enigma）”密碼機DES（數(shù)據(jù)加密標準）公開密鑰密碼量子密碼學密碼學的發(fā)展史大體上可以歸結(jié)為三個階段第一階段：1949年之前，密碼學還不是科學,而是藝術(shù)。第二階段：1949～1975年，密碼學成為科學。第三階段：1976年以后，密碼學的新方向——公鑰密碼學。3.1.2密碼系統(tǒng)通常一個密碼體制可以表達為一個五元組（M，C，K，E，D），其中：（1）M是可能明文的有限集稱為明文空間（2）C是可能密文的有限集稱為密文空間（3）K是一切可能密鑰構(gòu)成的有限集稱為密鑰空間（4）對于密鑰空間的任一密鑰有一個加密算法和相應的解密算法使得Ek：M->C和

Dk:C->M分別為加密和解密函數(shù)，且滿足Dk（Ek（M））=M。3.1.3密碼的分類1、按應用的技術(shù)或歷史發(fā)展階段劃分：2、按保密程度劃分：3、按密鑰方式劃分：4、按明文形態(tài)：5、按編制原理劃分：3.1.4近代加密技術(shù)1、對稱加密算法對稱加密算法（synmetric

algorithm），也稱為傳統(tǒng)密碼算法，其加密密鑰與解密密鑰相同或很容易相互推算出來，因此也稱之為秘密密鑰算法或單鑰算法。對稱算法分為兩類，一類稱為序列密碼算法（streamcipher），另一種稱為分組密碼算法（blockcipher）。對稱加密算法的主要優(yōu)點是運算速度快，硬件容易實現(xiàn)；其缺點是密鑰的分發(fā)與管理比較困難，特別是當通信的人數(shù)增加時，密鑰數(shù)目急劇膨脹。2、非對稱加密體制非對稱加密算法（Asynmetric

Algorithm）也稱公開密鑰算法（Public

Key

Algorithm）。公開密鑰體制把信息的加密密鑰和解密密鑰分離，通信的每一方都擁有這樣的一對密鑰。其中加密密鑰可以像電話號碼一樣對外公開，由發(fā)送方用來加密要發(fā)送的原始數(shù)據(jù)；解密密鑰則由接收方秘密保存，作為解密時的私用密鑰。公開密鑰體制最大的優(yōu)點就是不需要對密鑰通信進行保密，所需傳輸?shù)闹挥泄_密鑰。這種密鑰體制還可以用于數(shù)字簽名，。公開密鑰體制的缺陷在于其加密和解密的運算時間比較長，這在一定程度上限制了它的應用范圍。3.1.5密碼的破譯1、密鑰的窮盡搜索2、密碼分析已知明文的破譯方法選定明文的破譯方法差別比較分析法3、其它密碼破譯方法3.2古典密碼學3.2.1代換密碼代換密碼的特點是：依據(jù)一定的規(guī)則，明文字母被不同的密文字母所代替。1、移位密碼移位密碼基于數(shù)論中的模運算。因為英文有26個字母，故可將移位密碼定義如下：令P={A,B,C,……Z}，C={A,B,C,……Z},K={0，1，2,……25}，加密變換：Ek（x）=（x+k）mod

26解密變換：Dk（y）=（y-k）mod

262、單表代換密碼單表代換密碼的基本思想是：列出明文字母與密文字母的一一對應關(guān)系，明文AbcDefghijklm密文WJANDYUQIBCEF明文nopQrstuvwxyz密文GHKLMOPRSTVXZ例如：明文為networksecurity,則相就的密文為：GDPTHMCODARMIPX。3、多表替換密碼Vigenere密碼是一種典型的多表替換密碼算法。算法如下：設(shè)密鑰K=k1k2……kn,明文M=m1m2……mn,加密變換:ci≡（mi+ki）mod

26,i=1,2,……,n解密變換：mi≡（ci-ki）mod

26,i=1,2,……,n例如：明文X=cipher

block,密鑰為：hit則把明文劃分成長度為3的序列：cip

her

blo

ck每個序列中的字母分別與密鑰序列中相應字母進行模26運算，得密文：JQI

OMK

ITH

JS3.2.2置換密碼置換密碼的特點是保持明文的所有字母不變，只是利用置換打亂明文字母出現(xiàn)的位置。置換密碼體制定義如下：令m為一正整數(shù)，P=C={A,B,C,……Z}，對任意的置換π（密鑰），定義:加密變換：Eπ（x1,x2,……,xm）=（xπ（1）,xπ（2）……,xπ（m））,-1π

（1）

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

x

-1

（2）……,-1π

（m）x

）,置換密碼也不能掩蓋字母的統(tǒng)計規(guī)律，因而不能抵御基于統(tǒng)計的密碼分析方法的攻擊。3.3對稱密碼學3.3.1分組密碼概述3.3.2Feistel網(wǎng)絡1、擴散和混亂擴散和混亂是由Shannon提出的設(shè)計密碼系統(tǒng)的兩個基本方法，目的是抵抗攻擊者對密碼的統(tǒng)計分析。擴散就是指將明文的統(tǒng)計特性散布到密文中去混亂就是使密文和密鑰之間的統(tǒng)計關(guān)系變得盡可能復雜2、Feistel網(wǎng)絡結(jié)構(gòu)及特點Feistel提出利用乘積密碼可獲得簡單的代換密碼。將明文分組分為左右兩個部分：L0，R0，數(shù)據(jù)的這兩部分通過n輪（round）處理后，再結(jié)合起來生成密文分組；第i輪處理其上一輪產(chǎn)生的Li-1和Ri-1和K產(chǎn)生的子密鑰Ki

作為輸入。一般說來，子密鑰Ki與K不同，相互之間也不同，它是用子密鑰生成算法從密鑰生成的；每一輪的處理的結(jié)構(gòu)都相同，置換在數(shù)據(jù)的左半部分進行，其方法是先對數(shù)據(jù)的右半部分應用處理函數(shù)F，然后對函數(shù)輸出結(jié)果和數(shù)據(jù)的左半部分取異或（XOR）；處理函數(shù)F對每輪處理都有相同的通用結(jié)構(gòu)，但由循環(huán)子密鑰Ki來區(qū)分；在置換之后，執(zhí)行由數(shù)據(jù)兩部分互換構(gòu)成的交換；解密過程與加密過程基本相同。規(guī)則如下：用密文作為算法的輸入，但以相反順序使用子密鑰Ki；加密和解密不需要用兩種不同的方法。3.3.3

DES算法1、算法描述DES算法流程如圖3-4所示。首先把明文分成若干個64-bit的分組，算法以一個分組作為輸入，通過一個初始置換（IP）將明文分組分成左半部分（L0）和右半部分（R0），各為32-bit。然后進行16輪完全相同的運算，這些運算我們稱為函數(shù)f，在運算過程中數(shù)據(jù)與密鑰相結(jié)合。經(jīng)過16輪運算后，左、右兩部分合在一起經(jīng)過一個末轉(zhuǎn)換（初始轉(zhuǎn)換的逆置換IP-1），輸出一個64-bit的密文分組。S-盒置換，將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,擴展置換3212345456789891011121312131415161716171819202120212223242524252627282928293031321P-置換16

7

20

21291228171152326518311028241432273919133062211425子密鑰的生成密鑰通常表示為64-bit，但每個第8位用作奇偶校驗，實際的密鑰長度為56-bit。在DES的每一輪運算中，從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輪，相應左移位數(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。3、三重DES如上所言，DES一個致命的缺陷就是密鑰長度短，并且對于當前的計算能力，56位的密鑰長度已經(jīng)抗不住窮舉攻擊，而DES又不支持變長密鑰。但算法可以一次使用多個密鑰，從而等同于更長的密鑰。三重DES算法表示為：C=EK3（DK2（EK1（M）））

通常取K3=K1，則上式變?yōu)椋篊=EK1（DK2（EK1（M）））這樣對于三重DES的窮舉攻擊需要2112次，而不是DES的264次了。3.3.5對稱密碼的工作模式1、電子密碼本模ECBECB模式的缺點是：如果密碼分析者有很多消息的明密文對，那就可能在不知道密鑰的情況下恢復出明文；更嚴重的問題是敵手通過重放，可以在不知道密鑰情況下修改被加密過的消息，用這種辦法欺騙接收者。2、密碼分組鏈模式CBC加密：Ci=Ek（Pi⊕Ci-1）解密：Pi=Ci-1⊕Dk

（Ci）3、密碼反饋模式CFB在CFB模式下，設(shè)分組長度為n，數(shù)據(jù)可以在比分組長度小的k比特字符里進行加密（1≤k≤n）（稱為k比特反饋模式）。4、出反饋模式OFBOFB模式實際上就是一個同步流密碼，通過反復加密一個初始向量IV來產(chǎn)生一個密鑰流，將此密鑰流和明文流進行異或可得密文流。仍然需要一個初始向量（IV）。IV應當唯一但不須保密。加密和解密可表示為：加密：S0=IV；Si=Ek（Si-1）；Ci=Pi⊕Si解密：Pi=Ci⊕Si；Si=Ek（Si-1）（5）計數(shù)模式CTR該模式使用一個計數(shù)ctr（也是一個初始向量）。如圖3-17所示。加密：Ci=Ek（ctr+i）⊕Pi解密：Pi=Ek（ctr+i）⊕Ci3.4非對稱密碼體制3.4.1

RSARSA算法的思路如下：為了產(chǎn)生兩個密鑰，先取兩個大素數(shù)，p和q。為了獲得最大程度的安全性，兩數(shù)的長度一樣。計算乘積n=p*q，然后隨機選取加密密鑰e，使e和（p-1）*（q-1）互素。最后用歐幾里得（Euclidean）擴展算法計算解密密鑰d，d滿足ed≡1

mod

（p-1）（q-1），即d≡e-1

mod

（p-1）（q-1）。則e和n為公開密鑰，d是私人密鑰。兩個大數(shù)p和q加密消息時，首先將消息分成比n小的數(shù)據(jù)分組（采用二進制數(shù)，選到小于n的2的最大次冪），設(shè)mi表示消息分組，ci表示加密后的密文，它與mi具有相同的長度。加密過程：ci=mie（modn）解密過程：mi=cid（mod

n）一個實際的例子來幫助理解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=1

mod

160且d

<160，

d=23因為23×7=161=

1×160+1⑥公鑰KU={7,187}⑦私鑰KR={23,187}假設(shè)給定的消息為：M=88，則加密:C

=

887解密:M

=

1123mod

187

=