工學第2章-現(xiàn)代密碼學技術課件

第二章現(xiàn)代密碼學技術第二章現(xiàn)代密碼學技術1本章提示2.1分組加密技術2.2公鑰加密技術本章提示22.1分組加密技術本節(jié)提示2.2.1基本概念2.2.2標準算法的介紹DES算法國際數(shù)據(jù)加密算法（IDEA）AES算法2.2.3分組密碼的分析方法2.2.4分組密碼的工作模式2.1分組加密技術本節(jié)提示32.2.1基本概念密碼學中常見的有兩種體制:對稱密碼體制(單鑰密碼體制)如果一個加密系統(tǒng)的加密密鑰和解密密鑰相同，或者雖然不相同，但是由其中的任意一個可以很容易地推導出另一個，即密鑰是雙方共享的,則該系統(tǒng)所采用的就是對稱密碼體制。非對稱密碼體制(公鑰密碼體制)分組密碼是指將處理的明文按照固定長度進行分組，加解密的處理在固定長度密鑰的控制下，以一個分組為單位獨立進行，得出一個固定長度的對應于明文分組的結果。屬于對稱密碼體制的范疇。2.2.1基本概念密碼學中常見的有兩種體制:4基本概念（續(xù)）在分組密碼的設計中用代替、置換手段實現(xiàn)擴散和混淆功能。混淆指加密算法的密文與明文及密鑰關系十分復雜，無法從數(shù)學上描述，或從統(tǒng)計上去分析。擴散指明文中的任一位以及密鑰中的任一位，對全體密文位有影響。經由此種擴散作用，可以隱藏許多明文在統(tǒng)計上的特性，增加密碼的安全基本概念（續(xù)）在分組密碼的設計中用代替、置換手段實現(xiàn)擴散和混52.2.2標準算法的介紹DES算法國際數(shù)據(jù)加密算法（IDEA）AES算法2.2.2標準算法的介紹DES算法6DES加密算法的背景發(fā)明人美國IBM公司W(wǎng).Tuchman和C.Meyer1971-1972年研制成功。基礎1967年美國HorstFeistel提出的理論產生美國國家標準局（NBS)1973年5月到1974年8月兩次發(fā)布通告，公開征求用于電子計算機的加密算法。經評選從一大批算法中采納了IBM的LUCIFER方案。標準化DES算法1975年3月公開發(fā)表，1977年1月15日由美國國家標準局頒布為數(shù)據(jù)加密標準（DataEncryptionStandard），于1977年7月15日生效。DES加密算法的背景發(fā)明人7DES加密算法的背景美國國家安全局（NSA,NationalSecurityAgency)參與了美國國家標準局制定數(shù)據(jù)加密標準的過程。NBS接受了NSA的某些建議，對算法做了修改，并將密鑰長度從LUCIFER方案中的128位壓縮到56位。1979年，美國銀行協(xié)會批準使用DES。1980年，DES成為美國標準化協(xié)會(ANSI)標準。1984年2月，ISO成立的數(shù)據(jù)加密技術委員會(SC20)在DES基礎上制定數(shù)據(jù)加密的國際標準工作。DES加密算法的背景美國國家安全局（NSA,Nationa8實現(xiàn)的設計原則軟件實現(xiàn)的要求：使用子塊和簡單的運算。密碼運算在子塊上進行，要求子塊的長度能自然地適應軟件編程，如8、16、32比特等。應盡量避免按比特置換，在子塊上所進行的密碼運算盡量采用易于軟件實現(xiàn)的運算。最好是用處理器的基本運算，如加法、乘法、移位等。硬件實現(xiàn)的要求：加密和解密的相似性，即加密和解密過程的不同應僅僅在密鑰使用方式上，以便采用同樣的器件來實現(xiàn)加密和解密，以節(jié)省費用和體積。盡量采用標準的組件結構，以便能適應于在超大規(guī)模集成電路中實現(xiàn)。實現(xiàn)的設計原則軟件實現(xiàn)的要求：使用子塊和簡單的運算。密碼運9簡化的DESSimplifiedDES方案，簡稱S-DES方案。加密算法涉及五個函數(shù)：(1)初始置換IP(initialpermutation)(2)復合函數(shù)fk1，它是由密鑰K確定的，具有置換和替代的運算。(3)轉換函數(shù)SW(4)復合函數(shù)fk2(5)初始置換IP的逆置換IP-1簡化的DESSimplifiedDES方案，簡稱S-DES10

11加密算法的數(shù)學表示

IP-1*fk2*SW*fk1*IP也可寫為

密文=IP-1（fk2(SW(fk1(IP(明文)))))其中K1=P8(移位(P10(密鑰K)))K2=P8(移位(移位(P10(密鑰K))))解密算法的數(shù)學表示：明文=IP-1（fk1(SW(fk2(IP(密文)))))加密算法的數(shù)學表示

IP-1*fk2*SW*fk1*IP12對S-DES的深入描述（1）S-DES的密鑰生成：設10bit的密鑰為（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10)置換P10是這樣定義的P10(k1,k2,…,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6)相當于P10=LS-1為循環(huán)左移，在這里實現(xiàn)左移1位。LS-2為循環(huán)左移，在這里實現(xiàn)左移2位。

P8=

按照上述條件,若K選為(1010000010),產生的兩個子密鑰分別為K1=(10100100),K2=(01000011)對S-DES的深入描述（1）S-DES的密鑰生成：13

S-DES的密鑰生成

10-bit密鑰P10LS-1LS-1LS-2LS-2P8P8K18K255585S-DES的密鑰生成 10-bit密鑰P10LS-14

(2)S-DES的加密運算:

初始置換用IP函數(shù):IP=12345678 26314857

末端算法的置換為IP的逆置換:IP-1=1234567841357286易見IP-1(IP(X))=X(2)S-DES的加密運算:15[工學]第2章--現(xiàn)代密碼學技術課件16

函數(shù)fk，是加密方案中的最重要部分，它可表示為：fk(L,R)=(LF(R,SK),R)

其中L，R為8位輸入,左右各為4位,F為從4位集到4位集的一個映射,并不要求是1-1的。SK為子密鑰。對映射F來說：首先輸入是一個4-位數(shù)（n1,n2,n3,n4），第一步運算是擴張/置換（E/P）運算：

