現(xiàn)代密碼學(xué)總結(jié)

1、現(xiàn)代密碼學(xué)總結(jié) 第一講 緒論· 密碼學(xué)是保障信息安全的核心· 安全服務(wù)包括：機(jī)密性、完整性、認(rèn)證性、不可否認(rèn)性、可用性· 一個(gè)密碼體制或密碼系統(tǒng)是指由明文（m或p）、密文（c）、密鑰（k）、加密算法（E）和解密算法（D）組成的五元組。· 現(xiàn)代密碼學(xué)分類(lèi)：· 對(duì)稱(chēng)密碼體制：（又稱(chēng)為秘密密鑰密碼體制，單鑰密碼體制或傳統(tǒng)密碼體制）密鑰完全保密；加解密密鑰相同；典型算法：DES、3DES、AES、IDEA、RC4、A5· 非對(duì)稱(chēng)密碼體制：（又稱(chēng)為雙鑰密碼體制或公開(kāi)密鑰密碼體制）典型算法：RSA、ECC第二講 古典密碼學(xué)· 代換密碼：

2、古典密碼中用到的最基本的處理技巧。將明文中的一個(gè)字母由其它字母、數(shù)字或符號(hào)替代的一種方法。（1）凱撒密碼：c = E(p) = (p + k) mod (26) p = D(c) = (c k) mod (26)（2）仿射密碼：明文p Z26，密文c Z26 ，密鑰k=(a,b) ap+b = c mod (26)（3）單表代換、多表代換Hill密碼：（多表代換的一種）明文p (Z26)m，密文c (Z26)m ，密鑰K 定義在Z26上m*m的可逆矩陣加密 c = p * K mod 26 解密p = c * K-1 mod 26Vigenere密碼：查表解答（4）轉(zhuǎn)輪密碼機(jī)：· 置

3、換密碼··· ：將明文字符按照某種規(guī)律重新排列而形成密文的過(guò)程列置換，周期置換· 密碼分析：· 統(tǒng)計(jì)分析法：移位密碼、仿射密碼和單表代換密碼都沒(méi)有破壞明文的頻率統(tǒng)計(jì)規(guī)律，可以直接用統(tǒng)計(jì)分析法· 重合指數(shù)法· 完全隨機(jī)的文本CI=0.0385，一個(gè)有意義的英文文本CI=0.065· 實(shí)際使用CI的估計(jì)值CI：L：密文長(zhǎng)。 fi：密文符號(hào)i發(fā)生的數(shù)目。第三講 密碼學(xué)基礎(chǔ)第一部分 密碼學(xué)的信息論基礎(chǔ)· Shannon的保密通信系統(tǒng)模型· 對(duì)稱(chēng)密碼體制· 非對(duì)稱(chēng)密碼體制· 一個(gè)密碼體

