密码学经典多图加密法

Slide Title,广东警官学院 计算机系,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,经典多图加密法,1,内容纲要,Playfair,加密法,Hill,加密法,多图加密法概念,2,定义,复习加密类型,单码加密,:,每个明文字母被映射到一个密文字母（一旦密钥确定，则每个明文字母只能由一个确定的密文字母代替）,多码加密,:,（一旦密钥确定，则每个明文字母可以由多个密文字母代替）,多图加密就是一次加密多个明文字母,即一个明文字母组由一个密文字母组一次加密（或者说由多个密文字母代替该明文字母组）,3,连体字加密,例如,一个连体字母（两个字母）密码可以代替明文中的一对字母,“,at”,由 “,ui”,替换,“,ai”,可以由 “,nj”,替换,这是一个很强大的加密方法，因为连体字母比单个字母多很多,在英语中只有,26,个字母，但是有,676 (26 x 26),种可能的连体字母,使用单字母的频率分析是无效的,注意到字母,a,由两字母代替,4,Playfair,加密,Playfair Cipher,是,Charles Wheatstone,（惠斯通）在,1854,左右开发的,但是这个加密方法是以他的朋友,Baron Playfair,的名字来命名的。,Playfair,是一种多图加密方法，它使得单字母频率分析完全失效 。,它的密钥是,5 x 5,的字母矩阵,(j,被i代替，或不被使用,),，该矩阵是由一个关键词来确定的。,例如,关键词是,harpsicord,则矩阵是,:,P,R,A,H,S,D,O,C,I,B,K,G,F,E,L,T,Q,N,M,U,Y,X,W,V,Z,注意,:,harpsicord,第2个R,舍弃。,5,Playfair,规则,整个文章需要预处理,1，,j,由,i,代替,2，用一个无效的字母插放到两个重复的字母之间，如：,q,放到两个 “,tt”,之间，变为“,tqt”,。,3，如果明文只有奇数个字母,用一个无效的字母放在最后。（无效字母需要通信双方约定，一般是极少出现的字母）,密文是根据明文对,(m,1,and m,2,),来确定的,如果,m,1,and m,2,位于密钥矩阵的同一行,他们分别由他们各自右边的字母代替,如果,m,1,and m,2,在同一列，那么它们由他们各自下方的字母代替,如果,m,1,and m,2,位于不同的行或列，则它们由它们构成的矩形同行顶点字母代替。,6,规则1,使用关键词 “,software”,来构造密钥矩阵：,明文字母对,: “RE”,变成 “,EB”,注意,:,同行字母是首尾相连并循环的，所以“,LQ”,变成 “,ML”,，,T,F,O,S,W,B,E,R,A,C,I,H,G,D,K,P,N,M,L,Q,Y,X,V,U,Z,Q,E,R,L,E,B,L,M,7,规则2,使用关键词 “,software”,来构造密钥矩阵：,明文对“,AL”,变成“,DU”,注意,:,同行字母是首尾相连并循环的，所以“,TY”,变成 “,BT”,T,F,O,S,W,B,E,R,A,C,I,H,G,D,K,P,N,M,L,Q,Y,X,V,U,Z,A,L,T,U,D,Y,B,T,8,规则3,使用关键词 “,software”,来构造密钥矩阵：,字母对 “,OP”,形成了一个虚构的矩形：所以它们被替换为“,TM”,T,F,O,S,W,B,E,R,A,C,I,H,G,D,K,P,N,M,L,Q,Y,X,V,U,Z,P,O,T,M,9,注意,Playfair,是历史上首次使用连体字母一次性加密成两个字母 ， 所以结果依靠字母对,因此,Playfair,方法消除了单个字母的（频率）特征,此外,这种连体加密使得可供频率分析的参考元素减少一半,(100 letter text has only 50 digraphs),可能的连体字母组的数目比单个字母的频率要大的多，其语言特征通过更多的元素得以分散,很少人知道它的使用，但英国战争办公室在布尔战争用过它,10,Playfair in CAP,playfair在CAP 中的实现:,11,辨认,Playfair,Playfair,密文有几个特征，这些特征能够帮助我们辨认该加密系统是否是,Playfair,加密系统,由于,Playfair,加密系统,是一个替换加密,因此稀有（,j, k, q, x, and z,）字母会出现的频率比较它们在明文中出现的频率高,密文有偶数个字母,当密文被分成两个一组时，重复出现的字母,SS, EE, MM, . . .,就不会出现,.,12,CAP Feature,CAP will help in the process of identifying a Playfair (or other polygraphic) system,Select,PolyID,13,Playfair,加密法特征1,明文中的每个字母在密文中都不会用其自己来表示，也就是说明文字母“,A”,不可能用密文字母“,A”,来表示；,明文中两个倒置的双图（如“,ER”,和“,RE”,）在密文中也是用倒置的双图来表示的；,明文中的每个字母只能用某,5,个字母中的一个来加密，这,5,个字母包括在方格中位于该字母下方的字母和与其同行的其他,4,个字母之一。,14,Playfair,加密特征,2,其他的特征包括,:,任何一对字母：位于矩形顶点的字母出现的可能性是同行或同列字母的两倍,任何已知字母都不能表示它的斜对角的字母,当一个密文字母已经确定是某个明文字母的替代，那么它有,20%,的机会在明文中代替该明文字母,15,寻找可能的单词法,考虑下面由,Playfair,方法加密的密文,:,pk km km ew dw qn bs hl uf gq zk zp tl fc ls fq tn ca,zw ae ns fq tn zw ps el kz kc xc rb ke tm wg co ab fk,vn cl uf ui df ch hq kc mp,假设明文短语“,a,sample of,”,在密文中,16,攻击过程,关于Playfair加密的已知明文攻击法的一般过程包括如下步骤：,找到一个,匹配模式,构造可能,的方阵,融合这些,可能的方阵,失败,构造有效,的方阵,失败,succeed,已经完善,的方阵,17,步骤1,对密文进行单个和连体字母的频率分析后，通过对照明文和密文寻找可能的排列,一个可能的排列是指不违反任何一条已知的 Playfair方阵的特征,Known:,Ciphertext:,ah ty cv vg ui no pq,te st a,t es ta,te st a,18,例子,在下面的例子中进行如下尝试:,as am pl eo f-,不是有效的匹配：,1. km,不能映射到两不同的字母对,2.,不管是字母,m,还是字母,e,都不能映射到自己,pk km km ew dw qn bs hl uf gq zk zp tl fc ls fq tn ca,zw ae ns fq tn zw ps el kz kc xc rb ke tm wg co ab fk,vn cl uf ui df ch hq kc mp,19,例子,(,续,),After two slides, the matchings are:,pk km km ew dw qn bs hl uf gq zk zp tl fc ls fq tn ca,zw ae ns fq tn zw ps el kz kc xc rb ke tm wg co ab fk,vn cl uf ui df ch hq kc mp,as am pl eo f-,Will not work because,1. km,不能映射到两不同的字母对,2. m,不能映射到它自己,20,继续尝试,移动4个字母后:,pk km km ew dw qn bs hl uf gq zk zp tl fc ls fq tn ca,zw ae ns fq tn zw ps el kz kc xc rb ke tm wg co ab fk,vn cl uf ui df ch hq kc mp,as am pl eo f-,结果,: 4,可能的字母对,as km,am ew,pl dw,eo - qn,这是个有效的匹配，因为这里没有违反任何一个,Playfair,规则,21,步骤2,可能的方阵,每种可能的字母对都代表,Playfair,方阵的一种状态,as km,am ew,pl dw,eo - qn,1,as = KM,2,am = EW,3,pl = DW,4,eo = QN,最后这里还是没有解决问题, 所以返回到第一步,W,M,E,A,E,M,A,W,E,W,M,M,S,K,A,K,S,A,M,K,M,S,W,L,D,P,D,L,P,W,D,W,L,N,O,Q,E,Q,O,E,N,Q,N,O,22,重复步骤1,重复步骤1 ，向右移动2个字母寻找匹配:,pk km km ew dw qn bs hl uf gq zk zp tl fc ls fq tn ca,zw ae ns fq tn zw ps el kz kc xc rb ke tm wg co ab fk,vn cl uf ui df ch hq kc mp,as am pl eo f-,这也是一个可能的匹配,结果,: 4,组可能的字母对,as ew,am dw,pl qn,eo - bs,23,重复步骤2,Each of the possible pairings represents a state of the Playfair square,as ew,am dw,pl qn,eo - bs,我们可以得出:,方格1要求：“a”和“e”必须在同一行或者同一列；,方格2要求：“a”和“d”必须在同一行或者同一列；,方格4要求：“e”和“b”必须在同一行或者同一列。,W,M,D,A,D,M,A,W,D,M,W,W,S,E,A,E,S,A,W,E,W,S,N,L,Q,P,Q,L,P,N,Q,N,L,S,O,B,E,B,O,E,S,B,S,O,1,as = EW,4,eo = BS,2,am = DW,3,pl = QN,24,步骤3,理由,1,除关键词以外，字母表中的其他字母是按顺序出现在方格中的。,有可能,A,B,C,D,E,不是关键词中的字母，所以它们形成了方阵的第2行,从这里可以推测关键词是5个字母的长度,D,C,B,A,E,W,D,C,B,A,E,A,与,W,应该在,同行或同列,25,步骤3,理由,2,继续应用需要的条件,:,M,W,S,D,C,B,A,E,W,D,C,B,A,E,E,与,S,应该在,同行或同列,W,S,D,C,B,A,E,D,与,M,应该在,同行或同列,M,O,W,S,D,C,B,A,E,M,R,O,W,S,D,C,B,A,E,I,H,G,F,K,Q,P,N,L,T,Y,X,V,U,Z,猜测可能的单词,?,因为这里满足所有其他条件，同时它也是一个好的,候选密钥方阵,B,与,O,应该在,同行或同列,26,Using CAP 1,CAP provides some basic tools for breaking playfair,Including a known word search,27,Using CAP 2,CAP also provides a simple Playfair worksheet,28,希尔加密,另一种多图加密方法是由数学家,Lester Hill,在,1929,开发的,-,称之为,Hill Cipher,的加密方法,它用,m,个密文字母代替,m,个连续的明文字母,29,希尔加密过程,每个字母都由一个数字代替,a = 0, b = 1, . . ., z = 25,当,m,= 3,时：明文,p,1,p,2,p,3,转换到密文,c,1,c,2,c,3,是由下面,3,个方程确定,:,c,1,= (k,11,p,1,+ k,12,p,2,+ k,13,p,3,) mod 26,c,2,= (k,21,p,1,+ k,22,p,2,+ k,23,p,3,) mod 26,c,3,= (k,31,p,1,+ k,32,p,2,+ k,33,p,3,) mod 26,红色字母,K密钥,30,M =,( ),17 17 5,21 18 21,2 2 19,希尔矩阵,希尔加密法是一个实矩阵乘法加密系统,加密密钥是个,n x n,矩阵,M,解密密钥是,M,-1,例如,当,n = 3,一个可能的密钥是,:,4 9 15,15 17 6,24 0 17,M,-1,=,( ),加密 ,n o w,13 14 22,(,17 17 5,21 18 21,2 2 19,(,) = ( ),mod 26,),13,14,22,23,20,4,x u e,31,破解希尔加密法,希尔加密法是一种 对唯密文攻击具有很高的抵抗性能的加密方法,.,事实上,矩阵越大，这种抵抗性越强,但是它很容易被已知明文攻击法破解,.,这个破解的方法类似于仿射加密法的破解，利用明文和密文组构成一个方程组系统，然后解出密钥矩阵,.,32,理论,密文矩阵式由明文矩阵乘以密钥矩阵得到的:,因此, 如果我们知道明文矩阵的逆矩阵，就可以算出密钥矩阵 :,C = MK,K = M,-1,C,过程,:,求出已知明文的逆矩阵,乘以明文所对应的密文矩阵，然后再验证这个结果是不是密钥矩阵,33,例子,Eve截获了如下密文:,209 37 59 255 110 196 247 90 52 34 1 68,11 130 43 23 20 26 219 119 93 164 12 63,110 202 124 137 112 158 232 23 127 118 128 123,115 89 62 224 199 10 199 142 104 242 120 4,142 26 230 159 129 164 133 153 31 256 210 62,她怀疑密文中有以下单词,:,“she can not attack us”,34,Plaintext Matrix,Eve 把已知明文转换成数字 (using ASCII representation for the characters which assigns a number between 0 and 255),计算得到逆矩阵是,:,35,寻找验证,Eve,继续用这个矩阵乘以密文矩阵,这样得到的每个结果都是一个解密的密钥,.,尝试了很多次，都不是所有的密钥,最后,Eve,发现了密钥,:,36,Using CAP,Breaking a Hill cipher by hand is very time consuming however CAP will automate the process,Enter your bestguess for the size,Enter a possibleplaintext segment,Try the possiblekeys until one works,37,Summary,多图加密法的概念,Playfair加密法,Hill加密法,38,