2-對稱密匙密碼1

1、思考題解答假設(shè)已知使用的是凱撒密碼，從下面密文恢復(fù)明文：VSRQJHEREVTXDUHSDQWV凱撒密碼是通過對明文字符移位3進行加密的：A-D,B-E.因此解碼（恢復(fù)明文）時反向移位3,V-S, S-P.對應(yīng)密匙，得到明文： VSRQJHEREVTXDUHSDQWV- SPONGEBOBSQUAREPANTS sponge bob square pants思考題解答假設(shè)使用移位n位簡單替代密碼，找出密匙并恢復(fù)明文：CSYEVIXIVQMREXIH編制一個程序， 密文給定，使用循環(huán)（例如， i=1; i(2,4,1,3);列置換(1,2,3,4)-(3,1,2,4)W E _ AR E _ T

2、_ R E T R E _ TH E R ！R H E !O G E T W E _ A _ W E AH E R ！O G E TE O G T密文 retrhe! weaeogt思考題解答已知KITLKE是根據(jù)字母編碼表加密而來 e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111如果明文是thrill,密匙是什么，如果明文是tiller,密匙又是什么？明文thrill: t-k, h-i, r-t, i-l, l-k, l-e.111K1=011, 001K2=010, 101K3=111,010K4=100, 100K5=011, 100K6=

3、000.由異或規(guī)則得： K1=100, K2=011，K3=010, K4=110, K5=011, K6=100因此， 密匙為：100-011-010-110-011-100明文tiller: t-k, i-i, l-t, l-l, e-k, r-e.111K1=011, 010K2=010, 100K3=111,100K4=100, 000K5=011, 101K6=000.由異或規(guī)則得： K1=100, K2=001，K3=001, K4=011, K5=111, K6=101因此， 密匙為：100-001-001-011-111-1012 對稱密匙密碼對稱密匙密碼流密碼(Stream

4、Ciphers) 根據(jù)一次一密獲得密匙相對較短密匙被擴展為更長的密匙流(keystream)Keystream被用做一次一密的密匙只用到了混淆分組密碼(Block cipher) 根據(jù)電碼本密碼獲得分組密碼密匙決定電碼本每個密匙生成一個不同的電碼本混淆和擴散都得到利用流密碼 Stream Ciphers流密碼現(xiàn)在已不如分組密碼流行本節(jié)討論一種流密碼A5/1基于線性移位寄存器（硬件實現(xiàn)）用于GSM移動通信系統(tǒng)流密碼原理流密碼使用n比特長的密匙K，并將其擴展為更長的密匙流。將密匙流與明文做異或運算， 得到密文C。密匙流的使用方法與一次一密中的密匙相同。解密時將密文與密匙做異或運算得到明文。函數(shù)可表

5、示為StreamCipher(K)=SK是密匙， S是和一次一密中對等的密匙流A5/1 原理1A5/1 使用3個線性移位寄存器(LFSR)寄存器X: 19 bits (x0,x1,x2, ,x18)寄存器Y: 22 bits (y0,y1,y2, ,y21)寄存器Z: 23 bits (z0,z1,z2, ,z22)三個寄存器共有64 bits密匙K采用64 bits。 初始時密匙K被載入3個寄存器A5/1 原理2對每一步做: m = major(x8, y10, z10) Major（多數(shù)）函數(shù)定義: major(0,1,0) = 0 and major(1,1,0) = 1 如果 x8 =

6、 m 那么 X寄存器 進行移位運算 t = x13 x16 x17 x18xi = xi1 for i = 18,17,1 and x0 = t如果 y10 = m 那么 Y寄存器進行移位運算t = y20 y21yi = yi1 for i = 21,20,1 and y0 = t如果 z10 = m 那么 Z寄存器進行移位運算t = z7 z20 z21 z22zi = zi1 for i = 22,21,1 and z0 = t密匙流比特最后由 x18 y21 z22 產(chǎn)生A5/1原理3每次運算獲得一個比特密匙用于初始化三個寄存器每個寄存器是否進行移位操作由M(x8, y10, z10)

