搜索
密码学经典密码一、经典密码虽然用近代密码学的观点来看，许多经典密码是很不安全的，或者说是极易破译的。但是我们不能忘记经典密码在历史上发挥的巨大作用。另外，编制经典密码的基本方法对于编制近代密码仍然有效。一、经典密码经典密码编码方法：置换，代换，代数1、置换密码•把明文中的字母重新排列，字母本身不变，但其位置改变了，这样编成的密码称为置换密码。–(1)最简单的置换密码是把明文中的字母顺序倒过来，然后截成固定长度的字母组作为密文。明文：明晨5点发动反攻。MINGCHENWUDIANFADONGFANGONG密文：GNOGNAFGNODAFNAIDUWNEHCGNIM一、经典密码例如：明文：MINGCHENWUDIANFADONGFANGONG矩阵：MINGCH选出顺序：按列ENWUDIANFADO改变矩阵大小和取出序列NGFANG可得到不同的密码ONG密文：MEANOINNGNNWFFGGUAACDDNHIOG•(2)把明文按某一顺序排成一个矩阵，然后按另一顺序选出矩阵中的字母以形成密文，最后截成固定长度的字母组作为密文。一、经典密码•理论上：①、置换密码的加密钥是置换矩阵p，解密钥是置换矩阵p-1。②、置换密码经不起已知明文攻击。123…na1a2a3…anP=一、经典密码2、代换密码首先构造一个或多个密文字母表，然后用密文字母表中的字母或字母组来代换明文字母或字母组，各字母或字母组的相对位置不变，但其本身改变了。这样编成的密码称为代换密码。①单表代换密码②多表代换密码一、经典密码⑴．单表代换密码只使用一个密文字母表，并且用密文字母表中的一个字母来代换明文字母表中的一个字母。明文字母表：A＝{a0,a1,...,an-1}密文字母表：B＝{b0,b1,...,bn-1}定义一个由A到B的映射：f:A→Bf(ai)=bi设明文：M=（m0,m1,...,mn-1）,则密文：C=(f(m0),f(m1),...,f(mn-1))。简单代换密码的密钥就是映射函数f或密文字母表B。一、经典密码⑴单表代换密码①、加法密码–A和B是有n个字母的字母表。–定义一个由A到B的映射：f:A→Bf(ai)=bi=ajj=i+kmodn–加法密码是用明文字母在字母表中后面第k个字母来代换。–K=3时是著名的凯撒密码。一、经典密码⑴单表代换密码②、乘法密码–A和B是有n个字母的字母表。–定义一个由A到B的映射：f:A→Bf(ai)=bi=ajj=ikmodn其中，(n,k)=1。–注意：只有(n,k)=1，才能正确解密。一、经典密码⑴单表代换密码③密钥词组代换密码：随机选一个词语，去掉其中的重复字母，写到矩阵的第一行，从明文字母表中去掉这第一行的字母，其余字母顺序写入矩阵。然后按列取出字母构成密文字母表。一、经典密码举例：密钥：HONGYE矩阵：HONGYE选出顺序：按列ABCDFIJKLMPQ改变密钥、矩阵大小RSTUVW和取出序列，得到不同的XZ密文字母表。密文字母表:B={HAJRXOBKSZNCLTGDMUYFPVEIQW}一、经典密码⑵、多表代换密码–单表代换密码的安全性不高，一个原因是一个明文字母只由一个密文字母代换。–构造多个密文字母表，–在密钥的控制下用相应密文字母表中的一个字母来代换明文字母表中的一个字母。一个明文字母有多种代换。Vigenere密码：著名的多表代换密码一、经典密码明文字母ABCDEFGHIJKLMNOPQRSTUVWXYZAABCDEFGHIJKLMNOPQRSTUVWXYZBBCDEFGHIJKLMNOPQRSTUVWXYZACCDEFGHIJKLMNOPQRSTUVWXYZABHHIJKLMNOPQRSTUVWXYZABCDEFGXXYZABCDEFGHIJKLMNOPQRSTUVWYYZABCDEFGHIJKLMNOPQRSTUVWXZZABCDEFGHIJKLMNOPQRSTUVWXYVigenre方阵密钥字母一、经典密码Vigenre密码的代换规则是用明文字母在Vigenre方阵中的列和密钥字母在Vigenre方阵中的行的交点处的字母来代换该明文字母。例如，设明文字母为P，密钥字母为Y，则用字母N来代换明文字母P。明文：MINGCHENWUDIANFADONGFANGONG密钥：XINGCHUIPINGYEKUOYUEYONGDAJIANGLIU密文：JQAMEOYVLCQOYRPURMHKDOAMRNP解密就是利用Vigenre方阵进行反代换。Ci=Mi+KimodnMi=Ci+Kimodn一、经典密码3、代数密码：①Vernam密码明文、密文、密钥都表示为二进制位：M=m1,m2,…,mnK=k1,k2,…,knC=c1,c2,…,cn②加密：c1=mi⊕ki,i=1,2,…,n解密：m1=ci⊕ki,i=1,2,…,n③因为加解密算法是模2加，所以称为代数密码。④对合运算：f=f-1，模2加运算是对合运算。密码算法是对和运算，则加密算法＝解密算法，工程实现工作量减半。⑤Vernam密码经不起已知明文攻击。一、经典密码⑥一种极端情况：一次一密•密钥是随机序列。•密钥至少和明文一样长。•一个密钥只用一次。⑦一次一密是绝对不可破译的，但它是不实用的。⑧一次一密给密码设计指出一个方向，人们用序列密码逼近一次一密。一、经典密码二、经典密码的穷举分析1、单表代换密码分析①加法密码–因为f(ai)=bi=ajj=i+kmodn–所以k=1,2，...,n-1,共n-1种可能，密钥空间太小。以英文为例，只有25种密钥。–经不起穷举攻击。二、经典密码的穷举分析1、单表代换密码分析②乘法密码–因为f(ai)=bi=ajj=ikmodn，且（k,n）=1。–密钥空间更小。–对于英文字母表，n=26，k=1,3,5,7,9,11,15,17,19,21,23,25取掉1，共11种，比加法密码更弱。–经不起穷举攻击。二、经典密码的穷举分析1、单表代换密码分析③密钥词语代换密码–因为密钥词语的选取是随机的，所以密文字母表完全可能穷尽明文字母表的全排列。–以英文字母表为例，n=26，所以共有26！种可能的密文字母表。26！≈41026–用计算机也不可能穷举攻击。–注意：穷举不是攻击密钥词语代换密码的唯一方法。三、经典密码的统计分析2、密钥词组单表代换密码的统计分析–任何自然语言都有自己的统计规律。–如果密文中保留了明文的统计特征，就可用统计方法攻击密码。–由于单表代换密码只使用一个密文字母表，一个明文字母固定的用一个密文字母来代换，所以密文的统计规律与明文相同。–因此，单表代换密码可用统计分析攻破。三、经典密码的统计分析•英语的统计规律–每个单字母出现的频率稳定。最高频率字母E次高频率字母TAOINSHR中高频率字母DL低频率字母CUMWFGYPB最低频率字母VKJXQZ三、经典密码的统计分析•英语的统计规律–频率最高的双字母组：THHEINERANREEDONESSTENATTONTHANDOUEANGASORTIISETITARTESEHIOF三、经典密码的统计分析•英语的统计规律–频率最高的三字母组：THEINGANDHEREREENTTHAWASETHFORDHTHATSHEIONHISERSVER其中THE的频率是ING的3倍！三、经典密码的统计分析•英语的统计规律–英文单词以E，S，D，T为结尾的超过一半。–英文单词以T，A，S，W为起始字母的约占一半。–还有其它统计规律！三、经典密码的统计分析经得起统计分析是对近代密码的基本要求！