《第1章简单密码体制及分析.ppt》由会员分享，可在线阅读，更多相关《第1章简单密码体制及分析.ppt（72页珍藏版）》请在课桌文档上搜索。
1、课程名称:计算机密码学教材:计算机密码应用基础1,总 目 录,第1章 简单密码体制及分析第2章 分组密码第3章 香农理论第4章 序列密码和移位寄存器第5章 RSA公钥密码体制第6章 其它公钥密码体制第7章 数字签名,第1章 简单密码体制及分析,1.1 密码学的基本概念1.2 一些简单密码体制与它的破译,密码学既属于计算机科学,也可算是应用数学,更确切地说,它是二者之间的边缘学科,数学无疑是其重要的工具.计算机的出现和广泛普及,使人类社会步入信息化时代,也使安全保密研究揭掉了神秘的面纱,成为大家感兴趣并能为更多人服务的科学.信息在社会中的地位和作用越来越重要，已成为社会发展的重要战略资源.,1.
2、1 密码学的基本概念,1.引言,信息安全所面临的威胁来自很多方面，并且随着时间的变化而变化。这些威胁可以宏观地分为人为威胁和自然威胁。自然威胁可能来自于各种自然灾害、恶劣的场地环境、电磁辐射和电磁干扰、网络设备自然老化等。这些事件有时会直接威胁信息的安全，影响信息的存储媒质。,我们主要讨论人为威胁，也就是对信息的人为攻击。这些攻击手段都是通过寻找系统的弱点，以便达到破坏、欺骗、窃取数据等目的，造成经济上和政治上不可估量的损失。根据美国FBI的调查,美国每年因为网络安全造成的经济损失超过1.70亿美元.面对如此严重危害计算机数据安全的种种威胁,必须采取措施确保计算机数据的安全保密.确保数据安全就
3、是采取措施免受未授权的泄露、篡改和毁坏，主要包括数据秘密性、真实性和完整性。,要确保计算机数据的安全保密，必须综合采取各种措施才能奏效，除法律、行政、教育等措施外，最重要的是要采取技术保护措施。技术措施可分为访问控制技术和密码技术两大类。我们主要讨论密码技术.,密码学的发展历程,第一次世界大战前，密码学重要的进展很少出现在公开文献中1918年，20世纪最有影响的分析文章，重合指数及其在密码学中的应用问世1949年，Shanon发表了题为“保密系统的通信理论”19491967密码学文献很少1976年，W.Diffie,M.Hellman提出了公开密钥密码1977年，美国联邦政府正式颁布DES19
4、77年至今，公开的密码学研究爆炸性的增长,2.密码学的基本概念,通信双方采用保密通信系统保护需要发送的消息，使未授权者不能提取信息。发送方将要发送的消息称为明文，明文被变换成看似无意义的随机消息，称为密文，这种变换过程称为加密；其逆过程，即由密文恢复出原明文的过程称为解密。对明文进行加密操作的人员称为加密员或密码员。密码员对明文进行加密时所采用的一组规则称为加密算法。,传送消息的预定对象称为接收者，接收者对密文进行解密时所采用的一组规则称为解密算法。加密和解密算法的操作通常都是在一组密钥控制下进行的，分别称为加密密钥和解密密钥。传统密码体制所用的加密密钥和解密密钥相同，或实质上等同，即从一个易
5、于得出另一个，称其为单钥或对称密码体制。若加密密钥和解密密钥不相同，从一个难于推出另一个，则称为双钥或非对称密码体制。密钥是密码体制安全保密的关键，它的产生和管理是密码学中的重要研究课题。,在信息传输和处理系统中，除了预定的接收者外，还有非授权者，他们通过各种办法（如搭线窃听、电磁窃听、声音窃听等）来窃取机密信息，称其为截收者。截收者虽然不知道系统所用的密钥，但通过分析可能从截获的密文推断出原来的明文或密钥，这一过程称为密码分析，从事这一工作的人员称为密码分析员，研究如何从密文推演出明文、密钥或解密算法的学问称为密码分析学。对一个保密通信系统采取截获密文进行分析的这类攻击称为被动攻击。现代信息
6、系统还可能遭受的另一类攻击是主动攻击，非法入侵者、攻击者或黑客主动向,系统采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利己害人的目的。这是现代信息系统中更为棘手的问题。一个密码系统，它由以下几部分组成：明文消息空间M，密文消息空间C，密钥空间K，在单钥体制下，此时密钥ke=kdK 需经安全的密钥信道由发送方传给接收方；加密变换Eke：MC，其中keK，由加密器完成；解密变换Dkd：CM，由解密器实现。称(M,C,K,EKe,DKd)为密码系统。对于给定明文消息mM，密钥keK，加密变换将明文m变换为密文c，即c=f(m,ke)=Eke(m)mM,keK,接收方利用通过安全信道送来
7、的密钥k（kK，单钥体制下）或用本地密钥发生器产生的解密密钥kd（双钥体制下）控制解密操作D，对收到的密文进行变换得到明文消息，即：m=Dkd(c)mM,kdK而密码分析者，则用其选定的变换函数h，对截获的密文c进行变换，得到的明文是明文空间中的某个元素,即m=h(c)一般mm。如果m=m，则分析成功。,密码系统模型,为了保护信息的保密性，抗击密码分析,密码系统应当满足下述要求：系统即使达不到理论上是不可破的，也应当为实际上不可破的。就是说，从截获的密文或某些已知的明文密文对，要决定密钥或任意明文在计算上是不可行的。系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerck
8、hoff原则。加密和解密算法适用于所有密钥空间中的元素。系统便于实现和使用。,16,密码学分类：密码编制学和密码分析学密码系统的组成：（1）明文空间M；（2）密文空间C；（3）密钥空间K，对任意kK，k=（kd，ke）；（4)加密算法E，C=E（M，ke）；（5）解密算法D，M=D（C，kd）。,一个密码系统包含明文字母空间、密文字母空间、密钥空间和算法。密码系统的两个基本单元是算法和密钥。密码系统的两个基本单元中，算法是相对稳定的，视为常量；密钥则是不固定的，视为变量。为了密码系统的安全，频繁更换密钥是必要的。一般来说算法是公开的，真正需要保密的是密钥。因此在密钥的分发和存储时应当特别小心。
9、,密码体制根据密钥可划分为两大类，即单钥体制和双钥体制。,密码体制分类,单钥体制的加密密钥和解密密钥相同。采用单钥体制的系统的保密性主要取决于密钥的保密性，与算法的保密性无关，即由密文和加解密算法不可能得到明文。换句话说，算法无需保密，需保密的仅是密钥。,密钥可由发送方产生然后再经一个安全可靠的途径（如信使递送）送至接收方，或由第三方产生后安全可靠地分配给通信双方。如何产生满足保密要求的密钥以及如何将密钥安全可靠地分配给通信双方是这类体制设计和实现的主要课题。密钥产生、分配、存储、销毁等问题，统称为密钥管理。这是影响系统安全的关键因素，即使密码算法再好，若密钥管理问题处理不好，就很难保证系统的
10、安全保密。,双钥体制是由Diffie和Hellman于1976年首先引入的。采用双钥体制的每个用户都有一对选定的密钥：一个是可以公开的，可以像电话号码一样进行注册公布；另一个则是秘密的。因此双钥体制又称为公钥体制。双钥密码体制的主要特点是将加密密钥和解密密钥分开，因而可以实现多个用户加密的消息只能由一个用户解读，或由一个用户加密的消息而使多个用户可以解读。前者可用于公共网络中实现保密通信，而后者可用于实现对用户的认证。,根据对明文的划分与密钥的使用方法不同,可将密码体制分为两种方式：一是明文消息按字符（如二元数字）逐位地加密，称之为流密码或序列密码；另一种是将明文消息分组（含有多个字符），逐组
11、地进行加密，称之为分组密码。,密码体制一般可分为传统密码序列密码、分组密码、公钥密码、量子密码体制。广泛应用于军事、商业经济、网络间的通信等领域，涉及了数学、物理、计算机科学、电子学、系统工程、语言学等学科内容。,密码分析者攻击密码的方法主要有以下三种,穷举攻击统计分析攻击数学分析攻击,密码编制与密码分析示意图,M M=DAB（C）明文 C=EAB(M)密文 明文 密钥KAB 密钥KAB,密码分析员,发送方A,接收方B,密码系统的攻击类型的划分是由攻击者可获取的信息量决定。其中，最困难的攻击类型是唯密文攻击，这种攻击的手段一般是穷搜索法，即对截获的密文依次用所有可能的密钥试译，直到得到有意义的
12、明文。只要有足够多的计算时间和存储空间，原则上穷举攻击总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的。敌手因此还需对密文进行统计分析，为此需要知道被加密的明文的类型，比如英文文本、法文,根据密码分析者可利用的数据来分类,文本、MD-DOS执行文件等。唯密文攻击时，敌手知道的信息量最少，因此最易抵抗。然而，很多情况下，敌手可能有更多的信息，也许能截获一个或多个明文及其对应的密文，也许知道消息中将出现的某种明文格式。例如ps格式文件开始位置的格式总是相同的，电子资金传送消息总有一个标准的报头或标题。这时的攻击称为已知明文攻击，敌手也许能够从已知的明
13、文被变换成密文的方式得到密钥。,根据密码分析者可利用的数据来分类，破译密码的类型分为三种,仅知密文攻击已知明文攻击：计算机程序易受这种攻击选择明文攻击：计算机文件系统和数据库易受这种攻击,攻击类型分类,人为攻击可分为被动攻击和主动攻击,被动攻击-即窃听，是对系统的保密性进行攻击，如搭线窃听、对文件或程序的非法拷贝等，以获取他人的信息。被动攻击又分为两类，一类是获取消息的内容，很容易理解；第二类是进行业务流分析，假如我们通过某种手段，比如加密，使得攻击者从截获的消息无法得到消息的真实内容，然而敌手却有可能获得消息的格式、确定通信双方的位置和身份以及通信的次数和消息的长度，这些信息可能对通信双方来
14、说是敏感的。被动攻击因不对消息做任何修改，因而是难以检测的，所以抗击这种攻击的重点在于预防而非检测。,主动攻击这种攻击包括对数据流的某些篡改或产生某些假的数据流。主动攻击又可分为以下三个子类：中断：是对系统的可用性进行攻击，如破坏计算机硬件、网络或文件管理系统。篡改：是对系统的完整性进行攻击，如修改数据文件中的数据、替换某一程序使其执行不同的功能、修改网络中传送的消息内容等。伪造：是对系统的真实性进行攻击。如在网络中插入伪造的消息或在文件中插入伪造的记录。,绝对防止主动攻击是十分困难的，因为需要随时随地对通信设备和通信线路进行物理保护，因此抗击主动攻击的主要途径是检测，以及对此攻击造成的破坏进
15、行恢复。,1.2 一些简单密码体制与它的破译,1.置换密码把明文中的字母重新排列，字母本身不变,例：明文为this cryptosystem is not secure。排成矩阵：thiscr yptosy stemis notsec ure密文为tysnu hptor itete soms csie rysc。,2.单表代替密码,首先构造一个密文字母表，然后用密文字母表中的字母或字母组来代替明文字母表中的字母或字母组，各字母或字母组的相对位置不变，但其本身改变了。设A=a0，a1，an-1 为含n个字母的明文字母表，B=b0，b1，bn-1 为含n个字母的密文字母表，定义一个由A到B的一一映
16、射。f：AB，f（ai）=bi设明文M=（m0，m1，mn-1），则相应的密文C=（f（m0），f（m1），f（mn-1）,1.因子设a，b(b0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b|a，且称b是a的因子。,数论简介,整数具有以下性质：a|1，那么a=1。a|b且b|a，则a=b。对任一b(b0)，b|0。b|g，b|h，则对任意整数m、n有b|(mg+nh)。,这里只给出的证明，其他3个性质的证明都很简单。性质的证明：由b|g，b|h知，存在整数g1、h1，使得g=bg1,h=bh1所以mg+nh=mbg1+nbh1=b(mg1+nh1),因此b|(mg+nh
17、)。,2.素数称整数p(p1)是素数，如果p的因子只有1，p。任一整数a(a1)都能惟一地分解为以下形式：其中p1p2pt是素数，ai0(i=1,t)。例如91=711，11011=711213,这一性质称为整数分解的惟一性，也可如下陈述：设P是所有素数集合，则任意整数a(a1)都能惟一地写成以下形式：其中ap0,等号右边的乘积项取所有的素数，然而大多指数项ap为0。相应地，任一正整数也可由非0指数列表表示。例如：11011可表示为a7=1,a11=2,a13=1。两数相乘等价于对应的指数相加，即由k=mn 可得：对每一素数p,kp=mp+np。而由a|b可得：对每一素数p,apbp。,设n是
18、一正整数，a是整数，如果用n除a，得商为q，余数为r，则 a=qn+r,0rn,其中 为小于或等于 的最大整数。用a mod n表示余数r，则。如果(a mod n)=(b mod n)，则称两整数a和b模n同余，记为ab mod n。称与a模n同余的数的全体为a的同余类，记为a，称a为这个同余类的表示元素。注意：如果a0(mod n)，则n|a。,模运算,同余有以下性质：若n|(a-b)，则ab mod n。(a mod n)(b mod n)，则ab mod n。ab mod n,则ba mod n。ab mod n,bc mod n,则ac mod n。从以上性质易知，同余类中的每一元素
19、都可作为这个同余类的表示元素。,求余数运算（简称求余运算）a mod n将整数a映射到集合0,1,n-1，称求余运算在这个集合上的算术运算为模运算，模运算有以下性质：(a mod n)+(b mod n)mod n=(a+b)mod n。(a mod n)-(b mod n)mod n=(a-b)mod n。(a mod n)(b mod n)mod n=(ab)mod n。,性质的证明：设（a mod n）=ra，(b mod n)=rb，则存在整数j、k使得a=jn+ra，b=kn+rb。因此(a+b)mod n=(j+k)n+ra+rb mod n=(ra+rb)mod n=(a mod
20、 n)+(b mod n)mod n（证毕）性质、的证明类似。,最大公因数称c是两个整数a、b的最大公因数，如果 c是a的因子也是b 的因子，即c是a、b的公因子。a和b的任一公因子，也是c的因子。表示为c=gcd(a,b)或c=(a,b)。,由于要求最大公因子为正，所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一般gcd(a,b)=gcd(|a|,|b|)。由于任一非0整数能整除0，可得gcd(a,0)=|a|。如果将a，b都表示为素数的乘积，则gcd（a,b）极易确定。例如：300=22315218=2132gcd(18,300)=213150=6一般
21、由c=gcd(a,b)可得：对每一素数p，cp=min(ap,bp)。,由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因子.如果gcd(a,b)=1，则称a和b互素。于是下面讨论用辗转相除法求两个大数的最大公因子。定理:设a,b,c是任意三个不全为零的整数,且a=bn+c,0cn,则gcd(a,b)=gcd(b,c),或记为(a,b)=(b,c)再用b除c,一直继续下去,直到余数为0,则最后一个非0余数即为a和b的最大公因数.,最小公倍数称c是两个整数a、b的最小公倍数，如果 c是a的倍数也是b 的倍数，即c是a、b的公倍数。c是一切公倍数中最小的正数。表示为c=lc
22、ma,b或c=a,b。,几类单表代替密码,加法密码：f（ai）=aj，ji+k（mod n），0kn，取n=26。乘法密码：f（ai）=aj，jik（mod n），0kn，（k，n）=1。仿射密码：f（ai）=aj，jik1+k0（mod n），（k1，n）=1。密钥词组代替密码用一词组或短语作密钥，去掉密钥中的重复字母，把结果作为矩阵的第一行，其次从明文字母表中补入其余字母，最后按某一顺序从矩阵中取出字母构成密文字母表。例：密钥为red star，明文为data security。,字母与数字对应表,3.单表代替密码的统计分析,极高频率字母组：e z次高频率字母组：taonirsh jvbh
23、dilc中等频率字母组：dlucm xseyr低频率字母组：pfywgbv tfkawnp甚低频率字母组：jkqxz mqgou双字母：th he in er an re ed 三字母：the ing and her are ent英文字母出现的频率如表1-2.,举例,YKHLBA JCZ SVIJ JZB LZVHI JCZ VHJ DR IZXKHLBA VSS RDHEI DR YVJV LBXSKYLBA YLALJVS IFZZXC CVI LEFHDNZY EVBTRDSY JCZ FHLEVHT HZVIDB RDH JCLI CVI WZZB JCZ VYNZBJ DR ELX
24、HDZSZXJHDBLXI JCZ XDEFSZQLJT DR JCZ RKBXJLDBI JCVJ XVB BDP WZ FZHRDHEZY WT JCZ EVXCLBZ CVI HLIZB YHVEVJLXVSST VI V HZIKSJ DR JCLI HZXZBJ YZNZSDFEZBJ LB JZXCBDSDAT EVBT DR JCZ XLFCZH ITIJZEI JCVJ PZHZ DBXZ CDBILYZHZY IZXKHZ VHZ BDP WHZVMVWSZ,Ze，Va，三字母单词JCZ？e：the2字母单词VIa？：an，as，am，at，I s三字母单词VHZa？e：ar
25、e，age Hr。三字母单词JZBte？：Bn4字母单词JCLIth？s：LI4字母单词WZZB？een：Wb6字母单词HZVIDBreas？n：Do,2字母单词DRo？：Rf3字母单词BDPno？：Pw4字母单词DBXZon？e：Xc4字母单词EVBT？any：Em2字母单词WTB？：Ty3字母单词BDPno？：Pw,4字母单词DBXZon？e：Xc4字母单词EVBT？any：EmIFZZXCs？eech：FpFZHRDHEZYperforme？：YdVSSa？：SlJZXCBDSDATtechnono？yAg3字母单词结尾LBAi？g：BnYKHLBAd？ring：KuLEFHDNZYim
26、pro？ed：NvWHZVMVWSZbrea？able Mk,4.多表代替密码,构造d个密文字母表设Bj=bj0，bj1，bjn-1，j=0，1，d-1为d个含n个字母的密文字母表,A=a0，a1，an-1 为含n个字母的明文字母表，定义d个映射。fj：ABj，fj（ai）=bji设明文M=（m0，m1，mn-1），则相应的密文C=（f0（m0），f1（m1），fd-1（md-1），f0（md），）,例:Vigenere密码,若K=k1k2km，M=m1m2mn，C=c1c2cn其中cimi+ki（mod 26）至于密钥k可以通过周期性地延长，周而复始，反复以至无穷。即ki+lm=ki例：密钥
27、为cipher，明文为thiscryptosystem。明文:19 7 8 18 2 17 24 15 19 14 18 24 18密钥:2 8 15 7 4 17 2 8 15 7 4 17 2 密文:21 15 23 25 6 8 0 23 8 21 22 15 20 这样密文串为VPXZGIAXIVWPUBTT.,例:已知vigenere密码中,密钥为cipher,试对密文VPXZGIAXIVWPUBTT解密.解:密文:21 15 23 25 6 8 0 23 8 21 22 15 20 密钥:2 8 15 7 4 17 2 8 15 7 4 17 2 明文:19 7 8 18 2 17
28、 24 15 19 14 18 24 18于是明文为thiscryptosystem.,例：试破译vigenere密码加密得到的密文UFQUIUDWFHGLZARIHWLLWYYFSYYQATJPFKMUXSSWWCSVFAEVWWGQCMVVSWFKUTBLLGZFVITYOEIFASJWGGSJEPNSUETPTMPOPHZSFDCXEPLZQWKDWFXWTHASPWIUOVSSSFKWWLCCEZWEUEHGVGLRLLGWOFKWLUWSHEVWSTTUARCWHWBVTGNITJRWWKCOTPGMILRQESKWGYHAENDIULKDHZIQASFMPRGWRVPBUIQQDS
29、VMPFZMVEGEEPFODJQCHZIUZZM,5.对Vigenere密码的分析,确定密钥字的长度m：1Kasiski测试，2使用重合指数。DWF 7 112 105 EVW 47 162 115 LLG 64 149 85 BJW 78 278 200由于105、115、85、200的最大公约数为5，所以它非常可能是密钥字的长度。,2重合指数:假设C=c1c2cn是n个字符的串,C的重合指数记为IC(C),其中英文文献:根据表1-2的统计结果IC(C)=0.0687随机字母序列:IC(C)=0.0385假设使用的密钥词组的长度为m,可将密文分成m行,算每一行的重合指数,进一步确定密钥词组
30、的长度.,将密文分成5行,并求其重合指数:1.UUGIWYJUWAGVUGTFGPTOFPKWPVKCUGGWHTCVTKGQGNKQPVQMVPQUKOCR.IC=0.0623.进一步可得m=5.确定密钥字母：考虑两行的互重合指数是有用的，求出ij=kj-ki,确定密钥字母:考虑两个串的互重合指数。将第i行每位后推k位得到的新序列和第j行联合计算重合指数,6.代数密码或Vernam密码,若K=k1k2k3，M=m1m2m3，其中mi=0或1，ki=0或1，C=c1c2c3 其中ci=mi+ki例：明文为cat，密钥为key，于是M=000100000010011K=0101000100110
31、00C=010000010001011,该密码体制在已知明文攻击面前就非常脆弱,因为ki=mi+ci，为了增强Vernam密码的强度，一种极端情况是（1）密钥是真正的随机序列；（2）密钥的长度大于等于明文的长度；（3）一个密钥只用一次。如果能作到这些,则Vernam密码就不可破译了.,7.Hill加密算法,Hill加密算法的基本思想是将l个明文字母通过线性变换将它们转换为l个密文字母。解密只要作一次逆变换就可以了，密钥就是变换矩阵本身。,其中,或写成 一般取n=26,其中,解密:,其中所有算术运算都在模26下进行.在模26的情形下,矩阵K有逆矩阵的充分必要条件是gcddetK,26=1.证明:若gcddetK,26=1,则相反,若矩阵K有逆矩阵,8.关于Hill密码的已知明文攻击,假定攻击者已知道正在使用的l值,他也窃取了至少有l个不同的l元组,满足,如果令,若提供的矩阵M是可逆的，则能计算出,如果M不是可逆，就必须试另外l个明文-密文对。,例：假设明文worker利用l=2的Hill密码加密，得到密文为QIHRYB，求密钥K。解：首先选取前两个明文-密文对，我们得到矩阵方程,于是我们重新考虑第二、三明文-密文对，我们得到如下矩阵方程：,于是,所以,这个可以利用第一个明文-密文对得到验证。假定攻击者不知道l的值，他可通过穷举的方式确定。,
