現(xiàn)代密碼學(xué)知識(shí)點(diǎn)整理

1、第一章基本概念1.密鑰體制組成部分：明文空間，密文空間，密鑰空間，加密算法，解密算法2、一個(gè)好密鑰體制至少應(yīng)滿(mǎn)足的兩個(gè)條件：(1)已知明文和加密密鑰計(jì)算密文容易；在已知密文和解密密鑰計(jì)算明文容易；(2)在不知解密密鑰的情況下，不可能由密文c推知明文3、密碼分析者攻擊密碼體制的主要方法：(1)窮舉攻擊(解決方法：增大密鑰量)(2)統(tǒng)計(jì)分析攻擊(解決方法：使明文的統(tǒng)計(jì)特性與密文的統(tǒng)計(jì)特性不一樣)(3)解密變換攻擊(解決方法：選用足夠復(fù)雜的加密算法)4、四種常見(jiàn)攻擊(1)唯密文攻擊：僅知道一些密文(2)已知明文攻擊：知道一些密文和相應(yīng)的明文(3)選擇明文攻擊：密碼分析者可以選擇一些明文并得到相應(yīng)的密

2、文(4)選擇密文攻擊：密碼分析者可以選擇一些密文，并得到相應(yīng)的明文【注：以上攻擊都建立在已知算法的基礎(chǔ)之上；以上攻擊器攻擊強(qiáng)度依次增加；密碼體制的安全性取決于選用的密鑰的安全性】第二章古典密碼(一)單表古典密碼1、定義：明文字母對(duì)應(yīng)的密文字母在密文中保持不變2、基本加密運(yùn)算設(shè) q 是一個(gè)正整數(shù)，Zq =0,1,2,.,q f; Zq =k w Zq |gcd(k,q) =1(1)加法密碼加密算法：X =Y = Zq；父=Zq,對(duì)任意 mW X;k w k ,密文為:c = Ek(m) = (m + k) mod q密鑰量：q (2)乘法密碼加密算法：X =Y =Zq尸=Zq，對(duì)任思 m= X;

3、 ku K ，管又為：c = Ek(m) = km mod q解密算法：m = Dk(c) = k'cmod q密鑰量：(q)(3)仿射密碼 加密算法：X =Y=Zq;K=(k1,k2)|k1 =Zq,k2=Zq,對(duì)任意 m 之 X* =的*2產(chǎn)需；密又c = Ek（m）=（k1 k2m）mod q解密算法：m = Dk(c) = k2(c-k1)mod q密鑰量：q (q)(4)置換密碼加密算法：X =Y =Zq;Zq上的全體置換的集合，對(duì)任意mwX;k=crWM ,密文 q qc = Ek (m) - (m)密鑰量：q!仿射密碼是置換密碼的特例3.幾種典型的單表古典密碼體制11)

4、Caeser 體制:密鑰 k=3(2)標(biāo)準(zhǔn)字頭密碼體制：4.單表古典密碼的統(tǒng)計(jì)分析(1) 26個(gè)英文字母出現(xiàn)的頻率如下：頻率約為0.120.06 至U 0.09之間約為0.04約0.015到0.028之間小于0.01字母et,a,o,i.n,s ,h,rd,lc,u,m,w,f,g ,y,p,bv,k,j,x,q,z【注：出現(xiàn)頻率最高的雙字母：th ;出現(xiàn)頻率最高的三字母：the】(二)多表古典密碼1 .定義：明文中不同位置的同一明文字母在密文中對(duì)應(yīng)的密文字母不同2 .基本加密運(yùn)算(1)簡(jiǎn)單加法密碼加密算法：設(shè)Xn =Yn=Z：,M=Z：,對(duì)任意 m = (m1,.,mn)w Xn,k = (

5、k1,.,kn)WM,密文:c =Ek(m) ug k1,.,mn kn)密鑰量：qn(2)簡(jiǎn)單乘法密碼密鑰量：(q)n1 .簡(jiǎn)單仿射密碼密鑰量：qn ：(q)n2 .簡(jiǎn)單置換密碼密鑰量：(q!)n(3)換位密碼密鑰量：n!(4)廣義置換密碼密鑰量：(qn)!(5)廣義仿射密碼密鑰量：qn%3 .幾種典型的多表古典密碼體制11) Playfair 體制：密鑰為一個(gè)5X5的矩陣加密步驟：a.在適當(dāng)位置闖入一些牛I定字母，譬如q,使得明文字母串的長(zhǎng)度為偶數(shù)，并且將明文字母串按兩個(gè)字母一組進(jìn)行分組，每組中的兩個(gè)字母不同。b.明文m1m2對(duì)應(yīng)的密文c1c2的確定：m1和m2同行或同列，則 。為m1后的

