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

第2讲密码学及其工具2.1密码学基本概念2.2古典密码2.3DES与RSA2.4PGP2.5社会工程学密码分析器2.1密码学基本概念2.1.1密码体制2.1.2密码分析2.1.3密码学的理论基础密码学(Cryptology)是一门古老的科学。大概自人类社会出现战争便产生了密码，以后逐渐形成了一门独立的学科。在密码学形成和发展历程中，科学技术的发展和战争的刺激都起了积极的推动作用。电子计算机一出现便被用于密码破译，使密码进入电子时代，其后有几个值得关注的里程碑：1949年香农发表《保密系统的通信理论》，把密码学置于坚实的数学基础上，标志着密码学作为一门科学的形成；1976年W.Diffie和M.Hellman提出公开密钥密码，从而开创了一个密码新时代；1977年美国联邦政府颁布数据加密标准DES；1994年美国联邦政府颁布密钥托管加密标准EES，同年颁布数字签名标准DSS，2001年颁布高级加密标准AES；目前，量子密码因其具有可证明的安全性，同时还能对窃听行为进行检测，从而研究广泛；生物信息技术的发展也推动了DNA计算机和DNA密码的研究自古以来，密码主要用于军事、政治、外交等要害部门，因而密码学的研究工作本身也是秘密进行的。后来，随着计算机网络的普及，电子政务、电子商务和电子金融等对确保信息安全的需求的增加，民间出现了一些不从属于保密机构的密码学者。实践证明，正是这种公开研究和秘密研究相结合的局面促进了今天密码学得空前繁荣。研究密码编制的科学称为密码编制学(Cryptography)；研究密码破译的科学称为密码分析学(Cryptannalysis)；密码编制学和密码分析学共同组成密码学(Cryptology)。密码学的基本思想是伪装信息，使未授权者不能理解它的真实含义。所谓伪装就是对数据进行一组可逆的数学变换。伪装前的原始数据称为明文(Plaintext)，伪装后的数据称为密文(Ciphertext)，伪装的过程称为加密(Encryption)。加密在加密密钥(Key)的控制下进行。用于对数据加密的一组数学变换称为加密算法发信者将明文数据加密成密文，再将密文数据送入网络传输或存入计算机文件，而且只给合法收信者分配密钥。合法收信者接收到密文后，施行与加密变换相逆的变换，去掉密文的伪装恢复出明文，这一过程称为解密(Decryprion)。解密在解密密钥的控制下进行。用于解密的一组数学变换称为解密算法，而且解密算法是加密算法的逆。2.1.1密码体制明文加密算法信道明文解密算法MM攻击者CC加密密钥加密密钥安全信道密钥KKeKd一个密码系统通常简称为密码体制(Cryptosystem)，由五部分组成：①明文空间M，它是全体明文的集合；②密文空间C，它是全体密文的集合；③密钥空间K，它是全体密钥的集合。其中，每一个密钥K均由加密密钥Ke和解密密钥Kd组成，即K=Ke,Kd④加密算法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发表的《保密系统的通信理论》从信息论的角度对信息源、密钥、加密和密码分析进行了数学分析，用不确定性和唯一解距离来度量密码体制的安全性，阐明了密码体制、完善保密、纯密码、理论保密和实际保密等重要概念，把密码置于坚实的数学基础之上，标志着密码学作为一门独立学科的形成。从此，信息论成为密码学重要的理论基础之一。Shannon建议采用扩散、混淆和乘积迭代的方法设计密码，并且以“揉面团”的过程形象地比喻扩散、混淆和乘积迭代的概念。所谓扩散就是将每一位明文和密钥数字的影响扩散到尽可能多得密文数字中。理想状态下，明文和密钥的每一位都影响密文的每一位，一般称这种情形达到“完备性”。所谓混淆就是是密文和密钥之间的关系复杂化。密文和密钥之间的关系越复杂，则密文和明文之间、密文和密钥之间的统计相关性越小，从而使统计分析不能奏效。设计一个复杂密码一般是比较困难的，利用乘积迭代方法对简单密码进行组合迭代，可以得到理想的扩散和混淆，从而可以得到安全的密码。计算复杂性理论是密码学的另一个理论基础。为计算求解一类问题，总需要一定量的时间资源和空间资源。消耗资源的多少取决于要求解问题的规模大小。设要求解的问题规模（如，输入变量的个数或输入长度）为n，若对于所有的n和所有长度为n的输入，计算最多要用f(n)步完成，则称该问题的计算复杂度为f(n)。若f(n)为n的多项式，则称其为多项式复杂度。粗略的讲，计算机可以在多项式时间复杂度内解决的问题称为P类问题；否则，为NP类问题。P类问题是计算机可计算的，而NP问题是计算机不可计算的困难问题。NP问题中最难得问题称为NP完全问题，即NPC问题。Shannon指出设计一个安全的密码本质上就是要寻找一个难解的问题。这样，计算复杂性理论的发展将直接影响密码的安全。此外，密码的设计应该遵循公开设计原则。密码体制的安全仅依赖于密钥的保密，而不应依赖于对算法的保密。当然，密码设计的公开原则并不等于所有的密码在应用时都要公开加密算法。也就是说，在公开的原则下设计密码，在实际使用时对算法保密，将会更加安全。2.2古典密码2.2.1置换密码2.2.2替代密码2.2.3代数密码2.2.4古典密码的统计分析2.2.1置换密码把明文中的字母重新排列，字母本身不变，但其位置改变，这样编成的密码称为置换密码。最简单的置换密码是把明文中字母顺序颠倒过来，然后截成固定长度的字母组作为密文。例如：明文：明晨5点发动反攻。mingchenwudianfadongfangong密文：gnognafgnodafnaiduwnehcgnim倒序的置换密码显然是很弱的。另一种置换密码是把明文按某一顺序排成一个矩阵，其中不足部分用Ф填充，而Ф是明文中不会出现的一个符号；然后按另一个顺序选出矩阵中的字母以形成密文，最后截成固定长度的字母组作为密文。明文：WHATCANYOULEARNFROMTHISBOOK”明文矩阵：举例明文WHATCANYOULEARNFROMTHISBOOKФФФФФ选出顺序：按列密文：WOROHUOOALMKTETФCAHФARIФNNSФYFBФ可以看出，改变矩阵的大小和选出顺序可以得到不同形式的密码。一种巧妙的方法：首先选一个词语作为密钥，去掉重复字母；然后按字母的字典顺序给密钥字母编号，并按照密钥的长度把明文排列成矩阵；最后按照数字序列中的数字顺序按列选出密文密钥：k=computer明文：WHATCANYOULEARNFROMTHISBOOK”按密钥排列明文：举例密钥COMPUTER顺序号14358726明文WHATCANYOULEARNFROMTHISBOOKФФФФФ密文：WORONNSФALMKHUOOTETФYFBФARIФCAHФ2.2.2替代密码首先构造一个或多个密文字母表，然后用密文字母表中的字母或字母组来替代明文字母或字母组，各字母或字母组的相对位置不变，但其本身改变，这样编成的密码称为替代密码。按照替代所使用的密文字母表的个数可将替代密码分为单表替代密码、多表替代密码和多名替代密码1.单表替代密码又称为简单替代密码。它只使用一个密文字母表，并且用密文字母表中的一个字母来替代一个明文字母表中的一个字母。设A={a0,a1,…,an-1};B={b0,b1,…,bn-1}定义一个由A到B的一一映射：f:AB,即f(ai)=bi设明文M=(m0,m1,…,mn-1)，则密文C=(f(m0),f(m1),…,f(mn-1))1）加法密码加法密码的映射函数：f(ai)=bi=aj，j=i+kmodn,k是0kn的正整数著名的加法密码是古罗马的凯撒大帝使用的密码Caesar密码取k=3，因此其密文字母表就是把明文字母表循环右移3位后得到的字母表。2）乘法密码乘法密码的映射函数：f(ai)=bi=aj，j=ikmodn其中，要求k和n互素。因为仅当(k,n)=1时，才存在两个整数x,y，使得xk+yn=1，才能有xk=1modn