5保障与安全密码学06

1、第三章 密码学（2） 传统密码技术 一、 数据表示方法数据的表示有多种形式，使用最多的是文字，还有图形、声音、图像等。这些信息在计算机系统中都是以某种编码的方式来存储的。 传统加密方法的主要应用对象是对文字信息进行加密解密。 古典加密技术两个基本组成部分：代替与变换 二、 代替密码代替密码（Substitution Cipher）在代替密码中,用一组密文字母来代替一组明文字母以隐藏明文,但保持明文字母的位置不变。 传统密码技术代替密码就是将明文字母表P中的每个字母用密文字母表C中的相应字母来代替这一类密码，包括移位密码、替换密码、仿射密码、乘数密码、多项式代替密码、密钥短语密码等。接收者对密文

2、进行逆替换就恢复出明文来。在经典密码学中，有四种类型的代替密码。简单代替密码（Simple Substitution Cipher) Caesar 多名码代替密码 多字母代替密码 多表代替密码Vigenre 。传统密码技术1单表代替密码 单表代替密码的一种典型方法是凯撒（Caesar）密码，又叫循环移位密码。它的加密方法就是把明文中所有字母都用它右边的第k个字母代替，并认为Z后边又是A。这种映射关系表示为如下函数：F(a)=(a+k) mod n其中：a表示明文字母；n为字符集中字母个数；k为密钥。 传统密码技术映射表中，明文字母中在字母表中的相应位置数为如A=0，B=1，具体形式如下：设k3

3、；对于明文PCOMPUTE SYSTEMS则f（C）=（2+3） mod 26=5=Ff（O）=（14+3）mod 26=17=Rf（M）=（12+3）mod 26=15=Pf（S）=（18+3） mod 26=21=V所以，密文C= Ek（P）=FRPSXRWHUVBVWHPV。 恺撒密码的特点单字母密码（简单替换技术）简单，便于记忆令26个字母分别对应于025，a=0，b=1y=24，z=25。缺点：结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构。已知加密与解密算法C=E(p)=(p+k)mod(26)p=D(C)=(C-k)mod(26)25个可能的密钥k,适用Brute

4、-Force Cryptanalysis明文所用的语言是已知的，且其意义易于识别 Caesar CipherCaesar 密码的数学表示 设：A the value 0, B 1, C 2, . Y 24, Z 25; 加密算法：Ek: i - i + k (mod 26) 解密算法： Dk: i - i - k (mod 26) 例1: plain: meet me after the toga partycipher: PHHW PH DIWHU WKH WRJD SDUWB1oggv og chvgt vjg vqic rctva2nffu nf bgufs uif uphb qbsuz

5、3meet me after the toga party4ldds ld zesdq sgd snfz ozqsx56789qiix qi ejxiv xli xske tevxcBrute-force cryptanalysis is easily performed:simply try all the 25possible keys.作业1：用C编制上述程序2多表代替密码 多表代替密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率分布，每个映射是简单代替密码中的一对一映射。维吉尼亚Vigenere 密码和博福特Beaufort 密码均是多表代替密码的例子。多表代替密码有多个单

6、字母密钥，每一个密钥被用来加密一个明文字母。第一个密钥加密明文的第一个字母，第二个密钥加密明文的第二个字母等，所有密钥使用完后密钥又再循环使用。密钥k可以通过周期性地延长反复进行以至无穷。Vigenere Cipher Table a b c d e f g h i j k l m n o p q r s t u v w x y za a b c d e f g h i j k l m n o p q r s t u v w x y zb 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 ac c d e f g h i j k l m n o

7、 p q r s t u v w x y z a bd d e f g h i j k l m n o p q r s t u v w x y z a b ce e f g h i j k l m n o p q r s t u v w x y z a b c df f g h i j k l m n o p q r s t u v w x y z a b c d e g g h i j k l m n o p q r s t u v w x y z a b c d e f h h i j k l m n o p q r s t u v w x y z a b c d e f g i i j

8、k l m n o p q r s t u v w x y z a b c d e f g h j j k l m n o p q r s t u v w x y z a b c d e f g h i k k l m n o p q r s t u v w x y z a b c d e f g h i j l l m n o p q r s t u v w x y z a b c d e f g h i j k m m n o p q r s t u v w x y z a b c d e f g h i j k l n n o p q r s t u v w x y z a b c d

