第2讲密码学与PGP和社会工程学密码分析器.ppt

《第2讲密码学与PGP和社会工程学密码分析器.ppt》由会员分享，可在线阅读，更多相关《第2讲密码学与PGP和社会工程学密码分析器.ppt（62页珍藏版）》请在三一文库上搜索。

1、第2讲 密码学及其工具,2.1 密码学基本概念 2.2 古典密码 2.3 DES与RSA 2.4 PGP 2.5 社会工程学密码分析器,2.1 密码学基本概念,2.1.1 密码体制 2.1.2 密码分析 2.1.3 密码学的理论基础,密码学(Cryptology)是一门古老的科学。大概自人类社会出现战争便产生了密码，以后逐渐形成了一门独立的学科。在密码学形成和发展历程中，科学技术的发展和战争的刺激都起了积极的推动作用。 电子计算机一出现便被用于密码破译，使密码进入电子时代，其后有几个值得关注的里程碑： 1949年香农发表保密系统的通信理论，把密码学置于坚实的数学基础上，标志着密码学作为一门科学

2、的形成； 1976年W. Diffie和M. Hellman提出公开密钥密码，从而开创了一个密码新时代； 1977年美国联邦政府颁布数据加密标准DES； 1994年美国联邦政府颁布密钥托管加密标准EES，同年颁布数字签名标准DSS，2001年颁布高级加密标准AES； 目前，量子密码因其具有可证明的安全性，同时还能对窃听行为进行检测，从而研究广泛；生物信息技术的发展也推动了DNA计算机和DNA密码的研究,自古以来，密码主要用于军事、政治、外交等要害部门，因而密码学的研究工作本身也是秘密进行的。后来，随着计算机网络的普及，电子政务、电子商务和电子金融等对确保信息安全的需求的增加，民间出现了一些不从

3、属于保密机构的密码学者。实践证明，正是这种公开研究和秘密研究相结合的局面促进了今天密码学得空前繁荣。 研究密码编制的科学称为密码编制学(Cryptography) ；研究密码破译的科学称为密码分析学(Cryptannalysis)；密码编制学和密码分析学共同组成密码学(Cryptology)。,密码学的基本思想是伪装信息，使未授权者不能理解它的真实含义。所谓伪装就是对数据进行一组可逆的数学变换。伪装前的原始数据称为明文(Plaintext)，伪装后的数据称为密文(Ciphertext)，伪装的过程称为加密(Encryption)。加密在加密密钥(Key)的控制下进行。用于对数据加密的一组数学变

4、换称为加密算法 发信者将明文数据加密成密文，再将密文数据送入网络传输或存入计算机文件，而且只给合法收信者分配密钥。 合法收信者接收到密文后，施行与加密变换相逆的变换，去掉密文的伪装恢复出明文，这一过程称为解密(Decryprion)。解密在解密密钥的控制下进行。用于解密的一组数学变换称为解密算法，而且解密算法是加密算法的逆。,2.1.1 密码体制,一个密码系统通常简称为密码体制(Cryptosystem)，由五部分组成： 明文空间M，它是全体明文的集合； 密文空间C，它是全体密文的集合； 密钥空间K，它是全体密钥的集合。其中，每一个密钥K均由加密密钥Ke和解密密钥Kd组成，即K= 加密算法E，

5、它是一族由M到C的加密变换； 解密算法D，它是一族由C到M的解密变换。 对于明文空间M中的每个明文，加密算法E在密钥Ke的控制下将明文M加密为密文C： C=E(M,Ke) (2-1) 而解密算法D在密钥Kd的控制下，解密C成明文M: M=D(C,Kd)=D(E(M,Ke), Kd) (2-2),如果一个密码体制的Ke=Kd，或者由其中一个很容易推出另一个，则称该密码体制为单密钥密码体制或对称密码体制或传统密码体制，否则称双密钥密码体制。进而，如果在计算上Kd不能由Ke推出，这样，将Ke公开也不会损害Kd的安全，于是便可将Ke公开。这种密码体制称为公开密钥密码体制，简称公开密码体制。 根据明密文

6、的划分和密钥的使用不同，可将密码体制分为分组密码和序列密码体制。 设M为明文，分组密码将M划分称一系列的明文块Mi，通常每块包含若干位或字符，并且每一块Mi都用同一个密钥Ke进行加密，即 M=(M1,M2,Mn) C=(C1,C2,Cn) 其中，Ci=E(Mi,Ke) (i=1,2,n),而序列密码将明文和密钥都划分成为或字符的序列，并且对明文序列中的每一个位或字符都用密钥序列中的对应分量进行加密，即 M=(m1,m2,mn) Ke=(ke1,ke2,ken) C=(c1,c2,cn) 其中，ci=E(mi,kei) (i=1,2,n) 分组密码每一次加密一个明文块，而序列密码每一次加密一位或