6、字符，c2為m?后的字符；若 色和m2既不同行也不同列，則c1c2在mm2所確定的矩形的其他兩個(gè)角上，J和R同行，C2和m2同行。(2) Vigenere 體制設(shè)明文 m =m1m2.mn,密鑰 k = k1k2.kn則密文： c = Ek(m) =G ,其中 c =(mi ki)mod 26 i =1,2,.n當(dāng)密鑰長(zhǎng)度比明文長(zhǎng)度短時(shí)，密鑰可周期性地重復(fù)利用。(3) Vernam體制設(shè) 明 文 m =m1m2m.，密 鑰k = k1k2. R.其 中，mi, ki w GF (2)i之1則 密 文c =c1c2. .q.,其中 ci =mi 份 ki i 21(4) Hill 體制設(shè)明文m

7、=(m1m2.mn) w Z26 ,密文c = 9&.6)w Z26,密鑰為Z26上的nXn街可逆方陣K =(kij)n洵，則：c = mK mod 261m = cK mod 264.多表古典密碼的統(tǒng)計(jì)分析(1)分析步驟： 確定密鑰字的長(zhǎng)度；確定密鑰的內(nèi)容(2)確定密鑰字的常用方法：Kasisiki測(cè)試法和重合指數(shù)法Kasisiki測(cè)試法可以找出可能密鑰；而重合指數(shù)法可以進(jìn)一步確定密鑰kasisiki 測(cè)試法步驟：a.尋找密文中長(zhǎng)度至少為 3的相同的密文片段；b.計(jì)算沒(méi)對(duì)密文片段之間的距離為d1,d2,.,di ; c.計(jì)算可能密鑰m = gcd(d1,d2,.,di)重合指數(shù)法：2

8、5X fi(fi-1)25Ic(x)八 Pi2 =0.065n(n -1)y其中fi和Pi分別為英文字母A,B,.,Z在長(zhǎng)度為n的英文字符串中出現(xiàn)的次數(shù)，及各字符出現(xiàn)的概率第三章香農(nóng)理論1、密碼體制各組成部分的嫡之間的關(guān)系：H(K |C) =H (K) H(M )-H(C)2、語(yǔ)言L的冗余度:Rl =1Hllog2|X |3、偽密鑰(1)定義：密碼分析者得到眾多可能密鑰中除正確密鑰之外的一個(gè)密鑰(2)對(duì)于任意一個(gè)密文，用不同的密鑰進(jìn)行解密，如果得到的有意義的明文越多，則偽密 鑰也越多。這是判斷哪個(gè)密鑰正確的難度就越大。(3)對(duì)于一個(gè)密鑰體制，設(shè) X是明文字母表，丫是密文字母表，并且|X|=|Y

9、| ，設(shè) Rl 是明文語(yǔ)言的冗余度，假設(shè)密鑰的選取滿(mǎn)足均勻分布，則對(duì)于任意一個(gè)場(chǎng)地為n的密鑰字母串,當(dāng)n充分大時(shí)，萎靡要的期望數(shù)目sn滿(mǎn)足:r -J-1n | X |n Rl(4)唯一解距離log | K |令sn = 0 ,解之：no定1一LRl log |X |一個(gè)密鑰體制的唯一解距離就是密碼分析者在有足夠的計(jì)算時(shí)間的情況下, 算出正確密鑰所需的密文的平均長(zhǎng)度。能夠唯一的計(jì)明文語(yǔ)言的冗余度越大，唯一解距離就越小，密碼分析者在唯密文攻擊的情況下就越容易 求得正確的密鑰。第三章DES（一）DES算法1 .基本參數(shù)分組加密算法：明文和密文為64位分組長(zhǎng)度對(duì)稱(chēng)算法：加密和解密除密鑰編排不同外，使用