E/P 41232341事實上，它的直觀表現(xiàn)形式為：

n4n1 n2n3n2n3n4n1函數(shù)fk，是加密方案中的最重要部分，它可表示為：17

8-bit子密鑰：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后與E/P的結果作異或運算得：

n4+k11 n1+k12n2+k13 n3+k14 n2+k15 n3+k16n4+k17 n1+k18把它們重記為8位：

P0,0 P0,1 P0,2 P0,3P1,0P1,1 P1,2 P1,3上述第一行輸入進S-盒S0，產生2-位的輸出；第二行的4位輸入進S盒S1，產生2-位的輸出。兩個S盒按如下定義：8-bit子密鑰：K1=(k11,k12,k13,k1418

S盒按下述規(guī)則運算：將第1和第4的輸入比特做為2-bit數(shù)，指示為S盒的一個行；將第2和第3的輸入比特做為S盒的一個列。如此確定為S盒矩陣的（i,j）數(shù)。例如：（P0,0,P0,3）=(00),并且(P0,1,P0,2)=(10)確定了S0中的第0行2列（0，2）的系數(shù)為3，記為（11）輸出。由S0,S1輸出4-bit經置換

P4243 1它的輸出就是F函數(shù)的輸出。SW函數(shù)為左四位和右四位進行交換。S盒按下述規(guī)則運算：19DES算法描述為二進制編碼數(shù)據(jù)設計的，可以對計算機數(shù)據(jù)進行密碼保護的數(shù)學運算。DES使用56位密鑰對64位的數(shù)據(jù)塊進行加密，并對64位的數(shù)據(jù)塊進行16輪編碼。在每輪編碼時，一個48位的“每輪”密鑰值由56位的“種子”密鑰得出來。DES算法的入口參數(shù)有三個：Key、Data和Mode。Key為8個字節(jié)共64位，是DES算法的工作密鑰；Data也為8個字節(jié)64位，是要被加密或被解密的數(shù)據(jù)；Mode為DES的工作方式，有兩種：加密或解密64位明文變換到64位密文，密鑰64位，實際可用密鑰長度為56位。DES算法描述為二進制編碼數(shù)據(jù)設計的，可以對計算機數(shù)據(jù)進行密20DES算法框圖DES算法框圖21DES算法描述（續(xù)）初始換位的功能是把輸入的64位數(shù)據(jù)塊按位重新組合，并把輸出分為L0、R0兩部分，每部分各長32位，其置換規(guī)則見下表：

58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157例：設置換前的輸入值為D1D2D3......D64，則經過初始置換后的結果為：L0=D58D50...D8；R0=D57D49...D7。

DES算法描述（續(xù)）初始換位的功能是把輸入的64位數(shù)據(jù)塊按位22DES算法描述（續(xù)）逆置換正好是初始置的逆運算?！纠康?位經過初始置換后，處于第40位，而通過逆置換，又將第40位換回到第1位，其逆置換規(guī)則如下表所示：

40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725

DES算法描述（續(xù)）23DES算法的一次迭代過程圖DES算法的一次迭代過程圖24DES算法描述（續(xù)）擴展置換為:

3212345456789891011121312131415161716171819202120212223242524252627282928293031321

P-盒置換為：1672021291228171152326518311028241432273919133062211425

DES算法描述（續(xù)）擴展置換為:25在變換中用到的S1,S2...S8為選擇函數(shù)，俗稱為S-盒，是DES算法的核心。其功能是把6bit數(shù)據(jù)變?yōu)?bit數(shù)據(jù)。

S1:

1441312151183106125907

0157414213110612119538

4114813621115129731050

1512824917511314100613

在S1中，共有4行數(shù)據(jù)，命名為0，1、2、3行；每行有16列，命名為0、1、2、3，......，14、15列。

現(xiàn)設輸入為：D＝D1D2D3D4D5D6

令：列＝D2D3D4D5

行＝D1D6

然后在S1表中查得對應的數(shù)，以4位二進制表示，此即為選擇函數(shù)S1的輸出。

在變換中用到的S1,S2...S8為選擇函數(shù)，俗稱為S-盒，26101100102

0123456789101112131415014413121511831061259071015741421311061211953824114813621115129731050315128249175113141006130010輸出4位使用選擇函數(shù)S1的例子輸入6位S1101100100123427密鑰Ki(48bit)的生成算法密鑰Ki(48bit)的生成算法28[工學]第2章--現(xiàn)代密碼學技術課件29DES的破解DES的實際密鑰長度為56-bit，就目前計算機的計算機能力而言，DES不能抵抗對密鑰的窮舉搜索攻擊。1997年1月28日，RSA數(shù)據(jù)安全公司在RSA安全年會上懸賞10000美金破解DES，克羅拉多州的程序員Verser在Inrernet上數(shù)萬名志愿者的協(xié)作下用96天的時間找到了密鑰長度為40-bit和48-bit的DES密鑰。

1998年7月電子邊境基金會（EFF）使用一臺價值25萬美元的計算機在56小時之內破譯了56-bit的DES。

1999年1月電子邊境基金會（EFF）通過互聯(lián)網(wǎng)上的10萬臺計算機合作，僅用22小時15分就破解了56-bit的ＤES。DES的破解DES的實際密鑰長度為56-bit，就30DES算法的公開性與脆弱性DES的兩個主要弱點：密鑰容量：56位不太可能提供足夠的安全性

不過這些破譯的前提是，破譯者能識別出破譯的結果確實是明文，也即破譯的結果必須容易辯認。如果明文加密之前經過壓縮等處理，辯認工作就比較困難。S盒：可能隱含有陷井（Hiddentrapdoors）DES的半公開性：S盒的設計原理至今未公布DES算法的公開性與脆弱性DES的兩個主要弱點：31[工學]第2章--現(xiàn)代密碼學技術課件32國際數(shù)據(jù)加密算法（IDEA）IDEA（InternationalDataEncryptionStandard）由瑞士聯(lián)邦理工學院的XuejiaLai和JamesMassey于1990年提出，分組長度為64-bit，密鑰長度為128-bit。能抵抗差分密碼分析，目前還沒有發(fā)現(xiàn)明顯的安全漏洞，應用十分廣泛。著名的電子郵件安全軟件PGP就采用了IDEA進行數(shù)據(jù)加密。國際數(shù)據(jù)加密算法（IDEA）IDEA（Internation33IDEA的混淆特性IDEA的混淆特性是經由混合下述三種操作而成的：以比特為單位的異或運算，用表示。定義在模（mod65536）的模加法運算，其操作數(shù)都可以表示成16位整數(shù)，用＋表示這個操作。定義在模＋1（mod65537）的模乘法運算?！袸DEA的混淆特性IDEA的混淆特性是經由混合下述三種操作而34IDEA的混淆特性（續(xù)）由于上面3個操作，基于以下的“非兼容性“（Incompatible），當應用在IDEA時，可以充分發(fā)揮出混淆的特性。三種中的任意兩個，都不滿足“分配律”，例如運算⊙及＋，任意a，b，c∈，則有：

