第三讲古典密码课件

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机安全保密,第三讲 古典密码,wzy,武汉大学,计算机学院,1,计算机安全保密第三讲 古典密码wzywhu.edu.c,古典密码,虽然用近代密码学的观点来看，许多古典密码是很不安全的，或者说是极易破译的。,但是我们不能忘记古典密码在历史上发挥的巨大作用。,另外，,编制古典密码的基本方法对于编制近代密码仍然有效。,2,古典密码 虽然用近代密码学的观点来看,第三讲 古典密码,换位法,替代法,3,第三讲 古典密码换位法3,置换密码,把明文中的字母重新排列，字母本身不变，但其位置改变了，这样编成的密码称为置换密码。,最简单的置换密码是把明文中的字母顺序倒过来，然后截成固定长度的字母组作为密文。,明文：,明晨5点发动反攻。,MING CHEN WU DIAN FA DONG FAN GONG,密文：,GNOGN AFGNO DAFNA IDUWN EHCGN IM,4,置换密码把明文中的字母重新排列，字母本身不变，但其位置改变了,例如：,明文：,MING CHEN WU DIAN FA DONG FAN,GONG,矩阵：,MINGCH,选出顺序：,按列,ENWUDI,ANFADO,改变矩阵大小和取出序列,NGFANG,可得到不同的密码,ONG,密文：,MEANO INNGN NWFFG GUAA CDDN,HIOG,把明文按某一顺序排成一个矩阵， 然后按另一顺序选出矩阵中的字母以形成密文，最后截成固定长度的字母组作为密文。,5,把明文按某一顺序排成一个矩阵， 然后按另一顺序,古典密码,换位法,思路,打乱明文中各字母的顺序，使明文中的单词错乱，隐蔽其含义,6,古典密码换位法6,古典密码,换位法,方法,加密时，将明文的字符（一维数据）按照一定顺序放入高维空间（一维以上）中，然后按照另一种顺序取出字符，形成密文（一维数据）,解密时，先将密文按照相应顺序放入高维空间中，再按照原始顺序取出明文,7,古典密码换位法7,古典密码,换位法,举例,明文：,M,=,INTELLIGENT,放入34的矩阵,8,古典密码换位法8,古典密码,换位法,加密方法,整体加密，取列向量,密文为E,k,(,M,) =,ILENLNTITEG,按行加密，取列顺序2413,密文为E,k,(,M,) =,NEITLGLINET,9,古典密码换位法9,古典密码,双轨密码：18611865年,明文：,DiscreteAndSystem,加密：,D s r t A d y t m,i c e e n S s e,密文：,DsrtAdytm,iceenSse,10,古典密码双轨密码：18611865年10,理论上：,、,置换密码的加密钥是置换矩阵,p,，,解密钥是置换矩阵,p,-1,。,、,置换密码经不起已知明文攻击。,1 2 3 n,a,1,a,2,a,3, a,n,P =,11,理论上：、置换密码的加密钥是置换矩阵 p ， 1,习 题,已知换位密码的换位表为：（2,7,5,3,8,4,6,1），试对明文 software 加密。,答案：,12,习 题已知换位密码的换位表为：（2,7,5,3,8,4,6,习 题,已知换位密码的换位表为：（2,7,5,3,8,4,6,1），试对明文 software 加密。,答案：orwfetas,13,习 题已知换位密码的换位表为：（2,7,5,3,8,4,6,古典密码,换位法,算法特点：易于手工操作，明密文都是字符串且等长,算法缺陷：明文密文中的各字母出现次数是相同的，只是位置不同，密码分析员可以通过移动字母顺序进行破译,14,古典密码换位法14,古典密码,替代法,简单替代,多表替代,同音替代,组合替代,15,古典密码替代法15,替代法,简单替代,思路,将明文中字母按照一定规律替换成其他字母，隐蔽其含义,方法,设定规则，将明文中的字母,x,替换成字母,f,(,x,),16,替代法简单替代16,替代法,简单替代,举例,设密钥为,k,，加密规则是,f,(,x,) = (,x,+,k,) mod 26,当,k,= 3时,明文,M,=,FIGHTATNIGHT ，,被加密成,密文E,k,(,M,)=,ILJKWDWQLJKW,C语言的实现方式,c=(a-A)+k)%26)+A;,选择具有自反特点的加密函数,f,(,a,)=(,k,-,a,) mod 26,17,替代法简单替代17,替代法,简单替代,特点,易于手工操作，明密文都是字符串且等长，明文中的字母在密文中都以其他字母所取代,缺陷,明文字母的出现次数与相应密文字母的出现次数是相同的，因而明文中的字母统计特性在密文中也存在，容易被攻击。（例如：明文中字母e出现得最多，而加密后字母h出现得最多）,18,替代法简单替代18,替代法,多表替代,思路,采用多个代替密钥交替加密明文，以减弱频率特性,19,替代法多表替代19,替代法,多表替代,Vigenere密码,设明文字母为,a,，当前密钥字母为,k,i,，则密文字母为,f,i,(,a,) = (,a,+,k,i,) mod 26,举例,20,替代法多表替代20,替代法,多表替代,举例,设明文,M,=,INTELLIGENT,密钥,k,=,PLAYPLAYPLA,密文E,k,(,M,)=,XYTCAMIETYT,21,替代法多表替代21,22,22,例：用Vigenere密码加密明文：intrusion detection，密钥为NEU。,答案：vrneymvsh qinrgnvsh,M,= int rus ion det ect ion,K,= neu neu neu neu neu neu,C,= vrn eym vsh qin rgn vsh,23,例：用Vigenere密码加密明文：intrusion de,替代法,多表替代,特点,明文字母周期性地被不同的密钥字母加密,缺陷,被相同密钥字母加密的密文仍然具有频率统计特性。一旦密码分析员猜对了密码长度后，容易在密文中发现频率统计特性，然后分别对每个密钥字母破译,24,替代法多表替代24,替代法,多表替代,攻击思路：首先猜测密钥长度，即加密周期，再分别破译各密钥字母,猜测周期的方法,重合度（index of coincidence）,粗糙度（measure of roughness）,25,替代法多表替代25,替代法,游动密钥密码,思路,采用很长的、不重复的密钥加密明文，避免密钥周期,方法,利用诸如字典、圣经等，又长又不重复的文本作为密钥，采用多表替换加密明文,26,替代法游动密钥密码26,替代法,同音代替密码,思路,对于出现频率较高的明文字母采用多个不同的密文表示，以消除密文中的频率统计特性,方法,根据明文字母表中各字母的一般出现概率，为每个明文字母分配一定数量的不重复的随机数，加密时从中随机选取一个作为密文,27,替代法同音代替密码27,替代法,同音代替密码,举例,设加密矩阵为,28,替代法同音代替密码28,替代法,同音代替密码,举例,设明文,M,=,P L A I N P I L O T,则加密的结果可能为：,C,= 91 44 56 65 59 33 08 76 28 78,29,替代法同音代替密码29,替代法,同音代替密码,特点,单字母频率特性在密文中被消除，不易破译,缺陷,多字母频率特性仍不能完全消除,30,替代法同音代替密码30,替代法,组合替代,思路：一次替代明文中的多个字母,特点：一定程度上消除字母频率统计特性,明文字母之间产生了相关性，其基本思想被应用于后面将详细讲述的对称分组密码,31,替代法组合替代31,代数密码：,Vernam,密码,明文、密文、密钥都表示为二进制位：,M=m,1,m,2, ,m,n,K,=k,1,k,2, ,k,n,C =c,1,c,2, ,c,n,加密,：,c,1,= m,i,k,i,i=1,2, ,n,解密,：,m,1,= c,i,k,i,i=1,2, ,n,因为加解密算法是模,2,加，所以称为代数密码。,对合运算：,f=f,-1,，,模,2,加运算是对合运算。,密码算法是对和运算，则加密算法解密算法，工程实现工作量减半。,Vernam,密码经不起已知明文攻击。,32,代数密码： Vernam密码32,Vernam密码与一次一密密码,Vernam密码：,加密：,c,i,=,m,i,+,k,i,mod 2,解密：,m,i,=c,i,+k,i,mod 2,例：11000,10010 01010,一次一密：密钥为一个随机且不重复的字符序列。,33,Vernam密码与一次一密密码Vernam密码：33,代数密码：,如果密钥序列有重复，则,Vernam,密码是不安全的。,一种极端情况：一次一密, 密钥是随机序列。, 密钥至少和明文一样长。, 一个密钥只用一次。,一次一密是绝对不可破译的，但它是不实用的。, 一次一密给密码设计指出一个方向，人们用序列密码逼近一次一密。,34,代数密码： 如果密钥序列有重复，则Vernam密码是不安全,古典密码的穷举分析,单表代替密码分析,加法密码,因为f(a,i,)= b,i,=a,j,j=i+k,mod n,所以k=1,2，. ,n-1,共n-1种可能，,密钥空间太小。以英文为例，只有25种密钥。,经不起穷举攻击。,35,古典密码的穷举分析单表代替密码分析35,古典密码的穷举分析,单表代替密码分析,密钥词语代替密码,因为密钥词语的选取是随机的，所以密文字母表完全可能穷尽明文字母表的全排列。,以英文字母表为例，n=26，所以共有26！种可能的密文字母表。,26！4,10,26,用计算机也不可能穷举攻击。,注意：穷举不是攻击密钥词语代替密码的唯一方法。,36,古典密码的穷举分析单表代替密码分析36,古典密码的统计分析,密钥词组单表代替密码的统计分析,任何自然语言都有自己的统计规律。,如果密文中保留了明文的统计特征，就可用统计方法攻击密码。,由于单表代替密码只使用一个密文字母表，一个明文字母固定的用一个密文字母来代替，所以密文的统计规律与明文相同。,因此，单表代替密码可用统计分析攻破。,37,古典密码的统计分析密钥词组单表代替密码的统计分析,单字母频率分布图,38,单字母频率分布图 38,古典密码的统计分析,英语的统计规律,每个单字母出现的频率稳定。,最高频率字母 E,次高频率字母 T A O I N S H R,中高频率字母 D L,低频率字母 C U M W F G Y P B,最低频率字母 V K J X Q Z,39,古典密码的统计分析英语的统计规律 39,古典密码的统计分析,英语的统计规律,频率最高的双字母组：,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,40,古典密码的统计分析英语的统计规律 40,古典密码的统计分析,英语的统计规律,频率最高的三字母组：,THE ING AND HER ERE ENT THA WAS,ETH FOR DHT HAT SHE ION HIS ERS,VER,其中THE,的频率是ING的3倍！,41,古典密码的统计分析英语的统计规律 41,古典密码的统计分析,英语的统计规律,英文单词以E，S，D，T为结尾的超过一半。,英文单词以T，A，S，W为起始字母的约占一半。,还有其它统计规律,！,42,古典密码的统计分析英语的统计规律 42,古典密码的统计分析,经得起统计分析是对,近代密码的基本要求！,43,古典密码的统计分析43,第三讲 古典密码,结束,44,第三讲 古典密码结束44,