7、一个字符。序列密码是要害部门使用的主流密码，而商用领域则多用分组密码。 根据加密算法在使用过程中是否变化，可将密码体制分为固定算法密码体制和演化密码体制。固定算法密码体制的加解密算法固定不变；而演化密码体制将密码学和演化计算相结合，使得在加密过程中加密算法也不断演化。,2.1.2 密码分析,如果能够根据密文系统地确定出明文或密钥，或者能够根据明文-密文对系统地确定出密钥，则称这个密码是可破译的。研究密码破译的科学称为密码分析学。密码分析者攻击密码的方法主要有三种： 1）穷举攻击 穷举攻击是指密码分析者采用依次试遍所有可能的密钥对所获得的密文进行解密，直至得到正确的明文；或者用一个确定的密钥对所

8、有可能的明文进行加密，直至得到所获得的密文。 理论上，对于任何使用密码只要有足够的资源都可以用穷举攻击将其攻破。从平均角度讲，采用穷举攻击破译一个密码必须试遍所有可能密钥的一半。 穷举攻击所花费的时间等于尝试次数乘以一次解密或加密所需的时间。可以通过增大密钥量或加大解密或加密算法的复杂性来对抗穷举攻击。,2）统计分析攻击 统计分析攻击是指密码分析者通过分析密文和明文的统计规律来破译密码。 统计分析攻击在历史上为破译古典密码作出过很大贡献。对抗统计分析攻击的方法是设法使明文的统计特性不带入密文。这样，密文不带有明文的痕迹，从而使统计分析攻击成为不可能。 3）数学分析攻击 数学分析攻击是指密码分析

9、者对加解密算法的数学基础和某些密码学特性，通过数学求解的方法来破译密码。 数学分析攻击是对基于数学难题的各种密码的主要威胁，为此，应当选用具有坚实数学基础和足够复杂的加解密算法。,此外，根据密码分析者可利用的数据资源来分类，可将攻击密码的类型分为以下四种： 1）仅知密文攻击 仅知密文攻击是指密码分析者仅根据截获的密文来破译密码。 2）已知明文攻击 已知明文攻击是指密码分析者根据已知的某些明文-密文对来破译密码。 3）选择明文攻击 选择明文攻击是指密码分析者能够选择明文并获得相应的密文。 4）选择密文攻击 选择密文攻击是指密码分析者能够选择密文并获得相应的明文。这种攻击主要攻击公开密钥密码体制，

10、特别是攻击其数字签名。,一个密码，如果无论密码分析者截获多少密文和用什么技术方法进行攻击都不能被攻破，则称该密码是绝对不可破译的。绝对不可破译的密码在理论上是存在的，这就是著名的“一次一密”密码。但是，由于密钥管理上的困难，“一次一密”密码是不实用的。理论上，如果能够获得足够的资源，那么任何实际可使用的密码又都是可破译的。 如果一个密码，不能被密码分析者根据可利用的资源所破译，则称其是计算上不可破译的。因为任何秘密都有其时效性，因此，对我们更有意义的是在计算上不可破译的密码。,2.1.3 密码学的理论基础,1949年，shannon发表的保密系统的通信理论从信息论的角度对信息源、密钥、加密和密

11、码分析进行了数学分析，用不确定性和唯一解距离来度量密码体制的安全性，阐明了密码体制、完善保密、纯密码、理论保密和实际保密等重要概念，把密码置于坚实的数学基础之上，标志着密码学作为一门独立学科的形成。从此，信息论成为密码学重要的理论基础之一。 Shannon建议采用扩散、混淆和乘积迭代的方法设计密码，并且以“揉面团”的过程形象地比喻扩散、混淆和乘积迭代的概念。所谓扩散就是将每一位明文和密钥数字的影响扩散到尽可能多得密文数字中。理想状态下，明文和密钥的每一位都影响密文的每一位，一般称这种情形达到“完备性”。所谓混淆就是是密文和密钥之间的关系复杂化。密文和密钥之间的关系越复杂，则密文和明文之间、密文

