实验二古典密码

1、实验2古典密码实验2古典密码1.实验目的(1) 了解古典密码中的基本加密运算。(2) 了解几种典型的古典密码体制。(3) 掌握古典密码的统计分析方法。2实验内容(1)古典密码体制 简单移位加密(单表代换)该加密方法中，加密时将明文中的每个字母向前推移K位。经典恺撒密码加密图2-1加载文件1实验2古典密码图2-1加载文件#实验2古典密码变换就是这种变换，取k=3。步骤1：打开CAP4软件，并加载实验一附带的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加载文件#实验2古典密码图2-1加载文件#实验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：.即勺创白"it图2-1加载文件#实验2古典密码flflmT Brf- AScfrCiphvTHlAddi图2-1加载文件#实验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 问 Acklism ciTeMiAd*Sin步骤2：采用恺撒加密方法手工加密“mw.txt”打开CAP4菜单栏“ Cipher”菜单项选择"simple shift”选项，并选择移位值“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 .#实验2古典密码#实验2古典密码Analysis Tools5 rmph Analyse：Cipher text-图2-2参数设置/fS* CAF Crypt«ci-4j：>hic Anilyi i s Prcr w> 网In-tpirT與 xkCLpHwegiAh-jfutPU 卫 *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曲*卩中朴曲卜*创社T od事 T rainapEtwlkMi 百engl匕 即bcr thn巧 內曲幣血T甘 弓trmn ToakPloizk iZiphi Tods：步骤3:比较二者的加密结果是否相同。步骤4：点击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实验2古典密码#实验2古典密码图2-4密钥分析 仿射密码加密(单表代换)在仿射密码加密(affine cipher)中，字母表中的字母被赋予一个数字，例如，a=0,b=1,c=2, , ,z=25.仿射密码加密法的密钥为025之间的数字对 (a,b )°a与26的最大公约数必须为1,这就是说能整除a和26的数只有1.现在假设m为明文字母的数字，而c为密文字母的数字，那么，这两个数字之间有如下关系：#实验2古典密码#实验2古典密码c=(am+b)(mod 26)-

