密码编码学-1(武武汉大学国际软件学院信息安全课程)

1信息安全

密码编码学杨敏武汉大学国际软件学院yangm@2密码编码学基本概念和术语密码学的历史古代密码古典密码现代密码3基本概念和术语密码技术的目的使不知道如何解密的黑客不可能由其截获的乱码中得到任何有意义的信息；使黑客不可能伪造任何乱码型的信息。密码学(密码技术)分类密码编码学：对信息进行编码实现信息隐蔽密码分析学：研究加密消息的破译或消息的伪造4基本概念和术语明文（plaintext）：被隐藏的消息密文（ciphertext）：隐藏后的消息加密（encryption）：由明文到密文的变换过程解密（decryption）：由密文恢复出原始明文的过程破译：非法接收者试图从密文分析出明文的过程5基本概念和术语密码算法(cryptographyalgorithm)是用于加密和解密的数学函数。加密算法(encryptionalgorithm).对明文进行加密操作时所采用的一组规则解密算法(decryptionalgorithm)接收者对密文解密所采用的一组规则6基本概念和术语密钥（Key）加密算法和解密算法是在一组仅有合法用户知道的秘密信息，称为密钥的控制下进行的。加密和解密过程中使用的密钥分别称为加密密钥和解密密钥。7密码体制加密解密明文X密文Y明文X密钥(K)对称密码体制(symmetriccryptosystem)加密密钥和解密密钥是相同的Y=E(K,X)X=D(K,Y)8对称密码体制的特点：无论加密还是解密都使用同一个密钥，因此，此密码体制的安全性就是密钥的安全。如果密钥泄露，则此密码系统便被攻破。最有影响的对称密码是1977年美国国家标准局颁布的DES算法。优点：安全性高、加解密速度快。缺点：1)随着网络规模的扩大，密钥的管理成为一个难点；2)无法解决消息确认问题；9密码体制加密解密明文X密文Y明文X加密密钥Ke解密密钥KdY=E(Ke,X)X=D(Kd,Y)非对称密码体制(asymmetriccryptosystem)加密密钥和解密密钥是成对出现加密过程和解密过程不同，使用的密钥也不同10非对称密码体制特点：是1976年W.Diffie和M.E.Hellman提出的一种新型密码体制。加密密钥与解密密钥不同，此时不需要安全信道来传送密钥。优点：由于加密和解密不同，且能公开加密密钥，而仅需保密解密密钥，所以非对称密码不存在密钥管理问题。非对称密码还有一个优点是可以拥有数字签名等新功能。最有名的对称密码是1977年由Rivest，Shamir和Adleman三人提出的RSA密码体制。缺点：非对称密码算法一般比较复杂，加解密速度慢。11密码分析密码分析是无须取得密钥而能将密文信息恢复成明文的科学。企图利用算法的性质和明文的一般特性或某些明密文推导出特别的明文或使用的密钥。 攻击类型密码分析者已知的信息唯密文攻击加密算法；要解密的密文已知明文攻击加密算法；要解密的密文；用(与待解密文)同一密钥加密的多个明密文对选择明文攻击加密算法；要解密的密文；分析者任选明文，并用(与待解密文)同一密钥加密的密文选择密文攻击加密算法；要解密的密文；分析者有目的选择密文，并用(与待解密文)同一密钥解密的对应明文选择文本攻击加密算法；要解密的密文；分析者任选明文，并用(与待解密文)同一密钥加密的密文；分析者有目的选择密文，并用(与待解密文)同一密钥解密的对于明文传统密码体制基于加密信息的攻击类型13密码分析穷举攻击攻击者对一条密文尝试所有可能的密钥，直到得到有意义的明文。穷举攻击是最基本也是比较有效的一种攻击方法。从理论上讲，可以尝试所有的密钥。穷举攻击的代价与密钥大小成正比。密码算法可以通过增大密钥位数或加大解密（加密）算法的复杂性来对抗穷举攻击。14下表是穷尽密钥空间所需的时间。从表中我们可以发现，当密钥长度达到128位以上时，以目前的资源来说，穷举攻击将不成功。15密码的安全性考虑无条件安全(Unconditionallysecure)无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性.一次一密计算上安全的破译密码的代价超出密文信息的价值破译密码的时间超出密文信息的有效生命期16基本概念和术语密码学的历史古代密码古典密码现代密码密码编码学17密码学的发展史古代加密方法（手工阶段）古典密码（机械阶段）现代密码（计算机阶段）18古代加密方法起源于公元前440年出现在古希腊战争中的隐写术(steganography)：通过隐藏消息的存在来保护消息.是现今信息隐藏的始祖

