密码学技术-古典密码学

福尔摩斯探案集之跳舞的小人•ＡＭＨＥＲＥＡＢＥＳＬＡＮＥ•ＡTＥＬＲＩGＥＳ•“天王盖地虎，宝塔镇河妖……”大家一定在电影里看过对暗号的场面。其实，这种暗号是一种最朴素的密码。只不过这种密码过于简单，经不起密码学家的分析，非常容易破译。将密码当成一种科学来研究，就产生了密码学。第二章密码学技术1、密码学概述2、古典密码学3、分组密码学4、公钥密码学本章重点及难点本章主要问题集中在现代密码学部分，对称密钥学中的DES加密算法及IDEA加密算法，公钥密码学中的RSA加密算法和ELGamal算法为本章的重点及难点，需要大家好好理解。密码学基本概念•明文：需要秘密传送的消息。•密文：明文经过密码变换后的消息。•加密：由明文到密文的变换。•解密：从密文恢复出明文的过程。•破译：非法接收者试图从密文分析出明文的过程。•加密算法：对明文进行加密时采用的一组规则。•解密算法：对密文进行解密时采用的一组规则。•密钥：加密和解密时使用的一组秘密信息。明文Plaintext密文Ciphertext加密Encryption解密Decryption密钥key加解密过程示意图明文明文密文加密算法解密算法密钥密钥加/解密原理描述假设明文字母用P或者M表示，密文字母用C表示,密钥用K表示,加密变换用E表示，解密变换用D表示，则有：•1.加密原理文字描述：C=Ek(p)•2.解密原理文字描述：p=Dk(C)加密变换EpC解密变换DpC密码学的发展历史发展史早在4000多年以前，古埃及人就在墓志铭中使用过类似于象形文字那样奇妙的符号；公元前约50年，凯撒密码－一种简单的字符替换－被认为是最早的正式算法；双轨式密码、网格式密码、字典编号密码；传统密码学、现代密码学、量子密码学。•1949年之前古典加密学密码学作为一种技艺，是一门艺术，而不是一种科学1949～1975年shannon的“communicationtheoryofsecrecysystem”密码学成为科学主要技术：单密钥的对称密钥加密算法•1976年以后Diffie,Hellman发表“newdirectionsincryptography”密码学的新方向——公钥密码学应用领域军事、外交、情报商业、个人通信example-i•(象形文字的修改)ModifiedHieroglyphics,c.1900B.C.密码学的第一个例子是对标准书写符号的修改例如:古埃及法老坟墓上的文字思想:代替(substitution)example-ii•SpartanScytale,c.500B.C.斯巴达人用于加解密的一种军事设备发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想：置换（permutation)example-iii•Polybius’Checkerboard,205~123B.C.•明文:POLYBIUS•密文:3534315412244543123451ABCDE2FGHIJK3LMNOP4QRSTU5VWXYZExample-iv•CaesarCipher,c.50B.C.ABCDEFG……XYZDEFGHIJ……ABC明文:Caesarcipherisashiftsubstitution密文:FDHVDUFLSKHULVDVKLIWVXEVWLWXWLRQExample-V•Nomenclator代码本c.1400字母、符号、单词、短语代码代码字母、符号、单词、短语应用：WorldWarII2.1古典密码•代换密码–单表代换密码•移位密码•替换密码•仿射密码–多表代换密码•Vigenère(维吉尼亚）密码•置换密码代换密码•令Θ表示明文字母表，内有q个“字母”或“字符”，可以将Θ抽象地表示为一个整数集•在加密时通常将明文消息划分成长为L的消息单元，称为明文组，以m表示，如•m也称作L－报文，它可以看作是定义在上的随机变量•L＝1为单字母报（1－gram），L＝2为双字母报（digrams），L＝3为三字母报（trigrams）。这时明文空间为。1,,1,0qZq10,),,,,(110LlZmmmmmqlLLqZ10,),,,(110LlZmmmmmLZZZZNlLqqqLq个LqZP代换密码（续）•令ξ表示q个“字母”或“字符”的密文字母表，抽象地可用整数集表示•密文单元或组为•c是定义在上的随机变量。密文空间•一般地，明文和密文由同一字母表构成，即Θ＝ξ1,,1,0''qZq10,,)(,,,('''110'''LlZcLccccqlL个）''LqZ''LqZC代换密码（续）•代换密码可以看作是从到的映射。时，称作单字母代换，也称作流密码（Streamcipher）。时，称作多码代换，亦称分组密码（Blockcipher）。•一般地，选择相同明文和密文字母表。此时，若,则代换映射是一一映射，密码无数据扩展。若,则有数据扩展，可将加密函数设计成一对多的映射，即明文组可以找到多于一个密文组来代换，这称之为多名（或同音）代换密码（Homophonicsubstitutioncipher）。若,则明文数据被压缩，此时代换映射不可能构成可逆映射，从而密文有时也就无法完全恢复出原明文消息，因此保密通信中必须要求。但的映射可以用在认证系统中。LqZ''LqZ1L1L'LL'LL'LL'LL'LL代换密码（续）•在Θ＝Ξ，，时，若对所有明文字母，都用一种固定的代换进行加密，则称这种密码为单表代换（Monoalphabeticsubstitute）。若用一个以上的代换表进行加密，这就称作多表代换（Polyalphabeticsubstitute）。•这是古典密码中的两种重要体制。还有一个常见的是多字母代换密码。'qq1L单表代换密码•单表代换密码是对明文的所有字母都用一个固定的明文字母表到密文字母表的映射，即。令明文，则相应地密文为•几类常见的单表代换密码–移位密码–替换密码–仿射密码•单表代换密码不能非常有效地抵抗密码攻击，因为语言的特征仍能从密文中提取出来qqZZf:10mmm)()()(1010mfmfccmec移位密码•由于英文字符有26个字母，可以建立英文字母和模26的剩余之间的对应关系：ABCDEFGHIJKLMN012345678910111213OPQRSTUVWXYZ141516171819202122232425移位密码（续）•对于英文文本，则明文、密文空间都可定义为（很容易推广到n个字母的情况）。容易看出移位满足我们密码系统的定义，即。26Z,))((xxxedkk对每个26Z设定义，且。,250,26kZKCP对26mod)(kxxek26,26mod)(Zyxkyydk凯撒密码历史上最著名的移位密码就是凯撒密码。凯撒密码(Caesarcipher)（1）原理（明密对照表）明文：abcdefghIjklmnopqrstuvwxyz密文：DEFGHIJKLMNOPQRSTUVWXYZABC（2）算法描述（数学描述）假设明文字母用P表示，密文字母用C表示，密钥用K表示，加密变换用E表示，解密变换用D表示，并设a=0,b=1,c=2,d=3,…x=23,y=24,z=25,则有：C=Ek(p)=(p+3)mod(26)p=Dk(C)=(C-3)mod(26)----C不够减时可向前借位在计算机中，a=97,b=98,c=99,d=100,…x=120,y=121,z=122，则：明密对照表如下：明文：97，98，99，100，…，120，121，122密文：100，101，102，103，…，97，98，99加/解密算法描述如下：C=Ek(p)=[(p-97)+3]mod(26)+97p=Dk(C)=[(C-97)-3]mod(26)+97----若[(C-97-3)]＜0时，C可借位（1）求明文字母a的密文字母的过程如下：C=[（a-97）+3]mod(26)+97=3+97=100(d)（2）求明文字母z的密文字母的过程如下：C=[（z-97)+3]mod(26)+97=28mod(26)+97=2+97=99（c)（3）求密文字母C的明文字母的过程如下：p=[(99-97)-3]mod(26)+97=[(2-3)+26]mod(26)+97=25+97=122（z)(4)求密文字母A的明文字母的过程如下：p=[(97-97)-3]mod(26)+97=[(0-3)+26]mod(26)+97=23+97=120(x)替换密码•定义设，密钥空间K由所有可能的26个符号0，1，…….，25的置换组成。对每一个置换，定义则，其中的逆置换。26ZCP)()(xxe)()(1yyd是1•置换的表示为：•替换密码的密钥是由26个字母的置换组成。这些置换的数目是26！，超过，是一个非常大的数。这样即使对现代计算机来说，穷举密钥搜索也是不可行的。显然，替换密码的密钥（26个元素的随机置换）太复杂而不容易记忆，因此实际中密钥句子常被使用。密钥句子中的字母被依次填入密文字母表（重复的字母只用一次），未用的字母按自然顺序排列。''''''25242321025242321026100.4仿射密码•加密函数为：–当a＝1时，为移位密码;–当b=0时，为乘法密码；•仿射函数是双射–当且仅当gcd(a,26)=1时同余方程对每个y有唯一的解26,26mod)(Zbabaxxe)26(modybax仿射密码系统•设，且对定义且•因为满足，gcd(a,26)=1的只有12种候选，对参数没有要求。所以仿射密码有种可能的密钥。26ZCP1)26,gcd(:),(2626aZZbaKKbak),(26mod)(baxxe26mod)()(1byaydk),(26Zyx26Za3122612a单表加密的破解•对于单表替代密码，加法密码和乘法密码的密钥量比较小，可利用穷举密钥的方法进行破译。•穷举不是攻击密码的惟一方法，密码分析者便可利用语言的统计特性进行分析。如果明文语言的这种统计特性在明文中有所反映，密码分析者便可通过分析明文和密文的统计规律而破译密码。表26个英文字母出现频率统计表字母出现频率字母出现频率a0.0856n0.0707b0.0139o0.0797c0.0279p0.0199d0.0378q0.0012e0.1304r0.0677f0.0289s0.0607g0.0199t0.1045h0.0528u0.0249i0.0627v0.0092j0.0013w0.0149k0.0042x0.0017l0.0339y0.0199m0.0249z0.0008通过对26个英文字母出现频率的分析，可以有以下结果：（1）e出现的频率最大，约为0.13；（2）t，a，o，i，n，s，h，r出现的频率约在0.06～0.1之间；（3）d，l出现的频率在0.04附近；（4）c，u，m，w，f，g，y，p，b出现的频率约在0.015～0.029之间；（5）v，k，j，x，q，z出现的频率小于0.01。在密码分析中，除了考虑单字母统计特性外，掌握双字母、三字母的统计特性以及字母之间的连缀关系等信息也是很有用的。出现频率最高的30个双字母组合依次是：thheineranreedonesstenattonthandoueangasortiisetitartesehiof出现频率最高的20个三字母组合依次是：theingandherereentthanthwasethfordthhatsheioninthissthersver•特别的，the出现的频率几乎是ing的3倍，这在密码分析中很有用。此外，统计资料还表明：英文单词以e，s，d，t字母结尾的超过一半。英文单词以t，a，s，w为起始字母的约占一半。•以上这些统计数据是通过非专业性文献中的字母进行统计得到的。对于密