9、e f g h i j k l m o o p q r s t u v w x y z a b c d e f g h i j k l m n p p q r s t u v w x y z a b c d e f g h i j k l m n o q q r s t u v w x y z a b c d e f g h i j k l m n o p r r s t u v w x y z a b c d e f g h i j k l m n o p q s s t u v w x y z a b c d e f g h i j k l m n o p q r t t u v w x

10、y z a b c d e f g h i j k l m n o p q r s u u v w x y z a b c d e f g h i j k l m n o p q r s t v v w x y z a b c d e f g h i j k l m n o p q r s t u w w x y z a b c d e f g h i j k l m n o p q r s t u v x x y z a b c d e f g h i j k l m n o p q r s t u v w y y z a b c d e f g h i j k l m n o p q r

11、s t u v w x z z a b c d e f g h i j k l m n o p q r s t u v w x y The table lists the keycharacters ontop and theplaintextcharacters onthe side 这种加密的加密表是以字母表移位为基础把26个英文字母进行循环移位，排列在一起，形成2626的方阵。该方阵被称为维吉尼亚表。采用的算法为f（a）=（a+Bi） mod n（i=（1，2，n）即一个明文字母可表示为多个密文字母。：例如：明文为System，密钥为dog，加密过程如下：明文：S y s t e m密钥

12、：d o g d o g密文：V my s在这个例子中，每三个字母中的第一、第二、第三个字母分别移动（mod 26）3个，14个和6个位置。第四章 传统密码学设密钥k=k1k2kn，明文M=m1m2mn，加密变换Ek(M)=c1c2cn。其中ci( mi + ki) mod 26，i=1,2n。优点：能抵抗简单的字母频率分析攻击。多表密码加密算法结果将使得对单表置换用的简单频率分析方法失效。例 设密钥k =cipher，明文消息appliedcryptosystem， 试用维吉尼亚密码对其进行加密，然后再进行解密。解：由密钥k=cipher，得n=6，密钥对应的数字序列为 (2，8，15，7，

13、4，17)。然后将明文按每6个字母进行分组，并转换这些明文字母为相应的数字，再用模26加上对应密钥数字，其加密过程如下表 解密使用相同的密钥，但用模26的减法代替模26加法 密钥为cipher的维吉尼亚密码加密过程 密文为：cxesmvfkgftkqanzxvo。作业2：用C编制上述程序 a b c d e f g h i j k l m n o p q r s t u v w x y za a b c d e f g h i j k l m n o p q r s t u v w x y zb 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

14、 ac c d e f g h i j k l m n o p q r s t u v w x y z a bd d e f g h i j k l m n o p q r s t u v w x y z a b ce e f g h i j k l m n o p q r s t u v w x y z a b c df f g h i j k l m n o p q r s t u v w x y z a b c d e g g h i j k l m n o p q r s t u v w x y z a b c d e f h h i j k l m n o p q r s t u v

15、 w x y z a b c d e f g i i j k l m n o p q r s t u v w x y z a b c d e f g h j j k l m n o p q r s t u v w x y z a b c d e f g h i k k l m n o p q r s t u v w x y z a b c d e f g h i j l l m n o p q r s t u v w x y z a b c d e f g h i j k m m n o p q r s t u v w x y z a b c d e f g h i j k l n n o p

16、 q r s t u v w x y z a b c d e f g h i j k l m o o p q r s t u v w x y z a b c d e f g h i j k l m n p p q r s t u v w x y z a b c d e f g h i j k l m n o q q r s t u v w x y z a b c d e f g h i j k l m n o p r r s t u v w x y z a b c d e f g h i j k l m n o p q s s t u v w x y z a b c d e f g h i j

17、 k l m n o p q r t t u v w x y z a b c d e f g h i j k l m n o p q r s u u v w x y z a b c d e f g h i j k l m n o p q r s t v v w x y z a b c d e f g h i j k l m n o p q r s t u w w x y z a b c d e f g h i j k l m n o p q r s t u v x x y z a b c d e f g h i j k l m n o p q r s t u v w y y z a b c d