19隐写术字符标记：印刷或打印的文本字母经选择用铅笔重写。该标记通常不可见，除非该纸以一定的角度对着亮光看。不可见墨水：使用一些物质来书写，但不留下任何可见痕迹，除非加热该纸或在该纸上涂上某种化学药品。扎小孔：在所选的字母上扎小孔，这些小孔通常不可见，除非把该纸放在光的前面。格孔密写卡：将它覆盖在一张纸上从格孔中写入密件，然后在纸上余下部分填入其它字句，使它像一般信件。20例如：格孔密写卡密文：王先生：来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。弟：李明

明文：情报在雨伞把中。21古代加密方法斯巴达人用于加解密的一种军事设备(SpartanScytale,400B.C.)发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想：置换（permutation)22古代加密方法Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。23古代加密方法一个叫AeneasTacticus的希腊人在《论要塞的防护》一书中对传输密文做了最早的论述。公元前2世纪，一个叫Polybius的希腊人设计了一种将字母编码成符号对的方法，他使用了一个称为Polybius的校验表，表中包含许多后来在加密系统中常见的方法，如代替与换位。24密码学的发展史古代加密方法（手工阶段）古典密码（机械阶段）现代密码（计算机阶段）25古典密码古典密码系统已经初步体现出近代密码系统的雏形，它比古代加密方法复杂，其变化较小。古典加密技术主要使用代换或者置换技术。古典密码使用手工或机械变换的方式实现。26两种基本加密技术代换（代替、替换）技术将明文字母替换成其它字母、数字或符号的方法。置换（换位）技术保持明文的所有字母不变，只是打乱明文字母的位置和次序。27古典代换加密技术又可以分为:简单代换密码，又称为单字母代换密码：它将明文的一个字符用相应的一个密文字符代替。使用一个字母表（明文的一个字母总是被同一个固定的字母代换）的简单代换密码也称为单表代换密码。例如：Caesar密码。多字母代换密码：它是对多于一个字母进行代换例如：Playfair密码；Hill密码。多表代换密码：是将明文消息中出现的同一个字母，在加密时不是完全被同一个固定的字母代换，而是根据其出现的位置次序，用不同的字母代换。例如：Vigenere密码。28代换密码——单字母代换Caesar密码：公元前50年，由JuliusCaesar发明，最早用在军方。加密：将明文中的每个字母，用在字母表中它后面的第3个字母代替。解密：反过来，将密文中的每个字母，用它前面的第3个字母代替。ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC字母编码明文：Systemmodels

密文：Vbvwhpprghov29代换密码——单字母代换一般的恺撒密码加密：每个明文字母用它后面的第k个字母代替解密：每个密文字母用它前面的第k个字母代替其中k为密钥，1k25一般的恺撒密码的破译分析已知加密和解密算法需要测试的密钥只有25个明文所用的语言是已知的，且其意义易于识别。因此：可以采用穷举攻击30练习密文：HTRUZYJWXDXYJR算法：一般的凯撒密码明文:?Computersystem31Caesar密码安全性上面的例子说明，凯撒密码不足以对抗穷举攻击。因此是不安全的。这个例子说明一个密码体制安全至少要能够抵抗穷举密钥搜索攻击，普通的做法是将密钥空间变得足够大。但是，很大的密钥空间并不是保证密码体制安全的充分条件，下面的例子可以说明这一点。32代换密码——单表代换改进：使用密钥词的恺撒密码使用密钥词控制字母表中的排列ABCDEFGHIJKLMNOPQRSTUVWXYZwordABCEFGHIJKLMNPQRSTUVXYZ字母编码密钥词为word33单表代换分析密钥空间增加(26!)，穷举搜索这么多的密钥很困难但这并不表示该密码不容易破解破解这类密码的突破点是由于语言本身的特点是充满冗余的，每个字母使用的频率不相等