10、同一算法密鑰長(zhǎng)度：有效密鑰 56位，但每個(gè)第8位為奇偶校驗(yàn)位，可忽略密鑰可為任意的56位數(shù)，但存在弱密鑰，容易避開(kāi)采用混亂和擴(kuò)散的組合，每個(gè)組合先替代后置換，共 16輪2 .加密流程圖設(shè)明文5=則DES的加密過(guò)程可描述為:J = &T鳥(niǎo)=上一對(duì) K）/= 1216DES的第版加密結(jié)構(gòu)圖3 .子密鑰的產(chǎn)生(二)分組密碼的工作模式1 .分類(lèi)電碼本(ECB)模式密碼分組鏈接(CBC)模式密碼反饋(CFB)模式輸出反饋(OFB)模式計(jì)數(shù)器模式(CTR)2 .總評(píng)(1) ECB莫式簡(jiǎn)單、高速，但最弱，易受重發(fā)和替換攻擊，一般不采用。(2) CBC CFG OFB莫式的選用取決于實(shí)際的特殊需求。(

11、3)明文不易丟信號(hào)，對(duì)明文的格式?jīng)]有特殊要求的環(huán)境可選用CBC模式。需要完整性認(rèn)證功能時(shí)也可選用該模式。(4)不易丟信號(hào)，或?qū)γ魑母袷接刑厥庖蟮沫h(huán)境，可選用CFB模式。(5)信號(hào)特別容易錯(cuò)，但明文冗余特別多，可選用OF瞰式。第四章AES1.AES的理論基礎(chǔ)1 1) AES的字節(jié)運(yùn)算AES中一個(gè)字節(jié)是用有限域GF(28)上的元素表示，通過(guò)倍成函數(shù) xtime ()實(shí)現(xiàn)(2)AES的字運(yùn)算AES中的32位字表示為系數(shù)在有限域GF(28)上的次數(shù)小于4的多項(xiàng)式，即a(x)= a3x3 a2x2 a1x a02 .AES加密(1) AES密碼是一種迭代式密碼結(jié)構(gòu)，但不是Feistel 密碼結(jié)構(gòu)(2)

12、對(duì)于AES算法，算法的輪數(shù)依賴(lài)于密鑰長(zhǎng)度 ：將輪數(shù)表示為Nr,當(dāng)Nk =4時(shí),Nr = 10; 當(dāng)Nk =6時(shí),Nr = 12;當(dāng)Nk =8時(shí)Nr= 14?！酒渲校好荑€的列數(shù)記為 Nk, Nk =密鑰長(zhǎng)度(bits ) + 32(bits) 。 Nk可以取白值為 4、6和8,對(duì)應(yīng)的密鑰長(zhǎng)度分別為 128位、192位和256 位】(3)加密過(guò)程：(以128位為例)AES需迭代十輪，需要 11個(gè)子密鑰。前面9輪完全相同，每輪包括4階段，分別是字節(jié)代換(SubBytes )、行移位(Shift Rows)、列混淆(Mix Columns)和輪密鑰加(Add Round Key);最后一輪只3個(gè)階段，

13、缺少列混淆。明文第10輪密文3.AES的解密加密的逆過(guò)程4.AES的安全性(1)抗差分分析和線性分析(基于軌跡策略)(2)抗窮舉密鑰攻擊(3)對(duì)密鑰的選擇沒(méi)有任何限制，還沒(méi)有發(fā)現(xiàn)弱密鑰和半弱密的存在第五章RSA(一)公鑰密碼體制1 .為解決的兩個(gè)問(wèn)題：密鑰的分配；數(shù)字簽名2 .對(duì)公鑰密碼體制的攻擊(1)窮舉法(2)根據(jù)公鑰計(jì)算私鑰(二)RSA算法1.體制原理(1)選取兩個(gè)大素?cái)?shù)p和q (保密)(2)計(jì)算 n=pq(公開(kāi))，4(n) =(p _1)(q_1)(保密)(3)隨機(jī)選取正整數(shù) e, 1 <e < (n),滿(mǎn)足gcd(e*(n) =1, e是公開(kāi)的加密密鑰。(4)計(jì)算d,滿(mǎn)足

14、ed三1(mod1(n) , d是保密的解密密鑰。(5)加密變換：對(duì)明文 mwzn,密文為c = memodn(6)解密變換：對(duì)密文 c w zn,明文為m = cd mod n【解密變換是加密變換的逆變換的證明】2.p和q選擇的限制(1) p和q的長(zhǎng)度應(yīng)該差不多(2) p1和q1都應(yīng)該包含大的素因子(3) gcd( p-1, q-1)應(yīng)該很小(三)大素?cái)?shù)生成1 .素?cái)?shù)分布定定理：設(shè)x > 0,兀(x)為不大于x的素?cái)?shù)的個(gè)數(shù)，則lim 7T(x) 1nx = 1。 x 二 x【注：素?cái)?shù)的分布極不均勻，素?cái)?shù)越大，分布越稀疏?！? .Legendra 符號(hào)設(shè)p>2是一個(gè)素?cái)?shù)，對(duì)任意整數(shù)

