實(shí)驗(yàn)二古典密碼

1、實(shí)驗(yàn)2古典密碼實(shí)驗(yàn)2古典密碼1.實(shí)驗(yàn)?zāi)康?1) 了解古典密碼中的基本加密運(yùn)算。(2) 了解幾種典型的古典密碼體制。(3) 掌握古典密碼的統(tǒng)計(jì)分析方法。2實(shí)驗(yàn)內(nèi)容(1)古典密碼體制 簡(jiǎn)單移位加密(單表代換)該加密方法中，加密時(shí)將明文中的每個(gè)字母向前推移K位。經(jīng)典愷撒密碼加密圖2-1加載文件1實(shí)驗(yàn)2古典密碼圖2-1加載文件#實(shí)驗(yàn)2古典密碼變換就是這種變換，取k=3。步驟1：打開CAP4軟件，并加載實(shí)驗(yàn)一附帶的mw.txt ”，如圖2-1所示。£.1El pch Cifhn* %P l A int AK t,Analysis TooKsAnpxizUijt frirnd fro Paris

2、 exan.i.ne!d tils empty si-ass vl th surprlsie-j as if etpa口幻工曰.七11cxn had taken 口l;a>c皀 while he wa5n? t looking； I cxoured sone kore wine- and he settled back in his 匚hatri. face tilted up ttHrarda the sun.圖2-1加載文件#實(shí)驗(yàn)2古典密碼圖2-1加載文件#實(shí)驗(yàn)2古典密碼C±pli«irt QKt.PA倨TaotEPij 臥 alpPtabm咚 TjM由 nrwl

3、k; AlyuiM-maIlBiMTI T«tX匚 fhwfei T iwh 旦 Lk& i&piw Tpglg Fubbu Is：.即勺創(chuàng)白"it圖2-1加載文件#實(shí)驗(yàn)2古典密碼flflmT Brf- AScfrCiphvTHlAddi圖2-1加載文件#實(shí)驗(yàn)2古典密碼Plain七包掘七Analysis Tools5訴訃Ky皿d T1&出円如dphahciiG IToc*?Tiarwposhcn QeniHii:匕 Iguiithm!； PWjaphi: Twfa £liearri Tgla 匚T皿 EZ匸加"b FUbic 札e

4、y EjvHenK.FIT 問(wèn) Acklism ciTeMiAd*Sin步驟2：采用愷撒加密方法手工加密“mw.txt”打開CAP4菜單欄“ Cipher”菜單項(xiàng)選擇"simple shift”選項(xiàng)，并選擇移位值“shift value”為3，加密步驟1中加載的文件，如圖 2-2所示。Oiur friend froa Pails examined his enptywith surprise oe ifevaporation hid ta.ken place while he wa三:n" 1 looking. I poured sone nore vine und hs

5、settled bach in his chalrP face tlHeid ujp towards t hiE .S Lin .#實(shí)驗(yàn)2古典密碼#實(shí)驗(yàn)2古典密碼Analysis Tools5 rmph Analyse：Cipher text-圖2-2參數(shù)設(shè)置/fS* CAF Crypt«ci-4j：>hic Anilyi i s Prcr w> 網(wǎng)In-tpirT與 xkCLpHwegiAh-jfutPU 衛(wèi) *i n+.<T-K t.Our ft 1 end from Paris ejeanined his： empty gl占哼毀 with surprisep

6、 as if evaporation had taken fplace while he wasn-1 looking. I poured 2one Aore vine aid. he setxled back Ln his chalrp race tilted up towards the slitlSTffnuSgl甲嶺T曲*卩中樸曲卜*創(chuàng)社T od事 T rainapEtwlkMi 百engl匕 即bcr thn巧 內(nèi)曲幣血T甘 弓trmn ToakPloizk iZiphi Tods：步驟3:比較二者的加密結(jié)果是否相同。步驟4：點(diǎn)擊CAP4軟件中的"Simple analys

7、is”下的"shift”鍵，觀察愷撒加密法的可能密鑰值，并分析其攻擊的難度，如圖2-4所示。Analysis TookPlaintext5mpk-Anai5FW如sbelic TE：fTdampmitiofi:呂 IjEihmwEUi!占 mTZmT 站TimkFl址用丫直屮工Dur friend frow Faris enaTiined his capty glase with surprisr, as if evBpQrali w had takm*hilc he rasn111:I poured 打口鼻尺"pre：雷 1 口巴 嗣 he wuttiedin hl#ti

