应用密码学第2讲-311课件

应用密码学应用密码学第2章 古典密码学1回顾回顾l语言的统计特性l单表代替密码l单表代替密码的分析l多表代替密码22.1 语言的统计特性语言的统计特性l研究保密性和密码破译方法的实质：就是研究明文信息在密文信息中有多大程度的泄漏。l下面假设讨论的语言是某种语言的文字：设字母表为 X=x0，x1，xm-1 为了方便起见，字母表也用0（m-1）之间的数字来表示，此时字母表为 Zm=0，1，m132.1 语言的统计特性语言的统计特性l例如，英文字母表可以表示为 X=a，b，c，x，y，z 或者 Zm=0，1，2，24，25 明文是由Zm中的元素和固定的结合规则确定的。因此具有语言的统计特性。例如：字母q后总是跟着字母u。42.1 语言的统计特性语言的统计特性l语言的一阶统计特性 称P=p0，p1，pm-1为语言的一阶统计特性。其中，pi（0 i m-1）代表字母 i 在该语言中出现的概率。l英文的一 阶统计特性：统计单个英文字母在一段足够长的英文课文中出现的概率统计单个英文字母在一段足够长的英文课文中出现的概率.例2.1 英文字母表X=a，b，c，x，y，z，由独立试验产生明文单码，Beker在1982年统计的样本总数100362，得到单码的概率分布见表2.1.5表2.1 英文字母的概率分布字母概率字母概率字母概率A0.08167J0.00153S0.06327B0.01492K0.00772T0.09056C0.02782L0.04025U0.02758D0.04253M0.02405V0.00978E0.12702N0.06749W0.02360F0.02280O0.07567X0.00150G0.02015P0.01929Y0.01974H0.06094Q0.00095Z0.00074I0.06966R0.0549762.1 语言的统计特性l英文字母出现的概率大小排列：ETAOINSHRDLCUMWFGYPBVKJXQZ 按字母出现的概率分类：表2.2 英文字母分类表1234567极大概率字母集：E大概率字母集：T A O较大概率子母集：I N S H R平均概率字母集：D L较低概率字母集：C M W F G Y P B U低概率字母集：V K极低概率字母集：J X Q X72.1 语言的统计特性语言的统计特性语言的一阶特性至少在以下两个方面没有反映出英文的语言特性：(1)双字母出现的概率例如QE出现的概率。按照一阶特性计算QE出现的概率为 p（QE）=0.0095 0.12702 1.21 10-4 但是在英文课文中QE根本不会出现。(2)四字母SEND和SEDN在一阶统计特性下出现的概率相等，这也不符合实际。82.1 语言的统计特性语言的统计特性l双字母出现的频数表示为：N(i，j)i,j=0,1,2,(m-1)双字母出现的概率p(xi,xj)近似地可以表示为 p(xi,xj)=N(i，j)/(N1)l可以看到英文双字母的概率最大的可以看到英文双字母的概率最大的30对字母按概率大小排列为：对字母按概率大小排列为：th he in er an re ed on es st en at to nt ha nd ou ea ng as or ti is et it ar te se hi of例2.2 由独立试验产生双字母表。根据Beker在1982年的统计结果我们可以计算 p(SEND)=p(SE)p(ND)0.7919 p(SEDN)=p(SE)p(DN)0.08146 p(QE)=092.1 语言的统计特性语言的统计特性同理，三字母出现的概率可以近似地表示为 p(xi,xj,xk)=N(I,j,k)/(N2)注意：在实际的通信中除了字母外还有数字，标点符号等，他们的统计特性也要考虑进去。另外数据格式，报头信息对于密码体制的安全有重要意义，在密码分析中起着非常重要的作用。10英文的其它统计特性l冠词冠词the对英文的统计特性影响很大对英文的统计特性影响很大,它使它使t,h,th,he和和the在单字母在单字母,双字母和三字母的统计中都为高概率的双字母和三字母的统计中都为高概率的元素元素.l英文中大约有一半的词以英文中大约有一半的词以e,s,d 和和 t 结尾结尾.l英文中大约有一半的词以英文中大约有一半的词以t,a,s 和和 w 开头开头.112.2.1移位代替密码移位代替密码以下将q个字母的字母表与Z模q中数作一一对应,利用每个字母对应的数字代替该字母。例如,将英文字母表作如下对应:a b c y z 0 1 2 24 25这样,可以用0表示a,用1表示b.。移位代替密码是最简单的一种代替密码。其加密变换为：，0 m,cq 显然,移位代替密码的密钥空间中元素的个数为q,其中k=0是恒等变换。试着写出解密变换的公式122.2.1移位代替密码移位代替密码例2.3 凯撒密码(Caesar Cipher)是对英文字母表进行移位代替的密码,其中q=26。例如,选择密钥k=3,则有下述代替表:明: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 z密: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 C 设明文m=hello every body 试计算其密文。13解密时,只要用密钥k=23的加密密表对密文 c 进行加密运算就可恢复出原明文。这种密码是将明文字母表中字母位置下标与密钥 k 进行模 q 加法运算的结果作为密文字母位置下标,相应的字母即为密文字母,因此又称其为加法代替密码。142.2 乘法代替密码 乘法代替密码的加密变换为：，0 c q。这种密码又叫采样密码(decimation cipher)，这是因为其密文字母表是将明文字母表按下标每隔k位取出一个字母排列而成(字母表首尾相接)。显然,当gcd(k,q)=1,即k与q互素时明文字母与密文字母才是一一对应的。15l若q为素数,则有q-2个可用密钥。否则就只有(q)-1个可用密钥。这里(q)是欧拉函数,它表示小于q且与q互素的正整数的个数。162.2 乘法代替密码l例2.4 英文字母表q=26,选k=9,则有乘法代替密码的明文密文字母对应表:l 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 明: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 z 密:A J S B KTC LUD M V E N W F O X G P Y H Q Z I R 若明文m=multiplicative cipher 密文c=？172.2.3仿射代替密码 将移位代替密码和乘法代替密码结合起来就构成仿射代替密码。其加密变换为 其中 ,以 表示仿射代替密码的密钥。当k0=0时,就得到乘法代替密码,当k1=1时就得到移位代替密码。q=26时,可用的密钥数为2612-1=311个。解密变换为 182.2.3仿射代替密码例例2.5 仿射代替密码的代替表为:c=m7+3，m=cipher 求c=?试计算解密变换的代替表.192.2.4 密钥短语密码密钥短语密码 可以通过下述方法对例2.2.1 的加法代替密码进行改造,得到一种密钥可灵活变化的密码。选一个英文短语,称其为密钥字(key word)或密钥短语(key phrase)，如HAPPY NEWYEAR,按顺序去掉重复字母得HAPYNEWR。将它依次写在明文字母表之下,而后再将明文字母表中未在短语中出现过的字母依次写在此短语之后,就可构造出一个代替表,如下所示:明: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 z 密:H A P Y N E W R B C D F G I J K L M O Q S T U V X Z203.3 单表代替密码的分析1.识别报文：统计密报的一阶统计特性识别报文：统计密报的一阶统计特性,判断是否为单表判断是否为单表密密.2.破译方法：猜字法破译方法：猜字法 (1)统计密文字母出现的频次统计密文字母出现的频次 (2)利用各字母在密文中出现的频次和明文的一阶统计特利用各字母在密文中出现的频次和明文的一阶统计特性猜字性猜字.注意到注意到 常在字头出现的字母：常在字头出现的字母：T,A,S,O,I,C,W,P,B,F 常在字尾出现的字母：常在字尾出现的字母：E,S,D,N,T,R,Y,F,O,L (3)利用模式字或模式短语利用模式字或模式短语.如如the,people等等21应用举例应用举例设给定密文为设给定密文为UZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESX UDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPD TSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MB ZWP FUPZ HMDJ UD TMOHMQ22密文字母频次表lA B C D E F G H I J K L M N 2 2 0 6 6 4 2 7 1 1 0 0 8 0 O P Q R S T U V W X Y Z9 16 3 0 10 3 10 5 4 5 2 14 密文字母集密文字母集 对应的明文所属的类或字母集对应的明文所属的类或字母集 P,Z E,TH,M,O,S,U A,I,N,O,R,S,H23P e,Z tlUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl t e e te t t e elUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl t e t t t e e elTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl e t t e e e t t e lZWP FUPZ HMDJ UD TMOHMlt e e t 24lUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl t e e t e t h a t e elUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl t e t t t e e elTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl e t t e e e t t e lZWP FUPZ HMDJ UD TMOHMlt he e t W h,S a 25W h,S alUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl t a e e te a t h a t e e alUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl a t e t ta t h a e e e lTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e th t a e e e t a t e lZWP FUPZ HMDJ UD TMOHMlt h e e t 26lUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl t a e e te a t h a t e e alUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl a t e t t a t ha v e beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e t h t a e e e t at e lZWP FUPZ HMDJ UD TMOHMl t he e t F v,A b,D n27F v,A b,D nlUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl t a e e te a th a t ev e alUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl n a b t e t n t a t have beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e t h t a e e e n t a t ve lZWP FUPZ HMDJ UD TMOHMl t he v e t n n 28lUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl i t a e e te a th a t ev e alUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl n a bu t e t n t a t have beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e t h t a e e e n t at ve lZWP FUPZ HMDJ UD TMOHMlt he v i e t n I nU i,I u 29U i,I ulUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t a i e e te a th a t eve alUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl I n a but i e t n t a t have beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e i t h i t i a e e en t at i ve lZWP FUPZ HMDJ UD TMOHMl t he v i e t n I n30lUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl i t wa s i e e te a t h at e ve alUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl in a but i e t n t a t have beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e w i t h i t i a e e e nt at i ve lZWP FUPZ HMDJ UD TMOHMl the vi e t n I nQ w,O s31Q w,O slUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t was i s s e es t e a th a t se ve a lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n a but i e t n t a t s have beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e wi t h i t i a e e s e nt at I ve s lZWP FUPZ HMDJ UD TMOHMQl t he v I et n i n s w32lUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t was i s s e e s t e a th at se ve r a l lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n a but i e t n t a t s ha ve beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e wi th i t i a e e sen t a t ive s lZWP FUPZ HMDJ UD TMOHMQl t he vi e t n i n s wE r,X l33E r,X llUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t was i s l s e e s t e r a th at s eve r a l lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n r a l but i re t n t a t s ha ve be enlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e wi t h l i t i a l r e re s e n ta t iv es lZWP FUPZ HMDJ UD TMOHMQl t he vi e t n i n s w34lUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t was i s l s e e s te r a th a t seve r al lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n r a l but i re t n ta t s have be enlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e wi t h l i t i a l r e pre s e n ta t i ve s lZWP FUPZ HMDJ UD TMOHMQl t he vi e t n i n s wY p35lUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t was i s l s e e s ter a th a t sev e ra l lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n r a l but i re t nt a t s ha ve be enlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e wi t h p l i t i a l r e pre s en ta t i v es lZWP FUPZ HMDJ UD TMOHMQl t he vi e t n i n s wY p36lUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t was i s l s e e s t er a t h a t seve r a l lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n r a l but i re t n t a t s ha ve be enlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e wi t h p ol i t i c a l r ep re se n ta t I v es lZWP FUPZ HMDJ UD TMOHMQl t he vi et n i n s wM o,H c37M o,H clUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t was i s c l o se e s te r a th at se v er al lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n o r a l but i r e ct c on t ac t s have beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e wi t h p ol i t i c a l r e pre se n ta t I v es o lZWP FUPZ HMDJ UD TMOHMQl t he v I et c o n I n o s co w38lUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t was i s c l o s e e s t er a t h a t se ve r a l lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n o r a l but d i re c t co n ta c ts ha ve beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl a e wi t h po l I t I ca l re p re se n ta t I v es o lZWP FUPZ HMDJ UD TMOHMQl t he v I et c on I n mo sco wT m,V d39T m,V dlUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t was d i sc l o sed e st e rd a th a t sev e r al lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n o rma l but d i r ect co n ta c ts h ave beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBlmade wi th po l I t I c al re pr e se n ta t I ve s o lZWP FUPZ HMDJ UD TMOHMQl t he vi e t con I n mo s c ow40lUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t was di s c l o sed e st e rd a th a t sev e ra l lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n f o r mal but d I re c t con ta c ts ha ve beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBlmade wi t h po l I t I c al rep r e se n ta ti ves o lZWP FUPZ HMDJ UD TMOHMQl t he vi e t c on in mos co wB f41B flUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl it was d I s c l o sed e st e r da th a t sev e ra l lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n f o rma l but di re c t co n ta ct s ha ve be enlT SVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl made wi th po l I t I c al re pr e se nt a t I ve s of lZWP FUPZ HMDJ UD TMOHMQl t he vi et c on in mos cow42 密文密文:a b c d e f g h i j k l m n 明文明文:B F N R V C U O 密文密文:o p q r s t u v w x y z 明文明文:S E W A M I D H L P T 由于由于c,k,l,n,r在密文中没出现在密文中没出现,只需要判断只需要判断g,j对应对应的明文字母的明文字母.它们可能对应的明文字母集为它们可能对应的明文字母集为 g,j G,J,K,Q,X,Y,Z.43lUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl I t was d I s c l o sed y e s te rd ay t h at sev e ra l lUDBME TSX AIZ VUEPHZ HMDZSHZO WSFP APPDl i n f o r mal but di re c t co n ta c ts ha ve be e nlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl made wi t h po l I t I c al re pr es e nt a t I ve s of lZWP FUPZ HMDJ UD TMOHMQl t h e vi e t c o ng I n mos cow （越共）越共）44G y,J glUZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESXl it was disclosed yesterday that several lUDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPDl informal but direct contacts have beenlTSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MBl made with political representatives of lZWP FUPZ HMDJ UD TMOHMQl the viet cong in moscow45 破译密表明文明文 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 z密文密文 S A H V P B J W U.X T D M Y .E O Z I F Q .G .l注注意意到到V,W,X,Y,Z在在密密文文代代替替表表中中以以4为为间间距距隔隔开开,将将密文字母按列写成密文字母按列写成4行得行得:S P U T N I K A B C D E F G H J L M O Q R V W X Y Z 显然第一行为密钥字显然第一行为密钥字,第第5个字母为个字母为N(或或K/L),则第则第7个个字母为字母为K/L(或或N),相应的密钥字为相应的密钥字为SPUTNIK.46小结小结l语言的表示方法及统计特性l移位代替、乘法代替、仿射代替、密钥短语作业：2.2、2.3、2.447