12、和密钥之间的统计相关性越小，从而使统计分析不能奏效。设计一个复杂密码一般是比较困难的，利用乘积迭代方法对简单密码进行组合迭代，可以得到理想的扩散和混淆，从而可以得到安全的密码。,计算复杂性理论是密码学的另一个理论基础。为计算求解一类问题，总需要一定量的时间资源和空间资源。消耗资源的多少取决于要求解问题的规模大小。 设要求解的问题规模（如，输入变量的个数或输入长度）为n，若对于所有的n和所有长度为n的输入，计算最多要用f(n)步完成，则称该问题的计算复杂度为f(n)。若f(n)为n的多项式，则称其为多项式复杂度。 粗略的讲，计算机可以在多项式时间复杂度内解决的问题称为P类问题；否则，为NP类问题

13、。P类问题是计算机可计算的，而NP问题是计算机不可计算的困难问题。NP问题中最难得问题称为NP完全问题，即NPC问题。 Shannon指出设计一个安全的密码本质上就是要寻找一个难解的问题。这样，计算复杂性理论的发展将直接影响密码的安全。 此外，密码的设计应该遵循公开设计原则。密码体制的安全仅依赖于密钥的保密，而不应依赖于对算法的保密。当然，密码设计的公开原则并不等于所有的密码在应用时都要公开加密算法。也就是说，在公开的原则下设计密码，在实际使用时对算法保密，将会更加安全。,2.2 古典密码,2.2.1 置换密码 2.2.2 替代密码 2.2.3 代数密码 2.2.4 古典密码的统计分析,2.2

14、.1 置换密码,把明文中的字母重新排列，字母本身不变，但其位置改变，这样编成的密码称为置换密码。 最简单的置换密码是把明文中字母顺序颠倒过来，然后截成固定长度的字母组作为密文。 例如： 明文：明晨5点发动反攻。 ming chen wu dian fa dong fan gong 密文：gnogn afgno dafna iduwn ehcgn im 倒序的置换密码显然是很弱的。 另一种置换密码是把明文按某一顺序排成一个矩阵，其中不足部分用填充，而是明文中不会出现的一个符号；然后按另一个顺序选出矩阵中的字母以形成密文，最后截成固定长度的字母组作为密文。,明文：WHAT CAN YOU LEAR

15、N FROM THIS BOOK” 明文矩阵：,举例,选出顺序：按列 密文：WORO HUOO ALMK TET CAH ARI NNS YFB 可以看出，改变矩阵的大小和选出顺序可以得到不同形式的密码。一种巧妙的方法：首先选一个词语作为密钥，去掉重复字母；然后按字母的字典顺序给密钥字母编号，并按照密钥的长度把明文排列成矩阵；最后按照数字序列中的数字顺序按列选出密文,密钥：k=computer 明文：WHAT CAN YOU LEARN FROM THIS BOOK” 按密钥排列明文：,举例,密文： WORO NNS ALMK HUOO TET YFB ARI CAH,2.2.2 替代密码,首