4、制是一個(gè)六元組：（P, C, K1, K2, E, D )P-明文空間 C-密文空間 K1 -加密密鑰空間 K2 -解密密鑰空間E -加密變換 D -解密變換 對(duì)任一kK1,都能找到k K2，使得D k (E k (m)=m，mM.· 熵和無(wú)條件保密· 設(shè)隨機(jī)變量X=xi | i=1,2,n, xi出現(xiàn)的概率為Pr(xi) 0, 且 , 則X的不確定性或熵定義為熵H(X)表示集X中出現(xiàn)一個(gè)事件平均所需的信息量(觀察前)；或集X中每出現(xiàn)一個(gè)事件平均所給出的信息量(觀測(cè)后).· 設(shè)X=xi|i=1,2,n, xi出現(xiàn)的概率為p(xi) 0，且i=1,n p(xi)=1

5、; Y=yi|i=1,2,m, yi出現(xiàn)的概率為p(yi) 0，且i=1,m p(yi)=1;則集X相對(duì)于集Y的條件熵定義為· X視為一個(gè)系統(tǒng)的輸入空間，Y視為系統(tǒng)的輸出空間，通常將條件熵H(X|Y)稱(chēng)作含糊度，X和Y之間的平均互信息定義為：I(X,Y)=H(X)-H(X|Y) 表示X熵減少量。· 完善保密的（無(wú)條件保密的）密碼系統(tǒng)（P,C,K,E,D）系統(tǒng)滿足 或 第二部分 復(fù)雜性理論· 算法計(jì)算復(fù)雜性常常用兩個(gè)變量來(lái)度量：時(shí)間復(fù)雜度（計(jì)算復(fù)雜度）T和空間復(fù)雜度S· 假設(shè)一個(gè)算法的計(jì)算復(fù)雜度為O(nt)，其中t為常數(shù)，n為輸入問(wèn)題的長(zhǎng)度，則稱(chēng)這算法的復(fù)

6、雜度是多項(xiàng)式的。具有多項(xiàng)式時(shí)間復(fù)雜度的算法為多項(xiàng)式時(shí)間算法。· 如果一個(gè)算法的復(fù)雜度為O(tf(n)，t為大于1的常數(shù)，f（n）是以n為自變量的多項(xiàng)式函數(shù)，則稱(chēng)該算法的復(fù)雜度是指數(shù)的。當(dāng)f（n）是大于常數(shù)而小于線性函數(shù)時(shí)，稱(chēng)為亞指數(shù)時(shí)間算法。· 如果一個(gè)判定問(wèn)題存在解它的多項(xiàng)式時(shí)間的算法，則稱(chēng)該問(wèn)題屬于P類(lèi).如果一個(gè)判定問(wèn)題不存在解它的多項(xiàng)式時(shí)間的算法，且對(duì)于一個(gè)解答可以在多項(xiàng)式時(shí)間驗(yàn)證其是否正確，則稱(chēng)該問(wèn)題屬于NP類(lèi).第四講 分組密碼· DES算法· 整體結(jié)構(gòu)：Feistel結(jié)構(gòu)· 給定明文，通過(guò)一個(gè)固定初始置換IP來(lái)重排輸入明文塊P中的比特

7、，得到比特串P0=IP(P)=L0R0，這里L(fēng)0和R0分別是P0的前32比特和后32比特· 16輪迭代，密鑰生成按下述規(guī)則進(jìn)行16次迭代，即1i16這里 是對(duì)應(yīng)比特的模2加，f是一個(gè)函數(shù)（稱(chēng)為輪函數(shù)）；16個(gè)長(zhǎng)度為48比特的子密鑰Ki(1i16)是由密鑰k經(jīng)密鑰編排函數(shù)計(jì)算出來(lái)的.· 對(duì)比特串R16L16使用逆置換IP-1得到密文C，即C=IP-1 (R16L16)· 注意：第十六輪迭代左右兩塊不交換· 分組密碼的輪函數(shù)(f)· 長(zhǎng)度為32比特串Ri-1作為第一輸入，以長(zhǎng)度為48比特串Ki作為第二個(gè)輸入，產(chǎn)生長(zhǎng)度為32比特的輸出 ·

8、擴(kuò)展置換（E盒）：32位輸入擴(kuò)展為48位輸出：按照8行6列次序排列，從32,1,2排列，上一行的后兩位一次在下一行的起始位置得到重用。· 密鑰加：按位異或加，計(jì)算· S盒代換：DES中唯一的非線性部分8個(gè)S盒。每個(gè)S盒輸入均為6位，輸出為4位。Bj=b1b2b3b4b5b6, b1b6確定行r的二進(jìn)制表示, b2b3b4b5確定列c的二進(jìn)制表示，行列確定唯一長(zhǎng)度為4的二進(jìn)制數(shù)字· P置換：根據(jù)固定置換P(*)進(jìn)行置換· DES算法的密鑰編排算法· 64比特密鑰K，根據(jù)固定置換PC-1來(lái)處理K得到PC-1（K）=C0D0，C0和D0分別由最前和最

9、后28比特組成（去除8,16,24,32,40,48,56,64這8位奇偶校驗(yàn)位）· 對(duì)1i16， DES的每一輪中使用K的56比特中的48個(gè)比特（壓縮方法：刪除C中的9,18,22,25位和D中的7,9,15,26位）· 計(jì)算Ci=LSi(Ci-1)和Di=LSi(Di-1)，且Ki=PC-2(CiDi)，LSi表示循環(huán)左移兩個(gè)或一個(gè)位置, 具體地, 如果i=1,2,9,16就移一個(gè)位置，否則就移兩個(gè)位置, PC-2是另一個(gè)固定的置換。· DES的解密與加密使用一樣的算法，以密文y作為輸入，以相反順序使用密鑰編排K16,K15,K1，輸出的是明文X·

10、DES算法的擴(kuò)散· 兩輪擴(kuò)散：· 三輪擴(kuò)散：從LO的一塊數(shù)據(jù)影響開(kāi)始· AES算法· 128位（16個(gè)字）輸入明文，128位密鑰長(zhǎng)度，第一次迭代前 明文 密鑰· AES算法整體結(jié)構(gòu)：· AES算法的輪函數(shù)Rijndael輪函數(shù)1）字節(jié)代換（SubByte） 2）行移位（ShiftRow） 3）列混合（MixColumn） 4）密鑰加（AddRoundKey） 字節(jié)代換：字節(jié)代換是非線形變換，獨(dú)立地對(duì)狀態(tài)的每個(gè)字節(jié)進(jìn)行，代換表（即S-盒）是可逆的 S盒可以由以下兩步運(yùn)算得到：· 求輸入元素在m(x)=x8+x4+x3+x+1

11、上的逆元；· 對(duì)上步中所求得的逆元進(jìn)行如下運(yùn)算行移位：行移位是將狀態(tài)陣列的各行進(jìn)行循環(huán)移位，不同狀態(tài)行的位移量不同；第0行不移動(dòng)；第1行左移1字節(jié)；第2行左移2字節(jié)；第3行左移3字節(jié) · 列混合: 其中：（00000010）*(a7a6a5a4a3a2a1a0)=( a6a5a4a3a2a1a00) ,a7為0; =( a6a5a4a3a2a1a00) (00011011),a7為1 （00000001）*(a7a6a5a4a3a2a1a0)= (a7a6a5a4a3a2a1a0)（00000011）*(a7a6a5a4a3a2a1a0)= （00000010）*(a7a6

12、a5a4a3a2a1a0) (a7a6a5a4a3a2a1a0)· 密鑰加:密鑰加是將輪密鑰簡(jiǎn)單地與狀態(tài)進(jìn)行逐比特異或；輪密鑰由種子密鑰通過(guò)密鑰編排算法得到 注：結(jié)尾輪函數(shù)將列混合這一步驟去掉· AES算法的密鑰編排算法· 密鑰編排指從種子密鑰得到輪密鑰的過(guò)程，AES的密鑰編排由密鑰擴(kuò)展和輪密鑰選取兩部分組成,基本原則如下:輪密鑰的總比特?cái)?shù)等于輪數(shù)加1再乘以分組長(zhǎng)度；（10+1）*128=1408）種子密鑰被擴(kuò)展成為擴(kuò)展密鑰輪密鑰從擴(kuò)展密鑰中取，第1輪輪密鑰取擴(kuò)展密鑰的前Nb個(gè)字，第2輪輪密鑰取接下來(lái)的Nb個(gè)字· 密鑰擴(kuò)展：每一列的4個(gè)字節(jié)組成一個(gè)字&g