18、 e f g h i j k l m n o p q r s t u v w x z z a b c d e f g h i j k l m n o p q r s t u v w x y OperationA keyword is selected and it is repeatedly written above the plaintextEXAMPLE: using the keyword “hold”HOLDHOLDHOLDHOLDHOKEYplaintextI STHELPIATNXETSTHI a b c d e f g h i . . .a a b c d e f g h ib

19、 b c d e f g h i j . . .n c d e f g h i j k . . .d d e f g h i j k l . . .e e f g h i j k l m . . .f f g h i j k l m n . . .g g h i j k l m n o . . .h h i j k l m n o p . . .i i j k l m n o p q . . .j j k l m n o p q r . . . k k l m n o p q r s . . .l l m n o p q r s t . . .m m n o p q r s t u . . .

20、n n o p q r s t u v . . .o o p q r s t u v w . . .p p q r s t u v w x . . .q q r s t u v w x y . . .r r s t u v w x y z . . .s s t u v w x y z a . . .t t u v w x y z a b . . .u u v w x y z a b c . . .ACiphertextVTVHKEGQHEBQDWDLESelect Vigenere from the Ciphers MenuEnter akeyword传统密码技术3多名码代替密码（Homoph

21、onic Substitution）：它与简单代替密码相似，只是映射是一对多的，每个明文字母可以加密成多个密文字母。 例如， A可能对应于5、13、25 B可能对应于7、9、31、42当对字母的赋值个数与字母出现频率成比例时，安全性将有所提高。这是因为密文符号的相关分布会近似于平的，可以挫败频率分析。1401年Duchy Mantua公司就开始使用多名码代替密码，比简单代替密码难破译，但仍不能掩盖明文语言的所有统计特性，用已知明文攻击，较容易破解，但用唯密文攻击要困难一些。第四章 传统密码学多字母或多码代替密码 不同于前面介绍的代替密码都是每次加密一个明文字母，多字母代替密码将明文字符划分为长

22、度相同的消息单元，称为明文组，对字符块成组进行代替，这样一来使密码分析更加困难。多字母代替的优点是容易将字母的自然频度隐蔽或均匀化，从而有利于抗击统计分析。Playfair密码，Hill密码都是这一类型的密码4 多字母代替密码-Playfair （英国一战期间曾用）第四章 传统密码学密钥由25个英文字母（J与I相同）组成的5阶方阵。 每一对明文字母 m1和m2，都根据下面的6条规则进行加密。（1）明文字母 m1和m2同行。密文是其右边字母。（2）明文字母 m1和m2同列。密文是其下边字母。（3）明文字母 m1和m2不同行、不同列。密文是长方形的另两个顶点。（4）明文字母 m1和m2相同。在m1

23、和m2之间加一个无效字母。（5）明文有奇数个字母，末尾加一个无效字母。（6）I、J看成是相同字母。4 多字母或多码代替密码-Playfair （英国一战期间曾用）4 多字母代替密码-Playfair Playfair:将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。 密钥是55变换矩阵: I与J视为同一字符C I P H ER A B D FG K L M NO Q S T UV W X Y Z加密规则:按成对字母加密 相同对中的字母加分隔符(如x) balloon ba lx lo on 同行取右边: he EC 同列取下边: dm MT 其他取交叉: kt MQ

24、OD TRPlayfair举例以前面的55变换矩阵(cipher)为例 C I P H ER A B D FG K L M NO Q S T UV W X Y Z(1)balloon ba lx lo on(2)book bo ok(3)fill fi lx lxdb sp gs ugrs qgae sp spPlayfair密码分析Playfair有2626=676种字母对组合字符出现几率一定程度上被均匀化基于字母频率的攻击比较困难依然保留了相当的结构信息5 .仿射密码（affine cipher）体制仿射密码是代替密码的一个特例。在仿射密码中： 加密函数形式为 要求唯一解的充要条件是gcd

25、( a,26)=1 该体制描述为： 设P=C=Z/(26) 对 定义 ek(x)=ax+b (mod 26) 和dk(y)=a-1(y-b)(mod 26) 与26互素的数为1，3，5，7，9，11，15，17，19，21，23，25（12个）因此，模为26的仿射密码的密钥空间为1226=312在Z/(26)的情形下，与26互素的数的元的乘法逆为1-1=13-1 =9(39=27=26+1)5-1 =21(521=105=264+1)7-1 =15(715=105=264+1)11-1 =19(1119=209=268+1)17-1 =23(1723=391=2615+1)25-1 =25（6