8、lted up tpwai-dFPlanTtfwiAdtiiSize L-ipheiT ewl: fid±See3實(shí)驗(yàn)2古典密碼#實(shí)驗(yàn)2古典密碼圖2-4密鑰分析 仿射密碼加密(單表代換)在仿射密碼加密(affine cipher)中，字母表中的字母被賦予一個(gè)數(shù)字，例如，a=0,b=1,c=2, , ,z=25.仿射密碼加密法的密鑰為025之間的數(shù)字對(duì) (a,b )°a與26的最大公約數(shù)必須為1,這就是說(shuō)能整除a和26的數(shù)只有1.現(xiàn)在假設(shè)m為明文字母的數(shù)字，而c為密文字母的數(shù)字，那么，這兩個(gè)數(shù)字之間有如下關(guān)系：#實(shí)驗(yàn)2古典密碼#實(shí)驗(yàn)2古典密碼c=(am+b)(mod 26)-

9、1(c-b)(mod 26) 其中，(mod 26)的操作是：除以26,得其余數(shù)。例如，選取密鑰為(7, 3)?？梢宰鳛榉律涿艽a的加密鑰。m=ac(H)=(7c(0)=(7c(T)=(7這樣，對(duì)于這個(gè)密鑰，”因?yàn)?與26互素，也就是只有公約數(shù)1,所以(乙3)將“hot ”轉(zhuǎn)換成數(shù)字7、14、19,利用仿射等式生成：X 7+3) mod 26=52 mod 26=0, 即為字母“ a “。X 14+3) mod 26=101 mod 26=23, 即為字母X 19+3) mod 26=136 mod 26=6, 即為字母” hot ”變成了“ axg “.4實(shí)驗(yàn)2古典密碼5實(shí)驗(yàn)2古典密碼CAP4

10、軟件中實(shí)現(xiàn)仿射密碼加密:步驟1:在CAP4軟件中加載要加密地的明文“mw.txt步驟2：選取Cipher菜單下的Affine Cipher菜單項(xiàng)，彈出如下對(duì)話框，如圖2-5所示。陽(yáng)曲訥 匡巫還p里亙;Ba幻TooUT ISO4PO£B<W 曰=凸IgWI亦占 Ffrpr5phk:E皿m TghQcfei Tort)呂 kK&.Whei T 皿RJMo、g 牙嚇申辛| o | UU |圖2-5設(shè)置加密密鑰步驟3：選擇圖中"Affine Cipher "中的“ Encipher “選項(xiàng)進(jìn)行加密，如圖2-6所示。圖2-6采用Affine Cipher 加密

11、6實(shí)驗(yàn)2古典密碼 維吉尼亞密碼加密（多表代換）Vigenere加密法是一個(gè)很著名的多表代換加密法。 該加密法是基于關(guān)鍵詞的多表 代換加密系統(tǒng)，但不像單表代換中的關(guān)鍵詞加密那樣， 使用關(guān)鍵詞來(lái)定義替換模式， 它是先將明文按照關(guān)鍵字的長(zhǎng)度分組，然后將分組中的每個(gè)字符與關(guān)鍵字中相應(yīng)位置上的字符進(jìn)行模 26加密運(yùn)算，這樣每個(gè)明文字母都與一個(gè)關(guān)鍵詞的字母關(guān)聯(lián)。例如：如果關(guān)鍵詞為"hold"，而明文為"this is the plaintext”那么，關(guān)鍵詞一明文的關(guān) 聯(lián)如下所示：ho 1(i h01 dho 1d h o1 d h0明丈th i j£ heP 1a

12、 i nIC XtaVt'f pe k1d wd p be h dh注意：以上的密文結(jié)果，也可以直接查找Vigenere表獲取密文.例如：上面示例中的第一對(duì)是"ht “.在Vigenere表中查找”"列和”"行，找到結(jié)果密文字母 ”", 重復(fù)這個(gè)過(guò)程。明文1ab.ee1Rh1J 'k1Eri&1*勺TstuVwXysa*b£efKh4JkI moP<4rsuVwyzbbcd年f耳hjjk1m nOPqr3uVwXy£ccdefghiJkniri oPqr9.tUlvw3LyEbdfKhiik1mXIo P