13、t;對(duì)w數(shù)組擴(kuò)充40個(gè)新列，構(gòu)成總共44列擴(kuò)展密鑰數(shù)組，如下產(chǎn)生（1）如果i不是4的倍數(shù)，那么wi=wi-4 wi-1（2）若果i是4的倍數(shù)，那么wi=wi-4 T(wi-1) T為一個(gè)復(fù)雜的函數(shù)T函數(shù)由三個(gè)部分組成：字循環(huán)，字節(jié)代換和輪常量異或· 字循環(huán)：將1個(gè)字中的4個(gè)字節(jié)循環(huán)左移1個(gè)字節(jié)。即b0 ,b1,b2,b3變換成b1,b2,b3,b4· 字節(jié)代換：對(duì)自循環(huán)的結(jié)果使用S盒（書(shū)上P112表4-15）· 將前兩步的結(jié)果同輪常量Rconj進(jìn)行異或，其中j表示輪數(shù)· 輪密鑰的選取· AES的解密變換· ByteSub的逆變換由代換

14、表的逆表做字節(jié)代換· 行移位運(yùn)算的逆變換是循環(huán)右移，位移量與左移時(shí)相同· 列混合運(yùn)算的逆運(yùn)算是類(lèi)似的，即每列都用一個(gè)特定的多項(xiàng)式d(x)相乘d(x)=0Bx3+0Dx2+09x+0E.· 密鑰加運(yùn)算的逆運(yùn)算是其自身· AES算法的擴(kuò)散第一輪第二輪總體· 其他典型分組密碼SMS4算法·· 128比特明文分為4個(gè)32比特字，分別賦值給四個(gè)寄存器A、B，C，D（D為最高）.進(jìn)行32輪F運(yùn)算，設(shè)每輪輸入為寄存器當(dāng)前狀態(tài)值 和輪密鑰為 ，則輪函數(shù)F為：將寄存器最右邊字A的值移出，高三個(gè)字順次右移32位，F(xiàn)函數(shù)的輸出賦值給最左邊的寄存器

15、字D.32輪的輸出 進(jìn)行反序變換R，然后輸出密文.· 輪函數(shù)F以字為單位進(jìn)行運(yùn)算，輸入寄存器值 和輪密鑰 合成置換T：是一個(gè)可逆變換，由非線性變換和線性變換L復(fù)合而成, 即T(.)=L(.)非線性變換由4個(gè)并行的S盒構(gòu)成線性變換L：· 密鑰編排算法· 加密密鑰長(zhǎng)度為128比特MK· 輪密鑰表示為 ，· 為系統(tǒng)參數(shù)， 為固定參數(shù)，用于密鑰擴(kuò)展算法· 密鑰擴(kuò)展算法：T變換與加密算法輪函數(shù)中的T基本相同,只將其中的線性變換L修改為固定參數(shù)CKi的取值方法為：設(shè) 為 的第j 字節(jié)（i=0,1,31；j=0,1,2,3,即則· 分組密

16、碼的運(yùn)行模式· 為了能在各種場(chǎng)合使用DES，定義了4中DES運(yùn)行模式：ECB,CBC,CFB,OFBAES的另外一種運(yùn)行模式：CTR· ECB模式最簡(jiǎn)單的一種分組密碼工作方式。一次處理一個(gè)明文分組。密文塊可以分別獨(dú)立解密，無(wú)順序要求；密鑰相同時(shí)，明文中相同的64比特分組產(chǎn)生相同的64比特密文塊；不存在錯(cuò)誤傳播，一塊密文傳送錯(cuò)誤只導(dǎo)致對(duì)應(yīng)明文解密錯(cuò)誤；主要用于發(fā)送少數(shù)量的分組數(shù)據(jù)；· CBC模式先對(duì)明文分組，一次對(duì)一個(gè)明文分組加密，加密算法的輸入是當(dāng)前明文分組和前一次密文分組的異或.在產(chǎn)生第1個(gè)密文分組時(shí)，需要有一個(gè)初始向量IV與第1個(gè)明文分組異或；解密時(shí)，IV和解

17、密算法對(duì)第1個(gè)密文分組的輸出進(jìn)行異或以恢復(fù)第1個(gè)明文分組；密鑰相同時(shí)，明文中相同的64比特分組產(chǎn)生不相同的64比特密文塊；存在錯(cuò)誤傳播，一塊密文傳輸錯(cuò)誤會(huì)導(dǎo)致下一塊密文解密失??；· CFB模式加密：設(shè)加密算法的輸入是64比特移位寄存器，其初值為某個(gè)初始向量IV. 加密算法輸出的最左（最高有效位）j比特與明文的第一個(gè)單元P1進(jìn)行異或，產(chǎn)生出密文的第1個(gè)單元C1. 傳送該單元并將輸入寄存器的內(nèi)容左移j位，用C1補(bǔ)齊最右邊（最低有效位）j位. 這一過(guò)程繼續(xù)到明文的所有單元都被加密為止.解密，將加密算法輸出的最左（最高有效位）j比特與密文的相應(yīng)單元異或，產(chǎn)生明文. 反饋到輸入寄存器的值為密文

18、單元消息被看作bit流，無(wú)須分組填充；適合數(shù)據(jù)以比特或字節(jié)為單位出現(xiàn)標(biāo)準(zhǔn)允許反饋任意比特；需要額外的初始向量密文塊需按順序逐一解密密鑰相同時(shí)，明文中相同的64比特分組產(chǎn)生不相同的64比特密文塊.存在錯(cuò)誤傳播（只傳播后面的幾塊）· OFB模式類(lèi)似于CFB, 不同之處在于OFB模式是將加密算法的輸出反饋到移位寄存器，而CFB模式中是將密文單元反饋到移位寄存器消息被看作比特流，無(wú)須分組填充密鑰流可以在已知消息之前計(jì)算，不需要按順序解密不存在比特錯(cuò)誤傳播發(fā)送者和接收者必須保持同步· CTR模式消息被看作bit流，無(wú)須分組填充；只使用加密算法，且所有加密都使用同一密鑰；需要額外的初始