a＋(b⊙c)≠（a＋b）⊙（a＋c）3個操作中的任意2個，都無法滿足“結合律”。例如運算＋及⊙，任意a，b，c∈，a＋(b⊙c)≠（a＋b）⊙（a＋c）

因此在IDEA的設計中，使用了這三種操作混合組合來打亂數(shù)據(jù)。攻擊者無法用化簡的方式來分析密文與明文及密鑰之間的關系。IDEA的混淆特性（續(xù)）35IDEA的擴散特性IDEA的擴散特性是建立在乘法/加法（MA）的基本結構上。該結構一共有4個16位的輸入，兩個16位的輸出。其中的兩個輸入來源于明文，另兩個輸入是子密鑰，源于128位加密密鑰。Lai經過分析驗證，數(shù)據(jù)經過8輪的MA處理，可以得到完整的擴散特性。IDEA的擴散特性IDEA的擴散特性是建立在乘法/加法（MA36[工學]第2章--現(xiàn)代密碼學技術課件37MA基本結構在IDEA中，擴散由被稱為乘積/相加(MA)結構的算法基本構件提供。這個結構以兩個從明文得到的16bit的數(shù)值和兩個從密鑰導出的子密鑰作為輸入并產生兩個16bit的輸出。已證明只需要使用4次這個結構就可以實現(xiàn)完全的擴散。

F1F2⊙⊙G1G2Z5Z6子密鑰（16位）明文輸入（16位）明文輸入（16位）子密鑰（16位）輸出（16位）輸出（16位）（i）（i）＋＋MA基本結構在IDEA中，擴散由被稱為乘積/相加(MA)結構38IDEA算法描述IDEA是由8輪相似的運算和隨后的一個輸出變換組成64位的明文分組在每一輪中都是被分成4份，每份從16位為一單元來處理每一輪中6個子密鑰×8＋輸出變換4個子密鑰＝52個子密鑰IDEA算法描述IDEA是由8輪相似的運算和隨后的一個輸出變39每一輪的運算又分成兩部分：第一部分即變換運算。利用加法及乘法運算將4份16位的子明文分組與4個子密鑰混合，產生4份16位的輸出。這4份輸出又兩兩配對，以邏輯異或將數(shù)據(jù)混合，產生兩份16位的輸出。這兩份輸出，連同另外的兩個子密鑰成為第二部分的輸入。第二部分即用以產生擴散特性的MA運算。MA運算生成兩份16位輸出。MA的輸出再與變換運算的輸出以異或作用生成4份16位的最后結果。這4份結果即成為下一輪運算的原始輸入。

每一輪的運算又分成兩部分：第一部分即變換運算。利用加法及乘法40子密鑰的產生首先將128位加密密鑰以16位為單位分成8組，其中前6組作為第一輪迭代運算的子密鑰，后2組用于第二輪迭代運算的前2組子密鑰。然后將128位密鑰循環(huán)左移25位，再分為8組子密鑰，其中前4組用于第二輪迭代運算，后4組用作第三輪迭代運算的前4組子密鑰，依此直至產生全部52個子密鑰。這52個子密鑰的順序為：

Z1(1)，Z2(1)，…，Z6(1)；Z1(2)，Z2(2)，…，Z6(2)；…；Z1(8)，Z2(8)，…，Z6(8)；Z1(9)，Z2(9)，Z3(9)，Z4(9)，子密鑰的產生首先將128位加密密鑰以16位為單位分成8組，其41IDEA的解密本質上與加密過程唯一不同的是解密密鑰子塊Ki(r)是從加密密鑰子塊Zi(r)按下列方式計算出來的：其中表示的模（＋1）的乘法逆，亦即，表示的模的加法逆，亦即＋=0。IDEA的解密本質上與加密過程唯一不同的是解密密鑰子塊Ki42IDEA的設計理念IDEA的設計主要考慮是針對16位為單位的處理器。因此無論明文、密鑰都是分成16位為一個單元進行處理。IDEA使用了三種簡單的基本操作，因此在執(zhí)行時可以達到非?？斓牟僮?。在33MHz386機器上運行，加密速度可以達到880kb/s。經過特殊設計的VLSI芯片，更可以達到55Mb/s的速度。IDEA采用三種非常簡單的基本操作，混合運算，以達到混淆目的。而相對地，DES采用經過特殊設計的S-盒，而對這些S-盒的分析又不對外公開。相較之下，IDEA的安全性評估，較易被大家接受。IDEA的整體設計非常規(guī)律。MA運算器及變換運算器重復使用在系統(tǒng)上。因此非常適合VLSI超大規(guī)模集成電路(VeryLargeScaleIntegratedcircuites)實現(xiàn)。IDEA的設計理念IDEA的設計主要考慮是針對16位為單位432.2.3分組密碼的分析方法解密與密碼分析解密是加密的逆過程，是指掌握密鑰和密碼算法的合法人員從密文恢復出明文的過程。密碼分析則是指非法人員對密碼的破譯，而且破譯以后不會告訴對方。

共同點“解密（脫密）”和“密碼分析（密碼破譯）”都是設法將密文還原成明文。