13、gr3-LLiVwxyMubcreth1jkEILnOR qrs1UVwXyzafacd密f¥hijk1mrioPQ r諾1niVwXyzbE.de密民hijk1mnoPqr suVwXy£bcd韋f鑰hijk1n-OpqrB tuVwX.y雷abcclcfiijk111tioPqTsf uvwXyabcdef庫(kù)hJk1m11opqr¥Vvr3E.ybcd亡rfit11ikk1mnQPqr再4UV wXy«bcdFshjlitLmna-P<1rai|iVZ MrbcdefKhijItmmnaPqrb1uVwx ybdrrshiiih1nnOPqr蠢

14、tuVwXy 更ahcaefRhijk1ni.ooPqT辛t弊VwXyE HibcdefRh1>k1mnPPqrStuVwKy£ brderEhi.ikJmnoQqr甘TuVwXyXAb ed.efehiJkImnoprr弐t11v iMrKyeBbc defRhik1m.n0PQKtuVwKyahud ef8hVjkmEkoPqrtVWXyzabde f8hijk1rtinopqrS-uuVwXyZ-玄bc<1ef Khtjk1mn口Pqr暮1VvwJEy£aLcdfK hiik1mnoPqtattiwWXy耳ifilbcdei電h ijktmnaP輒rsi科

15、¥31Myjt&bcdf靈hi JkImn©Pqr3>tuVwyysbedC-£h4j k1cunoPqr鼻iuVwX.£Rbrdefhijk 1mncPqrtuVwXyCAP4軟件中實(shí)現(xiàn)維吉尼亞加密:步驟1:在CAP4軟件中加載要加密地的明文“mw.txt “.2-7步驟2：選取Cipher菜單下的Vigenere菜單項(xiàng)，彈出如下對(duì)話框，如圖 所示。CikF iCfwt t E-jicr*phi c Aas.1 ykl k Fr口卩 tr圖2-7 設(shè)置加密密鑰詞步驟3：選擇"Encipher"菜單項(xiàng)加密。(2) 古典密

16、碼體制的統(tǒng)計(jì)分析因?yàn)楣诺涿艽a學(xué)中的大部分加密都是基于英文字母的，所以其相應(yīng)的明文和密 文都會(huì)遵循相應(yīng)的語(yǔ)言統(tǒng)計(jì)規(guī)律。根據(jù)明密文中的統(tǒng)計(jì)特性來(lái)破譯密文，是古典密 碼學(xué)破譯的基本方法。最容易觀察的字母特性是其出現(xiàn)頻率，所以古典密碼的統(tǒng)計(jì)分析很多也是以字 母出現(xiàn)頻率做為主要線索的。然而，大多數(shù)頻率分析是基于標(biāo)準(zhǔn)英語(yǔ)字母的常見頻 率表的，其中各個(gè)英文字母的出現(xiàn)頻率如下：從高到低的順序 ：ETAONIRSHDLUCMPFYWGEVJKQXZ 通常由于所加密明文的性質(zhì)不同，那么字母出現(xiàn)頻率也會(huì)有所差異，所以，一 般采用字母頻率來(lái)破譯時(shí)不能完全依照上述順序進(jìn)行相關(guān)對(duì)照來(lái)得出單表代換模 式，而是考慮將頻率分組

17、。標(biāo)準(zhǔn)英文字母出現(xiàn)四個(gè)頻率組：缺少但很少出現(xiàn)在其他分組中。 將密文中的字母字母在分組中的位置可能有些變化，出現(xiàn)頻率進(jìn)行統(tǒng)計(jì)后，可以將它們按照出現(xiàn)頻率的高低，先進(jìn)行簡(jiǎn)單分組，然后對(duì) 照以上頻率組，逐個(gè)分析，以便確定其單表代換模式。僅僅依靠以上規(guī)律通常還是很不充分的，的出現(xiàn)頻率來(lái)輔助破譯。例如，TH , HE,很多時(shí)候還會(huì)用到雙聯(lián)字母或三聯(lián)字母IN，RE, DE, ST, EN，AT, OR，IS,9實(shí)驗(yàn)2古典密碼#實(shí)驗(yàn)2古典密碼ERE, FOR等都比較常出現(xiàn)。ET, IT , AR , TE, HI , OF, THE , ING , 采用CAP4軟件來(lái)實(shí)現(xiàn)古典密碼的統(tǒng)計(jì)分析。 仿射密碼的統(tǒng)計(jì)分