19、向量；密鑰相同時(shí)，明文中相同的分組產(chǎn)生不相同的密文塊；不存在比特錯(cuò)誤傳播；效率，密鑰流可以在已知消息之前計(jì)算，不需要按順序解密；優(yōu)點(diǎn)：（1）硬件效率高，吞吐量?jī)H受可使用并行數(shù)量的限制； （2）軟件效率高，能夠并行計(jì)算 （3）預(yù)處理 （4）隨機(jī)訪問(wèn) （5）可證明安全性 （6）簡(jiǎn)單性· 查分分析思想設(shè)F為輪函數(shù)，共m輪迭代。P：表明明文P1和P2的差分；設(shè)R1：表示明文和密鑰輸入后第i輪輸出R1和R2的差分；· 如果 ，那么，對(duì)2t個(gè)密鑰計(jì)算，· 如果首先選取多個(gè)明文對(duì)，使得至少有一對(duì)為正確明文對(duì)，滿足其次重復(fù)猜測(cè)搜索密鑰 的過(guò)程第五講 流密碼· 序列密碼：

20、又稱(chēng)流密碼。指明文消息按字符逐位地加密的一類(lèi)密碼算法。· 流密碼分類(lèi)：· 同步序列密碼密鑰序列的產(chǎn)生獨(dú)立于明文消息和密文消息的一類(lèi)流密碼。OFB模式是同步序列密碼的一個(gè)例子；特性：發(fā)送方和接收方必須同步；無(wú)錯(cuò)誤傳播；優(yōu)點(diǎn)：容易檢測(cè)插入、刪除、重播等主動(dòng)攻擊；· 自同步序列密碼密鑰序列的產(chǎn)生是密鑰及固定大小的以往密文位的函數(shù)。特性：自同步特性； 有限的錯(cuò)誤傳播；優(yōu)點(diǎn)：接收端和發(fā)送端不同步，只要接收端能連續(xù)地正確地接受到n個(gè)密文符號(hào)，就能重新建立同步；· 流密碼原理密鑰系列產(chǎn)生器分為驅(qū)動(dòng)部分和組合部分。驅(qū)動(dòng)部分產(chǎn)生控制生成器的狀態(tài)序列；組合部分對(duì)驅(qū)動(dòng)部分的各

21、個(gè)輸出序列進(jìn)行非線性組合。驅(qū)動(dòng)器一般利用線性反饋移位寄存器LFSR，特別是利用最長(zhǎng)周期或m序列產(chǎn)生器實(shí)現(xiàn)；非線性反饋移位寄存器也可作為驅(qū)動(dòng)器。· 線性反饋移位寄存器· 反饋移位寄存器(FSR)是由n位的寄存器和反饋函數(shù)組成，如下圖所示，n位的寄存器中的初始值稱(chēng)為移位寄存器的初態(tài).工作原理：反饋函數(shù)f是n個(gè)變?cè)?b1,b2,bn)的布爾函數(shù). · 線性反饋移位寄存器的反饋函數(shù)為線性函數(shù) 設(shè)n級(jí)LFSR的輸出序列ai滿足遞推關(guān)系這種遞推關(guān)系可用一個(gè)一元高次多項(xiàng)式表示，稱(chēng)這個(gè)多項(xiàng)式為L(zhǎng)FSR的特征多項(xiàng)式· 設(shè) 是上的多項(xiàng)式，使的最小的p稱(chēng)為的周期或者階

22、3; n級(jí)LFSR輸出的序列的最大周期是2n-1· 當(dāng)LFSR的寄存器狀態(tài)遍歷2n 1個(gè)非零狀態(tài)時(shí)，序列的周期達(dá)到最大2n 1，這種序列被稱(chēng)為m序列· 若n次不可約多項(xiàng)式p(x)的階為2n-1，則稱(chēng)p(x)為n次本原多項(xiàng)式· ai是周期為2n 1的m-序列的充要條件是其特征多項(xiàng)式f(x)為n階本原多項(xiàng)式· 非線性組合部分· 濾波生成器又叫前饋生成器，一般由LFSR和濾波（前饋）函數(shù)兩部分組成. LFSR可以是一個(gè)，也可以是幾個(gè)，它們輸出的序列共同作為濾波函數(shù)的輸入。濾波函數(shù)要求具有很好的非線性性質(zhì)，以增強(qiáng)生成器的抗攻擊能力。Geffe序列發(fā)生器

23、: 兩個(gè)LFSR作為復(fù)合器的輸人，第三個(gè)LFSR控制復(fù)合器的輸出如果a1, a2, 和a3是三個(gè)LFSR的輸出，則Geffe發(fā)生器的輸出表示為：b = (a1 a2) ( a1 a3) a3 如果3個(gè)LFSR長(zhǎng)度分別為n1，n2和n3，線性復(fù)雜度為(n2+n3)n1+n3周期為3個(gè)LFSR周期的最小公倍數(shù)；如果3個(gè)本院反饋多項(xiàng)式的階數(shù)互素，那么發(fā)生器的周期是3個(gè)LFSR周期之積，即(2n1-1)(2n2-1)(2n3-1)· 鐘控生成器。最簡(jiǎn)單的鐘控生成器是用一個(gè)LFSR控制另一個(gè)LFSR的時(shí)鐘脈沖當(dāng)LFSR1輸出1時(shí)，時(shí)鐘脈沖通過(guò)與門(mén)使LFSR2進(jìn)行一次移位，從而生成下一位；當(dāng)LF