16、先构造一个或多个密文字母表，然后用密文字母表中的字母或字母组来替代明文字母或字母组，各字母或字母组的相对位置不变，但其本身改变，这样编成的密码称为替代密码。 按照替代所使用的密文字母表的个数可将替代密码分为单表替代密码、多表替代密码和多名替代密码 1.单表替代密码 又称为简单替代密码。它只使用一个密文字母表，并且用密文字母表中的一个字母来替代一个明文字母表中的一个字母。 设A=a0,a1,an-1; B=b0,b1,bn-1 定义一个由A到B的一一映射：f:AB,即f(ai)=bi 设明文M=(m0,m1,mn-1)， 则密文C=(f(m0),f(m1),f(mn-1),1）加法密码 加法密码

17、的映射函数： f(ai)=bi=aj，j=i+k mod n,k是0kn的正整数 著名的加法密码是古罗马的凯撒大帝使用的密码Caesar密码取k=3，因此其密文字母表就是把明文字母表循环右移3位后得到的字母表。 2）乘法密码 乘法密码的映射函数： f(ai)=bi=aj，j=ik mod n 其中，要求k和n互素。因为仅当(k,n)=1时，才存在两个整数x,y，使得xk+yn=1，才能有xk=1 mod n，才有i=xj mod n，密码才能正确解密。 例如，当用英文字母表作为明文字母表而取k=13时，因为(13,26)=131，会出现： f(A)=f(C)=f(E)=f(Y)=A f(B)=

18、f(D)=f(F)=f(Z)=N 这样，密文字母表变为B=A,N,A,N,A,N,A,N,3）仿射密码 乘法密码和加法密码相结合就构成了仿射密码。仿射密码的映射函数： f(ai)=bi=aj，j=ik1+k0 mod n 其中，要求k1和n互素，0=k0n,且不允许同时有k1=1 k0=0。 4）密钥词语替代密码 首先随机选用一个词组或短语作为密钥，去掉重复字母，把结果作为矩阵的第一行；其次，在明文字母表中去掉矩阵第一行中的字母，并将剩余字母依次写入矩阵的其余行；最后按某一顺序从矩阵中取出字母构成密文字母表。例如： 密钥：H O N G Y E 矩阵：H O N G Y E 选出顺序：按列 A

19、 B C D F I J K L M P Q R S T U V W X Z,2.多表替代密码 简单替代密码很容易被破译，提高替代密码强度的一种方法是采用多个密文字母表，使明文中的每个字母都有很多种可能的字母来替代。 构造d个密文字母表： Bj=bj0,bj1,bjn-1 , j=0,1,d-1 定义d个映射： fj:ABj,即fj(ai)=bji 设明文M=(m0,m1,md-1,md, ,mn-1) 则密文C=(f0(m0),f1(m1),fd-1(md-1),fd(md),) 由于加密用到了多个密文字母表，故称为多表替代密码。多表替代密码的密钥就是这组映射函数或密文字母表。 最著名的多表

20、替代密码是16世纪法国密码学者Vigenere使用的Vigenere密码。它依次把明文字母表循环右移0,1,2,25位，获得26个密文字母表，构成Vigenere方阵：,Vigenere方阵,Vigenere密码,设P = data security，k=best 则采用维吉尼亚密码的加密过程如下： 1.按密钥的长度将P分解若干节,2.对每一节明文，利用密钥best进行变换。 得到如下密文：C=EEK(P)=EELT TIUN SMLR,3.多名替代密码 为了抵抗频率分析攻击，希望密文中不残留明文字母的频率痕迹。一种明显的方法是设法将密文字母的频率分布拉平。这就是多名替代密码的出发点。 设明文

21、字母表A=a0,a1,an-1，对于每一个明文字母ai，作一个与之对应的字符集合bi ，且使bi中的字符个数正比于ai在明文中的相对频率，称bi为ai的多名字符集。以集合B=Bi|i=0,1,n-1作为密文字母表。定义映射函数：F:AB f(ai)=bji，而bjiBi 即映射函数f将明文字母ai映射到它的一个多名字符bji 。 设明文M=(m0,m1,mn-1) 则密文C=(f(m0),f(m1),f(mn-1)=(c0,c1,cn-1) ，其中ci是根据映射函数从多名字符集中随机选取的一个多名字符。 由于多名字符集合中的整数个数正比于相应字母的相对频率以及不同的多名字符集合间没有相同的整数

22、，而且每个多名字符的选取又是完全随机的，所以多名替代密码的密文字符频率分布是平坦的。这大大增强了密码的强度。,+,2.2.3 代数密码,异或运算（或称模2加运算）具有如下特点： 0 0 = 0; 0 1 = 1; 1 0 = 1; 1 1 = 0 a a = 0; a b b = a 即两个运算数相同，结果为0；不同，结果为1。 使用简单异或进行加密，就是将明文与密钥进行异或运算，解密则是对密文用同一密钥进行异或运算。即P k = C；C k = P 1917年美国电话电报公司的Gillbert Vernam为电报通信设计的Vernam密码就是将明文和密钥进行异或运算而得到密文的密码。Vern

23、am密码的突出特点是其加密运算和解密运算相同，都是异或运算。但它经不起已知明文攻击。 数学上，如果一个变换的正变换和逆变换相同，则称其为对合运算。对合运算可使加解密公用同一算法，工程实现的工作量减少一半。,+,+,+,+,+,+,+,+,2.2.4 古典密码的统计分析,任何自然语言都有许多固有的统计特性。如果自然语言的这种统计特性在密文中有所反映，则密码分析者便可以通过分析明文和密文的统计规律而将密码破译。 1.语言的统计特性 英文文献中，各英文字母的概率分布： A8.167;B1.492;C2.782;D4.253;E12.702;F2.228 G2.015;H6.094;I6.966;J0

24、.153;K0.772;L4.025; M2.406;N6.749;O7.507;P1.929;Q0.095;R5.987; S6.327;T9.056;U2.758;V0.978;W2.360;X0.150; Y1.974;Z0.074 其中，极高频率字母为E;次高为TAOINSHR;中等为DL;低频率为CUMWFGYPB;基低频率为VKJXQZ,不仅单字母以相对稳定的频率出现，而且双字母组和三字母组同样如此。 这些统计数据，对密码分析者都是十分重要的信息。此外，密码分析者的文学、历史、地理等方面的知识对于破译密码也是十分重要的因素。 2.古典密码分析 以简单替代密码为例。 对于加法密码，密

25、钥整数k只是n-1个不同的取值。对于明文字母表以英文字母表的情况，k只有25中可能的取值。即使是对于明文字母表以8位扩展ASCII码而言，k也只有255中可能的取值。因此，只要对k的可能取值逐一穷举就可破译加法密码。 乘法密码比加法密码更容易破译。因为密钥整数k要满足条件(n,k)=1，因此k只有(n)(即，n的欧拉函数)个不同的取值。去掉k=1这一恒等情况，k的取值只有(n)-1种。对于明文字母表为英文字母表的情况，k只能取3、5、7、9、11、15、17、19、21、23、25共11种不同的取值，比加法密码弱得多。,仿射密码的保密性能好些。其可能的密钥也只有n(n)-1种。对于明文字母表为

26、英文字母表的情形，可能的密钥只有26*12-1=311种。如果用计算机破译，则完全可以非常方便地破译出来。 本质上，密文字母表实际上是明文字母表的一种排列。设明文字母表含n个字母，则共有n!种排列，对于明文字母表为英文字母表的情况，可能的密文字母表有26!41026种。由于密钥词组代替密码的密钥词组可以随意选择，故这26!种不同的排列中的大部分被用作密文字母表也是不可能的。即使使用计算机，企图用穷举一切密钥的方法来破译密钥词组替代密码也是不可能的。那么，密钥词组替代密码是不是牢不可破呢？其实不然，因为穷举并不是攻击密码的唯一方法。这种密码仅在传输短的消息时是保密的，一旦消息足够长，密码分析者便

27、可利用其他的统计分析方法迅速破解之。,字母和字母组的统计数据对于密码分析者来说是十分重要的。因为它们可以提供有关密钥的许多信息。例如，由于字母E比其他字母的概率要高得多，如果是简单替代密码，那么可以预计大多密文都将包含一个频率比其他字母都高的字母。当出现这种情况时，完全可以猜测这个字母对应的明文字母就是E。 一般，破译单替代密码的大致过程： 首先，统计密文的各种统计特征，如果密文量比较多，则完成这步后便可确定出大部分密文字母； 其次，分析双字母、三字母密文组，以区分元音和辅音字母； 最后，分析字母较多的密文，在这一过程中大胆使用猜测的方法，如果猜对一个或几个词，就会大大加快破译过程。,2.3

28、DES和RSA,2.3.1 数据加密标准DES 2.3.2 公开密钥密码的基本概念 2.3.3 RSA密码,2.3.1 数据加密标准DES,为适应社会对计算机数据安全保密越来越高的需求，美国国家标准局NBS于1973年开始公开征集，并于1977年1月5号采纳IBM的加密算法作为数据加密标准的DES加密算法。 DES的设计目标：用于加密保护静态存储和传输信道中的数据，安全使用10-15年。 DES综合利用了置换、替代、代数等多种密码技术。它设计精巧、实现容易、使用方便，堪称是适应计算机环境的近代传统密码的一个典范。DES的设计充分体现了Shannon信息保密理论所阐述的设计密码的思想，标志着密码

29、的设计与分析达到了一个新的水平。 DES是一种分组密码。明文、密文和密钥的分组长度都是64位。 DES是面向二进制的密码算法，因而能够加解密任何形式的计算机数据。 DES是对合运算，因而加密和解密共用同一算法，从而使工程实现的工作量减半。,DES算法的特点,1）对称算法：既可用于加密，也可用于解密。不同之处在于解密时用了16个子密钥的顺序和加密时所用的16个子密钥的顺序是颠倒的 2）64位的密钥，使用长度为56位（64位明文中，有8位用于奇偶校验）。 3）加密算法是混淆与扩散的结合，或者说是换位与置换的结合。 4）每个DES都在明文上实施16重相同的组合技术。这种重复性可以被非常理想地应用到一

30、个专用芯片中。,DES加密过程细化,初始换位和逆初始换位； 将64位明文分为32位的左右两段：L0和R0； 进行16轮相同的迭代运算：混淆+异或+交换； 将最后左右两段合并； 生成每一轮的子密钥。,+,+,+,+,初始换位IP和逆初始换位IP-1,逆初始换位IP-1,初始换位IP,DES子密钥的生成,压缩变换PC-1与分割得到C0，D0,PC-1的作用是去掉奇偶校验位8，16，24，32，40，48，56，64后，按56位进行换位。,密钥移位每轮左移位数,压缩置换PC-2,DES的f算法,F算法的主要组成 E-盒 S-盒 P-盒,E-盒（Expansion Permutation,扩展置换）,

31、把数据明文的右半部分Ri从32位扩展到48位,S-盒代换,S-盒是进行了压缩后的密钥（56位48位）与扩展后的明文分组（32位48位）异或后进行的。目的是对48位的输入替代压缩成32位的输出。替代由8个S-盒进行。每个S-盒有6位输入，4位输出。,P-盒置换,对S-盒的32位输出进行一次换位,DES的安全性,1.对于其设计目标，DES是安全的 DES综合运用了置换、替代和代数等多种密码技术，是一种乘积密码。DSE算法中除了S盒是非线性变换外，其余变换均为线性变换，所以DES安全的关键是S盒。这个非线性变换的本质是数据压缩，它把6位的数据压缩成4位数据。S盒为DES提供了多种安全的密码特性。S盒

32、用来提供混淆，使明文、密钥、密文之间的关系错综复杂，而P置换用来提供扩散，把S盒提供的混淆作用充分扩散开来。这样，S盒和P置换互相配合，形成了很强的抗差分攻击和抗线性攻击能力，其中抗差分攻击能力更强一些。DES的子密钥产生和使用很有特色，它确保了原密钥中的各位的使用次数基本相等。实验证明，56位密钥的每一位的使用次数都在12-15之间。 应用实践证明DES作为商用密码，用于其设计目标是安全的。除因密钥太短经不起当今网络计算和并行计算的穷举攻击外，没有发现DES存在其他严重的安全缺陷。,DES的安全性,2. DES存在的安全弱点 1）密钥较短 2）存在弱密钥和半弱密钥 DES存在一些弱密钥和半弱

33、密钥。在16次加密迭代中分别使用不同的子密钥是确保DES安全强度的一种重要措施，但实际上却存在一些密钥，由它们产生的16个子密钥不是互不相同，而是有相重的。 产生弱密钥的原因是子密钥产生算法中的C和D寄存器中的数据在循环移位下出现重复所致。据此，可推出以下四种弱密钥（十六进制）： 01 01 01 01 01 01 01 01 1F 1F 1F 1F 1F 1F 1F 1F E0 E0 E0 E0 E0 E0 E0 E0 FE FE FE FE FE FE FE FE,DES的安全性,此外，DES还存在半弱密钥。设k是给定的密钥，如果由k所产生的子密钥中存在重复者，但不是完全相同，则称k为半弱

34、密钥。以下半弱密钥所产生得16个子密钥中只有两种不同的子密钥，每种出现8次： 01 FE 01 FE 01 FE 01 FE FE 01 FE 01 FE 01 FE 01 1F E0 1F E0 1F E0 1F E0 E0 1F E0 1F E0 1F E0 1F 弱密钥和半弱密钥的存在无疑是DES的一个不足，但由于它们的数量与密钥总数256相比仍是微不足道的，所以这并不构成对DES太大的威胁，只要注意在实际应用中不使用它们就可以了。 3）存在互补对称性 设C=DES(M,K),则C=DES(M,K),其中M,C,K表示M,C,K的非，密码学上称这种特性为互补对称性。互补对称性使DES在选

35、择明文攻击下所需的工作量减半。,其他对称加密算法,IDEA（international data encryption algorithm，国际数据加密算法） 分组加密算法，分组长度为64b， 密钥长度128b； 核心由8轮迭代和一个输出变换组成，能使明码数据更好地扩散和混淆； 运算过程只需使用下面三种简单运算： 逐个的位异或； 模216加； 模（216+1）乘。 有专利限制。,AES（advanced encryption standard，高级加密标准）。 分组算法，分组大小为128b 密钥长度可以是128b、192b或256b，分别称为AES-128、AES-192、AES-256。 无

36、专利限制,2.3.2 公开密钥密码的基本概念,使用传统密码进行保密通信，通信双发必须首先预约持有相同的密钥才能进行。而私人和商业之间想通过通信工具洽谈生意又要保持商业秘密，有时很难做到事先预约密钥。另外，对于大型计算机网络，设有n个用户，任意两个用户之间有可能进行通信，共有n(n-1)/2种不同的通信方式，当n较大时，这个数目很大。从安全角度考虑，密钥应当经常更换，这样，在网络上产生、存储、分配并管理如此大量的密钥，其复杂性和危险性巨大。 1.公开密钥密码的基本思想 将传统密码中密钥k一分为二，分为加密密钥Ke和解密密钥Kd，并在计算复杂度上保证加密密钥Ke在计算上不能推导出解密密钥Kd 。这

37、样，即使将公开Ke也不会暴露Kd ，也不会损害密码的安全。如此，就从根本上克服了传统密码在密钥分配上的困难。,一个公开密钥密码应当满足以下三个条件： 解密算法D与加密算法E互逆，即对于所有明文M都有D(E(M,Ke),Kd)=M 在计算上不能由Ke求出Kd 算法E和D都是高效的 条件是公开密钥密码的安全条件，是公开密钥密码的安全基础。而且也是最难满足的。由于数学水平的限制，目前尚不能从数学上证明一个公开密钥密码完全满足这一条件，而只能证明不满足这一条件。 条件是公开密钥密码的实用条件，因为只有算法D和E都是高效的，密码才能实际应用。 满足以上三个条件，便可构成一个公开密钥密码，而且这个密码可以

38、确保数据的秘密性。而如果还要求确保数据的真实性，则应满足第四个条件： 对于所有明文M都有E(D(M,Kd),Ke)=M 条件是公开密钥密码能够确保数据真实性的基本条件。如果满足了条件、和 ，同样也可构成一个公开密钥密码，而且可以确保数据的真实性。 如果同时满足以上四个条件，则公开密钥密码可同时确保数据的秘密性和真实性。,2.基本工作方式 设M为明文，C为密文，E为加密算法，D为解密算法，Ke为公开的加密密钥，Kd为保密的解密密钥，每个用户都分配一对密钥，而且将所有用户的公开的加密密钥存入共享的密钥库PKDB中。 再设用户A要把数据M安全保密地传送给B，有以下三种通信协议： 1）确保数据的秘密性

39、 A：从PKDB中查B公开的加密密钥用B公开的加密密钥加密M得到密文C把C发给B B：用自己保密的解密密钥解密C，得到明文M 由于只有用户B才拥有保密的解密密钥，而且由公开的加密密钥在计算上不能推出保密的解密密钥，所以只有用户B才能获得明文M，从而确保了数据的秘密性。 然而，该通信协议并不能保证数据的真实性。因为PKDB是共享的，任何人都可以查到B公开的加密密钥，因此任何人都可以冒充A发送假数据给B，而不被B发现。,2）确保数据的真实性 A：用自己保密的解密密钥解密M，得到密文C 把C发给B B：从PKDB中查A公开的加密密钥用A公开的加密密钥加密C得到密文M 由于只有A才拥有保密的解密密钥，

40、而且由A公开的加密密钥在计算上不能推出保密的解密密钥，所以只有用户A才能发送数据M，任何人都不能冒充A发送M，从而保证了数据的真实性。 但是，因为PKDB是共享的，任何人都可以获得A公开的加密密钥，所以任何人都可以获得数据M 3）同时确保数据的秘密性和真实性 A：用自己保密的解密密钥解密M，得到中间密文S 从PKDB中查B公开的加密密钥用B公开的加密密钥加密S得到密文C把C发给B B：用自己保密的解密密钥解密C，得到中间密文S从PKDB中查A公开的加密密钥，并用之加密S，得到明文M,2.3.3 RSA密码,Ronald L. Rivest,Leonard M. Adleman,RSA（Rive

41、st,Shamir,Adleman）算法是1978年由R.Rivest、A.Shamir和I.Adleman提出的一种基于数论方法、也是理论上最为成熟的公开密钥体制，并已经得到广泛应用。,Adi Shamir,RSA数学基础,1. 费尔玛（Fermat）定理 描述1：若p是素数，a是正整数且不能被p整除，则ap-1 1 mod p。 描述2：对于素数p，若a是任一正整数，则ap a（mod p）。 例2.1 设p=3，a=2，则23-1=4 1 （mod 3）或23=82（mod 3）。 例2.2 设p=5，a=3，则35-1=81 1 （mod 5）或35=2433（mod 5）。,2. 欧

42、拉函数 欧拉（Euler）函数(n)表示小于n，并与n互素的正整数的个数。 例2.3 (6) = 2 1，5；(7) = 6 1，2，3，4，5，6；(9) = 6 1，2，4，5，7，8。 3. 欧拉（Euler）定理 欧拉定理：若整数a和m互素，则 a(m) 1 (mod m) 例2.4 设a=3，m=7，则有(7)=6，36=729，729 1(mod 7) 例2.5 设a=4，m=5，则有(5)=2，42=16，16 1(mod 5),RSA密钥的产生,基本过程： 选两个保密的大素数p和q （保密）。 计算n=pq（公开），(n)= (p-1)(q-1) （保密）。 随机选取一整数e，

43、满足1e(n)且gcd(n),e)=1（公开）。 计算d，满足de 1(mod (n) （保密）。 得到一对密钥：公开密钥：e,n，秘密密钥：d,n。 例子： 选择两个素数p = 7，q = 17 计算n = pq = 717 = 119 计算n的欧拉函数(n) = ( p - 1)(q - 1) = 616 = 96。 从0，95间选一个与96互质的数e = 5 根据式 5d = 1 mod 96 解出d=77，因为ed = 577=385=496+11 mod 96 得到公钥PK = (e,n) = 5,119，密钥SK = 77,119。,RSA加密/解密过程,基本过程： 1）明文数字化

44、，即将明文转换成数字串 2）分组。将二进制的明文串分成长度小于log2n的分组 3）加密算法 Ci=Mie（mod n） 最后得到的密文C由长度相同的分组Ci组成 4）解密算法 D(C) Cd (mod n),RSA加密/解密过程,例子： 1）产生密钥 设：p=43, q=59, n=4359=2537, (n)=4258=2436 取e=13（与(n)没有公因子）解方程 de （mod 2436）, 2436 = 13187+5, 5=2436-13187：13=25+3，3=13-25 1 = 3-2 = 3-(5-3)=23-5=2(13-25)-5=213-55=213-5(2436-

45、13187) =(1875+2)13-52436=93713-52436 即：937131(mod 2436) 故 e=13， d=937 2）加/解密 明文：public key encryptions 明文分组：pu bl ic ke ye nc ry pt io ns 明文数字化（按字母序，令a=00,b=01,c=02,，y=24,z=25）： 1520 0111 0802 1004 2404 1302 1724 1519 0814 1418 加密按照算法Mie（mod n）=Ci，如152013（mod 2537）=0095得到密文 0095 1648 1410 1299 1365

46、1379 2333 2132 1751 1289 解密：按照算法Cie（mod n）= Mi，如009513（mod 2537）= 1520。,RSA密钥的安全性,小合数的因子分解是容易的，但大合数的因子分解却是十分困难的。 密码分析者攻击RSA密码的一种可能的途径是截获密文C，从而求出明文M。 因为MCd (mod n),n是公开的，要从C中求出明文M，必须先求出d，而d是保密。 又因为ed1(mod (n),而e又是公开的，要从中求出d，必须先求出(n)，而(n)是保密的。 又因为(n)=(p-1)(q-1)，则要从中求出必须先求出p和q，而p和q是保密的。 又因为n=pq，这样要从n中求

47、出p和q，只有对n进行因子分解。 而当n足够大时，这是很困难的,2.4 PGP,PGP是一款国际顶级加密软件，可用于文件加密、电子邮件加密。PGP综合了传统加密方法和公开密钥加密方法的优点，是一种杂交的方法。当用户使用PGP来加密明文时，PGP首先要压缩明文（数据压缩可以节省传输时间和磁盘空间，还可以加强密文的安全性），其创造性在于把RSA公钥体系的方便和传统加密体系的高速度结合起来，并且在数字签名和密钥认证管理机制上有巧妙的设计。因而，PGP成为最流行的公钥加密软件包之一。 1991年，Phil Zimmermann推出PGP加密软件第一版，其核心就是RSA算法。目前版本的下载地址： htt

48、p:/web.mit.edu/network/pgp.html http:/www.pgpi.org 提供的软件版本: PGP6.5.8 参考手册：参见PGP教程,2.5 社会工程学密码分析器,社会工程学（Social Engineering），一种通过对受害者心理弱点、本能反应、好奇心、信任、贪婪等心理陷阱进行诸如欺骗、伤害等危害手段，取得自身利益的手法。社会工程学讲究的就是人们在社交过程中的心态，习惯，这些心态，习惯就是一条纽带，能够把你所有的信息串联起来。 http:/ 工具: 亦思社会工程学字典生成器,本讲可选题,1.古典密码加解密算法的实现，要求如下： 具有置换密码、单表替代密码中的加法密码、乘法密码和仿射密码、Vigenere密码以及代数密码的加密和解密功能； 具有加解密速度统计功能； 具有良好的人机界面。 2.古典密码破译算法的实现，要求如下： 具有置换密码、单表替代密码中的加法密码、乘法密码和仿射密码、Vigenere密码以及代数密码的破解算法； 具有破解速度统计功能； 具有良好的人机界面。 3.以DES作为加密算法开发文件加密软件系统，软件要求如下： 具有文件加密和解密功能； 具有加解密速度统计功能； 具有良好的人机界面。,4.密钥管理，要求如下： 陈述现有的各种密钥管理机制，并比较其优劣； 陈述正确、条理清晰，具有反映个人思考所得的内容。 5.数据完整性：H