而单表代换密码没有改变字母相对出现的频率明文字母的统计特性在密文中能够反映出来,当通过统计密文字母的出现频率，可以确定明文字母和密文字母之间的对应关系34英文字母统计特性英文单字母的相对频率表35单字母按照出现频率的大小可以分为下面5类：

(1)e：出现的频率大约为0.127(2)t,a,o,I,n,s,h,r：出现的频率大约在0.06-0.09之间

(3)d,l：出现的频率约为0.04(4)c,u,m,w,f,g,y,p,b：出现的频率大约在0.015-0.028之间

(5)v,k,j,x,q,z：出现的频率小于0.01英文字母统计特性36双字母和三字母组合都有现成的统计数据，常见的双字母组合和三字母组合统计表能够帮助破解密文。频率最高的30个双字母（按照频率从大到小排列）：

thheineranreedonesstenattonthandoueangasortiisetitartesehiof

频率最高的20个3字母（按照频率从大到小排列）：

theingandherereentthanthwasethfordthhatsheioninthissthersver英文字母统计特性37破解举例例3.1

已知下面的密文式由单表代换生产的：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ，试破译该密文首先统计密文中字母出现的频率，然后与英文字母出现频率比较。密文中字母的相对频率统计如下：38破解举例39将统计结果与频率表进行比较，可以猜测密文中P与Z可能是e和t，密文中的S,U,O,M出现频率比较高，可能与明文字母中出现频率相对较高的a,o,I,n,s,h,r这些字母对应密文中出现频率很低的几个字母C,K,L,N,R,I,J可能与明文字母中出现频率较低的字母v,k,j,x,q,z对应。就这样边试边改，最后得到明文如下：itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow破解举例40在尝试过程中，如果同时使用双字母和三字母的统计规律，那么更容易破译密文。如上面的密文中出现最多的双字母是ZW，它可能对应明文双字母出现频率较大的th，那么ZWP就可能是the，这样就更容易试出明文。破解举例41代换密码——多字母代换Playfair密码1854年由英国科学家CharlesWheatstone发明。将明文中的双字母音节作为一个单元并将其转换成密文的“双字母音节”。算法基于一个由密钥词构成的55字母矩阵。

42例：密钥词为monarchy，明文为balloon如果该字母对两个字母相同，则它们之间加一个填充字母，如x；则明文分为四个字母对：balxloon落在矩阵同一行的明文字母对中的字母由其右边的字母替换；on替换成na落在矩阵同一列的明文字母对中的字母由其下面的字母替换；ba替换成ib(或jb)其他的每组明文字母对中的字母如下替换：它所在的行是该字母的所在行，列则为另一个字母的所在列。

lo替换成pm

lx替换成suMONARCHYBDEFGI/JKLPQSTUVWXZ密文为：ibsupmna或jbsupmna43Playfair密码的安全性Playfair密码的安全性比单表代换密码提高了许多双字母共有26x26=676组合，因此频率统计分析表中需要676条统计数据Playfair密码中比单表代换更好地隐藏了明文中单字母的结构在第一次世界大战中被英军作为最好的密码系统使用，在第二次世界大战中也曾经被美军和盟军大量使用当然现在看来，该密码的安全性是很低的，它还保留明文的部分特征，只要给定几百个字母的密文情况下，该加密方法就可以破解44练习：Playfair加密假设密钥是cipher，使用Playfair算法加密如下明文：Playfaircipherwasactuallyinventedbywheatston45练习：Playfair加密由密钥词cipher可构建密钥矩阵：将明文按照两个字母分组为