24、SR1輸出0時(shí)，時(shí)鐘脈沖無(wú)法通過(guò)與門(mén)使LFSR2移位（走），從而LFSR2重復(fù)輸出前一位（停）。也稱(chēng)之為走停生成器· 典型流密碼算法· A5算法GSM系統(tǒng)主要使用的序列密碼加密算法，保護(hù)從基站到移動(dòng)設(shè)備傳輸信息x、y、z（位置分別為A、B、C的第9、11、11位）進(jìn)行鐘控，若三個(gè)位中間至少有兩個(gè)為“1”，則為“1”的寄存器進(jìn)行一次進(jìn)動(dòng)，而為“0”的不移。反過(guò)來(lái)，若三個(gè)位中至少有兩個(gè)為“0”，則為“0”的寄存器進(jìn)行一次移位，而為“1”的不移。這種機(jī)制保證了每次至少有兩個(gè)LFSR被驅(qū)動(dòng)移位· RC4算法典型的基于非線性數(shù)組變換的序列密碼。使用了一個(gè)256字節(jié)大小的非線

25、性數(shù)據(jù)表（簡(jiǎn)稱(chēng)S表），依據(jù)表進(jìn)行非線性變換，得到密鑰流。包括密鑰調(diào)度算法（KSA）和偽隨機(jī)生成算法（PRGA）第六講 HASH函數(shù)和MAC· Hash函數(shù)的定義：消息是任意有限長(zhǎng)度，哈希值是固定長(zhǎng)度。性質(zhì)：· 單向性（抗原像）：對(duì)干任意給定的消息，計(jì)算其哈希值容易。但是，對(duì)于給定的哈希值h，要找到M使得H(M)h在計(jì)算上是不可行的· 弱抗碰撞（抗二次原像）：對(duì)于給定的消息M1，要發(fā)現(xiàn)另一個(gè)消息M2，滿足H( M1 )H(M2)在計(jì)算上是不可行的· 強(qiáng)抗碰撞：找任意一對(duì)不同的消息M1，M2 ，使H(M1)H(M2 )在計(jì)算上是不可行的.分類(lèi)：·

26、改動(dòng)檢測(cè)碼MDC不帶密鑰的哈希函數(shù)，主要用于消息完整性· 消息認(rèn)證碼MAC帶密鑰的哈希函數(shù)，主要用于消息源認(rèn)證和消息完整性· MD5算法· 算法過(guò)程描述：· 消息填充填充一個(gè)1和若干個(gè)0使其長(zhǎng)度模512與448同余；再將消息的真實(shí)長(zhǎng)度以64比特表示附在填充結(jié)果后面，使總長(zhǎng)度為512比特的整數(shù)倍。· 初始向量MD5中有A,B,C和D4個(gè)32位的寄存器，最開(kāi)始存放4個(gè)固定的32位的整數(shù)參數(shù)，即初始鏈接變量，用于第一輪運(yùn)算：A=0x01234567 B=0x89ABCDEF C=0Xfedcba98 D=0x76543210· 分組處理（迭

27、代壓縮）壓縮分為4輪，每輪16步函數(shù)運(yùn)算，共64步；512bitMi被均分為16個(gè)子分組（32bit/組）參與每輪16步函數(shù)運(yùn)算。每步的輸入是4個(gè)32bit的鏈接變量和一個(gè)32bit的消息子分組，輸出為32bit；經(jīng)過(guò)4輪候，得到的4個(gè)寄存器值分別于輸入鏈接變量進(jìn)行模加，即是當(dāng)前中間散列值。· 輸出散列值128bit· 步函數(shù)每一輪的16個(gè)步函數(shù)相同，使用同一個(gè)非線性函數(shù)；不同輪的步函數(shù)使用的非線性函數(shù)不相同；四個(gè)非線性函數(shù)：Mj：消息分組Mi的第j（0<=j<=15）個(gè)32bit子分組。<<<s：循環(huán)左移s位常數(shù)Ti為· MD5與M

28、D4從三輪改為四輪；增加了一種邏輯運(yùn)算，第二輪函數(shù)從F(x,y,z)=(xy) v(xz) v(yz)改為(xz) v(y z)，以消弱對(duì)稱(chēng)性；改變第二輪和第三輪訪問(wèn)消息子分組的順序，使其形式更不相似；改變每輪移位量以實(shí)現(xiàn)更快的雪崩效應(yīng)；每步有唯一的加法常數(shù)ti，消除任何輸入數(shù)據(jù)的規(guī)律；每一步與上一步的結(jié)果相加，這將引起更快的雪崩效應(yīng)；· SHA256算法· 算法過(guò)程描述· 消息填充填充一個(gè)1和若干個(gè)0使其長(zhǎng)度模512與448同余；再將消息的真實(shí)長(zhǎng)度以64比特表示附在填充結(jié)果后面，使總長(zhǎng)度為512比特的整數(shù)倍。· 初始變量由前8個(gè)素?cái)?shù)的平方根的小數(shù)部分的

29、前32位(二進(jìn)制)生成用8個(gè)32bit寄存器ABCDEFGH表示。初始鏈接變量存入其中· 壓縮函數(shù)64輪運(yùn)算；512bit分組為單位處理消息對(duì)于64輪中的每一輪的t，使用一個(gè)32bit的Wt，其值由當(dāng)前被處理的512bit消息分組Mi導(dǎo)出；每輪中使用一個(gè)附加常數(shù)Kt（取前64個(gè)素?cái)?shù)的立方根的小數(shù)部分的二進(jìn)制表示的前32bit）· 最后一輪的輸出和第一輪的輸入模232相加產(chǎn)生Hi· 輸出散列值長(zhǎng)度為256比特· SHA256的輪函數(shù)· 第(i-1)塊的輸出鏈接變量a、b、c、d、e、f、g和h分別賦值：a=H0(i-1) b=H1(i-1) c=