9、1(c-b)(mod 26) 其中，(mod 26)的操作是：除以26,得其余数。例如，选取密钥为(7, 3)。可以作为仿射密码的加密钥。m=ac(H)=(7c(0)=(7c(T)=(7这样，对于这个密钥，”因为7与26互素，也就是只有公约数1,所以(乙3)将“hot ”转换成数字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实验2古典密码5实验2古典密码CAP4

10、软件中实现仿射密码加密:步骤1:在CAP4软件中加载要加密地的明文“mw.txt步骤2：选取Cipher菜单下的Affine Cipher菜单项，弹出如下对话框，如图2-5所示。阳曲訥 匡巫还p里亘;Ba幻TooUT ISO4PO£B<W 曰=凸IgWI亦占 Ffrpr5phk:E皿m TghQcfei Tort)吕 kK&.Whei T 皿RJMo、g 牙吓申辛| o | UU |图2-5设置加密密钥步骤3：选择图中"Affine Cipher "中的“ Encipher “选项进行加密，如图2-6所示。图2-6采用Affine Cipher 加密

11、6实验2古典密码 维吉尼亚密码加密（多表代换）Vigenere加密法是一个很著名的多表代换加密法。 该加密法是基于关键词的多表 代换加密系统，但不像单表代换中的关键词加密那样， 使用关键词来定义替换模式， 它是先将明文按照关键字的长度分组，然后将分组中的每个字符与关键字中相应位置上的字符进行模 26加密运算，这样每个明文字母都与一个关键词的字母关联。例如：如果关键词为"hold"，而明文为"this is the plaintext”那么，关键词一明文的关 联如下所示：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注意：以上的密文结果，也可以直接查找Vigenere表获取密文.例如：上面示例中的第一对是"ht “.在Vigenere表中查找”"列和”"行，找到结果密文字母 ”", 重复这个过程。明文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庫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软件中实现维吉尼亚加密:步骤1:在CAP4软件中加载要加密地的明文“mw.txt “.2-7步骤2：选取Cipher菜单下的Vigenere菜单项，弹出如下对话框，如图 所示。CikF iCfwt t E-jicr*phi c Aas.1 ykl k Fr口卩 tr图2-7 设置加密密钥词步骤3：选择"Encipher"菜单项加密。(2) 古典密

16、码体制的统计分析因为古典密码学中的大部分加密都是基于英文字母的，所以其相应的明文和密 文都会遵循相应的语言统计规律。根据明密文中的统计特性来破译密文，是古典密 码学破译的基本方法。最容易观察的字母特性是其出现频率，所以古典密码的统计分析很多也是以字 母出现频率做为主要线索的。然而，大多数频率分析是基于标准英语字母的常见频 率表的，其中各个英文字母的出现频率如下：从高到低的顺序 ：ETAONIRSHDLUCMPFYWGEVJKQXZ 通常由于所加密明文的性质不同，那么字母出现频率也会有所差异，所以，一 般采用字母频率来破译时不能完全依照上述顺序进行相关对照来得出单表代换模 式，而是考虑将频率分组

17、。标准英文字母出现四个频率组：缺少但很少出现在其他分组中。 将密文中的字母字母在分组中的位置可能有些变化，出现频率进行统计后，可以将它们按照出现频率的高低，先进行简单分组，然后对 照以上频率组，逐个分析，以便确定其单表代换模式。仅仅依靠以上规律通常还是很不充分的，的出现频率来辅助破译。例如，TH , HE,很多时候还会用到双联字母或三联字母IN，RE, DE, ST, EN，AT, OR，IS,9实验2古典密码#实验2古典密码ERE, FOR等都比较常出现。ET, IT , AR , TE, HI , OF, THE , ING , 采用CAP4软件来实现古典密码的统计分析。 仿射密码的统计分

18、析前提是，我们已经知道该段密文是采用仿射加密法加密的。步骤1打开CAP4软件，加载已经获取的密文 “fsbhmi.txt ”,并按下"Basic Tools”工具条中的“ Freq”按钮，统计密文中每个字母出现的几率，如图2-8所示。图2-8统计密文字母频率通过统计可知，密文中出现频率最高的字母依次是X、H、N、T、C、K、J,故可假设密文字符 X对应的是明文字符 E,密文字符H对应的铭文字符为 To步骤2:打开CAP4中的"Simple analysis”工具条中的"Afine ”按钮，输入 上述字母对，如图 2-9所示。图2-9验证猜测a注意：这里的ko,ki

19、,表示仿射加密函数为 y=kX+kg mod 26，所以其中ki的取值 只能属于下列整数集合 1，3，5，7, 9，11，15，17，19，21，23，25。很明显， 以上猜测有误，故可以进一步假设密文字母X对应的明文字符为 E，密文字符N对应的明文字符为 T，经测试可以知道，该猜测也不成立。接着测试可以发现密文字 符X对应明文E，密文字符T对应T的假设也不成立。试假设密文C对应明文T。步骤3：进一步验证上述猜测，其结果如下所示，如图2-10所示。图2-10验证猜测b通过测试发现，此次假设成立，即该段密文采用的仿射变换函数可能为y=9x+13mod 26.步骤4：采用上述假设结果， 在CAP4

20、软件的菜单项“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实验2古典密码12实验2古典密码冷"CLjditf#实验2古典密码日十T耐K皀卿田日T adi：Trmup&NKtiGentfa aKhmi：g 阳e t ooh：Qytirdw T cckPWizk 匚bhw TghPl七he Key 刘才旳£filFirwK.sy#实验2古典密码#实验2古典密码Su

22、e匚Adci#实验2古典密码#实验2古典密码图2-11破译密文采用以上猜测结果破译密文所获取的明文，具有意义，所以可以认定该次加密操作采用的加密变换函数为：y=9x+13 mod 26.3 .知识点(1) 模运算(带余除法)若a,b为两个整数，bz 0,则唯一存在两个整数q和r,使得下式成立a=bq+r, 0? rv|b|.模的定义如果a是一个整数，n是一个正整数，疋义a mod n为a除以n的余数a= n _a/n +(a mod n).例A: 113 mod 24=17 模算术运算由定义可知，运算(mod n)将所有的整数映射到集合 0,1, n-1,那么 在这个集合上进行的算术运算称为模

23、算术。模算术有如下的性质：(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.因此，普通算术的加、减、乘、除运算规则可以平移到模算术中。 Zn上模运算的性质：定义比n小的非负整数集合为Zn, Zn=0,1, , ,n-1,这个集合称为剩余类集，或模n的剩余类。更确切的说，Zn中的每个整数代表一个剩余类，我们可以将模 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, , 在剩余类的所有整数中，我们通常用最小非负整数来代表这个剩余类。寻找与k模同余(指的是两个数对同一个数求模结果相同，例如：整数 a和b对整数 n求模结果相同，我们就说 a和b模n同余，记为a= b (mod n)的最小非负整 数的过程，称为模n的k约化。如果我们在Zn中进行模运算，该运算具有如下性质： 交换律:(w+x) mod n=(x+w) mod

25、n(w x x) mod n=(x x w) mod n结合律:(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):对于Zn中的任意 w,存在一个 乙使得w+z= 0 mod n.注意：一般来说，在 Zn中，一个整数与n互素，那么在 Zn中有它的一个乘法逆元，使得该整数与其逆元相乘模n为1这里的互素指的是两个数的最大公约数为1.例3

26、:在Z 8中，整数1，3，5，7有一个乘法逆元，而 2，4和6没有。特别提醒：我们密码学中用到的运算均为模运算，对于古典密码体制来说，用 到的运算均为 Z 26上的模运算。(2)乘法逆元在仿射加密法中，我们是通过仿射函数变换来实现加密的，其加密变换函数一般表示为：ek(x)=ax+b mod 26,那么该函数的逆函数(也就是相应的解密函数)为：dk( y)=1/a(y-b) mod 26正如上面所述在密码学中，我们提及的运算一般是模运算，这里指的是Z26上的运算。在模运算中，将1/a表示为：a-1,称作a的乘法逆元，由乘法逆元性质可知：aa-1 =1 mod 26.由于在Z26中并不是所有的整

27、数都有乘法逆元，事实上，只有1，3，5，乙9，11，15，17，19，21，23，25才有乘法逆元，也就是说只有当加密变换函数中的a取上面这些值时，其才是可逆的，才能实现解密。另外，某个整数集上相关元素的乘法逆元的求解一般采用欧几里德扩展算法来实现(放在后续课程中讲解)，这里直接给出Z26上相关整数的乘法逆元，以便参考：-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 常见问题解答(1)密码学研究的主要问题是什么?解答：密码学的基本目的是在通信双方之间应用不安全的信道进行通信时，设法保 证通信安全。