2[1].3_单表代替密码的分析

第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 第三节 单表代替密码的分析第三节 单表代替密码的分析 1 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 2 攻击单表代替密码首先要识别所破译的报文是否是单表代替密码加密攻击单表代替密码首先要识别所破译的报文是否是单表代替密码加密 单表代替密码加密 的致命弱点是 单表代替密码加密 的致命弱点是 . . 启示：统计密文中每个字母出现的频次, 算出独 立抽样的单字母, 双字母和三字母的概率分布 启示：统计密文中每个字母出现的频次, 算出独 立抽样的单字母, 双字母和三字母的概率分布 密文的特性基本上同明文的单字母, 双 字母和三字母的统计特性相似, 所不同 的只不过是作了一次固定的代替而已。 密文的特性基本上同明文的单字母, 双 字母和三字母的统计特性相似, 所不同 的只不过是作了一次固定的代替而已。 猜字法：猜字法：该方法的主要依据是每个密文字母在密 文中出现的概率和自然语言的文字结合规律。 该方法的主要依据是每个密文字母在密 文中出现的概率和自然语言的文字结合规律。 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 1. 作出密文中每个字母出现的频次统计表作出密文中每个字母出现的频次统计表, 算出每个 密文字母出现的概率 算出每个 密文字母出现的概率, 并与明文字母的概率分布进行 对照 并与明文字母的概率分布进行 对照, 区分哪些是高概率字母区分哪些是高概率字母, 哪些是低概率字母。 一般说来 哪些是低概率字母。 一般说来, 这仅仅提示出某些密文字母对应的明文字 母可能属于表 这仅仅提示出某些密文字母对应的明文字 母可能属于表2.2中的哪一类中的哪一类, 还不能具体识别它确 切地对应哪个明文字母。 还不能具体识别它确 切地对应哪个明文字母。 3 攻击单表代替密码的基本步骤攻击单表代替密码的基本步骤 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 2. 用以上得到的信息和自然语言的文字结合规律用以上得到的信息和自然语言的文字结合规律, 即自然语言的双字母和三字母的统计特性即自然语言的双字母和三字母的统计特性, 推断 出一些可能的明密对应关系。 推断 出一些可能的明密对应关系。 4 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 3. 利用自然语言的文字结合规律验证上面推出的 明密对应关系 利用自然语言的文字结合规律验证上面推出的 明密对应关系, 同时还可能推断出一些新的明密 对应关系。 同时还可能推断出一些新的明密 对应关系。 5 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 4. 利用模式字或模式短语 由于加密是单表代替 利用模式字或模式短语 由于加密是单表代替, 所以明文中经常出现的词所以明文中经常出现的词, 如如 beginning, committee, people, tomorrow等等, 在密文中也 会以某种模式重复。如果猜出一个或几个词 在密文中也 会以某种模式重复。如果猜出一个或几个词, 或一个短 语 或一个短 语, 就会大大加速正确代替表的确定就会大大加速正确代替表的确定,这常常是攻击的关 键。这一技术在对付规格化的五字母为一组的密文时往 往会遇到些困难 这常常是攻击的关 键。这一技术在对付规格化的五字母为一组的密文时往 往会遇到些困难, 因为密文中无字长信息。因为密文中无字长信息。 6 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 ?一些字母在词头频繁出现一些字母在词头频繁出现, 另一些字母在词尾频繁出 现。 另一些字母在词尾频繁出 现。 7 自然语言的文字结合规律自然语言的文字结合规律 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 例如例如, 英文字母在词头频繁出现的十个字母按概率 大小依次为： 英文字母在词头频繁出现的十个字母按概率 大小依次为： T A S O I C W P B F 英文字母在词尾频繁出现的十个字母按概率大小依 次为： 英文字母在词尾频繁出现的十个字母按概率大小依 次为： E S D N T R Y F O L 8 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 ?辅音和元音的结合规律。这主要靠研究双字母辅音和元音的结合规律。这主要靠研究双字母, 三字 母和四字母的密文组合。这样的组合中一般必含有 一个元音。根据这些组合很可能确定出表示元音的 那些密文字母。 三字 母和四字母的密文组合。这样的组合中一般必含有 一个元音。根据这些组合很可能确定出表示元音的 那些密文字母。 9 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 例例2.6 给定密文为给定密文为 UZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESX UDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPD TSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MB ZWP FUPZ HMDJ UD TMOHMQ 10 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 攻击的第一步是作出密文字母出现的频次分布表攻击的第一步是作出密文字母出现的频次分布表: 11 字母字母ABCDEFGHIJKLM 频次频次2206642711008 字母字母NOPQRSTUVWXYZ 频次频次09163010310545214 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 第二步是确定其加密密表类型。 由密文字母出现的频次分布表不难看出 第二步是确定其加密密表类型。 由密文字母出现的频次分布表不难看出,此段密 文是单表代替加密的可能性很大。因为找不出有哪 个位置能使密文字母的概率分布和明文字母的概率 分布相匹配 此段密 文是单表代替加密的可能性很大。因为找不出有哪 个位置能使密文字母的概率分布和明文字母的概率 分布相匹配, 也不能把这个未知的分布用抽样转换成 正常分布 也不能把这个未知的分布用抽样转换成 正常分布, 从而断定它不是移位代替密码和乘法代替 密码 从而断定它不是移位代替密码和乘法代替 密码, 因此是混合型代替表加密的。因此是混合型代替表加密的。 12 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 第三步是根据密文字母的频次统计第三步是根据密文字母的频次统计, 确定某些密 文字母对应的明文字母可能属于表 确定某些密 文字母对应的明文字母可能属于表2.2中哪个类型或 哪几个字母组成的集合。此例中 中哪个类型或 哪几个字母组成的集合。此例中 密文字母集密文字母集 对应的明文所属的类或字母集对应的明文所属的类或字母集 P, Z E, T H,M,O,S,U A,I,N,O,R,S A,B,I,J,Q,T,Y G,J,K,Q,V,W,X,Y,Z 13 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 第四步是利用自然语言的文字结合规律进行 猜测。 第四步是利用自然语言的文字结合规律进行 猜测。 ?Z经常在词头或词尾出现经常在词头或词尾出现, 故猜测它与故猜测它与t对应对应, 而而P 经常在词尾出现而未在词头出现经常在词尾出现而未在词头出现, 所以猜测它与 明文字母 所以猜测它与 明文字母E对应。对应。 14 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 ?由于低频次密文字母由于低频次密文字母Q和和T都是两个词的词头都是两个词的词头, 因 此它们很可能是低频次的字母而且经常作词头的 字母集 因 此它们很可能是低频次的字母而且经常作词头的 字母集C,W,P,B,F中的元素。中的元素。 15 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 ?利用双字母利用双字母, 三字母统计特性及元音辅音拼写知识三字母统计特性及元音辅音拼写知识, 我们猜测单词我们猜测单词MB中必有一个元音字母中必有一个元音字母,而而B出现的频 次较低 出现的频 次较低, 故故M更可能为元音字母更可能为元音字母,否则可能否则可能B与与Y对 应。 对 应。 16 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 ?对于对于UZ和和UD,要么要么U为元音为元音,要么要么Z和和D都是元音而都是元音而U 为辅音。若为辅音。若U为辅音为辅音, 则相应的明文可能为则相应的明文可能为me,my或或 be,by, 但但U与与m或或b对应时对应时, 都不大象都不大象, 因为因为U出现的频 次较高。 因而可能 出现的频 次较高。 因而可能U为元音为元音, 而而Z和和D是辅音。若是辅音。若Z为 辅音 为 辅音, 则则ZWP将暗示将暗示W或或P为元音。由为元音。由P和和Z出现的频 次看 出现的频 次看, ZWP中的中的P可能为元音。可能为元音。 17 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 假定选假定选U为元音为元音, Z为辅音为辅音, 观察观察ZWSZ很象很象that, 则则 ZWP可能为定冠词可能为定冠词the。 由此。 由此 WSFP APPD he.ee. 可能暗示出单词可能暗示出单词have和和been。 18 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 19 至此至此, 我们得到密文和明文对照为我们得到密文和明文对照为: UZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESX .t .a. .e. .e.tea. that .eve.a. UDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPD .na. b.t .e.t nta.t. have been TSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MB .a.e th ta. .ee.e.tat.ve. ZWP FUPZ HMDJ UD TMOHMQ the et n. .n 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 由此可见由此可见, UZ可能为可能为at或或it, 但但As, 所以所以Ui。 而 。 而QUZW可能为可能为with, 即即Qw。因而。因而QSO为为was, 即即 Os。这与字母出现的频次关系一致。至此。这与字母出现的频次关系一致。至此, 我们 猜测的结果为 我们 猜测的结果为 it was .is.se. .estea. that seve.a. ina. b.t .i.e.t nta.ts have been .a.e with .iti.a. .ees- entatives the viet n. in sw 20 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 由此不难猜出由此不难猜出: GPOZPEVSG 是是 yesterday, OPFPESX 是是 several, EPYEP0PDZSZUFPO 是是 representatives, 而而 FUPZ HMDJ是是vietcong(越 共 越 共)。将这些代替关系用于密文。将这些代替关系用于密文, 再作进一步尝试就 可确定 再作进一步尝试就 可确定N, O, R对应的明文字母。对应的明文字母。 21 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 经过整理恢复的明文如下经过整理恢复的明文如下: it was disclosed yesterday that several informal(非正式的非正式的) but direct contacts have been made with political representatives of the viet cong （越南）（越南） in moscow 22 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 由于密文中由于密文中J,K,Z,X和和Q未出现未出现, 所以虽然破译了 这份报文 所以虽然破译了 这份报文, 但还未找出明密代替表。为了攻击用同一 代替表加密的其它密文 但还未找出明密代替表。为了攻击用同一 代替表加密的其它密文, 可进一步作些分析工作。列 出现有的代替表如下 可进一步作些分析工作。列 出现有的代替表如下: 23 字母字母abcdefghijklm 频次频次SAHVPBJWU?XT 字母字母nopqrstuvwxyz 频次频次DMY?EOZIFQ?G? 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 由上表可知字母由上表可知字母V, W, X, Y, Z在密文代替表中以在密文代替表中以 4为间距隔开为间距隔开, 将密文字母按照列写成将密文字母按照列写成4行得行得: S P U T . I . A B . D E F G H J . M O