30、H2(i-1) d=H3(i-1) e=H4(i-1) f=H5(i-1) g=H6(i-1) h=H7(i-1)· for t=0 to 63:（借助臨時(shí)寄存器T1和T2） a=T1+T2,b=a,c=b,d=c,e=(d+T1),f=e,g=f,h=g其中：Ch(e,f,g)=(ef)(非eg); Maj(a,b,c)=(ab) (ac)(bc) =ROTR2(a)ROTR13(a)ROTR22(a)=ROTR6(e) ROTR11(e)ROTR25(e) 且ROTRn(x)/ SHRn(x)表示對(duì)32bit變量x循環(huán)右移/左移n bit· 計(jì)算第i個(gè)Hash值H(i)

31、H0(i)=a+ H0(i-1) H1(i)=b+ H1(i-1) H2(i)=b+ H2(i-1) H3(i)=c+ H3(i-1)H4(i)=d+ H4(i-1) H5(i)=e+ H5(i-1) H6(i)=f+ H6(i-1) H7(i)=g+ H7(i-1)· 32bit的Wt是從512bit消息中導(dǎo)出的，方法如下：其中（x）= ROTR7(x)ROTR18(x)SHR3(x) (x)= ROTR17(x) ROTR19(x) SHR10(x)· SHA512和SHA284· SHA512填充消息M, 將消息填充到1024的整數(shù)倍；將填充消息分割為N個(gè)1

32、024比特長(zhǎng)的消息塊M(1)，M(2)，M(N)；設(shè)置初始Hash值H(0)；迭代壓縮，80步；N次迭代后的輸出512比特鏈接變量作為消息散列值輸出；SHA284與SHA512僅有兩點(diǎn)不同：初始Hash值H(0)的設(shè)置不同；輸出384比特長(zhǎng)的消息摘要；· 算法過(guò)程描述· 消息填充填充一個(gè)1和若干個(gè)0使其長(zhǎng)度模1024與896同余；再將消息的真實(shí)長(zhǎng)度以128比特表示附在填充結(jié)果后面，使總長(zhǎng)度為1024比特的整數(shù)倍。· 初始變量：· SHA384初始鏈接變量第九個(gè)至第十六個(gè)素?cái)?shù)的平方根小數(shù)部分前64位(二進(jìn)制)生成· SHA512初始鏈接變量前八個(gè)

33、素?cái)?shù)的平方根的小數(shù)部分的前64位(二進(jìn)制)生成· SHA384和SHA512的輪函數(shù)· (i-1)次迭代的輸出賦值給工作變量a、b、c、d、e、f、g和h；a=H0(i-1) b=H1(i-1) c=H2(i-1) d=H3(i-1) e=H4(i-1) f=H5(i-1) g=H6(i-1) h=H7(i-1)· for t=0 to 79：a=T1+T2,b=a,c=b,d=c,e=(d+T1),f=e,g=f,h=g· 計(jì)算第i個(gè)Hash值H(i)H0(i)=a+ H0(i-1) H1(i)=b+ H1(i-1) H2(i)=b+ H2(i-1)

34、H3(i)=c+ H3(i-1)H4(i)=d+ H4(i-1) H5(i)=e+ H5(i-1) H6(i)=f+ H6(i-1) H7(i)=g+ H7(i-1)· 消息認(rèn)證· 消息認(rèn)證碼（MAC）是一種消息認(rèn)證技術(shù)· 發(fā)送方A和接收方B共享密鑰K，若A向B發(fā)送消息M，則A計(jì)算利用C=F (K, M)計(jì)算MAC值；然后將原始消息M和C一起發(fā)送給接收方。接收方B對(duì)收到的消息M用相同的密鑰K進(jìn)行相同的計(jì)算得出新的MAC值C。并將接收到的C與其計(jì)算出的C進(jìn)行比較 ，若相等，則：(1) 接收方可以相信消息未被修改。(2) 接收方可以確信消息來(lái)自真正的發(fā)送方。F是MAC

35、函數(shù)，它利用密鑰K和任意長(zhǎng)度的消息M來(lái)生成一個(gè)固定長(zhǎng)度的短數(shù)據(jù)塊C。· 攻擊目的：偽造攻擊:攻擊者在沒(méi)有密鑰K的情況下，偽造一個(gè)未經(jīng)過(guò)認(rèn)證（M，Mac)對(duì).存在性偽造: 如果攻擊者只能夠?qū)σ粋€(gè)不由他控制的消息進(jìn)行偽造，那么這種偽造攻擊稱(chēng)為存在性偽造攻擊.選擇性偽造: 如果攻擊者能夠?qū)τ伤x擇的消息進(jìn)行偽造，那么這種偽造攻擊稱(chēng)為選擇性偽造攻擊.密鑰恢復(fù)攻擊:攻擊者通過(guò)分析一系列（M，Mac）對(duì)，找到控制這些（M，Mac）對(duì)的密鑰.非自適應(yīng)選擇明文攻擊: 敵手在使用Mac設(shè)備之前，必須已經(jīng)選定要測(cè)試的消息；自適應(yīng)選擇明文攻擊：敵手可以根據(jù)Mac設(shè)備的輸出，自行選擇下一次要測(cè)試的消息.&#