playfaircipherwasactualxlyinventedbywheatstonx则密文为

BSDWRBCAIPHECFIKQBHOQFSPMXEKZCMUHFDXYIIFUTUQLZ

CI/JPHERABDFGKLMNOQSTUVWXYZ46代换密码——多表代换多表代换：在明文消息中采用不同的单表代换。特征：采用相关的单表替换规则集由密钥决定给定替换的具体规则47代换密码——多表代换Vigenere密码1858年法国密码学家维吉尼亚提出替换规则由26个类似caesar密码的替换表组成，其中每一个替换表是对明文字母移位0到25次后得到的替换单表。每个替换单表由一个密钥字母表示。48ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJABCDEFGHIJKLMNOPQRSTUVWXYZBCDEFGHIJKLMNOPQRSTUVWXYZACDEFGHIJKLMNOPQRSTUVWXYZABDEFGHIJKLMNOPQRSTUVWXYZABCEFGHIJKLMNOPQRSTUVWXYZABCDFGHIJKLMNOPQRSTUVWXYZABCDEGHIJKLMNOPQRSTUVWXYZABCDEFHIJKLMNOPQRSTUVWXYZABCDEFGIJKLMNOPQRSTUVWXYZABCDEFGHJKLMNOPQRSTUVWXYZABCDEFGHI……

……Vigenere替换表密钥:deceptive明文:wearediscoveredsaveyourself密文:明文密钥deceptivedeceptivedeceptivewearediscoveredsaveyourselfzicvtwqngrzgvtwavzhcqyglmgj49Vigenere密码的安全性

维吉尼亚密码是将每个明文字母映射为几个密文字母。如果密钥字的长度是m，明文中的一个字母能够映射成这m个可能的字母中的一个。密文中字母出现的频率被隐蔽了，它的安全性明显比单表代换密码提高了。维吉尼亚密码的密钥空间比较大，对于长度是m的密钥字，密钥空间为26m

。当m=5，密钥空间所含密钥的数量大于1.1x107

Vigenere密码的攻击方法

如果两个相同明文序列之间的距离是密钥词长度的整倍数，那么产生的密文序列也是相同的。找到重复序列，推断出密钥词的长度。如果密钥词的长度是m,那么密码实际上包含了m个单表代替。利用明文语言的频率特征对这样的单表密码进行攻击。5051练习：Vigenere密码使用Vigenere密码加密单词explanation，密钥为leg。密钥：legleglegle明文：explanation密文：PBVWETLXOZR52一次一密：非周期多表代换密码

使用与明文一样长且无重复的随机密钥来加密明文，并且该密钥使用一次后就不再使用。密文和明文没有任何统计关系。理论上一次一密是不可攻破的。事实上，给出任何长度与密文一样的明文，都存在一个密钥产生这个明文。因此靠穷举密钥的方法，会得到大量可读的明文。无法确定哪一个是真正需要的。53一次一密的例子密文：yvelpqnqv密钥：fzqlabcmd明文：twoapples密文：yvelpqnqv密钥：kiaxyqakr明文：oneorange另见课本P36所示的例子。54一次一密一次一密的安全性是取决于密钥的随机性。但产生大规模随机密钥是一件很困难的事情，目前还没有很好的办法来解决这个问题。密钥分配也是一个难点，由于密钥不允许重复使用，因此存在大量的密钥分配问题。一次一密在实际中很少使用，主要是用于高度机密的低带宽信道。55转轮机：多轮代换56两种基本加密技术代换（代替、替换）技术将明文字母替换成其它字母、数字或符号的方法。置换（换位）技术保持明文的所有字母不变，只是打乱明文字母的位置和次序。57置换密码将明文的字母顺序打乱，得到新的排列最简单的置换密码：栅栏技术明文

meetmeafterthetogaparty置换方法

mematrhtgpryetefeteoaat密文

mematrhtgpryetefeteoaat58置换密码列置换以固定的宽