不同點二者的前提是不同的，“解密（脫密）”掌握了密鑰和密碼體制，而密碼分析（破譯）則沒有掌握密鑰和密碼體制2.2.3分組密碼的分析方法解密與密碼分析44分組密碼的分析方法(續(xù)）根據(jù)攻擊者掌握的信息，可將分組密碼的攻擊分為以下幾類：唯密文攻擊：攻擊者除了所截獲的密文外，沒有其他可利用的信息。已知明文攻擊：攻擊者僅知道當前密鑰下的一些明密文對。選擇明文攻擊：攻擊者能獲得當前密鑰下的一些特定的明文所對應的密文。選擇密文攻擊：攻擊者能獲得當前密鑰下的一些特定的密文所對應的明文。分組密碼的分析方法(續(xù)）根據(jù)攻擊者掌握的信息，可將分組密碼的45分組密碼的分析方法(續(xù)）一種攻擊的復雜度可以分為兩部分：數(shù)據(jù)復雜度和處理復雜度。數(shù)據(jù)復雜度是實施該攻擊所需輸入的數(shù)據(jù)量。處理復雜度是處理這些數(shù)據(jù)所需的計算量。

對某一攻擊通常是以這兩個方面的某一方面為主要因素，來刻畫攻擊復雜度?！纠纭扛F舉攻擊的復雜度實際就是考慮處理復雜度；差分密碼分析其復雜度主要是由該攻擊所需的明密文對的數(shù)量來確定。分組密碼的分析方法(續(xù)）一種攻擊的復雜度可以分為兩部分：數(shù)據(jù)46幾種常見的攻擊方法1.強力攻擊強力攻擊可用于任何分組密碼，且攻擊的復雜度只依賴于分組長度和密鑰長度，嚴格地講攻擊所需的時間復雜度依賴于分組密碼的工作效率（包括加解密速度、密鑰擴散速度以及存儲空間等）。強力攻擊常見的有：窮舉密鑰搜索攻擊、字典攻擊、查表攻擊和時間-存儲權衡攻擊等。幾種常見的攻擊方法1.強力攻擊47幾種常見的攻擊方法（續(xù)）2.差分密碼分析基本思想通過分析明文對的差值對密文對的差值的影響來恢復某些密鑰比特若給定一個r輪的迭代密碼，對已知n長明文對為和，定義其差分為式中表示集合中定義的群運算，為在群中的逆元。密碼分析者可隨機選擇具有固定差分的一對明文（只要求它們符合特定差分條件），然后使用輸出密文中的差分，按照不同的概率分配給不同的的密鑰。隨著分析的密文對越來越多，其中最可能的一個密鑰就顯現(xiàn)出來了。這就是正確的密鑰。幾種常見的攻擊方法（續(xù)）2.差分密碼分析48幾種常見的攻擊方法（續(xù)）3.線性密碼分析本質：一種已知明文攻擊方法?；舅枷耄和ㄟ^尋找一個給定密碼算法的有效的線性近似表達式來破譯密碼系統(tǒng)。對已知明文密文和特定密鑰，尋求線性表示式

式中，是攻擊參數(shù)。對所有可能密鑰，此表達式以概率成立。對給定的密碼算法，使極大化。為此對每一盒的輸入和輸出構造統(tǒng)計線性路線，并最終擴展到整個算法。幾種常見的攻擊方法（續(xù)）3.線性密碼分析49分組密碼的工作模式常用的分組密碼工作模式有4種：1.電子密碼本即ECB模式2.密碼分組連接模式（CBC）模式3.密碼反饋模式（CFB）模式4.輸出反饋模式（OFB）模式。分組密碼的工作模式常用的分組密碼工作模式有4種：50ECB(ElectronicCodeBook)ECB(ElectronicCodeBook)51CBC（CipherBlockChaining）CBC（CipherBlockChaining）52CFB（CipherFeedBack）CFB（CipherFeedBack）53OFB（OutputFeedBack）OFB（OutputFeedBack）542.3公鑰加密技術本節(jié)提示2.3.1基本概念2.3.2RSA公鑰密鑰算法2.3.3ElGamal算法2.3.4橢圓曲線算法2.3公鑰加密技術本節(jié)提示55對稱密碼體制的缺陷：

對稱密碼體制的缺陷：562.3.1基本概念1976年，W.Diffie和M.E.Hellman發(fā)表了“密碼學的新方向（NewDirectionsinCryptography)”一文，提出了公鑰密碼學（Public-keycryptography）的思想，在公鑰密碼體制（Public-keycryptosystem）中加密密鑰和解密密鑰是不同的，加密密鑰可以公開傳播而不會危及密碼體制的安全性。通信的一方利用某種數(shù)學方法可以產生一個密鑰對，一個稱為公鑰（Public-key)，另外一個稱為私鑰（Private-key)。該密鑰對中的公鑰與私鑰是不同的，但又是相互對應的，并且由公鑰不能推導出對應的私鑰。選擇某種算法（可以公開）能做到：用公鑰加密的數(shù)據(jù)只有使用與該公鑰配對的私鑰才能解密。是密碼學幾千年歷史中最有意義的結果2.3.1基本概念1976年，W.Diffie和M.E.H57公鑰加密方案公鑰加密方案58基本概念（續(xù)）公鑰加密算法的核心——單向陷門函數(shù)，即從一個方向求值是容易的。但其逆向計算卻很困難，從而在實際上成為不可行。定義1.設是一個函數(shù)，如果對任意給定的,計算,使得是容易計算的，但對于任意給定的，計算，使得是難解的，即求的逆函數(shù)是難解的，則稱是一個單向函數(shù)。基本概念（續(xù)）公鑰加密算法的核心——單向陷門函數(shù)，即從一個方59基本概念（續(xù)）定義2.設是一個函數(shù)，是與有關的一個參數(shù)。對于任意給定的，計算，使得是容易的。如果當不知參數(shù)時，計算的逆函數(shù)是難解的，但當知道參數(shù)時，計算函數(shù)的逆函數(shù)是容易的，則稱是一個單向陷門函數(shù)，參數(shù)稱為陷門?；靖拍睿ɡm(xù)）定義2.設是一個函數(shù)，是與有60公鑰的安全性依賴于足夠大的困難性差別類似與對稱算法,窮搜索在理論上是能夠破解公鑰密碼exhaustivesearch

但實際上,密鑰足夠長(>512bits)一般情況下,有一些已知的困難問題(hardproblem）要求足夠大的密鑰長度(>512bits)導致加密速度比對稱算法慢公鑰的安全性依賴于足夠大的困難性差別612.3.2RSA公鑰密碼算法RSA是Rivet，Shamir和Adleman于1978年在美國麻省理工學院研制出來的，它是一種比較典型的公開密鑰加密算法。基礎大數(shù)分解和素數(shù)檢測——將兩個大素數(shù)相乘在計算上很容易實現(xiàn)，但將該乘積分解為兩個大素數(shù)因子的計算量是相當巨大的，以至于在實際計算中是不能實現(xiàn)的。2.3.2RSA公鑰密碼算法RSA是Rivet，Shami62RSA公鑰密碼算法（續(xù)）算法內容(1)公鑰選擇兩個互異的大質數(shù)和，使，，是歐拉函數(shù)，選擇一個正數(shù)，使其滿足gcd，

則將作為公鑰。(2)私鑰求出正數(shù)使其滿足，則將作為私鑰。(3)加密變換將明文作變換,使，從而得到密文。(4)解密變換將密文作變換,使，從而得到明文。RSA公鑰密碼算法（續(xù)）算法內容63RSA公鑰密碼算法（續(xù)）如果A要發(fā)送信息M給B，A和B之間用以下方式進行通信：計算密文→發(fā)送C給B→從A

接收C→計算明文.一般要求p，q為安全質數(shù)，現(xiàn)在商用的安全要求為n的長度不少于1024位。應用：PEM，PGPRSA公鑰密碼算法（續(xù)）如果A要發(fā)送信息M給B，A和B之間用64RSA公鑰密碼算法（續(xù)）算法的安全性分析1.如果密碼分析者能分解的因子和，他就可以求出和解密的密鑰，從而能破譯RSA，因此破譯RSA不可能比因子分解難題更困難。2.如果密碼分析者能夠不對進行因子分解而求得，則可以根據(jù)求得解密密鑰，從而破譯RSA。因為

所以知道和就可以容易地求得和，從而成功分解，因此，不對進行因子分解而直接計算并不比對進行因子分解更容易。RSA公鑰密碼算法（續(xù)）算法的安全性分析65RSA公鑰密碼算法（續(xù)）3.如果密碼分析者既不能對n進行因子分解,也不能求而直接求得解密密鑰，則他就可以計算是的倍數(shù)。而且利用的倍數(shù)可以容易地分解出n的因子。因此直接計算解密密鑰并不比對n進行因子分解更容易。注意問題p和q的長度相差不能太多.p-1和q-1都應該包含大的素因子。p-1和q-1的最大公因子要盡可能小。RSA公鑰密碼算法（續(xù)）3.如果密碼分析者既不能對n進行因子66RSA參數(shù)選擇需要選擇足夠大的素數(shù)p,q

通常選擇小的加密指數(shù)e,且與?(N)

互素e

對所有用戶可以是相同的最初建議使用e=3現(xiàn)在3太小常使用e=216-1=65535

解密指數(shù)比較大RSA參數(shù)選擇需要選擇足夠大的素數(shù)p,q67RSA舉例例子：1.選素數(shù)p=47和q＝71，得n=3337,(n)=46×70＝3220；2.選擇e=79，求得私鑰d=e-1

1019(mod3220）。3.公開n=3337和e=79.4.現(xiàn)要發(fā)送明文688，計算：68879(mod3337)=15705.收到密文1570后，用私鑰d＝1019進行解密：15701019（mod3337)=688RSA舉例例子：68RSA安全性RSA安全性基于計算?(N)的困難性要求分解模N

RSA安全性RSA安全性基于計算?(N)的困難性69RSA的實現(xiàn)問題需要計算模300digits(or1024+bits)的乘法計算機不能直接處理這么大的數(shù)（計算速度很慢）需要考慮其它技術，加速RSA的實現(xiàn)RSA的實現(xiàn)問題需要計算模300digits(or170RSA–的快速實現(xiàn)加密很快，指數(shù)小解密比較慢，指數(shù)較大利用中國剩余定理CRT，CRT對RSA解密算法生成兩個解密方程（利用M=CdmodR）即:M1=Mmodp=(Cmodp)dmod(p-1)

M2=Mmodq=(Cmodq)dmod(q-1)

解方程M=M1modpM=M2modq具有唯一解（利用CRT）：:M=[((M2+q-M1)umodq]p+M1

其中p.umodq=1RSA–的快速實現(xiàn)加密很快，指數(shù)小712.2.3ElGamal算法該體制是由ElGamal在1985年提出的，其安全性是基于有限域上計算離散對數(shù)的困難性。

ElGamal提出了加密模型和認證模型兩種體制，加密模型沒有被充分應用，而其認證模型是美國數(shù)字簽名標準（DSS）的基礎。2.2.3ElGamal算法該體制是由ElGamal在19722.2.3ElGamal算法算法內容1.選取大素數(shù)，是一個本原元，和公開。2.隨機選取整數(shù)計算是公開的加密密鑰，是保密的解密密鑰。3.明文空間為，密文空間為4.加密變換為：對任意明文，秘密隨機選取一個整數(shù)，則密文為其中5.解密變換：對任意密文，明文為2.2.3ElGamal算法算法內容73ElGamal算法的安全性分析有限域上的離散對數(shù)問題定義設是素數(shù)，，是一個本原元，已知和，求滿足的唯一整數(shù)，稱為有限域上的離散對數(shù)問題。現(xiàn)在要求在ElGamal密碼算法的應用中，素數(shù)p按十進制表示至少應該有150位數(shù)字，并且p-1至少應該有一個大的素因子。ElGamal算法的安全性分析有限域上的離散對數(shù)問題74密鑰建立密鑰生成：選取一個大素數(shù)p及本原元amodp接收者Bob有一個密秘鑰d

計算β=admodp

密鑰建立密鑰生成：75ElGamal加密為加密M

發(fā)送者選擇隨機數(shù)k,0<=k<=p-1

計算消息密鑰K:K=βkmodp

計算密文對:C={C1,C2}

C1=akmodp

C2=K.Mmodp

發(fā)送到接收者k

需要永久保密ElGamal加密為加密M76ElGamal解密首先計算messagekeyK

K=C1dmodp=ak.d

modp

計算明文:M=C2.K-1

modp

ElGamal解密首先計算messagekeyK77ElGamalExample選擇p=97

及本原根a=5

recipientBob選擇秘密鑰d=58&計算并發(fā)布公鑰β=558=44mod97

Alice要加密M=3toBob首先得到Bob的公開密鑰β=44

選擇隨機k=36

計算:

K=4436=75mod97

計算密文對:C1=536=50mod97

C2=75.3mod97=31mod97

發(fā)送{50,31}

toBobBob恢復messagekeyK=5058=75mod97

Bob計算K-1=22mod97

Bob恢復明文M=31.22=3mod97

ElGamalExample選擇p=97及本原根a=782.2.4橢圓曲線算法1985年Koblitz和Miller提出在密碼學中應用橢圓曲線的思想，使其成為構造公開密鑰密碼系統(tǒng)的一個有利工具。其安全性是基于橢圓曲線上的離散對數(shù)計算的困難性。優(yōu)點：橢圓曲線上離散對數(shù)的計算要比有限域上離散對數(shù)的計算更困難。與RSA相比，橢圓曲線密碼體制能用較短的密鑰達到較強的安全性，這樣實現(xiàn)上能節(jié)省系統(tǒng)資源。2.2.4橢圓曲線算法1985年Koblitz和Mille79橢圓曲線算法（續(xù)）1.有限域上的橢圓曲線設表示一個有限域，是域上的橢圓曲線，則是一個點的集合，表示為：其中表示無窮遠點。在上定義’+’運算，是過的直線與曲線的另一交點關于x軸的對稱點，當時，是點的切線與曲線的另一交點關于軸的對稱點。這樣，構成可換群(Abel群)，O是加法單位元(零元)。橢圓曲線算法（續(xù)）1.有限域上的橢圓曲線80橢圓曲線算法（續(xù)）橢圓曲線離散對數(shù)問題（ECDLP）：

給定義在上的橢圓曲線，一個階的點和點，如果存在1，確定整數(shù)1,01n-1,。RSA是基于因子分解，其算法的核心就是如何尋找大數(shù)的因子分解，但ECDLP是比因子分解難得多的問題。橢圓曲線算法（續(xù)）橢圓曲線離散對數(shù)問題（ECDLP）：81橢圓曲線中兩種運算示意圖橢圓曲線上的加法：P＋Q＝R橢圓曲線上一點的2倍：P＋P＝R橢圓曲線中兩種運算示意圖橢圓曲線上的加法：橢圓曲線上一點的282橢圓曲線算法（續(xù)）2.橢圓曲線上的密碼算法1985年N.Koblitz和Miller提出將橢圓曲線用于密碼算法，分別利用有限域上橢圓曲線的點構成的群，實現(xiàn)了離散對數(shù)密碼算法。橢圓曲線數(shù)字簽名算法ECDSA，由IEEE工作組和ANSI（AmercianNationalStandardsInstitute）X9組織開發(fā)。橢圓曲線算法（續(xù)）2.橢圓曲線上的密碼算法83橢圓曲線算法（續(xù)）3.橢圓曲線密碼算法的發(fā)展RSA的長密鑰帶來了運算速度慢和密鑰存儲與管理的問題。由于其自身的優(yōu)點，橢圓曲線密碼學被普遍認為將替代RSA成為通用的密碼算法。應用：數(shù)字簽名，智能卡研究：陶仁驥，陳世華－基于有限自動機的公開密鑰加密方法:FAPKC0，F(xiàn)APKC1，F(xiàn)APKC2，F(xiàn)APKC3。橢圓曲線算法（續(xù)）3.橢圓曲線密碼算法的發(fā)展842.4流密碼技術本節(jié)友情提示2.4.1流密碼基本原理2.4.2二元加法流密碼2.4.3幾種常見的流密碼算法2.4流密碼技術本節(jié)友情提示852.4流密碼技術在單鑰密碼體制中，按照加密時對明文處理方式的不同，可分為分組密碼和流密碼。流密碼亦稱為序列密碼，是將待加密的明文分成連續(xù)的字符或比特，然后用相應的密鑰流對之進行加密，密鑰流由種子密鑰通過密鑰流生成器產生。密鑰流可以方便地利用以移位寄存器為基礎的電路來產生。特點：實現(xiàn)簡單，加密速度快，錯誤傳播低。2.4流密碼技術在單鑰密碼體制中，按照加密時對明文處理方式862.4.1流密碼基本原理原理通過隨機數(shù)發(fā)生器產生性能優(yōu)良的偽隨機序列（密鑰流），使用該序列加密信息流（逐比特加密），得到密文序列。種子密鑰K隨機數(shù)發(fā)生器加密變換密鑰流Ki明文流mi密文流Ci2.4.1流密碼基本原理原理種子密鑰K隨機數(shù)發(fā)生器加密變87按照加解密的工作方式，流密碼分為同步流密碼和自同步流密碼。1.同步流密碼密鑰流的產生完全獨立于信息流。密鑰流生成器ki種子密鑰k安全信道ciki解密變換密鑰流生成器

ci公開信道加密變換種子密鑰K按照加解密的工作方式，流密碼分為同步流密碼和自同步流密碼。密88流密碼基本原理（續(xù)）2.自同步流密碼是一種有記憶變換的密碼，每一個密鑰字符是由前面n個密文字符參與運算推導出來的，其中n為定值。即，如果在傳輸過程中丟失或更改了一個字符，則這一錯誤就要向前傳播n個字符。有錯誤傳播現(xiàn)象。密鑰流生成器ki種子密鑰k安全信道ciki解密變換密鑰流生成器

ci公開信道加密變換種子密鑰k流密碼基本原理（續(xù)）2.自同步流密碼密鑰流生成器ki種子密鑰892.4.2二元加法流密碼符號描述與示例加密操作：

密鑰流：k1,k2,k3,…⊕⊕⊕

明文流：m1,m2,m3,…↓↓↓

密文流：c1,c2,c3,…解密操作：

密鑰流：k1,k2,k3,…⊕⊕⊕

密文流：c1,c2,c3,…↓↓↓

明文流：m1,m2,m3,…[例]電報內容“專列下午2點到達?！钡募用苓^程如下：密鑰流：78,35,02,E4,B2…⊕⊕⊕⊕⊕明文流：D7,A8,C1,D0,CF,C2,CE,E7,32,B5,E3,B5,BD,B4,EF,A1,A3

↓↓↓↓↓密文流：AF,9D,C3,34,7D…2.4.2二元加法流密碼符號描述與示例[例]電報內容“專列90二元加法流密碼（續(xù)）Golomb隨機性假設：在序列的一個周期內，0與1的個數(shù)相差至多為1；在序列的一個周期圈內，長為1的游程數(shù)占總游程數(shù)的1/2，長為2的游程數(shù)占總游程數(shù)的，…,長為的游程數(shù)占總游程數(shù)的且在等長的游程中0，1游程各占一半；序列的異相自相關系數(shù)為一個常數(shù)。滿足Golomb隨機性假設的序列稱為偽隨機序列。二元加法流密碼（續(xù)）Golomb隨機性假設：91二元加法流密碼（續(xù)）流密碼的設計最核心的問題是密鑰流生成器的設計。密鑰流生成器一般由線性反饋移位寄存器(LinearFeedbackShiftRegisterLFSR)和一個非線性組合函數(shù)兩部分構成，其中，線性反饋移位寄存器部分稱為驅動部分，另一部分稱為非線性組合部分。驅動部分（LFSR）非線性組合部分密鑰流ki二元加法流密碼（續(xù)）流密碼的設計最核心的問題是密鑰流生成器的92二元加法流密碼（續(xù)）反饋移位寄存器（feedbackshiftregister）1.組成結構反饋移位寄存器由n位的寄存器（稱為n-級移位寄存器）和反饋函數(shù)（feedbackfunction）組成。移位寄存器序列的理論由挪威政府的首席密碼學家ErnstSelmer于1965年提出。bn-1…b3b2b1bn反饋函數(shù)f(b1,…,bn)輸出位oi二元加法流密碼（續(xù)）反饋移位寄存器（feedbackshi93二元加法流密碼（續(xù)）2.工作原理移位寄存器中所有位右移一位，最右邊移出的位是輸出位，最左端的一位由反饋函數(shù)的輸出填充，此過程稱為進動一拍。反饋函數(shù)f(b1,…,bn)是n元(b1,…,bn)的布爾函數(shù)。移位寄存器根據(jù)需要不斷地進動m拍，便有m位的輸出，形成輸出序列o1o2…om。二元加法流密碼（續(xù)）2.工作原理94二元加法流密碼（續(xù)）[例1]如圖所示為一個3-級反饋移位寄存器，反饋函數(shù)f(x)=b3⊕b2，初態(tài)為：100。輸出序列生成過程如下：狀態(tài)輸出位100→0110→0011→1101→1110→0011→1101→1110→0因此，對應初態(tài)(100)的輸出序列為：0011011011

…（周期為3）b3b2b1t2t3(a)移位寄存器結構圖(110)(011)(101)初態(tài)(100)(b)狀態(tài)轉移圖110(c)序列圈0二元加法流密碼（續(xù)）[例1]如圖所示為一個3-級反饋移位寄95二元加法流密碼（續(xù)）3.輸出序列的周期移位寄存器的周期是指輸出序列中連續(xù)且重復出現(xiàn)部分的長度（位數(shù)）。如[例1]輸出序列中連續(xù)且重復出現(xiàn)的序列為：011，則其周期為3。其輸出序列可表示為：0(011)∞。將其用圖的方式表示出來稱為“序列圈”，如圖（c）所示。4.狀態(tài)某一時刻移位寄存器中所有位的值稱為一個狀態(tài)。n-級的FSR共有2n個狀態(tài)。3-級移位寄存器的狀態(tài)共有23=8個，它們分別是：000,001,010,011,100,101,110,111。但是，并非所有的狀態(tài)都被用到。如[例1]除初始狀態(tài)以外，僅有三個狀態(tài)周期性地參與了輸出序列的產生。二元加法流密碼（續(xù)）3.輸出序列的周期4.狀態(tài)96二元加法流密碼（續(xù)）當反饋移位寄存器的反饋函數(shù)是異或變換時，這樣的反饋移位寄存器叫線性反饋移位寄存器，如圖所示：二元加法流密碼（續(xù)）當反饋移位寄存器的反饋函數(shù)是異或變換時，97二元加法流密碼（續(xù)）移位寄存器中存儲器的個數(shù)稱為移位寄存器的級數(shù)，移位寄存器存儲的數(shù)據(jù)為寄存器的狀態(tài)，狀態(tài)的順序從左到佑依次為從最高位到最低位。在所有狀態(tài)中，叫初態(tài)，并且從左到右依次稱為第一級、第二級、…、第n級，亦稱為抽頭1、抽頭2、抽頭3、….、抽頭n。n級線性反饋移位寄存器的有效狀態(tài)為個。它主要是用來產生周期大，統(tǒng)計性能好的序列。二元加法流密碼（續(xù)）移位寄存器中存儲器的個數(shù)稱為移位寄存器的98二元加法流密碼（續(xù)）非線性組合部分主要是增加密鑰流的復雜程度，使密鑰流能夠抵抗各種攻擊（對流密碼的攻擊手段主要是對密鑰流進行攻擊）。以線性反饋移位寄存器產生的序列為基序列，經過不規(guī)則采樣、函數(shù)變換等（即非線性變換），就可以得到實用安全的密鑰流。不規(guī)則采樣是在控制序列下，對被采樣序列進行采樣輸出，得到的序列稱為輸出序列?？刂菩蛄械目刂品绞接戌娍胤绞?、抽取方式等，函數(shù)變換有前饋變換、有記憶變換等。二元加法流密碼（續(xù)）非線性組合部分主要是增加密鑰流的復雜程度99二元加法流密碼（續(xù)）代表性的序列模型1、鐘控模型當LFSR-1輸出1時，時鐘信號被采樣，即能通過“與門”驅動LFSR-2進動一拍；當LFSR-1為0時，時鐘信號不被采樣，即不能通過“與門”，此時LFSR-2不進動，重復輸出前一位。鐘控發(fā)生器的示意圖如下：二元加法流密碼（續(xù)）代表性的序列模型1002、前饋模型

Geffe發(fā)生器是前饋序列的典型模型，其前饋函數(shù)g(x)=(x1x2)⊕(x2x3)為非線性函數(shù)，即當LFSR-2輸出1時，g(x)輸出位是LFSR-1的輸出位；當LFSR-2輸出0時，g(x)輸出位是LFSR-3的輸出位。Geffe發(fā)生器示意圖如下：2、前饋模型1012.4.3幾種常見的流密碼算法1.A5算法法國，歐洲數(shù)字蜂窩移動電話系統(tǒng)（GSM）中使用的序列密碼加密算法3個LFSR，移位寄存器的長度分別是19、22和23，但抽頭都較少2.Rambutan算法英國的算法，由通信電子安全組織設計5個LFSR組成，每個LFSR長度大約為80-級，而且有10個抽頭。3.RC4算法由RonRivest于1987年為RSA數(shù)據(jù)安全公司設計的可變密鑰長度的序列密碼，廣泛用于商業(yè)密碼產品中。4.SEAL算法IBM公司的PhilRogaway和DonCoppersmith設計的一種易于用軟件實現(xiàn)的序列密碼。是一個偽隨機函數(shù)簇。2.4.3幾種常見的流密碼算法1.A5算法102第二章現(xiàn)代密碼學技術第二章現(xiàn)代密碼學技術103本章提示2.1分組加密技術2.2公鑰加密技術本章提示1042.1分組加密技術本節(jié)提示2.2.1基本概念2.2.2標準算法的介紹DES算法國際數(shù)據(jù)加密算法（IDEA）AES算法2.2.3分組密碼的分析方法2.2.4分組密碼的工作模式2.1分組加密技術本節(jié)提示1052.2.1基本概念密碼學中常見的有兩種體制:對稱密碼體制(單鑰密碼體制)如果一個加密系統(tǒng)的加密密鑰和解密密鑰相同，或者雖然不相同，但是由其中的任意一個可以很容易地推導出另一個，即密鑰是雙方共享的,則該系統(tǒng)所采用的就是對稱密碼體制。非對稱密碼體制(公鑰密碼體制)分組密碼是指將處理的明文按照固定長度進行分組，加解密的處理在固定長度密鑰的控制下，以一個分組為單位獨立進行，得出一個固定長度的對應于明文分組的結果。屬于對稱密碼體制的范疇。2.2.1基本概念密碼學中常見的有兩種體制:106基本概念（續(xù)）在分組密碼的設計中用代替、置換手段實現(xiàn)擴散和混淆功能。混淆指加密算法的密文與明文及密鑰關系十分復雜，無法從數(shù)學上描述，或從統(tǒng)計上去分析。擴散指明文中的任一位以及密鑰中的任一位，對全體密文位有影響。經由此種擴散作用，可以隱藏許多明文在統(tǒng)計上的特性，增加密碼的安全基本概念（續(xù)）在分組密碼的設計中用代替、置換手段實現(xiàn)擴散和混1072.2.2標準算法的介紹DES算法國際數(shù)據(jù)加密算法（IDEA）AES算法2.2.2標準算法的介紹DES算法108DES加密算法的背景發(fā)明人美國IBM公司W(wǎng).Tuchman和C.Meyer1971-1972年研制成功?；A1967年美國HorstFeistel提出的理論產生美國國家標準局（NBS)1973年5月到1974年8月兩次發(fā)布通告，公開征求用于電子計算機的加密算法。經評選從一大批算法中采納了IBM的LUCIFER方案。標準化DES算法1975年3月公開發(fā)表，1977年1月15日由美國國家標準局頒布為數(shù)據(jù)加密標準（DataEncryptionStandard），于1977年7月15日生效。DES加密算法的背景發(fā)明人109DES加密算法的背景美國國家安全局（NSA,NationalSecurityAgency)參與了美國國家標準局制定數(shù)據(jù)加密標準的過程。NBS接受了NSA的某些建議，對算法做了修改，并將密鑰長度從LUCIFER方案中的128位壓縮到56位。1979年，美國銀行協(xié)會批準使用DES。1980年，DES成為美國標準化協(xié)會(ANSI)標準。1984年2月，ISO成立的數(shù)據(jù)加密技術委員會(SC20)在DES基礎上制定數(shù)據(jù)加密的國際標準工作。DES加密算法的背景美國國家安全局（NSA,Nationa110實現(xiàn)的設計原則軟件實現(xiàn)的要求：使用子塊和簡單的運算。密碼運算在子塊上進行，要求子塊的長度能自然地適應軟件編程，如8、16、32比特等。應盡量避免按比特置換，在子塊上所進行的密碼運算盡量采用易于軟件實現(xiàn)的運算。最好是用處理器的基本運算，如加法、乘法、移位等。硬件實現(xiàn)的要求：加密和解密的相似性，即加密和解密過程的不同應僅僅在密鑰使用方式上，以便采用同樣的器件來實現(xiàn)加密和解密，以節(jié)省費用和體積。盡量采用標準的組件結構，以便能適應于在超大規(guī)模集成電路中實現(xiàn)。實現(xiàn)的設計原則軟件實現(xiàn)的要求：使用子塊和簡單的運算。密碼運111簡化的DESSimplifiedDES方案，簡稱S-DES方案。加密算法涉及五個函數(shù)：(1)初始置換IP(initialpermutation)(2)復合函數(shù)fk1，它是由密鑰K確定的，具有置換和替代的運算。(3)轉換函數(shù)SW(4)復合函數(shù)fk2(5)初始置換IP的逆置換IP-1簡化的DESSimplifiedDES方案，簡稱S-DES112

113加密算法的數(shù)學表示

IP-1*fk2*SW*fk1*IP也可寫為

密文=IP-1（fk2(SW(fk1(IP(明文)))))其中K1=P8(移位(P10(密鑰K)))K2=P8(移位(移位(P10(密鑰K))))解密算法的數(shù)學表示：明文=IP-1（fk1(SW(fk2(IP(密文)))))加密算法的數(shù)學表示

IP-1*fk2*SW*fk1*IP114對S-DES的深入描述（1）S-DES的密鑰生成：設10bit的密鑰為（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10)置換P10是這樣定義的P10(k1,k2,…,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6)相當于P10=LS-1為循環(huán)左移，在這里實現(xiàn)左移1位。LS-2為循環(huán)左移，在這里實現(xiàn)左移2位。

P8=

按照上述條件,若K選為(1010000010),產生的兩個子密鑰分別為K1=(10100100),K2=(01000011)對S-DE