1、加密加密解密解密明文明文密文密文原始明文原始明文加密加密密鑰密鑰解密解密密鑰密鑰kI 安安 全全 信信 道道 kI KG KG ki ki mi ci ci mi Eki(mi) Eki(mi) 線性反饋移位寄存器線性反饋移位寄存器 f(x)為線性函數(shù)，輸出序列滿足下式為線性函數(shù)，輸出序列滿足下式 knknknknkknacacacaafa22111),(n若敵手得到一段長為若敵手得到一段長為2n的密鑰序列的密鑰序列由此可推出線性反饋移位寄存器連續(xù)的由此可推出線性反饋移位寄存器連續(xù)的n+1個狀態(tài)：個狀態(tài)：1 22nzz zz11 21222312311122122nnnnnnnnnnnSz z

2、za aaSz zza aaSzzzaaa記為記為記為l做矩陣l而l若X可逆，則12nXSSS122311221112111nnnnnnnnnnnnaaaaaaaaacccaaacccX111122nnnnncccaaaX解密算法加密算法密鑰k=(k0, k1, kt-1 )密鑰k=(k0, k1, kt-1 )明文明文x=(x0, x1, xm-1)明文明文x=(x0, x1, xm-1)密文密文x=(y0, y1, ym-1)Feistel加密結(jié)構(gòu)加密結(jié)構(gòu)輸入是分組長為輸入是分組長為2w的明文和一個密鑰的明文和一個密鑰K。將每組明。將每組明文分成左右兩半文分成左右兩半L0和和R0，在進(jìn)行完

3、，在進(jìn)行完n輪迭代后，左輪迭代后，左右兩半再合并到一起以產(chǎn)生密文分組。其第右兩半再合并到一起以產(chǎn)生密文分組。其第i輪迭輪迭代的輸入為前一輪輸出的函數(shù)：代的輸入為前一輪輸出的函數(shù)：其中其中Ki是第是第i輪用的子密鑰，由加密密鑰輪用的子密鑰，由加密密鑰K得到。一得到。一般地，各輪子密鑰彼此不同而且與般地，各輪子密鑰彼此不同而且與K也不同。也不同。111,iiiiiiLRRLF RKxykDESyxkDES-1xiyikDESyixkDES-1+64 bit存儲64 bit存儲y i-1 + +xixiyiyikkXi 64bitXi 64bitYi 64bitYi 64bitDES DES-1 選

4、最左邊 k 位 選最左邊 k 位k bitk bityi-Lyi-2yi-1 +xiyik64bit64bitDES 選最左邊選最左邊 k 位位ki64 bit 寄存寄存器器k bitk bit +xiyik64bit64bit DES-1 選最左邊選最左邊 k 位位k bit64 bit 寄存寄存器器k bitki 輸入輸入 64 bit明文明文數(shù)據(jù)數(shù)據(jù) 初始置換初始置換IP 乘積變換乘積變換 （16輪迭代）輪迭代） 逆初始置換逆初始置換IP-1 64 bit密文數(shù)據(jù)密文數(shù)據(jù) 輸出輸出 標(biāo)準(zhǔn)數(shù)據(jù)加密算法標(biāo)準(zhǔn)數(shù)據(jù)加密算法(y3 , y2, y1 , y0)=(0,0,1,0) 00112233

5、44556677100011111110001111111000110111100010111110000011111001001111101000111110yxyxyxyxyxyxyxyx 定理定理3.1 系數(shù)在系數(shù)在GF(28)上的多項式上的多項式a3x3+a2x2+a1x+a0是模是模x4+1可逆的，當(dāng)且僅當(dāng)矩陣可逆的，當(dāng)且僅當(dāng)矩陣在在GF(28)上可逆。上可逆。0321103221033210aaaaaaaaaaaaaaaa將以上關(guān)系寫成矩陣形式即得（證畢）032103211032103221032103321032101000010000100001aaaahhhhaaaahhhh

6、aaaahhhhaaaahhhh SMS4概況l SMS4分組密碼算法是國家密碼管理局于分組密碼算法是國家密碼管理局于2006年年1月月6日日公布的無線局域網(wǎng)產(chǎn)品使用的密碼算法，是國內(nèi)官方公公布的無線局域網(wǎng)產(chǎn)品使用的密碼算法，是國內(nèi)官方公布的第一個商用密碼算法。布的第一個商用密碼算法。l SMS4是一個分組密碼算法，分組長度和密鑰長度均為是一個分組密碼算法，分組長度和密鑰長度均為128比特。加密算法與密鑰擴(kuò)展算法都采用比特。加密算法與密鑰擴(kuò)展算法都采用32輪非線性迭輪非線性迭代結(jié)構(gòu)。代結(jié)構(gòu)。非線性變換中所使用的非線性變換中所使用的S盒是一個具有很好密碼學(xué)特性盒是一個具有很好密碼學(xué)特性的、由的、

7、由8比特輸入產(chǎn)生比特輸入產(chǎn)生8比特輸出的置換，在設(shè)計原理上，比特輸出的置換，在設(shè)計原理上，SMS4比比AES的的S盒設(shè)計多了一個仿射變換。盒設(shè)計多了一個仿射變換。SMS4有很高的靈活性，所采用的有很高的靈活性，所采用的S盒可以靈活地被替換，盒可以靈活地被替換，以應(yīng)對突發(fā)性的安全威脅。算法的以應(yīng)對突發(fā)性的安全威脅。算法的32輪迭代采用串行處輪迭代采用串行處理，這與理，這與AES中每輪使用代換和混淆并行地處理整個分中每輪使用代換和混淆并行地處理整個分組有很大不同。組有很大不同。l 它的解密算法與加密算法的結(jié)構(gòu)相同，只是輪密鑰的使它的解密算法與加密算法的結(jié)構(gòu)相同，只是輪密鑰的使用順序相反，解密輪密鑰

8、是加密輪密鑰的逆序。用順序相反，解密輪密鑰是加密輪密鑰的逆序。 SMS4算法的術(shù)語說明 在在SMS4算法中，用算法中，用 表示比特的向量集，表示比特的向量集， 中的元素稱為字節(jié)，中的元素稱為字節(jié)， 中的元素稱為字。中的元素稱為字。SMS4算法中構(gòu)造了一個與算法中構(gòu)造了一個與AES類似的類似的S盒，盒，該該S盒是一個固定的盒是一個固定的8比特輸入比特輸入8比特輸出的置比特輸出的置換，記為換，記為 SMS4中的采用了兩個基本運(yùn)算：中的采用了兩個基本運(yùn)算： ，32比特異比特異或；或； ，32比特循環(huán)左移比特循環(huán)左移 i i 位位。eZ282Z322Z(.)SboxiSMS4算法的術(shù)語說明（續(xù)）算法的

9、術(shù)語說明（續(xù)）lSMS4算法的加密密鑰長度為算法的加密密鑰長度為128比特，表比特，表示為，示為， 其中，其中， 為字。為字。l輪密鑰為，輪密鑰為， ， 為字。輪密鑰為字。輪密鑰由加密密鑰通過密鑰擴(kuò)展算法生成。由加密密鑰通過密鑰擴(kuò)展算法生成。l 為系統(tǒng)參數(shù)，為系統(tǒng)參數(shù)，l 為固定參數(shù)，用于密鑰為固定參數(shù)，用于密鑰擴(kuò)展算法。擴(kuò)展算法。),(3210MKMKMKMKMK iMK3 , 2 , 1 , 0i),(3110rkrkrkirk),(3210FKFKFKFKFK ),(3110CKCKCKCKSMS4 的輪函數(shù)的輪函數(shù)l設(shè)輸入為設(shè)輸入為 ，輪密鑰為，輪密鑰為 ，則輪函數(shù)為：則輪函數(shù)為：l其

10、中其中 稱為合成置換，是一個由非線稱為合成置換，是一個由非線性變換和線性變換復(fù)合而成的可逆變換，即性變換和線性變換復(fù)合而成的可逆變換，即 43223210)(),(ZXXXX322Zrk)(),(32103210rkXXXTXrkXXXXF322322:ZZT(.)(.)LTXiXi+1Xi+2Xi+3rkia0a1a2a3b0b1b2b3ssssB2B10B18B1，如果，如果gcd(a, n) = 1,則則:a?(n) 1mod n. eg: 求求3801的后兩位數(shù)字的后兩位數(shù)字 解：解： 3801（mod 100）的結(jié)果）的結(jié)果 ?(100) = 100(1-1/2)(1-1/5) =

11、40， 有有3801 (340)2031 3 (mod 100)例例 使用使用RSA算法計算：如果算法計算：如果p=11，q=17，選取，選取e=7，求解密密鑰，求解密密鑰d。若令明文為若令明文為m=5，求密文，求密文c。驗證。驗證加解密的正確性。加解密的正確性。解：解：p=11，q=17，那么，那么n=pq=187 加密密鑰加密密鑰e=7，與，與 互素，互素，那么，通過擴(kuò)展的歐幾里德算法，可以那么，通過擴(kuò)展的歐幾里德算法，可以求得解密密鑰求得解密密鑰公開公開e和和n，將，將d作為私鑰保密，舍棄作為私鑰保密，舍棄p和和q。當(dāng)當(dāng)m=5，則加密為，則加密為驗證解密正確性驗證解密正確性 所以，使用所

12、以，使用RSA可以正確進(jìn)行公開密鑰加可以正確進(jìn)行公開密鑰加解密。解密。(1)(1)160pq1mod16023de7mod1875 mod187146ecm232 1111mod187146 mod187(146 )146mod187( 2)146mod1875dmc 是否有不通過分解大整數(shù)的其他攻擊途徑？下面證明由n直接確定(n)等價于對n的分解。設(shè)n=pq中，pq，由(n)=(p-1)(q-1)，則有 p+q=n-(n)+1以及由此可見，由p、q確定(n)和由(n)確定p、q是等價的。nnnnqpqp41)(422 1212ppqpqqpqpql 解密過程解密過程：l計算明文計算明文: l

13、 這是因為這是因為21modxCMpC21modmodmodmodkkxkxkCy My MpppMpCgyElGamal 解密解密橢圓曲線密碼體制的優(yōu)點(diǎn)橢圓曲線密碼體制的優(yōu)點(diǎn)l 安全性高安全性高攻擊有限域上的離散對數(shù)可用指數(shù)積分法，運(yùn)算復(fù)雜度攻擊有限域上的離散對數(shù)可用指數(shù)積分法，運(yùn)算復(fù)雜度為為 。 對對ECCECC上離散對數(shù)攻擊并不上離散對數(shù)攻擊并不有效。有效。攻擊攻擊ECCECC上離散對數(shù)問題的方法只有大步小步法，復(fù)雜上離散對數(shù)問題的方法只有大步小步法，復(fù)雜度為度為 。p pmaxmax是是ECCECC形成的交換群的階形成的交換群的階的最大素因子，因此的最大素因子，因此ECCECC上的密碼

14、體制比基于有限域上上的密碼體制比基于有限域上離散對數(shù)問題的公鑰體制更安全離散對數(shù)問題的公鑰體制更安全32)log)(log(log(expppO)(exp(logmaxpOfffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分為L個分組Y0,Y1,YL-1b:明文分組長度n:輸出hash長度CV：各級輸出，最后一個輸出值是hash值無碰撞壓縮函數(shù)f是設(shè)計的關(guān)鍵x ElGamal數(shù)字簽名體制數(shù)字簽名體制 ElGamal數(shù)字簽名體制是數(shù)字簽名體制是T.ElGamal在在1985年發(fā)表關(guān)于年發(fā)表關(guān)于ElGamal公開密鑰密公開密鑰密碼時給出的兩個體制之一，該體制中重要碼時

15、給出的兩個體制之一，該體制中重要的有的有NIST于于1991年公布的數(shù)字簽名標(biāo)準(zhǔn)年公布的數(shù)字簽名標(biāo)準(zhǔn)中所使用的數(shù)字簽名算法（中所使用的數(shù)字簽名算法（DSA），專），專門用于數(shù)字簽名，它的安全性主要基于求門用于數(shù)字簽名，它的安全性主要基于求解離散對數(shù)問題的困難性。解離散對數(shù)問題的困難性。ElGamal數(shù)字簽名l 1參數(shù)與密鑰生成參數(shù)與密鑰生成 選取大素數(shù)選取大素數(shù)p, 是一個本原元。是一個本原元。p和和g公開。公開。 隨機(jī)選取整數(shù)隨機(jī)選取整數(shù)x,1xp 2，計算，計算 。 公鑰為公鑰為y，私鑰為，私鑰為x。l 2簽名簽名 對于消息對于消息m，首先隨機(jī)選取一個整數(shù)，首先隨機(jī)選取一個整數(shù)k, 1kp

16、 2 ，然后計算：然后計算： , 則則m的簽名為的簽名為(r, s)，其中，其中h為為Hash函數(shù)。函數(shù)。l 3驗證驗證 對于消息簽名對對于消息簽名對(m, (r, s)，如果：，如果： 則則(r, s)是是m的有效簽名。的有效簽名。*pgZmodxygpmodkrgp1( ( )mod(1)sh mxr kp()modrsh my rgp因為因為s = (h (m) xr) k 1 mod (p 1)我們有我們有sk+xr =h(m)mod(p 1)所以所以()()modh mskxrskxrrsggg gy rp簽名合理性證明簽名合理性證明2. ElGamal簽名的安全性分析簽名的安全性分

17、析 ElGamal數(shù)字簽名可能存在以下三數(shù)字簽名可能存在以下三種攻擊方式。種攻擊方式。第一種攻擊方法第一種攻擊方法：由于私鑰：由于私鑰 是保密的，是保密的，所以，攻擊者要得到這個密鑰，必須求解所以，攻擊者要得到這個密鑰，必須求解離散對數(shù)問題離散對數(shù)問題 ，這是一個困難問，這是一個困難問題。但是，秘密隨機(jī)數(shù)題。但是，秘密隨機(jī)數(shù) 一旦暴露，則一旦暴露，則解：解： ，即可求得密，即可求得密鑰鑰 ，方案被攻破。，方案被攻破。xloggyk1( ( )mod(1)xh msk rpx第二種攻擊方法第二種攻擊方法：關(guān)于秘密隨機(jī)數(shù)：關(guān)于秘密隨機(jī)數(shù)K的另一個問題是：不可用同一個的另一個問題是：不可用同一個K作

18、作兩次簽名。但若兩次簽名。但若A利用相同利用相同K簽名兩簽名兩次，即次，即 的簽名為的簽名為 及及 ，則攻擊者可以由聯(lián)立方程式則攻擊者可以由聯(lián)立方程式 可得：可得： ，同時可以求得同時可以求得K。因此，同一個。因此，同一個K不不可重復(fù)使用?？芍貜?fù)使用。12,m m1( ,)r s2( ,)r s1122()mod(1)()mod(1)h mxrksph mxrksp11122121 ()() ()mod(1)xh m sh m sssrp5.4 DSS數(shù)字簽名標(biāo)準(zhǔn)l1參數(shù)與密鑰生成參數(shù)與密鑰生成l 選取大素數(shù)選取大素數(shù)p，滿足，滿足 p ，其中，其中512L1024且且L是是64的倍數(shù)。顯然，

19、的倍數(shù)。顯然，p是是L位長的素位長的素數(shù)，數(shù)，L從從512到到1024且是且是64的倍數(shù)。的倍數(shù)。l 選取大素數(shù)選取大素數(shù)q，q是是p 1的一個素因子的一個素因子且且 ，即，即q是是160位的素數(shù)且是位的素數(shù)且是p 1的的素因子。素因子。l 選取一個生成元選取一個生成元 ，其中，其中h是一是一個整數(shù)，滿足個整數(shù)，滿足1hp 1并且并且 。l 隨機(jī)選取整數(shù)隨機(jī)選取整數(shù)x，0 xq，計算，計算 。l p、q和和g是公開參數(shù)，是公開參數(shù)，y為公鑰，為公鑰，x為私鑰。為私鑰。12L2L15916022q(1)/modpqghp(1)/mod1pqhpmodxygpl2簽名簽名 對于消息對于消息m，首先

20、隨機(jī)選取一個整數(shù)，首先隨機(jī)選取一個整數(shù)k , 0kq，然后計算：然后計算： , 則則m的簽名為的簽名為(r, s)，其中，其中h為為Hash函數(shù)，函數(shù)，DSS規(guī)規(guī)定定Hash函數(shù)為函數(shù)為SHA-1。l3驗證驗證 對于消息簽名對對于消息簽名對(m, (r, s)，首先計算：，首先計算： 然后驗證：然后驗證： 如果等式成立，則如果等式成立，則(r, s)是是m的有效簽名；否則簽的有效簽名；否則簽名無效。名無效。(mod )modkrgpq1( ( )modskh mxrq11mod , ( ) modwsquh m wqvr122mod , ( mod )moduuurwqvg ypq算法合理性證

21、明算法合理性證明l因為： s=k1 (h (m)+ xr)mod q所以： ks = (h (m)+ xr)mod ql于是我們有：121()()( () (mod )mod =(mod )mod =(mod )mod =(mod )mod =(mod )mod =(mod )mod =(mod )mod =uuh m wrwh m wxrwh mxr wkswksskvg ypqgypqggpqgpqgpqgpqgpqr第七章 密碼協(xié)議復(fù)習(xí)要點(diǎn)復(fù)習(xí)要點(diǎn)lDiffie-Hellman密鑰交換原理及安全性lShamirShamir門限方案門限方案lKerberos認(rèn)證協(xié)議認(rèn)證協(xié)議用戶B用戶ADi

22、ffie-Hellman密鑰交換lW.DiffieW.Diffie和和M.Hellman1976M.Hellman1976年提出年提出l算法的安全性基于求離散對數(shù)的困難性算法的安全性基于求離散對數(shù)的困難性選擇隨機(jī)數(shù)xp計算YA= gx mod p選擇隨機(jī)數(shù)yp計算YB= gy mod pYAYB計算K=YA y = gxy mod p計算K=YB x = gxy mod p中間人攻擊用戶B選擇隨機(jī)數(shù)yp計算YB= gy mod p計算KBC =YCy = gyz mod p用戶A選擇隨機(jī)數(shù)xp計算YA= gx mod p計算KAC=YC x = gxz mod p敵手C選擇隨機(jī)數(shù)zp計算YC=

23、 gz mod p計算KBC =YB z = gyz mod pYAYCYC計算KAC =YA z = gxz mod pYB端到端協(xié)議l1992年，Diffie、Oorschot和Wiener提出了一個端到端協(xié)議（station-to-station protocol） A B ga C（B）, gb, Ek（SigB（ga, gb） ） C（A）, Ek（SigA（ga, gb） ） 隱式密鑰認(rèn)證l Matsumoto-Takashima-Imai密鑰協(xié)商l 可抵抗中間人攻擊BABAbrarBCAC),(),(),(,),()(aSayAIDSigyAIDAC門限方案的一般概念門限方案的一

24、般概念l 秘密秘密s s被分為被分為n n個部分個部分, ,每個部分稱為每個部分稱為shadow,shadow,由一個參與由一個參與者持有，使得者持有，使得l 由由k k個或多于個或多于k k個參與者所持有的部分信息可重構(gòu)個參與者所持有的部分信息可重構(gòu)s s。l 由少于由少于k k個參與者所持有的部分信息則無法重構(gòu)個參與者所持有的部分信息則無法重構(gòu)s s。l 稱為稱為(k,n)(k,n)秘密分割門限方案，秘密分割門限方案，k k稱為門限值。稱為門限值。l 少于少于k k個參與者所持有的部分信息得不到個參與者所持有的部分信息得不到s s的任何信息稱的任何信息稱該門限方案是完善的。該門限方案是完善

25、的。ShamirShamir門限方案門限方案l基于多項式基于多項式LagrangeLagrange插值公式插值公式設(shè)設(shè)(x(x1 1,y,y1 1), ),(x,(xk k,y,yk k) )是平面上是平面上k k個點(diǎn)構(gòu)成的點(diǎn)集，個點(diǎn)構(gòu)成的點(diǎn)集，其中其中x xi i(i=1,(i=1,k,)k,)各不相同，那么在平面上存在唯各不相同，那么在平面上存在唯一的一的k-1k-1次多項式次多項式f(x)f(x)通過這通過這k k個點(diǎn)個點(diǎn). .若把秘密若把秘密s s取做取做f(0)f(0)，n n個個shadowshadow取做取做f(xf(xi i)(i=1,)(i=1,n),n),那么利用其那么利用

26、其中任意中任意k k個個shadowshadow可以重構(gòu)可以重構(gòu)f(x)f(x)，從而可以得到，從而可以得到秘密秘密s sShamirShamir門限方案門限方案l 有限域有限域GF(q),qGF(q),q為大素數(shù)，為大素數(shù)，qn+1qn+1。秘密。秘密s s是是GF(q)0GF(q)0上均勻選取的隨機(jī)數(shù)，表示為上均勻選取的隨機(jī)數(shù)，表示為ssR RGF(q)0.k-1GF(q)0.k-1個系個系數(shù)數(shù)a a1 1,a ,a2 2, ,a ak-1k-1選取選取a ai i R RGF(q)0.GF(q)0.在在GF(q)GF(q)上構(gòu)造一個上構(gòu)造一個k-1k-1次多項式次多項式f(x)=af(x

27、)=a0 0+a+a1 1x+x+a+ak-1k-1x xk-1k-1l NN個參與者個參與者P P1 1, ,P,Pn n,P,Pi i的的ShadowShadow為為f(i)(i)。任意。任意k k個參與個參與者得到秘密，可使用者得到秘密，可使用(i(il l,f(i,f(il l)|l=1,)|l=1,k,k構(gòu)造方程組構(gòu)造方程組)()()()()()(11101111110kkkkkkkifiaiaaifiaiaaShamirShamir門限方案門限方案l 由由LagrangeLagrange插值公式插值公式)(mod)()()(11qiiixifxfkjkjllljlj)(mod)() 1(111qiiiifskjkjllljljkShamirShamir門限方案門限方案l如果如果k-1k-1個參與者想獲得個參與者想獲得s s，可構(gòu)造，可構(gòu)造k-1k-1個方程，個方