26、25=2525=2624+1）例子 设k（7，3），注意到7-1(mod 26)=15,加密函数是ek(x)=7x+3,相应的解密函数是dk(y)=15(y-3)=15y-19 , 易见 dk(ek(x)=dk(7x+3)=15(7x+3)-19 =x+45-19 =x (mod 26) 若加密明文：hot ，首先转换字母h,o,t成为数字7,14,19,然后加密：解密：作业3:编程实现上述加解密过程。6 Hill密码（1929）Hill cipher was developed by the mathematician Lester Hill in 1929.基于矩阵的线性变换: K是一个m

27、m矩阵,在Z/(26)上可逆,即存在K-1使得:KK-1 = I (在Z/(26) 对每一个k K,定义ek(x)=xK (mod 26) 和 dk(y)=yK-1 (mod 26)注：明文与密文都是 m元的向量（x1, x2 , xm ); (y1, y2,ym)，定理 设K=(k i,j)为一个定义在zn上的mm矩阵。若K在zn上可逆，则有K-1 = (detK)-1 k*，这里k*为K矩阵的伴随矩阵。推论 设矩阵为一个定义在zn上的矩阵。Hill密码的例子-i例子：当 m=2时，明文元素x=(x1,x2),密文元素y=(y1,y2) K= 若对明文july加密，它分成2个元素（j,u),

28、(l,y),分别对应于（9,20）,（11,24）,有（9,20） (mod 26)=(9960,72140）(mod 26)=（3,4） 且（11,24 ） (12172,88168) （11,22）于是对 july加密的结果为DELW。(y1,y2)=(x1,x2)K这是因为 = mod26=Detk=53mod26=11-1=1Hill密码的例子-ii为了解密，计算 且 因此，得到了正确的明文“july”Hill密码分析完全隐藏了字符(对)的频率信息线性变换的安全性很脆弱，易被已知明文攻击击破。对于一个m m的hill密码，假定有m个明文-密文对，明文和密文的长度都是m.可以把明文和密文

29、对记为：Pj=(p1j,p2j,.pmj)和Cj=(C1j,C2j,Cmj), 对任意,1j m 定义m m的方阵X=（Pij) Y=(Cij),得到Y=XK，K=X-1Y例子：friday PQCFKU (5 17)K =(15 16) (8 3)K =(2 5) (0 24)K =(10 20)这个结果可对第三个明文对进行验证练习假设明文worker利用n=2的Hill密码加密，得到密文qihryb，求密钥K。 解：将明文、密文划分为三组： 明文 （w, o）、（r, k）、（e, r） （22,14）、 (17,10 ) 、 (4,17 ) 密文 （q, i） 、（h, r） 、（y,

30、b） （16, 8）、 (7,17 ) 、 (24,1 )作业4 通过编程求出密钥 对Hill密码的已知明文分析练习假设明文worker利用n=2的Hill密码加密，得到密文qihryb，求密钥K。 解： 利用前两个明文密文对，构造矩阵方程： 计算明文方阵行列式， 由于（18,26）1，即该矩阵没有逆元，于是考虑第二、第三组明文密文对，得到矩阵方程： 对Hill密码的已知明文分析 249mod26=15 ，15-1=7显然，通过对比第一个明文密文对很容易验证该密钥。 如果密码分析者不知道加密分组长度l的值，那么可以通过逐一尝试不同的l值来得到密钥。 Hill密码体制的重要性在于它无可辩驳地表明

31、数学方法在密码学中的地位是不容置疑的。对Hill密码的已知明文分析 显然，通过对比第一个明文密文对很容易验证该密钥。 如果密码分析者不知道加密分组长度l的值，那么可以通过逐一尝试不同的l值来得到密钥。 Hill密码体制的重要性在于它无可辩驳地表明数学方法在密码学中的地位是不容置疑的。对Hill密码的已知明文分析Hill ProcessEach character is assigned a numerical value a = 0, b = 1, . . ., z = 25for m = 3 the transformation of p1p2p3 to c1c2c3 is given by