18、析前提是，我們已經(jīng)知道該段密文是采用仿射加密法加密的。步驟1打開CAP4軟件，加載已經(jīng)獲取的密文 “fsbhmi.txt ”,并按下"Basic Tools”工具條中的“ Freq”按鈕，統(tǒng)計(jì)密文中每個(gè)字母出現(xiàn)的幾率，如圖2-8所示。圖2-8統(tǒng)計(jì)密文字母頻率通過(guò)統(tǒng)計(jì)可知，密文中出現(xiàn)頻率最高的字母依次是X、H、N、T、C、K、J,故可假設(shè)密文字符 X對(duì)應(yīng)的是明文字符 E,密文字符H對(duì)應(yīng)的銘文字符為 To步驟2:打開CAP4中的"Simple analysis”工具條中的"Afine ”按鈕，輸入 上述字母對(duì)，如圖 2-9所示。圖2-9驗(yàn)證猜測(cè)a注意：這里的ko,ki

19、,表示仿射加密函數(shù)為 y=kX+kg mod 26，所以其中ki的取值 只能屬于下列整數(shù)集合 1，3，5，7, 9，11，15，17，19，21，23，25。很明顯， 以上猜測(cè)有誤，故可以進(jìn)一步假設(shè)密文字母X對(duì)應(yīng)的明文字符為 E，密文字符N對(duì)應(yīng)的明文字符為 T，經(jīng)測(cè)試可以知道，該猜測(cè)也不成立。接著測(cè)試可以發(fā)現(xiàn)密文字 符X對(duì)應(yīng)明文E，密文字符T對(duì)應(yīng)T的假設(shè)也不成立。試假設(shè)密文C對(duì)應(yīng)明文T。步驟3：進(jìn)一步驗(yàn)證上述猜測(cè)，其結(jié)果如下所示，如圖2-10所示。圖2-10驗(yàn)證猜測(cè)b通過(guò)測(cè)試發(fā)現(xiàn)，此次假設(shè)成立，即該段密文采用的仿射變換函數(shù)可能為y=9x+13mod 26.步驟4：采用上述假設(shè)結(jié)果， 在CAP4

20、軟件的菜單項(xiàng)“Cipher”下選擇“Afine ”， 解密密文，如圖2-11所示。5«聲加如岸Plaintextdurfri Endfronparls exan lnedhl s enptygl assl t hsurprls 匕占百 1 f evaporat i oriha dt akenpl acewhi 1 tshewasnt 1 Mking.1 pDureds >33.e norewinjeandhea et tl edbackljihi schalrfacet 111 eilu!ptEnvi pb.iTmEnter two numbers (a and b): 廠 w

21、 3. 5. 7. a 11-13.15.17. la Zl. 33. 25abcdetgliiJJtlBiiopqBtuvwxyznl"oxqpyhqE ± t a 1 s b k t c? 1 u d m e>ards tlnesun11實(shí)驗(yàn)2古典密碼12實(shí)驗(yàn)2古典密碼冷"CLjditf#實(shí)驗(yàn)2古典密碼日十T耐K皀卿田日T adi：Trmup&NKtiGentfa aKhmi：g 陽(yáng)e t ooh：Qytirdw T cckPWizk 匚bhw TghPl七h(yuǎn)e Key 劉才旳£filFirwK.sy#實(shí)驗(yàn)2古典密碼#實(shí)驗(yàn)2古典密碼Su

22、e匚Adci#實(shí)驗(yàn)2古典密碼#實(shí)驗(yàn)2古典密碼圖2-11破譯密文采用以上猜測(cè)結(jié)果破譯密文所獲取的明文，具有意義，所以可以認(rèn)定該次加密操作采用的加密變換函數(shù)為：y=9x+13 mod 26.3 .知識(shí)點(diǎn)(1) 模運(yùn)算(帶余除法)若a,b為兩個(gè)整數(shù)，bz 0,則唯一存在兩個(gè)整數(shù)q和r,使得下式成立a=bq+r, 0? rv|b|.模的定義如果a是一個(gè)整數(shù)，n是一個(gè)正整數(shù)，疋義a mod n為a除以n的余數(shù)a= n _a/n +(a mod n).例A: 113 mod 24=17 模算術(shù)運(yùn)算由定義可知，運(yùn)算(mod n)將所有的整數(shù)映射到集合 0,1, n-1,那么 在這個(gè)集合上進(jìn)行的算術(shù)運(yùn)算稱為模