7、決定密匙流比特由三個最右端比特進行XOR運算獲得y0y1y2y3y4y5y6y7y8y9y10y11y12y13y14y15y16y17y18y19y20y21z0z1z2z3z4z5z6z7z8 z9 z10 z11 z12z13z14z15z16z17z18z19z20z21z22XYZx0 x1x2x3x4x5x6x7x8x9x10 x11x12x13x14x15x16x17x18A5/1實例在這種情況下, m = maj(x8, y10, z10) = maj(1,0,1) = 1 寄存器 X 進行移位, Y不進行移位, Z進行移位密匙流比特由最右端比特進行XOR操作而得此例, 密匙流

8、比特是 0 1 0 = 1最后用密匙流和明文做XOR運算進行加密和解密110011001100110011000111100001111000011110001XYZ1010101010101010101流密碼總結(jié)密匙流的產(chǎn)生看似很復(fù)雜，但用硬件實現(xiàn)很簡單產(chǎn)生速度與計算機時鐘速度相當（可與語音同步）從一個64位密匙可產(chǎn)生無窮多密匙流最終會產(chǎn)生密匙流循環(huán)！流密碼總結(jié)因為過去基于軟件的密碼系統(tǒng)不能產(chǎn)生高速比特流，流密碼曾十分輝煌，當今，基于軟件的密碼系統(tǒng)的出現(xiàn)，使分組密碼成為主流密碼流的未來?密碼學(xué)家Shamir: “密碼流已步入死亡-the death of stream ciphers”-20

9、04或許太夸張但分組密碼是現(xiàn)今主流分組密碼 Block Ciphers(Iterated) 分組密碼（迭代）密文和明文均是固定長度的分組(block)通過若干輪使用輪函數(shù)(round function)迭代產(chǎn)生密文輪函數(shù)的輸入由前一輪的輸出和密匙組成分別設(shè)計一個安全的分組密碼或者一個高速的算法不難，但既安全又高效的算法則非常困難通常用軟件實現(xiàn)Feistel 密碼(Cipher)Feistel 密碼 是分組密碼的一種(分組)原則，不是一種特殊的密碼將明文分解成右半部分和左半部分: 明文 = (L0, R0)對于每一輪 i=1, 2,.,n, 計算：Li= Ri1 Ri= Li1 F(Ri1,Ki

10、)此處 F 是 輪函數(shù), Ki是第i輪的 子密匙(subkey)密文 = (Ln, Rn)Feistel 密碼解密解密: 密文 = (Ln, Rn)對每輪 i=n,n1,1, 計算Ri1 = LiLi1 = Ri F(Ri1,Ki)此處 F 是 輪函數(shù), Ki是第i輪的 子密匙 subkey 明文 = (L0,R0)此算法對所有函數(shù)F都適用但只對特定函數(shù)來說是安全的優(yōu)點在于所有安全性問題可以轉(zhuǎn)化為輪函數(shù)F的問題DES密碼20世紀70年代提出DES(Data Encryption Standard)根據(jù)IBM公司提出Feistel密碼之一的Lucifer密碼設(shè)計 當時，密碼技術(shù)除被政府和軍方所研

11、究及掌握，民間及商業(yè)對此尚無研究但計算機的發(fā)展，數(shù)據(jù)加密對商業(yè)至關(guān)重要美國標準局(NBS)提出了對密碼算法的征集獲勝者將成為美國政府及實際上的產(chǎn)業(yè)界標準因參與者不多，最終由唯一IBM提出的Lucifer算法獲得DES密碼由于技術(shù)力量不足，NBS求助于政府密碼機構(gòu)NSA (National Security Agency)由于NSA專門負責(zé)政府及軍方高級敏感信息加密研究，開始不愿參與民間密碼開發(fā) 后被懷疑在DES中植入后門，使NSA很容易破解DESLucifer算法經(jīng)過修改成為DES主要修改為將密匙長度由128位減為64位，并且64位中有8位勢用來校驗奇偶性的，實際密匙長度由為56。破譯難度降低了272倍，難怪被指動過手腳DES密碼歸納DES是16輪的Feistel結(jié)構(gòu)密碼DES的分組長度是64位 DES使用56位密匙DES每一輪使用48位的子密匙，每個