32、 3 equations: c1 = (k11p1 + k12p2 + k13p3) mod 26 c2 = (k21p1 + k22p2 + k23p3) mod 26c3 = (k31p1 + k32p2 + k33p3) mod 26KEYHill MatrixThe Hill cipher is really a matrix multiplication systemThe enciphering key is an n x n matrix, MThe deciphering key is M-1For example, if n = 3 one possible key is:1

33、7 17 521 18 21 2 2 19M = ( ) 4 9 1515 17 624 0 17M-1 = ( )Encrypt n o w 13 14 22 (17 17 521 18 21 2 2 19() = ( ) mod 26 u eFirst, enter the group size which is the same as the matrix size转轮机 上个世纪20年代，出现了转轮密码，而由德国发明家亚瑟谢尔比乌斯发明的Enigma 密码机最为著名。它主要由经电线相连的键盘、转子和显示器组成，转子本身也集成了26条线路（在下图中显示了6条），

34、把键盘的信号对应到显示器不同的小灯上去。在图中可以看到，如果按下a键，那么灯B就会亮，这意味着a被加密成了B。同样地我们看到，b被加密成了A，c被加密成了D，d被加密成了F，e被加密成了E，f被加密成了C。于是如果我们在键盘上依次键入cafe（咖啡），显示器上就会依次显示DBCE，这是最简单的加密方法之一简单代替密码。转轮机转轮机不仅仅如此，因为当键盘上一个键被按下时，相应的密文在显示器上显示，然后转子的方向就自动地转动一个字母的位置（在图中就是转动1/6圈，而在实际中转动1/26圈）。右图表示了连续键入3个b的情况。转轮机当第一次键入b时，信号通过转子中的连线，灯A亮起来，放开键后，转子转动

35、一格，各字母所对应的密码就改变了；第二次键入b时，它所对应的字母就变成了C；同样地，第三次键入b时，灯E闪亮。为使机器更安全，可以把几种转轮和移动的齿轮结合起来。因为所有转轮以不同的速度移动，n个转轮的机器的周期是26n。为进一步阻止密码分析，有些转轮机在每个转轮上还有不同的位置号。转轮机德国人为了战时使用，大大加强了其基本设计，军用的Enigma由3个转轮，从5个转轮中选取。转轮机中还有一块稍微改名明文序列的插板，有一个反射器导致每个转轮对每一个明文字母操作两次，结构如图所示。转轮机 于是转子自身的初始方向，转子之间的相互位置，以及连接板连线的状况就组成了所有可能的密钥：三个转子不同的方向组

36、成了26*26*26=17576种不同可能性；三个转子间不同的相对位置为6种可能性；连接板上两两交换6对字母的可能性数目非常巨大，有1种；于是一共有17576*6*1，大约为100000，即一亿亿种可能性。 但如此复杂的密码机在第二次世界大战中被破解了，首先是波兰人利用德军电报中前几个字母的重复出现，破解了早期的Enigma密码机，而后又将破译的方法告诉了法国人和英国人。英国人在计算机理论之父图灵的带领下，通过寻找德国人在密钥选择上的失误，并成功夺取德军的部分密码本，获得密钥，以及进行选择明文攻击等等手段，破解出相当多非常重要的德军情报。一次一密乱码本 如上所述的所有密码算法均被破解，那么是否

37、存在无法破解的理想加密方案呢？香农证明了一种密码属于这种情况，它就是一次一密乱码本（one-time pad）。一般说来，一次一密乱码本就是一个大的不重复的真随机密钥字母集，发送者用乱码本中的每一个密钥准确地加密一个明文字符，加密是明文字符和密钥字符进行模26加法。比如：明文：onetimepad密钥：TBFRGFARFM密文：IPKLPSFHGQ因为：O+Tmod26=I，N+Bmod26=P，E+Fmod26=K，如果窃听者不能得到用来加密的一次一密乱码本，这个方案就是完全保密的。给出的密文消息相当于同样长度的任何可能的明文消息。代替密码的特点单字母代替密码（Monoalphabetic Cipher) ：明文中字母的出现频度、重复字母的模式和字母相互之间的结合模式等统计特性不变，安全性差。多码代替密码 ：没有隐藏明文中不同字母的统计特性 ，但安全性有所提高。多字母代替密码 ：字符块被成组加密 ，有利于抗击统计分析。多表代替密码 ：有多个映射表，可隐藏单字母出现的频率分布。传统