23、算術(shù)。模算術(shù)有如下的性質(zhì)：(a mod n) + (b mod n) mod n=(a+b) mod n;(a mod n) -(b mod n) mod n=(a-b) mod n;(a mod n) x (b mod n)mod n=(a x b) mod n.因此，普通算術(shù)的加、減、乘、除運(yùn)算規(guī)則可以平移到模算術(shù)中。 Zn上模運(yùn)算的性質(zhì)：定義比n小的非負(fù)整數(shù)集合為Zn, Zn=0,1, , ,n-1,這個(gè)集合稱為剩余類集，或模n的剩余類。更確切的說(shuō)，Zn中的每個(gè)整數(shù)代表一個(gè)剩余類，我們可以將模 n的剩余類表示為0,1,2, ,n-1。例2:模4剩余類為：0= , ,-16,-12,-8,

24、-4,0,4,8,12,16 , 1 = , ,-15,-11,-7,-3,1,5,9,13,17, 2 = , ,-14,-10,-6,-2,2,6,10,14,18 , 3 = , ,-13,-9,-5,-1,3,7,11,15,19, , 在剩余類的所有整數(shù)中，我們通常用最小非負(fù)整數(shù)來(lái)代表這個(gè)剩余類。尋找與k模同余(指的是兩個(gè)數(shù)對(duì)同一個(gè)數(shù)求模結(jié)果相同，例如：整數(shù) a和b對(duì)整數(shù) n求模結(jié)果相同，我們就說(shuō) a和b模n同余，記為a= b (mod n)的最小非負(fù)整 數(shù)的過(guò)程，稱為模n的k約化。如果我們?cè)赯n中進(jìn)行模運(yùn)算，該運(yùn)算具有如下性質(zhì)： 交換律:(w+x) mod n=(x+w) mod

25、n(w x x) mod n=(x x w) mod n結(jié)合律:(w+x) +y mod n=w+(x+y) mod n(w x x) x y mod n=w x (x x y) mod n 分配率：wx (x+y) mod n=(w x x)+ (wx y) mod n 單位元 :(0+w) mod n=w mod n(1 x w) mod n=w mod n加法逆元(-w):對(duì)于Zn中的任意 w,存在一個(gè) 乙使得w+z= 0 mod n.注意：一般來(lái)說(shuō)，在 Zn中，一個(gè)整數(shù)與n互素，那么在 Zn中有它的一個(gè)乘法逆元，使得該整數(shù)與其逆元相乘模n為1這里的互素指的是兩個(gè)數(shù)的最大公約數(shù)為1.例3

26、:在Z 8中，整數(shù)1，3，5，7有一個(gè)乘法逆元，而 2，4和6沒(méi)有。特別提醒：我們密碼學(xué)中用到的運(yùn)算均為模運(yùn)算，對(duì)于古典密碼體制來(lái)說(shuō)，用 到的運(yùn)算均為 Z 26上的模運(yùn)算。(2)乘法逆元在仿射加密法中，我們是通過(guò)仿射函數(shù)變換來(lái)實(shí)現(xiàn)加密的，其加密變換函數(shù)一般表示為：ek(x)=ax+b mod 26,那么該函數(shù)的逆函數(shù)(也就是相應(yīng)的解密函數(shù))為：dk( y)=1/a(y-b) mod 26正如上面所述在密碼學(xué)中，我們提及的運(yùn)算一般是模運(yùn)算，這里指的是Z26上的運(yùn)算。在模運(yùn)算中，將1/a表示為：a-1,稱作a的乘法逆元，由乘法逆元性質(zhì)可知：aa-1 =1 mod 26.由于在Z26中并不是所有的整

27、數(shù)都有乘法逆元，事實(shí)上，只有1，3，5，乙9，11，15，17，19，21，23，25才有乘法逆元，也就是說(shuō)只有當(dāng)加密變換函數(shù)中的a取上面這些值時(shí)，其才是可逆的，才能實(shí)現(xiàn)解密。另外，某個(gè)整數(shù)集上相關(guān)元素的乘法逆元的求解一般采用歐幾里德擴(kuò)展算法來(lái)實(shí)現(xiàn)(放在后續(xù)課程中講解)，這里直接給出Z26上相關(guān)整數(shù)的乘法逆元，以便參考：-1 -1 -1 -1 -11 mod 26=1 ,3 mod 26=9,5 mod 26=21,7 mod 26=15,11 mod 26=19,-1 -117 mod 26=23,25 mod 26=254 常見問(wèn)題解答(1)密碼學(xué)研究的主要問(wèn)題是什么?解答：密碼學(xué)的基本目的是在通信雙方之間應(yīng)用不安全的信道進(jìn)行通信時(shí)，設(shè)法保 證通信安全。