15、 a之0,0 若a 三0(mod p)(亙)=J1若a是模p的平方剩余p -1若a是模p的非平方剩余3 .Jacobi 符號(hào)4 .模n的大數(shù)哥乘的快速算法5 . Solovay Strassen 素性測(cè)試測(cè)試的主要依據(jù)：設(shè) p>2是一個(gè)素?cái)?shù)，則對(duì)于任意整數(shù)a >0,盧)三a(p-1)/2(mod p)p第六章序列密碼與移位寄存器1 .序列密碼的基本原理2 .移位寄存器與移位寄存器序列(1)基本構(gòu)造16t才。時(shí)狀態(tài) 由=(成門(mén)一t +1 時(shí)狀態(tài)=+反饋移位寄存器序列：a0, a1, a2，at,反饋移位寄存器狀態(tài)序列：s0,s1，s2，st，(2)線性移位寄存器的表示線性遞推式(一元

16、多項(xiàng)式)： %4rl_+心理七十_之+%r1>一°聯(lián)系多項(xiàng)式(令f Ixj -1+c1x+c2x2+,.+cr1xn生成矩陣：設(shè)一個(gè)GF(q)上的門(mén)階線性移位寄存器的反饋函數(shù)為 /(.C1，Jl2,= 一(n-1 2 tig其年/6 GF3. w該線性移位寄存器在時(shí)刻t時(shí)的狀態(tài)為= £=例十一“£十片_1 L ,00。-*- 0 C Fn )1 0 (I * 0<7|_ I因?yàn)樵摼€性移位寄存器在時(shí)刻十+ 1時(shí)的狀態(tài)SJ+1 = (at+lf at+3< * ，0t+n)A。 1 口 口 u -rn.2q “三一 0 口 1 0 一01) 0 (I

17、 -*- 0 1 -cij其中fQ+rt = 一小” r.mi - rin(+n- 1 所以我們有再 ±+=tTf(3)線性移位寄存器序列極小多項(xiàng)式與周期a的極小多P(f)。故其極小多定義：對(duì)于一個(gè)移位寄存器序列 a,稱(chēng)其聯(lián)系多項(xiàng)式中次數(shù)最低的多項(xiàng)式為 項(xiàng)式。定義：滿(mǎn)足f(x)|1-xr的最小正整數(shù)r為f(x)的周期，記為p(f(x),簡(jiǎn)記為EG x4 +x3 +x2 + x+1 的周期為 5 因?yàn)?x4 +x3 +x2 +x+)(x+ i)= x5+i ,項(xiàng)式為x5 1(4)線性移存器序列的n階m序列定義：n級(jí)線性反饋移存器的最長(zhǎng)周期：2n-1,能達(dá)到最長(zhǎng)周期的線性移存器序列稱(chēng)為m

18、序列。本原多項(xiàng)式：若n次多項(xiàng)式f(x)是不可約多項(xiàng)式且 p(f)=qn-1 ,則稱(chēng)f(x)是GF(q)上的本原多項(xiàng)式。以本原多項(xiàng)式為聯(lián)系多項(xiàng)式產(chǎn)生的非零序列均是m序列m序列的偽隨機(jī)性GF(2)上的隨機(jī)序列的一般特性1-分布特性對(duì)任意的“/L "莖" <1瓦.一. % ) £( ； I':,都有Pr -也.，日")=(瓦/a，%)=薪2相關(guān)特性1g. £口Jj L如果丁 = 11對(duì)任意的丁學(xué)。.瓦*一戶(hù)(- I * =如果一口3.游程特性、對(duì)任意的1,有P(&+i , &+Q (L i+Jt+i = 1 | &

19、; = 1) = 31+1P 2+1 = &+='-'=8+比=1 - f (-i-fc+l = " | £ii =。)二,誠(chéng)十 L定理6.11設(shè)仃"=Swi研z)是GF(2)上的一個(gè)門(mén)階m序列，則在一個(gè)周期內(nèi)，。和1的出現(xiàn)次數(shù)分別為2吁1 - 1和2»-1在一個(gè)周期內(nèi)，游程總數(shù)為"t；對(duì)任意的1 WWn-雪長(zhǎng)為i 的0游程和1游程都有”個(gè)；長(zhǎng)為“ -1的0游程有一個(gè),長(zhǎng)為" 的1源隹有一個(gè)."、一的自相關(guān)函數(shù)為兄(丁)=如果7 = 0;如果0 < 丁 < 2"一2自相關(guān)函數(shù)反映

20、一個(gè)周期內(nèi)平均每位的相同程度m序列的游程分布規(guī)律將n級(jí)m序列的一個(gè)周期段首尾相接，其游程總數(shù)為N =2n，;其中沒(méi)有長(zhǎng)度大于 n的游程；有1個(gè)長(zhǎng)度為n的1游程，沒(méi)有長(zhǎng)度為 n的0游程；沒(méi)有長(zhǎng)度為n-1的1游程，有1 個(gè)長(zhǎng)度為n-1的0游程；有2n ”4個(gè)長(zhǎng)度為k(1EkEn-2)的1游程，有2n個(gè)長(zhǎng)度為k(1 Ek Wn2)的0游程。m序列密碼的破譯(5)線性移存器遞推式的求解a的連續(xù)2n位，可用解線解方程法：已知序列 a是由n級(jí)線性移存器產(chǎn)生的，且知性方程組的方法得到線性遞推式。B-M迭代算法流程圖：讀入N；她,Gfr 打卑加3品幾個(gè)重要結(jié)論A)設(shè)a(N) =(a0a1aN)是 GF(q)上

21、的一個(gè)長(zhǎng)度為 N的序列，a(N)作為B-M算法的輸入。設(shè)< fN(x),lN >是B-M算法的最終輸入結(jié)果，則 < fN(x),lN >一定是a(N)的線性綜合解B)設(shè)a(N) =(a°aiaN是GF(q)上的一個(gè)長(zhǎng)度為 N的序列。a(N)有唯一線性綜合解的充要條件為二2lN ENC)設(shè)a(N) =(a°aiaN J是GF(q)上的一個(gè)長(zhǎng)度為 N的序列。卜是能產(chǎn)生a(N)并且階數(shù)最小的線性移位寄存器的階數(shù)。則當(dāng)2lN > N時(shí)，a(N)有q2lN -N個(gè)線性綜合解。第七章數(shù)字簽名1 .數(shù)字簽名的特性可信的；不可偽造的；不可復(fù)制的；不可改變的；不

22、可抵賴(lài)的。2 .基于公鑰密碼的數(shù)字簽名RSAa字簽名描述如下：(1)秘密選取兩個(gè)大素?cái)?shù) p和q。(2)計(jì)算 n = pq*(n) =( p 1)(q1), n 公開(kāi)，e(n)保密(3)隨機(jī)選取正整數(shù)1<e<Wn),滿(mǎn)足gcd(e*(n) =1 , e是公開(kāi)的密鑰(4)計(jì)算d,滿(mǎn)足ed三1(mod e(n) .d是保密密鑰(5)簽名變換：對(duì)于消息 mwZn,則簽名為：Sig (m) = md (mod n)(6)簽名驗(yàn)證：對(duì)于 m,sWZn，如果m=se(mod n),則確認(rèn)s為消息m的有效簽名。第八章Hash函數(shù)1 .作用：保證數(shù)據(jù)的完整性和認(rèn)證性(主要用于鑒別)2 .定義：Has

23、h函數(shù)常用來(lái)構(gòu)造數(shù)據(jù)的短“指紋”：消息的發(fā)送者使用所有的消息產(chǎn)生一個(gè)附 件也就是短“指紋”，并將該短“指紋”與消息一起傳輸給接收者?！炯词箶?shù)據(jù)存儲(chǔ)在不安全的地方，接收者重新計(jì)算數(shù)據(jù)的指紋，并驗(yàn)證指紋是否改變，就能夠檢測(cè)數(shù)據(jù)的完整性。這是因?yàn)橐坏?shù)據(jù)在中途被破壞，或改變，短指紋就不再正確?！? . Hash函數(shù)的性質(zhì)：(1)單向性給定一個(gè)Hash值y,如果尋找一個(gè)消息 x,使得y=h (x)是計(jì)算上不可行的，則稱(chēng) h是單 向Hash函數(shù)(2)若抗碰撞性任給一個(gè)消息x,如果尋找另一個(gè)不同的消息x',使得h(x) =h(x ')是計(jì)算上不可行的，則稱(chēng)h是弱抗碰撞Hash函數(shù).(3)強(qiáng)

