第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.古典密码分析 以简单替代密码为例。 对于加法密码,密
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 密码学 PGP 社会 工程学 密码 分析器
链接地址:https://www.31doc.com/p-2908965.html