36、183; CBC-MAC· 填充數(shù)據(jù)，形成一串n比特組；其次，使用CBC模式加密這些數(shù)據(jù)；對(duì)最后的輸出分組進(jìn)行選擇處理和截?cái)啵ㄈ绻鹠n）形成MAC填充方法：（不知道數(shù)據(jù)的長(zhǎng)度，則應(yīng)選用填充方法2或3）方法1：對(duì)需要計(jì)算MAC的數(shù)據(jù)的右邊填充若干個(gè)或零個(gè)“0”比特，以便得到一個(gè)比特長(zhǎng)度是n的整數(shù)倍的數(shù)據(jù)串。方法2：對(duì)需要計(jì)算MAC的數(shù)據(jù)的右邊先填充一個(gè)“1”比特，然后填充若干個(gè)或零個(gè)“0”比特，以便得到一個(gè)比特長(zhǎng)度是n的整數(shù)倍的數(shù)據(jù)串。方法3：首先對(duì)需要計(jì)算MAC的數(shù)據(jù)的右邊填充若干個(gè)或零個(gè)“0”比特，以便得到一個(gè)比特長(zhǎng)度是n的整數(shù)倍的數(shù)據(jù)串；其次，在所得到的數(shù)據(jù)串的左邊 填充一個(gè)n比

37、特組，該組包含了未進(jìn)行填充的數(shù)據(jù)的比特長(zhǎng)度的二元表示，其左邊用“0”補(bǔ)齊。· n比特?cái)?shù)據(jù)組D1，D2，Dq,計(jì)算過(guò)程如下：(ek為加密函數(shù))· 置I1=D1，計(jì)算O1=ek(I1)· 對(duì)i=2，3，q，完成下列計(jì)算：Ii=DiOi-1 Oi=ek(Ii)· 對(duì)Oq進(jìn)行選擇處理和截?cái)?，獲得m比特MAC· 攻擊：· 假定MAC1=ek(D1)，則MAC2是兩個(gè)分組的消息（D1|D2）的一個(gè)合法MAC值，其中，D2=D1 MAC1。這種攻擊方法稱(chēng)為”cut and paste”攻擊。· 攻擊者想偽造消息D的合法MAC。首先，選擇消

38、息D1發(fā)送給認(rèn)證者，認(rèn)證者返回MAC1=ek(D1)然后計(jì)算D2=MAC1D，把消息（D1|D2）發(fā)送給認(rèn)證者，認(rèn)證者返回MAC2=ek(ek(D1)D2)則MAC2是消息D的合法MAC值：MAC2=ek(D)· HAMC· 使用Hash函數(shù)H，K1和K2（K1K2）計(jì)算MAC=H(K1 |H (K2|m)，其中K1和K2由同一個(gè)密鑰K導(dǎo)出· 工作流程：· H是hash函數(shù)（嵌入的散列函數(shù)），K是密鑰，K+是K左連填充若干0之后的結(jié)果，B表示計(jì)算消息摘要時(shí)消息分塊的字節(jié)長(zhǎng)度，L表示消息摘要按字節(jié)計(jì)算的長(zhǎng)度，M是消息輸入· ipad表示0x36重

39、復(fù)b/8次，opad表示0x5c重復(fù)b/8次· n表示嵌入散列函數(shù)產(chǎn)生的散列碼長(zhǎng)度· 一般來(lái)說(shuō)K的長(zhǎng)度不小于n；如果K大于b，則將其作為散列函數(shù)的輸入而產(chǎn)生一個(gè)n位的密鑰· HMAC(K,M)=H(K+opad) | H(K+ipad) |M· 在K的左邊加上足夠的0以得到B字節(jié)的K+；· 將（1）得到的K+與ipad異或，產(chǎn)生分組S1；· 將M接在（2）得到的S1后面；· 將H應(yīng)用于（3）的結(jié)果計(jì)算消息摘要；· K+與opad異或產(chǎn)生b位分組S0；（6） 將（4）消息摘要接在（5）的S0后面；（7） 應(yīng)用H于（6

40、）的結(jié)果，輸出該函數(shù)值HMAC(K,M)· CCT認(rèn)證加密標(biāo)準(zhǔn)· 消息認(rèn)證方式· SSL：認(rèn)證加密· IPSec：加密認(rèn)證· SSH：加密、認(rèn)證·· 先認(rèn)證后加密：接受方解密和驗(yàn)證程序都完成后才能確定消息是否有效。具有密文隱藏功能· 先加密后認(rèn)證：傳送信道不安全，傳送信息被篡改（或出現(xiàn)傳送錯(cuò)誤），接受方在解密運(yùn)算之前就可以發(fā)現(xiàn)，從而減少不必要的解密浪費(fèi)；不具有密文隱藏功能第七講 公鑰密碼· 公鑰加密體制的原理：· 參數(shù)生成過(guò)程：接收消息的端系統(tǒng)，產(chǎn)生一對(duì)用來(lái)加密和解密的密鑰公開(kāi)鑰和秘密鑰

41、3; 參數(shù)生成滿足的要求：公開(kāi)密鑰(public-key), 可以被任何人知道, 用于加密或驗(yàn)證簽名；私鑰(private-key), 只能被消息的接收者或簽名者知道,用于解密或簽名；由私鑰及公開(kāi)參數(shù)容易計(jì)算出公開(kāi)密鑰；由公鑰及公開(kāi)參數(shù)推導(dǎo)私鑰是困難的； · 原理圖：· 單向陷門(mén)函數(shù)單向函數(shù)：兩個(gè)集合X、Y之間的一個(gè)映射，使得Y中每一元素y都有唯一的一個(gè)原像xX由x易于計(jì)算它的像y，由y計(jì)算它的原像x是不可行的單向陷門(mén)函數(shù)：該函數(shù)是易于計(jì)算的，但求它的逆是不可行的，除非再已知某些附加信息。一族可逆函數(shù)fk，滿足 Y=fk(X)易于計(jì)算（當(dāng)k和X已知時(shí)）.· X=f

42、-1k(Y)易于計(jì)算（當(dāng)k和Y已知時(shí)）.· X=f-1k(Y)計(jì)算上是不可行的（當(dāng)Y已知但k未知時(shí)）.· 背包密鑰體制若用f充當(dāng)加密函數(shù)對(duì)明文消息m加密:首先將m寫(xiě)成二元表示，再將其分成長(zhǎng)為n的分組；然后求每一分組的函數(shù)值，以函數(shù)值(背包容積)作為密文分組.· 超遞增背包體制（1）解法：已知s為背包容積，對(duì)A從右向左檢查每一元素，以確定是否在解中:· 若san，則an在解中，令xn=1；若s<an，則an不在解中，令xn=0. 然后令2) 對(duì)an-1重復(fù)上述過(guò)程，一直下去，直到檢查出a1是否在解中.3) 檢查結(jié)束后得解 x=(x1x2xn).若XA

