Section 2.1 Summary of Classical Cryptography
Section 2.1 Summary of Classical Cryptography
本讲主要内容 。置换密码(列置换密码和周期置换密码) 。代换密码(单表代换密码、多表代换密码和维尔姆密 码) 。典型传统密码的分析(统计分析法和明文-密文对分 析法) CNR@HEU http://machunguang.hrbeu.edu.cn
本讲主要内容 置换密码(列置换密码和周期置换密码) 代换密码(单表代换密码、多表代换密码和维尔姆密 码) 典型传统密码的分析(统计分析法和明文-密文对分 析法) 3
简介 。在1949年Claude Shannon发表“保密系统的通信理论” 之前,密码学算法主要通过字符间的置换和代换实现,一 般认为这些密码体制属于传统密码范畴。 。传统密码体制是指那些比较简单的、大多数采用手工或机 械操作对明文进行加密、对密文进行解密的密码体制(对 称),其安全性绝大多数与加解密算法保密性密切相关。 。传统密码体制的技术、思想以及破译方法虽然很简单,但 是反映了密码设计和破译的思想,是学习密码学的基本入 口,对于理解、设计和分析现代密码仍然具有借鉴的价值。 CNR@HEU http://machunguang.hrbeu.edu.cn
简介 在1949年Claude Shannon Claude Shannon发表“保密系统的通信理论 保密系统的通信理论” 之前,密码学算法主要通过字符间的置换和代换实现,一 般认为这些密码体制属于传统密码范畴。 传统密码体制是指那些比较简单的、大多数采用手工或机 械操作对明文进行加密、对密文进行解密的密码体制 械操作对明文进行加密、对密文进行解密的密码体制(对 称), 其安全性绝大多数与 其安全性绝大多数与加解密算法保密性 加解密算法保密性密切相关。 传统密码体制的 传统密码体制的技术、思想以及破译方法虽然很简单,但 技术、思想以及破译方法虽然很简单,但 是反映了密 破的想 码设计和破译的思想,是学习 密 学的 码 基本入 口,对于理解、设计和分析现代密码仍然具有借鉴的价值。 4
置换密码 置换密码(Permutation Cipher)又叫换位密码(Transposi- tion Cipher),它根据一定的规则重新排列明文,以便打 破明文的结构特性。置换密码的特点是保持明文的所有字 符不变,只是利用置换打乱了明文字符的位置和次序。 。最常见的置换密码有二种: 列置换密码(明文遵照密钥的规程按列换位并且按列读出 序列得到密文): 周期置换密码(将明文P按固定长度分组,然后对每组 按1,2,…,m的某个置换重排位置从而得到密文C); 5 CNR@HEU http://machunguang.hrbeu.edu.cn
置换密码 置换密码(P t ti Ci h ) (Permutation Cipher)又叫换位密码(T i ransposi - tion Cipher) Cipher),它根据一定的规则重新排列明文,以便打 破明文的结构特性。置换密码的特点是保持明文的所有字 符不变,只是利用置换打乱了明文字符的位置和次序。 最常见的置换密码有二种: 列置换密码(明文遵照密钥的规程按列换位并且按列读出 序列得到密文 ); 周期置换密码(将明文P按固定长度m分组,然后对每组 按 的某个置换重排位置从而得到密文 1,2, ", m 的某个置换重排位置从而得到密文C) ; 5 , , , ) ;
列置换密码(加密) 将明文P以设定的固定分组宽度m按行写出,即每行有m个 字符。若明文长度不是的整数倍,则不足部分用双方约定 的方式填充,如双方约定用空格代替空缺处字符,不妨设 最后得字符矩阵[M]mxm 。按1,2,…,m的某一置换o交换列的位置次序得字符矩 阵[Mp]nxn; 。把矩阵[Mp]mxn按列1,2,,n的顺序依次读出得密文序 列C; 6 CNR@HEU http://machunguang.hrbeu.edu.cn
列置换密码(加密) 将明文P以设定的固定分组宽度 以设定的固定分组宽度m按行写出,即每行有m个 字符。若明文长度不是m的整数倍,则不足部分用双方约定 的方式填充,如双方约定用空格代替空缺处字符,不妨设 最后得字符矩阵 最后得字符矩阵 [M ] ; 按 的某一置换 交换列的位置次序得字符矩 [ ] M m×n 1,2,", m σ 阵 ; 把矩阵 按列 的顺序依次读出得密文序 [ ] MP m×n 把矩阵 [M ] 按列1 2 n 的顺序依次读出得密文序 列C; [ ] M P m×n 1,2,", n 6
列置换密码(解密) 。将密文C按与加密过程相同的分组宽度按列写得到字符 矩阵[Mplxn。 。按加密过程用的置换的逆置换σ1交换列的位置次序得 字符矩阵[M]mxn。 。把矩阵[M]xn按1,2,…,m行的顺序依次读出得明文P。 CNR@HEU http://machunguang.hrbeu.edu.cn
列置换密码(解密) 将密文C按与加密过程相同的分组宽度m按列写得到字符 矩阵 。 [ ] MP m×n 。 按加密过程用的置换 按加密过程用的置换 的逆置换 交换列的位置次序得 交换列的位置次序得 字符矩阵 σ −1 σ 字符矩阵 [M ] 。 把矩阵 按 行的顺序依次读出得明文P [ ] M m×n 把矩阵 [M ]m×n 按 1,2, " , m 行的顺序依次读出得明文P。 7
列置换密码加密(举例) e设明文P为“Beijing2008 Olympic Games”, 密钥σ=(143)(56),则加密过程为: i 82008O 020g08 46 1 y m p i c m y pl c i G a me s m a e G S 8 CNR@HEU http://machunguang.hrbeu.edu.cn
列置换密码加密(举例) 设明文P为“Beijing 2008 Olympic Games”, 密钥 σ = (1 4 3)( 5 6 ) ,则加密过程为: ⎡ ⎤ ⎡ ⎤ [ ] [ ] ⎥⎥⎤ ⎢⎢⎡ ⎥⎥⎤ ⎢⎢⎡ g O i e J B n i g O B e i J i n 2 0 0 8 σ 0 2 0 8 [ ] [ ] ⎥⎥⎥ ⎢⎢ ⇒ =⎢ ⎥⎥⎥ ⎢⎢ =⎢ × × m y p l c i g O M l y m p i c g O M P 2 0 0 8 0 2 0 8 4 6 4 6 ⎥⎦ ⎢⎣ ⎥⎦ ⎢⎣G a m e s m a e G s 8
列置换密码解密(举例) 。由矩阵 年[Mp]46得到密文C为“i0mme2yaJ0 peBgIGnOc i8is”. 根据加密密钥逆置换σ=(134)56),则解密过程如下: i e JBni Be iJin 02 )808 ay pl c i =46 820080 m ym p i c m a e Ga m e s 9 CNR@HEU http://machunguang.hrbeu.edu.cn
列置换密码解密(举例) 由矩阵 得到密文 [ ] 得到密文C为“i0mme2yaJ0peBglGnOc i8is”。 根据加密密钥逆置换 则解密过程如下 [ ] MP 4×6 (13 4)(5 6) 1 = − 根据加密密钥逆置换σ = (13 4)(5 6),则解密过程如下: ⎥⎤ ⎢⎡ ⎥⎤ ⎢⎡ − O B e i J i n O i e J B n i 0 2 0 8 2 0 0 8 1 σ [ ] [ ] ⎥⎥⎥ ⎢⎢⎢ ⇒ = ⎥⎥⎥ ⎢⎢⎢ × = × l y m p i c g O M m y p l c i g O MP 0 2 0 8 2 0 0 8 4 6 4 6 σ ⎥⎥⎦ ⎢⎢⎣ ⎥⎥⎦ ⎢⎢⎣ G a m e s l y m p i c m a e G s m y p l c i 9 ⎣ ⎦ ⎣ ⎦
周期置换密码 周期置换密码是将明文串P按固定长度分组, 然后对每组中的子串按1,2,…,m的某个置换重 排位置从而得到密文C。其中密钥σ包含分组长 度信息。解密时同样对密文C按长度m分组,并 按σ的逆置换σ把每组子串重新排列位置从而 得到明文P。 10 CNR@HEU http://machunguang.hrbeu.edu.cn
周期置换密码 周期置换密码是将明文串P按固定长度m分组, 然后对每组中的子串按 然后对每组中的子串按 的某个置换重 排位置从而得到密文 其中密钥 包含分组长 1,2,", m 排位置从而得到密文C。其中密钥 包含分组长 度信息 解密时同样对密文C按长度m分组 并 σ 度信息。解密时同样对密文C按长度m分组,并 按 的逆置换 把每组子串重新排列位置从而 −1 按σ 的逆置换 σ 把每组子串重新排列位置从而 得到明文P。 σ σ 10
周期置换密码(举例) 。明文: "State Key Laboratory of Networking and Switching"; 加密密钥:σ=(15623) 。明文分为七组: (StateK)(eyLabo)(ratory)(ofNetw)(orking)(andSwi)(tching) 。加密变换: (aKttSe)(Loyaeb)(tyaorr)(Nwfeot)(kgrion)(dinSaw)(hgcitn) 。最终密文: (aKttSeLoyaebtyaorrNwfeotkgriondinSawhgcitn) 由加密密钥易知解密密钥:61=(13265),解密易实现。 CNR@HEU http://machunguang.hrbeu.edu.cn
周期置换密码(举例) 明文: “State Key Laboratory of Networking and Switching”; 加密密钥:σ (15 6 2 3) 明文分为七组: σ = (15 6 2 3) (StateK)(eyLabo)(ratory)(ofNetw)(orking)(andSwi)(tching) 加密变换: (aKttSe)(Loyaeb)(tyaorr)(Nwfeot)(kgrion)(dinSaw)(hgcitn) 最终密文: (aKttSeLoyaebtyaorrNwfeotkgriondinSawhgcitn aKttSeLoyaebtyaorrNwfeotkgriondinSawhgcitn) 由加密密钥易知解密密钥 (1 3 2 6 5) 解密易实现 −1 11 由加密密钥易知解密密钥: , (1 3 2 6 5) ,解密易实现。 1 = − σ