第2讲 古典密码

第二讲古典加密方法授课：伍前红[e-mail],辅导：周红亮[e-mail]3古典加密方法3.1置换法3.2简单代换密码3.3同音代换密码3.4多表代换密码3.5多字母组代换密码3.1置换法置换法：只改变明文字母位置。按照一定的方法来重新排列字符，通常是借助于某种几何图表来实现。加密过程分为两个步骤：将明文按照一定的路径写入图表中；以某种路径从图表中取出字符构成密文。明文写入图表密文取出图例：例1设明文DATASECURITY写入一个3×4的矩阵：1234DATASECURITY若按照2－4－1－3的顺序将各列写出，则密文为:AEIAUYDSRTCT。周期置换密码周期置换密码：以一定的周期来变换明文字符。令Zd为从1到d的整数集合，f：Zd→Zd为Zd上的一个排列，密码的密钥由k＝(d，f)给出。连续的d个字符由f来加密。因此，明文信息：M＝m1…mdmd+1…m2d…被加密成密文为：Ek(M)＝mf(1)…mf(d)md+f(1)…md+f(d)…解密为其逆操作。与列置换密码相比，周期置换密码用计算机实现时效率更高。例2设d＝4，f为i:1234f(i):2413则第1个明文字母在密文中被移到第3个位置，而第2个明文字母被移到第一个位置，依此类推。明文DATASECURITY被加密为M=DATASECURITYEk(M)=AADTEUSCIYRT置换密码的破译置换密码中，密文中字母出现的频率与明文中字母出现的频率相同，所以密码员可以很容易的由此来判别置换密码。这种密码可以通过移动字母顺序的方法来破译。还可以参考双字母和三字母组合的出现频率分布。ABCDEFGHIJKLMNOPQRSTUVWXYZA.---..-.-..+-*.-.++*.-....B...-...-.-.......-C+...+..++.....+..-.--..D-...+...+.....-...---....E+-++---.-..++*-+.**+.---..F-...--..-.....+....-....G-...-...-.......-.-....H+...*...-....-.........I-.+-+--...--*+..-++-...J.......K...-................L-..-+...-..+..-...--...-M+...+...-.-.-+.-.....N-.+++-+.-.....+...+*....O----.+-....-+*--.+--+--...P-..-..-...-..--+.--..Q-R+.--*...+...-.+...++...-.S+.+.+-.-+...-.+-..-*-.--T+...*..**.....+..-+--.--U-.-.-.....-.-..---...V.+-.....W-...-.--.....-.......X..........-.....Y-.......-.....--..--.....Z.....双字母出现频率最大值为2.31%符号:*高频:大于1.15%+中频:大于0.46%-低频:大于0.12%.稀少:大于0.00%空格:未出现图3.1双字母组出现频率分布对于周期为d的置换密码，这d个字母共有d!种可能组合。假设所有的密钥出现的机会相等，则密钥的熵为H(K)=log2d!,使用Sterling的对d!的估计法，确定性距离：dlog2(d/e)3.2u=0.3dlog2(d/e)令D=3.2位/字母，设d=27，则d/e10，log2(d/e)3.2，因此，u27。3.2简单代换密码有四种代换密码：1.简单代换密码2.同音代换密码3.多表代换密码4.多字母代换密码简单代换密码：明文字母表中的每个字母用密文字母表中相应的字母来代换，位置不变。3.2.1简单代换密码的描述令A为n个字母的字母表{a0，a1，…，an-1}，则C为n个字母的字母表{f(a0)，f(a1)，…，f(an-1)}，其中f：A→C为从A中的每个字母到C中的相应字母的一对一映射。密码的密钥由C给出，或者说，由函数f给出。若明文信息为：M=m1，m2，…，则密文为：Ek(M)=f(m1)f(m2)…例3：查表法设f从标准的英语字母表A={A，B，C，…，Z}映射到如下的密文字母表C：A：ABCDEFGHIJKLMNOPQRSTUVWXYZC：HARPSICODBEFGJKLMNQTUVWXYZ则明文INTELLIGENT被加密为：M=INTELLIGENTEk(M)=？例3：查表法设f从标准的英语字母表A={A，B，C，…，Z}映射到如下的密文字母表C：A：ABCDEFGHIJKLMNOPQRSTUVWXYZC：HARPSICODBEFGJKLMNQTUVWXYZ则明文INTELLIGENT被加密为：M=INTELLIGENTEk(M)=DJTSFFDCSJT3.2.1简单代换密码的描述恺撒密码：基于移位字母表（有时也成为直接标准字母表）的密码，将字母表的字母右移K个位置，并对字母表长度做模运算，形式为：f(a)=(a+k)modnC语言的实现方式c=((a-’A’)+k)%26)+’A’;令k=3，n=26，明文：M=Message，则密文为：Phvvdjh基于标准字母表乘法的密码：f(a)=a·kmodn，其中k和n为互素的。3.2.1简单代换密码的描述基于仿射变换的密码：f(a)=(ak1+k0)modn其中：k1和n是互素的。利用t阶多项式变换可以生成高阶的变换。恺撒密码是0阶多项式变换，而仿射变换是一阶多项式变换。有些代换密码使用非标准的密文字母表，如兽栏密码。3.2.2单字母频率分析简单代换密码可能很容易的通过使用单字母频率分析法的只有密文的攻击来破译。基于移位字母表的密码通常易于破译，因为每个密文字母与相应的明文字母的差为一个常数。基于仿射变换的密码：求解联立方程组已知t个对应的明文字母mi和密文字母ci(1it)，则(m1k1+k0)modn=c1…(mtk1+k0)modn=ct例：明文：F(5),I(8)和L(11),对应的密文为：M(12),S(18)和Y(24)。(5k1+k0)mod26=12(1)(8k1+k0)mod26=18(2)(11k1+k0)mod26=24(3)(2)-(1)得：3k1mod26=6解得：k1=6*3-1mod26=6*9mod26=2代入(1)，得：k0=2字母期望值实际值%A8.07.5***************B1.51.4***C3.04.1********D4.03.2******E13.012.7*************************F2.02.3****G1.51.9****H6.03.8********I6.57.7***************J0.50.2K0.50.4*L3.53.8********M3.03.0******N7.07.0**************O8.07.5***************P2.03.0******Q0.20.2R6.56.7*************S6.07.3***************T9.09.2******************U3.02.8******V1.01.0**W1.51.4***X0.50.3*Y2.01.6***Z0.20.1每个*代表0.5%字母总数为:67375图3.3单字母频率分布图3.4以频率划分的字母高频:ETAONIRSH中频:DLUCM低频:PFYWGBV稀少:JKQXZ3.3同音代换密码：一个明文字母对应多个密文符号同音代换密码：将明文字母表中的每个字母a映射到一系列密文字母f(a)，这些f(a)称为同音字母。这样，一个明文信息M=m1m2…被加密为C=c1c2…,其中ci是从f(mi)的集合中随机选取的。因为密文符号的相关分布会近似于平的，可以挫败频率分析，所以同音代换密码比简单代换密码难破译得多。字母同音字母A1719344156606783I082253658890L034476N02091527324059O0111232842547080P3391T051020294558647899M=PLAINPILOTC=91445665593308762878Beale密码C=115732481837524917316265722715…M=Ihavedeposited…(1)When,inthecourseofhumanevents,itbecomesnecessary(11)Foronepeopletodissolvethepoliticalbandswhichhave(21)Connectedthemwithanother,andtoassumeamongthePowers(31)Oftheearththeseparateandequalstationtowhich(41)TheLawsofNatureandofNature’sGodentitlethem,(51)Adecentrespecttotheopinionsofmankindrequiresthat(61)Theyshoulddeclarethecauseswhichimpelthemtothe(71)separation.Weholdthesetruthstobeself-evident,that(81)Allmenarecreatedequal,thattheyareendowedby(91)TheirCreatorwithcertainunalienablerights,thatamong(99)TheseareLife,Liberty,andthepursuitofHappiness.高阶同音代换密码EILMSEILMS10221802111201250520190623130703160824151709211404M=SMILEX=LIMESC=21160519113.4多表代换密码多表代换密码：使用从明文字母到密文字母的多个映射，每个映射是像简单代换密码中的一对一映射。基于周期d的周期代换密码：给定d个密文字母表C1,…Cd，令fi：A→Ci为从明文字母表A到密文字母表Ci（1id）的映射，对明文信息：M＝m1…mdmd+1…m2d…加密，有：Ek(M)＝f1(m1)…fd(md)f1(md+1)…fd(m2d)…当d＝1时，密码为单表代换密码等价与简单代换密码。3.4.1Vigenère和Beaufort密码Vigenère密码是一种基于移位字母表的周期代换密码，它的密钥K由一个字母序列来指定：k＝k1…kd。其中：ki（i＝1，…，d）给出了第i个字母表的移动位数，即fi(a)＝(a+ki)modn.例如：明文INTELLIGENT用密钥PLAY加密为：M＝INTELLIGENTK＝PLAYPLAYPLAEk(M)＝XYTCAMIETYT使用Vigenère表可以方便地进行加密和解密。明文ABCDEFGHIJKLMNOPQRSTUVWXYZAABCDEFGHIJKLMNOPQRSTUVWXYZBBCDEFGHIJKLMNOPQRSTUVWXYZACCDEFGHIJKLMNOPQRSTUVWXYZABDDEFGHIJKLMNOPQRSTUVWXYZABCEEFGHIJKLMNOPQRSTUVWXYZABCDFFGHIJKLMNOPQRSTUVWXYZABCDEGGHIJKLMNOPQRSTUVWXYZABCDEFHHIJKLMNOPQRSTUVWXYZABCDEFGIIJKLMNOPQRSTUVWXYZABCDEFGHJJKLMNOPQRSTUVWXYZABCDEFGHIKKLMNOPQRSTUVWXYZABCDEFGHIJLL