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

第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年香农香农发表保密系统的通信理论保密系统的通信理论，把密 把密 码学置于坚实的数学基础上码学置于坚实的数学基础上，标志着密码学作为一门 科学的形成； 1976年W. Diffie和M. Hellman提出公开密钥密码公开密钥密码 ，从而开创了一个密码新时代； 1977年美国联邦政府颁布数据加密标准数据加密标准DESDES； 1994年美国联邦政府颁布密钥托管加密标准密钥托管加密标准EESEES， 同年颁布数字签名标准数字签名标准DSSDSS，2001年颁布高级加密标高级加密标 准准AESAES； 目前，量子密码量子密码因其具有可证明的安全性，同时 还能对窃听行为进行检测，从而研究广泛；生物信息 技术的发展也推动了DNA计算机和DNADNA密码密码的研究 自古以来，密码主要用于军事、政治、外 交等要害部门，因而密码学的研究工作本身也 是秘密进行的。后来，随着计算机网络的普及 ，电子政务、电子商务和电子金融等对确保信 息安全的需求的增加，民间出现了一些不从属 于保密机构的密码学者。实践证明，正是这种 公开研究和秘密研究相结合的局面促进了今天公开研究和秘密研究相结合的局面促进了今天 密码学得空前繁荣密码学得空前繁荣。 研究密码编制的科学称为密码编制学密码编制学 (Cryptography) ；研究密码破译的科学称为 密码分析学密码分析学(Cryptannalysis)；密码编制学和 密码分析学共同组成密码学密码学(Cryptology)。 密码学的基本思想是伪装信息基本思想是伪装信息，使未授权者不 能理解它的真实含义。所谓伪装伪装就是对数据进行 一组可逆的数学变换。伪装前的原始数据称为明明 文文(Plaintext)，伪装后的数据称为密文密文 (Ciphertext)，伪装的过程称为加密加密(Encryption) 。加密在加密密钥加密密钥(Key)的控制下进行。用于对数 据加密的一组数学变换称为加密算法加密算法 发信者将明文数据加密成密文，再将密文数据 送入网络传输或存入计算机文件，而且只给合法 收信者分配密钥。 合法收信者接收到密文后，施行与加密变换相 逆的变换，去掉密文的伪装恢复出明文，这一过 程称为解密解密(Decryprion)。解密在解密密钥 解密密钥的控 制下进行。用于解密的一组数学变换称为解密算解密算 法法，而且解密算法是加密算法的逆解密算法是加密算法的逆。 2.1.1 密码体制 明 文 加 密 算 法 信 道 明 文 解 密 算 法 MM 攻击者 CC 加密密钥加密密钥 安全信道 密钥K KeKd 一个密码系统通常简称为密码体制密码体制(Cryptosystem) ，由五部分组成： 明文空间明文空间M，它是全体明文的集合； 密文空间密文空间C，它是全体密文的集合； 密钥空间密钥空间K，它是全体密钥的集合。其中，每一 个密钥K均由加密密钥Ke和解密密钥Kd组成，即K= 加密算法加密算法E，它是一族由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公开。这 种密码体制称为公开密钥密码体制公开密钥密码体制，简称公开密码体公开密码体 制制。 根据明密文的划分和密钥的使用不同，可将密码 体制分为分组密码和序列密码体制。 设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) 分组密码每一次加密一个明文块，而序列密码每 一次加密一位或一个字符。序列密码是要害部门使用 的主流密码，而商用领域则多用分组密码。 根据加密算法在使用过程中是否变化，可将密码 体制分为固定算法密码体制和演化密码体制。固定算固定算 法密码体制法密码体制的加解密算法固定不变；而演化密码体制演化密码体制 将密码学和演化计算相结合，使得在加密过程中加密 算法也不断演化。 2.1.2 密码分析 如果能够根据密文系统地确定出明文或密钥，或 者能够根据明文-密文对系统地确定出密钥，则称这 个密码是可破译的可破译的。研究密码破译的科学称为密码分 密码分 析学析学。密码分析者攻击密码的方法主要有三种： 1）穷举攻击穷举攻击 穷举攻击穷举攻击是指密码分析者采用依次试遍所有可能依次试遍所有可能 的的密钥对所获得的密文进行解密，直至得到正确的明 文；或者用一个确定的密钥对所有可能的明文进行加 密，直至得到所获得的密文。 理论上，对于任何使用密码只要有足够的资源都理论上，对于任何使用密码只要有足够的资源都 可以用穷举攻击将其攻破可以用穷举攻击将其攻破。从平均角度讲，采用穷举 攻击破译一个密码必须试遍所有可能密钥的一半。 穷举攻击所花费的时间等于尝试次数乘以一次解 密或加密所需的时间。可以通过增大密钥量或加大解通过增大密钥量或加大解 密或加密算法的复杂性来对抗穷举攻击密或加密算法的复杂性来对抗穷举攻击。 2）统计分析攻击统计分析攻击 统计分析攻击统计分析攻击是指密码分析者通过分析密文和明 文的统计规律统计规律来破译密码。 统计分析攻击在历史上为破译古典密码作出过很 大贡献。对抗统计分析攻击的方法是设法使明文的统 计特性不带入密文。这样，密文不带有明文的痕迹， 从而使统计分析攻击成为不可能。 3）数学分析攻击数学分析攻击 数学分析攻击数学分析攻击是指密码分析者对加解密算法的数数 学基础和某些密码学特性学基础和某些密码学特性，通过数学求解的方法来破 译密码。 数学分析攻击是对基于数学难题的各种密码的主 要威胁，为此，应当选用具有坚实数学基础和足够复 杂的加解密算法。 此外，根据密码分析者可利用的数据资源来分类 ，可将攻击密码的类型分为以下四种： 1）仅知密文攻击仅知密文攻击 仅知密文攻击仅知密文攻击是指密码分析者仅根据截获的密文 来破译密码。 2）已知明文攻击已知明文攻击 已知明文攻击已知明文攻击是指密码分析者根据已知的某些明 文-密文对来破译密码。 3）选择明文攻击选择明文攻击 选择明文攻击选择明文攻击是指密码分析者能够选择明文并获 得相应的密文。 4）选择密文攻击选择密文攻击 选择密文攻击选择密文攻击是指密码分析者能够选择密文并获 得相应的明文。这种攻击主要攻击公开密钥密码体制 ，特别是攻击其数字签名。 一个密码，如果无论密码分析者截获多少密文和 用什么技术方法进行攻击都不能被攻破，则称该密码 是绝对不可破译的绝对不可破译的。绝对不可破译的密码在理论上是 存在的，这就是著名的“一次一密一次一密”密码密码。但是，由 于密钥管理上的困难，“一次一密”密码是不实用的。 理论上，如果能够获得足够的资源，那么任何实际可理论上，如果能够获得足够的资源，那么任何实际可 使用的密码又都是可破译的使用的密码又都是可破译的。 如果一个密码，不能被密码分析者根据可利用的 资源所破译，则称其是计算上不可破译计算上不可破译的。因为任何 秘密都有其时效性，因此，对我们更有意义的是在计 算上不可破译的密码。 2.1.3 密码学的理论基础 1949年，shannon发表的保密系统的通信理论从信息论 的角度对信息源、密钥、加密和密码分析进行了数学分析，用 不确定性和唯一解距离来度量密码体制的安全性，阐明了密码 体制、完善保密、纯密码、理论保密和实际保密等重要概念， 把密码置于坚实的数学基础之上，标志着密码学作为一门独立 学科的形成。从此，信息论信息论成为密码学重要的理论基础之一。 ShannonShannon建议采用扩散、混淆和乘积迭代的方法设计密码建议采用扩散、混淆和乘积迭代的方法设计密码 ，并且以“揉面团”的过程形象地比喻扩散、混淆和乘积迭代的 概念。所谓扩散扩散就是将每一位明文和密钥数字的影响扩散到尽 可能多得密文数字中。理想状态下，明文和密钥的每一位都影 响密文的每一位，一般称这种情形达到“完备性”。所谓混淆混淆就 是是密文和密钥之间的关系复杂化。密文和密钥之间的关系越 复杂，则密文和明文之间、密文和密钥之间的统计相关性越小 ，从而使统计分析不能奏效。设计一个复杂密码一般是比较困 难的，利用乘积迭代方法乘积迭代方法对简单密码进行组合迭代，可以得到 理想的扩散和混淆，从而可以得到安全的密码。 计算复杂性理论计算复杂性理论是密码学的另一个理论基础。为计算求解 一类问题，总需要一定量的时间资源和空间资源。消耗资源的 多少取决于要求解问题的规模大小。 设要求解的问题规模（如，输入变量的个数或输入长度） 为n，若对于所有的n和所有长度为n的输入，计算最多要用f(n) 步完成，则称该问题的计算复杂度计算复杂度为f(n)。若f(n)为n的多项式 ，则称其为多项式复杂度多项式复杂度。 粗略的讲，计算机可以在多项式时间复杂度内解决的问题 称为P P类问题类问题；否则，为NPNP类问题类问题。P类问题是计算机可计算的 ，而NP问题是计算机不可计算的困难问题。NP问题中最难得 问题称为NPNP完全问题完全问题，即NPC问题。 Shannon指出设计一个安全的密码本质上就是要寻找一个设计一个安全的密码本质上就是要寻找一个 难解的问题难解的问题。这样，计算复杂性理论的发展将直接影响密码的 安全。 此外，密码的设计应该遵循公开设计原则密码的设计应该遵循公开设计原则。密码体制的安密码体制的安 全仅依赖于密钥的保密，而不应依赖于对算法的保密全仅依赖于密钥的保密，而不应依赖于对算法的保密。当然， 密码设计的公开原则并不等于所有的密码在应用时都要公开加 密算法。也就是说，在公开的原则下设计密码，在实际使用时在公开的原则下设计密码，在实际使用时 对算法保密对算法保密，将会更加安全。 2.2 古典密码 2.2.1 置换密码 2.2.2 替代密码 2.2.3 代数密码 2.2.4 古典密码的统计分析 2.2.1 置换密码 把明文中的字母重新排列，字母本身不变，但其 位置改变，这样编成的密码称为置换密码置换密码。 最简单最简单的置换密码是把明文中字母顺序颠倒字母顺序颠倒过来 ，然后截成固定长度的字母组作为密文。 例如： 明文：明晨5点发动反攻。 ming chen wu dian fa dong fan gong 密文：gnogn afgno dafna iduwn ehcgn im 倒序的置换密码显然是很弱的。 另一种置换密码另一种置换密码是把明文按某一顺序排成一个矩矩 阵阵，其中不足部分用填充，而是明文中不会出现 的一个符号；然后按另一个顺序另一个顺序选出矩阵中的字母以 形成密文，最后截成固定长度的字母组截成固定长度的字母组作为密文。 明文：WHAT CAN YOU LEARN FROM THIS BOOK” 明文矩阵： 举例 明 文 WHATCANY OULEARNF ROMTHISB OOK选出顺序：按列 密文：WORO HUOO ALMK TET CAH ARI NNS YFB 可以看出，改变矩阵的大小和选出顺序可以得到不同形式的密码改变矩阵的大小和选出顺序可以得到不同形式的密码 。一种巧妙的方法方法：首先选一个词语作为密钥选一个词语作为密钥，去掉重复字母； 然后按字母的字典顺序给密钥字母编号按字母的字典顺序给密钥字母编号，并按照密钥的长度把明按照密钥的长度把明 文排列成矩阵文排列成矩阵；最后按按照数字序列中的数字顺序按列选出密文数字顺序按列选出密文 密钥：k=computer 明文：WHAT CAN YOU LEARN FROM THIS BOOK” 按密钥排列明文： 举例 密 钥COMPUTER 顺序号14358726 明 文 WHATCANY OULEARNF ROMTHISB OOK 密文： WORO NNS ALMK HUOO TET YFB ARI CAH 2.2.2 替代密码 首先构造一个或多个密文字母表，然后用密文字 母表中的字母或字母组来替代明文字母或字母组，各 字母或字母组的相对位置不变，但其本身改变，这样 编成的密码称为替代密码替代密码。 按照替代所使用的密文字母表的个数按照替代所使用的密文字母表的个数可将替代密 码分为分为单表替代密码、多表替代密码和多名替代密码 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）加法密码加法密码 加法密码的映射函数： f(ai)=bi=aj，j=j=i+ki+k mod n,k是0kn的正整数 著名的加法密码是古罗马的凯撒大帝使用的密码 Caesar密码取k=3，因此其密文字母表就是把明文字 母表循环右移3位后得到的字母表。 2）乘法密码乘法密码 乘法密码的映射函数： f(ai)=bi=aj，j=j=ikik mod n 其中，要求要求k k和和n 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)=f(D)=f(F)=f(Z)=N 这样，密文字母表变为B=A,N,A,N,A,N,A,N 3）仿射密码仿射密码 乘法密码和加法密码相结合就构成了仿射密码。仿射 密码的映射函数： f(ai)=bi=aj，j=ikj=ik 1 1 +k+k 0 0 mod n 其中，要求要求k k 1 1 和和n n互素，互素，0=k0=k 0 0 n,n,且不允许同时有且不允许同时有k k 1 1 =1 =1 k k0 0 =0=0。 4）密钥词语替代密码密钥词语替代密码 首先随机选用一个词组或短语作为密钥随机选用一个词组或短语作为密钥，去掉重复字 母，把结果作为矩阵的第一行；其次，在明文字母表中去 掉矩阵第一行中的字母，并将剩余字母依次写入矩阵的其 余行；最后按某一顺序从矩阵中取出字母构成密文字母表 。例如： 密钥：H O N G Y E 矩阵：H O N G Y E选出顺序：按列 A 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),) 由于加密用到了多个密文字母表，故称为多表替多表替 代密码代密码。多表替代密码的密钥就是这组映射函数或密 文字母表。 最著名的多表替代密码是16世纪法国密码学者 Vigenere使用的VigenereVigenere密码密码。它依次把明文字母表 循环右移0,1,2,25位，获得26个密文字母表，构成 Vigenere方阵： Vigenere方阵 明文a b c d ef g hijkl m n o p q rstu v w x y z aA B C D E F G H IJ K L M N O P Q R S T U V W X Y Z bB C D E F G H IJ K L M N O P Q R S T U V W X Y Z A eE F G H IJ K L M N O P Q R S T U V W X Y Z A B C D sS T U V W X Y Z A B C D E F G H IJ K L M N O P Q R tT U V W X Y Z A B C D E F G H IJ K L M N O P Q R S zZ A B C D E F G H IJ K L M N O P Q R S T U V W X Y Vigenere密码 设P = data security，k=best 则采用维吉尼亚密码的加密过程如下： 1.按密钥的长度将P分解若干节 2.对每一节明文，利用密钥best进行变换。 得到如下密文：C=EEK(P)=EELT TIUN SMLR 密钥best 明 文 data secu rity 3.多名替代密码多名替代密码 为了抵抗频率分析攻击，希望密文中不残留明文字母 的频率痕迹。一种明显的方法是设法将密文字母的频率分 布拉平。这就是多名替代密码的出发点出发点。 设明文字母表A=a0,a1,an-1，对于每一个明文字母ai ，作一个与之对应的字符集合bi ，且使bi中的字符个数正 比于ai在明文中的相对频率，称bi为ai的多名字符集。以集 合B=Bi|i=0,1,n-1作为密文字母表。定义映射函数： F:ABf(ai)=bji，而bjiBi 即映射函数f将明文字母ai映射到它的一个多名字符bji 。 设明文M=(m0,m1,mn-1) 则密文C=(f(m0),f(m1),f(mn-1)=(c0,c1,cn-1) ，其中ci 是根据映射函数从多名字符集中随机选取随机选取的一个多名字符 。 由于多名字符集合中的整数个数正比于相应字母的相 对频率以及不同的多名字符集合间没有相同的整数，而且 每个多名字符的选取又是完全随机的，所以多名替代密码多名替代密码 的密文字符频率分布是平坦的的密文字符频率分布是平坦的。这大大增强了密码的强度 。 + 2.2.3 代数密码 异或运算（或称模异或运算（或称模2 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密码就是将明文和密钥进行异或运 算而得到密文的密码。VernamVernam密码的突出特点是其加密码的突出特点是其加 密运算和解密运算相同密运算和解密运算相同，都是异或运算。但它经不起经不起 已知明文攻击已知明文攻击。 数学上，如果一个变换的正变换和逆变换相同， 则称其为对合运算对合运算。对合运算可使加解密公用同一算 法，工程实现的工作量减少一半工程实现的工作量减少一半。 + + + 2.2.4 古典密码的统计分析 任何自然语言都有许多固有的统计特性。如果自 然语言的这种统计特性在密文中有所反映，则密码分 析者便可以通过分析明文和密文的统计规律而将密码通过分析明文和密文的统计规律而将密码 破译破译。 1.语言的统计特性语言的统计特性 英文文献中，各英文字母的概率分布： A8.167;B1.492;C2.782;D4.253;E12.702;F2.228 G2.015;H6.094;I6.966;J0.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.古典密码分析古典密码分析 以简单替代密码简单替代密码为例。 对于加法密码加法密码，密钥整数k只是n-1个不同的取值。对 于明文字母表以英文字母表的情况，k只有25中可能的取 值。即使是对于明文字母表以8位扩展ASCII码而言，k也 只有255中可能的取值。因此，只要对只要对k 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*12-1=311种。如果用计算机破译 ，则完全可以非常方便地破译出来。 本质上，密文字母表实际上是明文字母表的一种本质上，密文字母表实际上是明文字母表的一种 排列排列。设明文字母表含明文字母表含n n个字母个字母，则共有n!n!种排列种排列， 对于明文字母表为英文字母表的情况，可能的密文字可能的密文字 母表母表有26!4102626!41026种种。由于密钥词组代替密码的密 钥词组可以随意选择，故这26!种不同的排列中的大 部分被用作密文字母表也是不可能的。即使使用计算 机，企图用穷举一切密钥的方法来破译密钥词组替代 密码也是不可能的。那么，密钥词组替代密码是不是 牢不可破呢？其实不然，因为穷举并不是攻击密码的穷举并不是攻击密码的 唯一方法唯一方法。这种密码仅在传输短的消息时是保密的，这种密码仅在传输短的消息时是保密的， 一旦消息足够长，密码分析者便可利用其他的统计分一旦消息足够长，密码分析者便可利用其他的统计分 析方法迅速破解之析方法迅速破解之。 字母和字母组的统计数据对于密码分析者来说是字母和字母组的统计数据对于密码分析者来说是 十分重要的十分重要的。因为它们可以提供有关密钥的许多信息 。例如，由于字母E比其他字母的概率要高得多，如 果是简单替代密码，那么可以预计大多密文都将包含密文都将包含 一个频率比其他字母都高的字母一个频率比其他字母都高的字母。当出现这种情况时 ，完全可以猜测这个字母对应的明文字母就是完全可以猜测这个字母对应的明文字母就是E E。 一般，破译单替代密码的大致过程破译单替代密码的大致过程： 首先，统计密文的各种统计特征统计密文的各种统计特征，如果密文量比 较多，则完成这步后便可确定出大部分密文字母确定出大部分密文字母； 其次，分析双字母、三字母密文组分析双字母、三字母密文组，以区分元音 和辅音字母； 最后，分析字母较多的密文分析字母较多的密文，在这一过程中大胆大胆 使用猜测的方法使用猜测的方法，如果猜对一个或几个词，就会大大 加快破译过程。 2.3 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-1510-15年年。 DES综合利用了置换、替代、代数等多种密码技术综合利用了置换、替代、代数等多种密码技术。它设 计精巧、实现容易、使用方便，堪称是适应计算机环境的近代 传统密码的一个典范。DES的设计充分体现了充分体现了ShannonShannon信息保信息保 密理论所阐述的设计密码的思想密理论所阐述的设计密码的思想，标志着密码的设计与分析达 到了一个新的水平。 DES是一种分组密码分组密码。明文、密文和密钥的分组长度都是 6464位位。 DES是面向二进制的密码算法面向二进制的密码算法，因而能够加解密任何形式 的计算机数据。 DES是对合运算对合运算，因而加密和解密共用同一算法加密和解密共用同一算法，从而使 工程实现的工作量减半。 DES算法的特点 1）对称算法对称算法：既可用于加密，也可用于解密。不同之处在于解密时用了 不同之处在于解密时用了 1616个子密钥的顺序和加密时所用的个子密钥的顺序和加密时所用的1616个子密钥的顺序是颠倒的个子密钥的顺序是颠倒的 2）64位的密钥密钥，使用长度为使用长度为5656位位（64位明文中，有8位用于奇偶校验） 。 3）加密算法是混淆与扩散的结合混淆与扩散的结合，或者说是换位与置换的结合换位与置换的结合。 4）每个DES都在明文上实施在明文上实施1616重相同的组合技术重相同的组合技术。这种重复性可以被非 常理想地应用到一个专用芯片中。 初始换位 56位密钥 64位密文组 64位明文组 16轮加密变换生成16个48位子密钥 压缩变换 逆初始换位 56位密钥 DES 64位明文组64位密文组 56位密钥 D E S 加 密 过 程 细 化 初始换位和逆 初始换位； 将64位明文分 为32位的左右两 段：L0和R0； 进行16轮相同 的迭代运算：混 淆+异或+交换； 将最后左右两 段合并； 生成每一轮的 子密钥。 64位明文组 初始换位IP 得到L0得到R0 f + K1 L1=R0R1=L0 f(R0,K1) f + K2 L2=R1R2=L1 f(R1,K2) f + L15=R14 R15=L14 f(R14,K15) f Ki + R16=L15 f(R15,K16)L16=R15 逆初始换位IP-1 K16 64位密文组 + + + + 初始换位IP和逆初始换位IP-1 408481656246432 397471555236331 386461454226230 375451353216129 364441252206028 353431151195927 342421050185826 33141949175725 585042342618102 605244362820124 625446383022146 645648403224168 57494133251791 595143352719113 615345372921135 635547393123157 逆初始换位IP-1 初始换位IP D E S 子 密 钥 的 生 成 64位密钥 56位密钥 压缩变换PC-1 分割得到C0，D0 左移左移 压缩变换PC-2 左移左移 压缩变换PC-2 左移左移 压缩变换PC-2 K1 K2 K16 （48位） （48位） （48位） 28位28位 压缩变换PC-1与分割得到C0，D0 PC-1的作用是去掉奇偶校验位8，16，24，32，40 ，48，56，64后，按56位进行换位。 C0=k57k49k41k52k44k36 D0=k43k55k47k20k12k4 5749413325179 1585042342618 1025951433527 1911360524436 63554739312315 762544638022 1466153453729 211352820124 密钥移位每轮左移位数 压缩置换PC-2 轮 数12345678910111213141516 移动位数1122222212222221 1417112415 3281562110 2319124268 1672720132 415231374755 304051453348 444939563453 464250362932 DES的f算法 F算法的主要组成 E-盒 S-盒 P-盒 32位Ri-1 + 48位Ki P-盒置换 32位Li-1 E-盒扩展置换 S-盒替代 + 32位Ri32位Li 48位 32位 48位 32位 E-盒（Expansion Permutation,扩展置换 ） 把数据明文的右半部分Ri从32位扩展到48位 12345678910111213141516输入 12345678910111213141516171819202122232448输出 12345678910111213141516（对应输入）459813 1217 25 1632 S-盒代换 S-盒是进行了压缩后的密钥（56位48位）与 扩展后的明文分组（32位48位）异或后进行的 。目的是对48位的输入替代压缩成32位的输出。 替代由8个S-盒进行。每个S-盒有6位输入，4位 输出。 S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8 48位输入 32位输出 P-盒置换 16720212912281711523265183110 28241432273919133062211425 对S-盒的32位输出进行一次换位 DES的安全性 1.对于其设计目标，对于其设计目标，DESDES是安全的是安全的 DES综合运用了置换、替代和代数等多种密码技术， 是一种乘积密码乘积密码。DSE算法中除了S盒是非线性变换外， 其余变换均为线性变换，所以DESDES安全的关键是安全的关键是S S盒盒。这个 非线性变换的本质是数据压缩，它把6位的数据压缩成4位 数据。S盒为DES提供了多种安全的密码特性。S S盒用来提盒用来提 供混淆供混淆，使明文、密钥、密文之间的关系错综复杂，而P P 置换用来提供扩散置换用来提供扩散，把S盒提供的混淆作用充分扩散开来 。这样，S盒和P置换互相配合，形成了很强的抗差分攻形成了很强的抗差分攻 击和抗线性攻击能力击和抗线性攻击能力，其中抗差分攻击能力更强一些。 DES的子密钥产生和使用子密钥产生和使用很有特色，它确保了原密钥中的确保了原密钥中的 各位的使用次数基本相等各位的使用次数基本相等。实验证明，56位密钥的每一位 的使用次数都在12-15之间。 应用实践证明实践证明DESDES作为商用密码，用于其设计目标是作为商用密码，用于其设计目标是 安全的安全的。除因密钥太短经不起当今网络计算和并行计算的 穷举攻击外，没有发现DES存在其他严重的安全缺陷。 DES的安全性 2. DES存在的安全弱点 1）密钥较短密钥较短 2）存在弱密钥和半弱密钥存在弱密钥和半弱密钥 DES存在一些弱密钥和半弱密钥。在16次加密迭代中 分别使用不同的子密钥是确保DES安全强度的一种重要措 施，但实际上却存在一些密钥，由它们产生的存在一些密钥，由它们产生的1616个子密钥个子密钥 不是互不相同，而是有相重的不是互不相同，而是有相重的。 产生弱密钥的原因是子密钥产生算法中的产生弱密钥的原因是子密钥产生算法中的C C和和D 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为半半 弱密钥弱密钥。以下半弱密钥所产生得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的一个不足，但由于 它们的数量与密钥总数数量与密钥总数2 256 56相比仍是微不足道的 相比仍是微不足道的，所以这并不 构成对DES太大的威胁，只要注意在实际应用中不使用它们就在实际应用中不使用它们就 可以了可以了。 3）存在互补对称性存在互补对称性 设C=DES(M,K),则C=DES(M,K),其中M,C,K表示M,C,K 的非，密码学上称这种特性为互补对称性互补对称性。互补对称性使DES 在选择明文攻击下所需的工作量减半在选择明文攻击下所需的工作量减半。 其他对称加密算法 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。 无专利限制 2.3.2 公开密钥密码的基本概念 使用传统密码进行保密通信，通信双发必须首先 预约持有相同的密钥才能进行。而私人和商业之间想 通过通信工具洽谈生意又要保持商业秘密，有时很难有时很难 做到事先预约密钥做到事先预约密钥。另外，对于大型计算机网络，设 有n个用户，任意两个用户之间有可能进行通信，共 有n(n-1)/2种不同的通信方式，当n较大时，这个数目 很大。从安全角度考虑，密钥应当经常更换，这样， 在网络上产生、存储、分配并管理如此大量的密钥，产生、存储、分配并管理如此大量的密钥， 其复杂性和危险性巨大其复杂性和危险性巨大。 1.公开密钥密码的基本思想基本思想 将传统密码中密钥k一分为二，分为加密密钥Ke和 解密密钥Kd，并在计算复杂度上保证加密密钥Ke在计 算上不能推导出解密密钥Kd 。这样，即使将公开Ke 也不会暴露Kd ，也不会损害密码的安全。如此，就 从根本上克服了传统密码在密钥分配上的困难。 一个公开密钥密码应当满足以下三个条件： 解密算法解密算法D D与加密算法与加密算法E E互逆互逆，即对于所有明文M都有 D(E(M,Ke),Kd)=M 在计算上不能由Ke求出Kd 算法算法E E和和D D都是高效的都是高效的 条件条件是公开密钥密码的安全条件是公开密钥密码的安全条件，是公开密钥密码的安全 基础。而且也是最难满足的。由于数学水平的限制，目前尚不能 从数学上证明一个公开密钥密码完全满足这一条件，而只能证明 不满足这一条件。 条件条件是公开密钥密码的实用条件是公开密钥密码的实用条件，因为只有算法D和E都是 高效的，密码才能实际应用。 满足以上三个条件，便可构成一个公开密钥密码，而且这个满足以上三个条件，便可构成一个公开密钥密码，而且这个 密码可以确保数据的秘密性密码可以确保数据的秘密性。而如果还要求确保数据的真实性， 则应满足第四个条件： 对于所有明文M都有E(D(M,Kd),Ke)=M 条件条件是公开密钥密码能够确保数据真实性的基本条件是公开密钥密码能够确保数据真实性的基本条件。如 果满足了条件满足了条件、和和 ，同样也可构成一个公开密钥密码，同样也可构成一个公开密钥密码， 而且可以确保数据的真实性而且可以确保数据的真实性。 如果同时满足以上四个条件，则公开密钥密码可同时确保数同时满足以上四个条件，则公开密钥密码可同时确保数 据的秘密性和真实性据的秘密性和真实性。 2.基本工作方式基本工作方式 设M为明文，C为密文，E为加密算法，D为解密算法 ，Ke为公开的加密密钥，Kd为保密的解密密钥，每个用 户都分配一对密钥，而且将所有用户的公开的加密密钥存 入共享的密钥库PKDB中。 再设用户A要把数据M安全保密地传送给B，有以下三 种通信协议： 1）确保数据的秘密性确保数据的秘密性 A：从PKDB中查B公开的加密密钥用用B B公开的加密公开的加密 密钥加密密钥加密M M得到密文得到密文C C把C发给B B：用自己保密的解密密钥解密用自己保密的解密密钥解密C C，得到明文M 由于只有用户B才拥有保密的解密密钥，而且由公开 的加密密钥在计算上不能推出保密的解密密钥，所以只有只有 用户用户B B才能获得明文才能获得明文M M，从而确保了数据的秘密性。 然而，该通信协议并不能保证数据的真实性。因为 PKDB是共享的，任何人都可以查到B公开的加密密钥， 因此任何人都可以冒充任何人都可以冒充A A发送假数据给发送假数据给B B，而不被，而不被B B发现发现。 2）确保数据的真实性确保数据的真实性 A：用自己保密的解密密钥解密用自己保密的解密密钥解密M M，得到密文，得到密文C C 把C 发给B B：从PKDB中查A公开的加密密钥用用A A公开的加密公开的加密 密钥加密密钥加密C C得到密文得到密文M M 由于只有A才拥有保密的解密密钥，而且由A公开的 加密密钥在计算上不能推出保密的解密密钥，所以只有用只有用 户户A A才能发送数据才能发送数据M M，任何人都不能冒充，任何人都不能冒充A A发送发送M M，从而保证 了数据的真实性。 但是但是，因为PKDB是共享的，任何人都可以获得A公开 的加密密钥，所以任何人都可以获得数据任何人都可以获得数据M M 3）同时确保数据的秘密性和真实性 A：用自己保密的解密密钥解密用自己保密的解密密钥解密M M，得到中间密文，得到中间密文S S 从PKDB中查B公开的加密密钥用用B B公开的加密密钥加密公开的加密密钥加密 S S得到密文得到密文C C把C发给B B：用自己保密的解密密钥解密用自己保密的解密密钥解密C C，得到中间密文S 从从PKDBPKDB中查中查A A公开的加密密钥，并用之加密公开的加密密钥，并用之加密S S，得到明文M 2.3.3 RSA密码 Ronald L. Rivest Leonard M. Adleman RSA（Rivest,Shamir,Adleman）算法是1978年由 R.Rivest、A.Shamir和I.Adleman提出的一种基于数 论方法、也是理论上最为成熟的公开密钥体制，并 已经得到广泛应用。 Adi Shamir RSA数学基础 1. 费尔玛（费尔玛（FermatFermat）定理）定理 描述描述1 1：若p是素数，a是正整数且不 能被p整除，则ap-1 1 mod p。 描述描述2 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. 欧拉函数欧拉函数 欧拉（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. 欧拉（欧拉（EulerEuler）定理）定理 欧拉定理：若整数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，满足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）明文数字化，即将明文转换成数字串 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