第三讲古典密码课件.ppt

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