24、抗碰撞性如果尋找兩個(gè)不同的消息x和x',使得h(x)=h(x ')是計(jì)算上不可行的， 則稱(chēng)h是強(qiáng)抗碰撞Hash函數(shù)4 .Hash函數(shù)的攻擊方法(1)窮舉攻擊：典型的生日攻擊(2)利用散列函數(shù)的代數(shù)結(jié)構(gòu)：攻擊其函數(shù)的弱性質(zhì)。通常的有中間相遇攻擊、修正分組 攻擊和差分分析攻擊等。5 .基于分組密碼的 Hash函數(shù)(1)基于分組密碼的CBC工作模式y(tǒng)i= Ek(xi y_)1 Mi Ml(2)基于分組密碼的CFC工作模式y(tǒng)i= xi份Ek (yi二)1 <i < l6.MD4算法(1)步驟MD4算法的輸入可以是任意長(zhǎng)度的消息x,對(duì)輸入消息按512位的分組為單位進(jìn)行處理，輸

25、出128位的散列值MD(x)。整個(gè)算法分為六個(gè)步驟。步驟1:消息的預(yù)處理設(shè)乂是一個(gè)消息，用二進(jìn)制表示。首先.由，生成一個(gè)數(shù)組M =叫叫/1一"爐一 L.Wi是長(zhǎng)度為32比特的t)的舊1)序列，i(Y LM由第生成：Id = (447 制)m" 5122令為小川如1的二進(jìn)制表示的長(zhǎng)度為64比特(bit如果，的長(zhǎng)度不足64比特伯的則在的左端濡0補(bǔ)足研"|1網(wǎng)"步驟:2:增加填充位步驟3:附加消息長(zhǎng)度值填充方法是把64比特的長(zhǎng)度分成兩個(gè) 32比特的字，低32比特字先填充，高32比特字后填 充步驟4:初始化M璘沖區(qū)步驟5:以512位的分組(16個(gè)字)為單位處理消

26、息步驟6:輸出(2)算法描述設(shè)人& C,。是四個(gè)腔位的寄存器.其切值(用十六進(jìn)制賽示j分別為再二67r45230L S=efcdab39t C=&8badcfe, 0=10325479對(duì)r = 0至Ml 6 - 1執(zhí)行第？步基第9步對(duì)六0至15執(zhí)行刈二例16，+用耨寄存器4 B，C. O中的值存慵到另外四個(gè)寄存器/W.SB，CC. DD中AAAf 8白二9，CC = G 00二口 執(zhí)行Rouridl®執(zhí)行RquMZ執(zhí)行Round?®A=AAA, + C C + CCT D= D + DD第九章密鑰協(xié)議1 .密鑰分配(1)定義：通信雙方中的一方選取一個(gè)秘密密鑰，然后傳送給另一方。2 2) Kerboros密鑰分配協(xié)議：Kerboros密鑰分配協(xié)議是一種在線式密鑰分配協(xié)議(。出 line key distributonprotoool)c 所謂在線(onJine)指的是， 當(dāng)兩個(gè)用戶(hù)U和V想要進(jìn)行保密通信時(shí),就根據(jù)協(xié)議產(chǎn)生 一個(gè)新的密鑰，而不是事先確定一個(gè)密鑰。Ea,(K.L) m1品、便，ID(5,KR m2£ID(U).71 m3七/4/鞏叫/：珀啤2.密鑰協(xié)商(1)定義：通信雙方可以在一個(gè)