43、=S，則背包問(wèn)題的解為X；否則原背包問(wèn)題無(wú)解 （2）偽裝，防攻擊方法：模數(shù)k和乘數(shù)t皆取常量，滿足k>ai，且gcd(t,k)=1，即t在模k下有乘法逆元.bit·ai mod k, i=1,2,n.得新的背包向量B=(b1,b2,bn)，記為 Bt·A mod k.用戶以B作為自己的公開(kāi)密鑰, t、t-1和k可作為其秘密的陷門(mén)信息，即解密密鑰.· 加密運(yùn)算：對(duì)明文分組X=(x1x2xn)的加密為c=f(x)=B·Xt·A·X mod k· 解密運(yùn)算：首先由st-1 c mod k求出s作為超遞增背包向量A的容積，再解

44、背包問(wèn)題即得x=(x1x2xn).· RSA算法（1）密鑰的產(chǎn)生· 選兩個(gè)安全的大素?cái)?shù)p和q。· 計(jì)算n=p×q，(n)=(p-1)(q-1),其中(n)是n的歐拉函數(shù)值。· 選一整數(shù)e，滿足1<e<(n)，且gcd(n),e)=1。· 計(jì)算d，滿足d·e1 mod (n),即d是e在模(n)下的乘法逆元，因e與(n)互素，由模運(yùn)算可知，它的乘法逆元一定存在。 · 以e,n為公開(kāi)鑰,d,n為秘密鑰。（2）加密：cme mod n（3）解密：mcd mod n· RSA的計(jì)算問(wèn)題模指數(shù)運(yùn)算的快速

45、算法求am可如下進(jìn)行，m寫(xiě)成二進(jìn)制表示法：m=bk2k+bk-12k-1+b12+b0，所以· ELGamal算法（1）密鑰的產(chǎn)生首先選擇一素?cái)?shù)p,生成元g和小于p的隨機(jī)數(shù)x，計(jì)算ygx mod p，以(y, g, p)作為公開(kāi)密鑰，x作為秘密密鑰.（2）加密過(guò)程 隨機(jī)選一與p-1互素的整數(shù)k，0<=k<=p-1 計(jì)算密文對(duì): C = C1,C2, 發(fā)送給接收者C1gk mod p, C2ykM mod p. （3）解密過(guò)程 （4）k永久保存？不能重復(fù)使用？ 攻擊者若已知k，可以計(jì)算yk,然后用C2/yk就得到明文；若是k重復(fù)使用，則C2/C2=M/M,知道其中的一個(gè)明文

46、，另一個(gè)可求。· 橢圓曲線密碼體制（1）密碼學(xué)中通常采用有限域上的橢圓曲線，它指曲線方程定義式中，所有系數(shù)都是某一有限域GF(p)中的元素（其中p為一大素?cái)?shù)）.其中最為常用的是y2x3+ax+b(mod p) (a,bGF(p), 4a3+27b2(mod p)0) 定義的曲線.（2）設(shè)P=(x1,y1)，Q=(x2,y2)，P-Q，則P+Q=(x3,y3)由以下規(guī)則確定：x32-x1-x2(mod p)y3(x1-x3)-y1(mod p)其中，· 利用橢圓曲線實(shí)現(xiàn)ElGamal密碼體制（1）密鑰生成：選取一條橢圓曲線，并得Ep(a,b)，取Ep(a,b)的一個(gè)生成元G，Ep(a,b)和G作為公開(kāi)參數(shù).用戶A選nA作為秘密鑰，并以PA=nAG作為公開(kāi)鑰.（2）加密：B若想向A發(fā)送消息Pm，選取一隨機(jī)正整數(shù)kCm=kG, Pm+kPA（3）解密：以密文點(diǎn)對(duì)中的第二個(gè)點(diǎn)減去用自己的秘密鑰與第一個(gè)點(diǎn)的倍乘Pm+kPA-nAkG=Pm+k(nAG)-nAkG=Pm第八講 數(shù)字簽名· 數(shù)字簽名的性質(zhì)：（數(shù)據(jù)完整性、數(shù)據(jù)源認(rèn)證性、數(shù)據(jù)不可否認(rèn)性） 能夠驗(yàn)證簽名產(chǎn)生者的身份，以及產(chǎn)生簽名的日期和時(shí)間.能保證被簽消息的內(nèi)容的完整性.數(shù)字簽名可由第三方公開(kāi)驗(yàn)證，從而能夠解決通信雙方的上述爭(zhēng)議.· 數(shù)字簽名電子簽名，是指附加在某一電子文檔中的一組特定