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

第2讲密码学及其工具2.1密码学基本概念2.2古典密码2.3DES与RSA2.4PGP2.5社会工程学密码分析器第2讲密码学及其工具2.1密码学基本概念12.1密码学基本概念2.1.1密码体制2.1.2密码分析2.1.3密码学的理论基础2.1密码学基本概念2.1.1密码体制2密码学(Cryptology)是一门古老的科学。大概自人类社会出现战争便产生了密码，以后逐渐形成了一门独立的学科。在密码学形成和发展历程中，科学技术的发展和战争的刺激都起了积极的推动作用。电子计算机一出现便被用于密码破译，使密码进入电子时代，其后有几个值得关注的里程碑：1949年香农发表《保密系统的通信理论》，把密码学置于坚实的数学基础上，标志着密码学作为一门科学的形成；1976年W.Diffie和M.Hellman提出公开密钥密码，从而开创了一个密码新时代；1977年美国联邦政府颁布数据加密标准DES；1994年美国联邦政府颁布密钥托管加密标准EES，同年颁布数字签名标准DSS，2001年颁布高级加密标准AES；目前，量子密码因其具有可证明的安全性，同时还能对窃听行为进行检测，从而研究广泛；生物信息技术的发展也推动了DNA计算机和DNA密码的研究密码学(Cryptology)是一门古老的科学。大概自人类社3自古以来，密码主要用于军事、政治、外交等要害部门，因而密码学的研究工作本身也是秘密进行的。后来，随着计算机网络的普及，电子政务、电子商务和电子金融等对确保信息安全的需求的增加，民间出现了一些不从属于保密机构的密码学者。实践证明，正是这种公开研究和秘密研究相结合的局面促进了今天密码学得空前繁荣。研究密码编制的科学称为密码编制学(Cryptography)；研究密码破译的科学称为密码分析学(Cryptannalysis)；密码编制学和密码分析学共同组成密码学(Cryptology)。自古以来，密码主要用于军事、政治、外交等要害部门，因而密码学4密码学的基本思想是伪装信息，使未授权者不能理解它的真实含义。所谓伪装就是对数据进行一组可逆的数学变换。伪装前的原始数据称为明文(Plaintext)，伪装后的数据称为密文(Ciphertext)，伪装的过程称为加密(Encryption)。加密在加密密钥(Key)的控制下进行。用于对数据加密的一组数学变换称为加密算法发信者将明文数据加密成密文，再将密文数据送入网络传输或存入计算机文件，而且只给合法收信者分配密钥。合法收信者接收到密文后，施行与加密变换相逆的变换，去掉密文的伪装恢复出明文，这一过程称为解密(Decryprion)。解密在解密密钥的控制下进行。用于解密的一组数学变换称为解密算法，而且解密算法是加密算法的逆。密码学的基本思想是伪装信息，使未授权者不能理解它的真实含义。52.1.1密码体制明文加密算法信道明文解密算法MM攻击者CC加密密钥加密密钥安全信道密钥KKeKd2.1.1密码体制明加信明解MM攻击者CC加密密钥加密密6一个密码系统通常简称为密码体制(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)一个密码系统通常简称为密码体制(Cryptosystem)，7如果一个密码体制的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)如果一个密码体制的Ke=Kd，或者由其中一个很容易推出另一个8而序列密码将明文和密钥都划分成为或字符的序列，并且对明文序列中的每一个位或字符都用密钥序列中的对应分量进行加密，即M=(m1,m2,…,mn) Ke=(ke1,ke2,…,ken) C=(c1,c2,…,cn)其中，ci=E(mi,kei)(i=1,2,…,n)分组密码每一次加密一个明文块，而序列密码每一次加密一位或一个字符。序列密码是要害部门使用的主流密码，而商用领域则多用分组密码。根据加密算法在使用过程中是否变化，可将密码体制分为固定算法密码体制和演化密码体制。固定算法密码体制的加解密算法固定不变；而演化密码体制将密码学和演化计算相结合，使得在加密过程中加密算法也不断演化。而序列密码将明文和密钥都划分成为或字符的序列，并且对明文序列9

2.1.2密码分析如果能够根据密文系统地确定出明文或密钥，或者能够根据明文-密文对系统地确定出密钥，则称这个密码是可破译的。研究密码破译的科学称为密码分析学。密码分析者攻击密码的方法主要有三种：1）穷举攻击穷举攻击是指密码分析者采用依次试遍所有可能的密钥对所获得的密文进行解密，直至得到正确的明文；或者用一个确定的密钥对所有可能的明文进行加密，直至得到所获得的密文。理论上，对于任何使用密码只要有足够的资源都可以用穷举攻击将其攻破。从平均角度讲，采用穷举攻击破译一个密码必须试遍所有可能密钥的一半。穷举攻击所花费的时间等于尝试次数乘以一次解密或加密所需的时间。可以通过增大密钥量或加大解密或加密算法的复杂性来对抗穷举攻击。

2.1.2密码分析如果能够根据密文系统地确定出明文或密102）统计分析攻击统计分析攻击是指密码分析者通过分析密文和明文的统计规律来破译密码。统计分析攻击在历史上为破译古典密码作出过很大贡献。对抗统计分析攻击的方法是设法使明文的统计特性不带入密文。这样，密文不带有明文的痕迹，从而使统计分析攻击成为不可能。3）数学分析攻击数学分析攻击是指密码分析者对加解密算法的数学基础和某些密码学特性，通过数学求解的方法来破译密码。数学分析攻击是对基于数学难题的各种密码的主要威胁，为此，应当选用具有坚实数学基础和足够复杂的加解密算法。2）统计分析攻击11此外，根据密码分析者可利用的数据资源来分类，可将攻击密码的类型分为以下四种：1）仅知密文攻击仅知密文攻击是指密码分析者仅根据截获的密文来破译密码。2）已知明文攻击已知明文攻击是指密码分析者根据已知的某些明文-密文对来破译密码。3）选择明文攻击选择明文攻击是指密码分析者能够选择明文并获得相应的密文。4）选择密文攻击选择密文攻击是指密码分析者能够选择密文并获得相应的明文。这种攻击主要攻击公开密钥密码体制，特别是攻击其数字签名。此外，根据密码分析者可利用的数据资源来分类，可将攻击密码的类12一个密码，如果无论密码分析者截获多少密文和用什么技术方法进行攻击都不能被攻破，则称该密码是绝对不可破译的。绝对不可破译的密码在理论上是存在的，这就是著名的“一次一密”密码。但是，由于密钥管理上的困难，“一次一密”密码是不实用的。理论上，如果能够获得足够的资源，那么任何实际可使用的密码又都是可破译的。如果一个密码，不能被密码分析者根据可利用的资源所破译，则称其是计算上不可破译的。因为任何秘密都有其时效性，因此，对我们更有意义的是在计算上不可破译的密码。一个密码，如果无论密码分析者截获多少密文和用什么技术方法进行132.1.3密码学的理论基础1949年，shannon发表的《保密系统的通信理论》从信息论的角度对信息源、密钥、加密和密码分析进行了数学分析，用不确定性和唯一解距离来度量密码体制的安全性，阐明了密码体制、完善保密、纯密码、理论保密和实际保密等重要概念，把密码置于坚实的数学基础之上，标志着密码学作为一门独立学科的形成。从此，信息论成为密码学重要的理论基础之一。Shannon建议采用扩散、混淆和乘积迭代的方法设计密码，并且以“揉面团”的过程形象地比喻扩散、混淆和乘积迭代的概念。所谓扩散就是将每一位明文和密钥数字的影响扩散到尽可能多得密文数字中。理想状态下，明文和密钥的每一位都影响密文的每一位，一般称这种情形达到“完备性”。所谓混淆就是是密文和密钥之间的关系复杂化。密文和密钥之间的关系越复杂，则密文和明文之间、密文和密钥之间的统计相关性越小，从而使统计分析不能奏效。设计一个复杂密码一般是比较困难的，利用乘积迭代方法对简单密码进行组合迭代，可以得到理想的扩散和混淆，从而可以得到安全的密码。2.1.3密码学的理论基础1949年，shannon发表14计算复杂性理论是密码学的另一个理论基础。为计算求解一类问题，总需要一定量的时间资源和空间资源。消耗资源的多少取决于要求解问题的规模大小。设要求解的问题规模（如，输入变量的个数或输入长度）为n，若对于所有的n和所有长度为n的输入，计算最多要用f(n)步完成，则称该问题的计算复杂度为f(n)。若f(n)为n的多项式，则称其为多项式复杂度。粗略的讲，计算机可以在多项式时间复杂度内解决的问题称为P类问题；否则，为NP类问题。P类问题是计算机可计算的，而NP问题是计算机不可计算的困难问题。NP问题中最难得问题称为NP完全问题，即NPC问题。Shannon指出设计一个安全的密码本质上就是要寻找一个难解的问题。这样，计算复杂性理论的发展将直接影响密码的安全。此外，密码的设计应该遵循公开设计原则。密码体制的安全仅依赖于密钥的保密，而不应依赖于对算法的保密。当然，密码设计的公开原则并不等于所有的密码在应用时都要公开加密算法。也就是说，在公开的原则下设计密码，在实际使用时对算法保密，将会更加安全。计算复杂性理论是密码学的另一个理论基础。为计算求解一类问题，152.2古典密码2.2.1置换密码2.2.2替代密码2.2.3代数密码2.2.4古典密码的统计分析2.2古典密码2.2.1置换密码162.2.1置换密码把明文中的字母重新排列，字母本身不变，但其位置改变，这样编成的密码称为置换密码。最简单的置换密码是把明文中字母顺序颠倒过来，然后截成固定长度的字母组作为密文。例如：明文：明晨5点发动反攻。 mingchenwudianfadongfangong密文：gnognafgnodafnaiduwnehcgnim倒序的置换密码显然是很弱的。另一种置换密码是把明文按某一顺序排成一个矩阵，其中不足部分用Ф填充，而Ф是明文中不会出现的一个符号；然后按另一个顺序选出矩阵中的字母以形成密文，最后截成固定长度的字母组作为密文。2.2.1置换密码把明文中的字母重新排列，字母本身不变，17明文：WHATCANYOULEARNFROMTHISBOOK”明文矩阵：举例明文WHATCANYOULEARNFROMTHISBOOKФФФФФ选出顺序：按列密文：WOROHUOOALMKTETФCAHФARIФNNSФYFBФ可以看出，改变矩阵的大小和选出顺序可以得到不同形式的密码。一种巧妙的方法：首先选一个词语作为密钥，去掉重复字母；然后按字母的字典顺序给密钥字母编号，并按照密钥的长度把明文排列成矩阵；最后按照数字序列中的数字顺序按列选出密文明文：WHATCANYOULEARNFROMTHI18密钥：k=computer明文：WHATCANYOULEARNFROMTHISBOOK”按密钥排列明文：举例密钥COMPUTER顺序号14358726明文WHATCANYOULEARNFROMTHISBOOKФФФФФ密文：WORONNSФALMKHUOOTETФYFBФARIФCAHФ密钥：k=computer举例密钥COMPUTER顺序号192.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))2.2.2替代密码首先构造一个或多个密文字母表，然后用密201）加法密码加法密码的映射函数：f(ai)=bi=aj，j=i+kmodn,k是0<k<n的正整数著名的加法密码是古罗马的凯撒大帝使用的密码Caesar密码取k=3，因此其密文字母表就是把明文字母表循环右移3位后得到的字母表。2）乘法密码乘法密码的映射函数：f(ai)=bi=aj，j=ikmodn其中，要求k和n互素。因为仅当(k,n)=1时，才存在两个整数x,y，使得xk+yn=1，才能有xk=1modn，才有i=xjmodn，密码才能正确解密。例如，当用英文字母表作为明文字母表而取k=13时，因为(13,26)=13≠1，会出现：f(A)=f(C)=f(E)=……=f(Y)=Af(B)=f(D)=f(F)=……=f(Z)=N这样，密文字母表变为B={A,N,A,N,A,N,……A,N}1）加法密码213）仿射密码乘法密码和加法密码相结合就构成了仿射密码。仿射密码的映射函数：f(ai)=bi=aj，j=ik1+k0modn其中，要求k1和n互素，0<=k0<n,且不允许同时有k1=1k0=0。4）密钥词语替代密码首先随机选用一个词组或短语作为密钥，去掉重复字母，把结果作为矩阵的第一行；其次，在明文字母表中去掉矩阵第一行中的字母，并将剩余字母依次写入矩阵的其余行；最后按某一顺序从矩阵中取出字母构成密文字母表。例如：密钥：HONGYE矩阵：HONGYE 选出顺序：按列ABCDFIJKLMPQ RSTUVW XZ3）仿射密码222.多表替代密码简单替代密码很容易被破译，提高替代密码强度的一种方法是采用多个密文字母表，使明文中的每个字母都有很多种可能的字母来替代。构造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使用的Vigenere密码。它依次把明文字母表循环右移0,1,2,…,25位，获得26个密文字母表，构成Vigenere方阵：2.多表替代密码23Vigenere方阵明文abcdefghijklmnopqrstuvwxyzaABCDEFGHIJKLMNOPQRSTUVWXYZbBCDEFGHIJKLMNOPQRSTUVWXYZA…eEFGHIJKLMNOPQRSTUVWXYZABCD…sSTUVWXYZABCDEFGHIJKLMNOPQRtTUVWXYZABCDEFGHIJKLMNOPQRS…zZABCDEFGHIJKLMNOPQRSTUVWXYVigenere方阵明文abcdefghijklmnopq24Vigenere密码设P=datasecurity，k=best则采用维吉尼亚密码的加密过程如下：1.按密钥的长度将P分解若干节2.对每一节明文，利用密钥best进行变换。得到如下密文：C=EEK(P)=EELTTIUNSMLR密钥best明文datasecurityVigenere密码设P=datasecurity，k253.多名替代密码为了抵抗频率分析攻击，希望密文中不残留明文字母的频率痕迹。一种明显的方法是设法将密文字母的频率分布拉平。这就是多名替代密码的出发点。设明文字母表A={a0,a1,…,an-1}，对于每一个明文字母ai，作一个与之对应的字符集合bi，且使bi中的字符个数正比于ai在明文中的相对频率，称bi为ai的多名字符集。以集合B={Bi|i=0,1,…,n-1}作为密文字母表。定义映射函数：F:AB f(ai)=bji，而bji∈Bi即映射函数f将明文字母ai映射到它的一个多名字符bji。设明文M=(m0,m1,…,mn-1)则密文C=(f(m0),f(m1),…,f(mn-1))=(c0,c1,…,cn-1)，其中ci是根据映射函数从多名字符集中随机选取的一个多名字符。由于多名字符集合中的整数个数正比于相应字母的相对频率以及不同的多名字符集合间没有相同的整数，而且每个多名字符的选取又是完全随机的，所以多名替代密码的密文字符频率分布是平坦的。这大大增强了密码的强度。3.多名替代密码26+2.2.3代数密码异或运算（或称模2加运算）具有如下特点：00=0;01=1;10=1;11=0aa=0;abb=a即两个运算数相同，结果为0；不同，结果为1。使用简单异或进行加密，就是将明文与密钥进行异或运算，解密则是对密文用同一密钥进行异或运算。即Pk=C；Ck=P1917年美国电话电报公司的GillbertVernam为电报通信设计的Vernam密码就是将明文和密钥进行异或运算而得到密文的密码。Vernam密码的突出特点是其加密运算和解密运算相同，都是异或运算。但它经不起已知明文攻击。数学上，如果一个变换的正变换和逆变换相同，则称其为对合运算。对合运算可使加解密公用同一算法，工程实现的工作量减少一半。+++++++++2.2.3代数密码异或运算（或称模2加运算）具有如下特272.2.4古典密码的统计分析任何自然语言都有许多固有的统计特性。如果自然语言的这种统计特性在密文中有所反映，则密码分析者便可以通过分析明文和密文的统计规律而将密码破译。1.语言的统计特性英文文献中，各英文字母的概率分布：A8.167;B1.492;C2.782;D4.253;E12.702;F2.228G2.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;基低频率为VKJXQZ2.2.4古典密码的统计分析任何自然语言都有许多固有的统28不仅单字母以相对稳定的频率出现，而且双字母组和三字母组同样如此。这些统计数据，对密码分析者都是十分重要的信息。此外，密码分析者的文学、历史、地理等方面的知识对于破译密码也是十分重要的因素。2.古典密码分析以简单替代密码为例。对于加法密码，密钥整数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种不同的取值，比加法密码弱得多。不仅单字母以相对稳定的频率出现，而且双字母组和三字母组同样如29仿射密码的保密性能好些。其可能的密钥也只有nФ(n)-1种。对于明文字母表为英文字母表的情形，可能的密钥只有26*12-1=311种。如果用计算机破译，则完全可以非常方便地破译出来。本质上，密文字母表实际上是明文字母表的一种排列。设明文字母表含n个字母，则共有n!种排列，对于明文字母表为英文字母表的情况，可能的密文字母表有26!≈4×1026种。由于密钥词组代替密码的密钥词组可以随意选择，故这26!种不同的排列中的大部分被用作密文字母表也是不可能的。即使使用计算机，企图用穷举一切密钥的方法来破译密钥词组替代密码也是不可能的。那么，密钥词组替代密码是不是牢不可破呢？其实不然，因为穷举并不是攻击密码的唯一方法。这种密码仅在传输短的消息时是保密的，一旦消息足够长，密码分析者便可利用其他的统计分析方法迅速破解之。仿射密码的保密性能好些。其可能的密钥也只有nФ(n)-1种。30字母和字母组的统计数据对于密码分析者来说是十分重要的。因为它们可以提供有关密钥的许多信息。例如，由于字母E比其他字母的概率要高得多，如果是简单替代密码，那么可以预计大多密文都将包含一个频率比其他字母都高的字母。当出现这种情况时，完全可以猜测这个字母对应的明文字母就是E。一般，破译单替代密码的大致过程：首先，统计密文的各种统计特征，如果密文量比较多，则完成这步后便可确定出大部分密文字母；其次，分析双字母、三字母密文组，以区分元音和辅音字母；最后，分析字母较多的密文，在这一过程中大胆使用猜测的方法，如果猜对一个或几个词，就会大大加快破译过程。字母和字母组的统计数据对于密码分析者来说是十分重要的。因为它312.3DES和RSA2.3.1数据加密标准DES2.3.2公开密钥密码的基本概念2.3.3RSA密码2.3DES和RSA2.3.1数据加密标准DES322.3.1数据加密标准DES为适应社会对计算机数据安全保密越来越高的需求，美国国家标准局NBS于1973年开始公开征集，并于1977年1月5号采纳IBM的加密算法作为数据加密标准的DES加密算法。DES的设计目标：用于加密保护静态存储和传输信道中的数据，安全使用10-15年。DES综合利用了置换、替代、代数等多种密码技术。它设计精巧、实现容易、使用方便，堪称是适应计算机环境的近代传统密码的一个典范。DES的设计充分体现了Shannon信息保密理论所阐述的设计密码的思想，标志着密码的设计与分析达到了一个新的水平。DES是一种分组密码。明文、密文和密钥的分组长度都是64位。DES是面向二进制的密码算法，因而能够加解密任何形式的计算机数据。DES是对合运算，因而加密和解密共用同一算法，从而使工程实现的工作量减半。2.3.1数据加密标准DES为适应社会对计算机数据安全保33DES算法的特点1）对称算法：既可用于加密，也可用于解密。不同之处在于解密时用了16个子密钥的顺序和加密时所用的16个子密钥的顺序是颠倒的2）64位的密钥，使用长度为56位（64位明文中，有8位用于奇偶校验）。3）加密算法是混淆与扩散的结合，或者说是换位与置换的结合。4）每个DES都在明文上实施16重相同的组合技术。这种重复性可以被非常理想地应用到一个专用芯片中。初始换位56位密钥64位密文组64位明文组16轮加密变换生成16个48位子密钥压缩变换逆初始换位56位密钥DES64位明文组64位密文组56位密钥DES算法的特点1）对称算法：既可用于加密，也可用于解密。不34DES加密过程细化初始换位和逆初始换位；将64位明文分为32位的左右两段：L0和R0；进行16轮相同的迭代运算：混淆+异或+交换；将最后左右两段合并；生成每一轮的子密钥。64位明文组初始换位IP得到L0得到R0f+K1L1=R0R1=L0f(R0,K1)f+K2L2=R1R2=L1f(R1,K2)f+L15=R14R15=L14f(R14,K15)fKi+R16=L15f(R15,K16)L16=R15逆初始换位IP-1K1664位密文组++++DES加密过程细化初始换位和逆初始换位；64位明文组初始换位35初始换位IP和逆初始换位IP-1

408481656246432397471555236331386461454226230375451353216129364441252206028353431151195927342421050185826331419491757255850423426181026052443628201246254`4638302214664564840322416857494133251791595143352719113615345372921135635547393123157逆初始换位IP-1初始换位IP初始换位IP和逆初始换位IP-1408481656246436DES子密钥的生成64位密钥56位密钥压缩变换PC-1分割得到C0，D0左移左移压缩变换PC-2左移左移压缩变换PC-2左移左移压缩变换PC-2K1K2K16┇（48位）（48位）（48位）28位28位DES子密钥的生成64位密钥56位密钥压缩变换PC-1分割得37压缩变换PC-1与分割得到C0，D0PC-1的作用是去掉奇偶校验位8，16，24，32，40，48，56，64后，按56位进行换位。C0=k57k49k41…k52k44k36D0=k43k55k47…k20k12k45749413325179158504234261810259514335271911360524436635547393123157625446380221466153453729211352820124压缩变换PC-1与分割得到C0，D0PC-1的作用是去掉奇偶38密钥移位——每轮左移位数压缩置换PC-2轮数12345678910111213141516移动位数11222222122222211417112415328156211023191242681672720132415231374755304051453348444939563453464250362932密钥移位——每轮左移位数压缩置换PC-2轮数123439DES的f算法F算法的主要组成E-盒S-盒P-盒32位Ri-1+48位KiP-盒置换32位Li-1E-盒扩展置换S-盒替代+32位Ri32位Li48位32位48位32位DES的f算法F算法的主要组成32位Ri-1+48位KiP-40E-盒（ExpansionPermutation,扩展置换）把数据明文的右半部分Ri从32位扩展到48位12345678910111213141516输入12345678910111213141516171819202122232448输出12345678910111213141516（对应输入）4598131217251632E-盒（ExpansionPermutation,扩展置换41S-盒代换S-盒是进行了压缩后的密钥（56位→48位）与扩展后的明文分组（32位→48位）异或后进行的。目的是对48位的输入替代压缩成32位的输出。替代由8个S-盒进行。每个S-盒有6位输入，4位输出。S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒848位输入32位输出S-盒代换S-盒是进行了压缩后的密钥（56位→48位）与扩展42P-盒置换1672021291228171152326518311028241432273919133062211425对S-盒的32位输出进行一次换位P-盒置换167202129122817115232651843DES的安全性1.对于其设计目标，DES是安全的DES综合运用了置换、替代和代数等多种密码技术，是一种乘积密码。DSE算法中除了S盒是非线性变换外，其余变换均为线性变换，所以DES安全的关键是S盒。这个非线性变换的本质是数据压缩，它把6位的数据压缩成4位数据。S盒为DES提供了多种安全的密码特性。S盒用来提供混淆，使明文、密钥、密文之间的关系错综复杂，而P置换用来提供扩散，把S盒提供的混淆作用充分扩散开来。这样，S盒和P置换互相配合，形成了很强的抗差分攻击和抗线性攻击能力，其中抗差分攻击能力更强一些。DES的子密钥产生和使用很有特色，它确保了原密钥中的各位的使用次数基本相等。实验证明，56位密钥的每一位的使用次数都在12-15之间。应用实践证明DES作为商用密码，用于其设计目标是安全的。除因密钥太短经不起当今网络计算和并行计算的穷举攻击外，没有发现DES存在其他严重的安全缺陷。DES的安全性1.对于其设计目标，DES是安全的44DES的安全性2.DES存在的安全弱点1）密钥较短2）存在弱密钥和半弱密钥DES存在一些弱密钥和半弱密钥。在16次加密迭代中分别使用不同的子密钥是确保DES安全强度的一种重要措施，但实际上却存在一些密钥，由它们产生的16个子密钥不是互不相同，而是有相重的。产生弱密钥的原因是子密钥产生算法中的C和D寄存器中的数据在循环移位下出现重复所致。据此，可推出以下四种弱密钥（十六进制）：01010101010101011F1F1F1F1F1F1F1FE0E0E0E0E0E0E0E0FEFEFEFEFEFEFEFEDES的安全性2.DES存在的安全弱点45DES的安全性此外，DES还存在半弱密钥。设k是给定的密钥，如果由k所产生的子密钥中存在重复者，但不是完全相同，则称k为半弱密钥。以下半弱密钥所产生得16个子密钥中只有两种不同的子密钥，每种出现8次：01FE01FE01FE01FEFE01FE01FE01FE011FE01FE01FE01FE0E01FE01FE01FE01F弱密钥和半弱密钥的存在无疑是DES的一个不足，但由于它们的数量与密钥总数256相比仍是微不足道的，所以这并不构成对DES太大的威胁，只要注意在实际应用中不使用它们就可以了。3）存在互补对称性设C=DES(M,K),则C’=DES(M’,K’),其中M’,C’,K’表示M,C,K的非，密码学上称这种特性为互补对称性。互补对称性使DES在选择明文攻击下所需的工作量减半。DES的安全性此外，DES还存在半弱密钥。设k是给定的密钥，46其他对称加密算法IDEA（internationaldataencryptionalgorithm，国际数据加密算法）分组加密算法，分组长度为64b，密钥长度128b；核心由8轮迭代和一个输出变换组成，能使明码数据更好地扩散和混淆；运算过程只需使用下面三种简单运算：·逐个的位异或；·模216加；·模（216+1）乘。有专利限制。AES（advancedencryptionstandard，高级加密标准）。分组算法，分组大小为128b密钥长度可以是128b、192b或256b，分别称为AES-128、AES-192、AES-256。无专利限制其他对称加密算法IDEA（internationa472.3.2公开密钥密码的基本概念使用传统密码进行保密通信，通信双发必须首先预约持有相同的密钥才能进行。而私人和商业之间想通过通信工具洽谈生意又要保持商业秘密，有时很难做到事先预约密钥。另外，对于大型计算机网络，设有n个用户，任意两个用户之间有可能进行通信，共有n(n-1)/2种不同的通信方式，当n较大时，这个数目很大。从安全角度考虑，密钥应当经常更换，这样，在网络上产生、存储、分配并管理如此大量的密钥，其复杂性和危险性巨大。1.公开密钥密码的基本思想将传统密码中密钥k一分为二，分为加密密钥Ke和解密密钥Kd，并在计算复杂度上保证加密密钥Ke在计算上不能推导出解密密钥Kd。这样，即使将公开Ke也不会暴露Kd，也不会损害密码的安全。如此，就从根本上克服了传统密码在密钥分配上的困难。2.3.2公开密钥密码的基本概念使用传统密码进行保密通信48一个公开密钥密码应当满足以下三个条件：①解密算法D与加密算法E互逆，即对于所有明文M都有D(E(M,Ke),Kd)=M②在计算上不能由Ke求出Kd③算法E和D都是高效的条件②是公开密钥密码的安全条件，是公开密钥密码的安全基础。而且也是最难满足的。由于数学水平的限制，目前尚不能从数学上证明一个公开密钥密码完全满足这一条件，而只能证明不满足这一条件。条件③是公开密钥密码的实用条件，因为只有算法D和E都是高效的，密码才能实际应用。满足以上三个条件，便可构成一个公开密钥密码，而且这个密码可以确保数据的秘密性。而如果还要求确保数据的真实性，则应满足第四个条件：④对于所有明文M都有E(D(M,Kd),Ke)=M条件④是公开密钥密码能够确保数据真实性的基本条件。如果满足了条件①、②和④，同样也可构成一个公开密钥密码，而且可以确保数据的真实性。如果同时满足以上四个条件，则公开密钥密码可同时确保数据的秘密性和真实性。一个公开密钥密码应当满足以下三个条件：492.基本工作方式设M为明文，C为密文，E为加密算法，D为解密算法，Ke为公开的加密密钥，Kd为保密的解密密钥，每个用户都分配一对密钥，而且将所有用户的公开的加密密钥存入共享的密钥库PKDB中。再设用户A要把数据M安全保密地传送给B，有以下三种通信协议：1）确保数据的秘密性A：从PKDB中查B公开的加密密钥用B公开的加密密钥加密M得到密文C把C发给BB：用自己保密的解密密钥解密C，得到明文M由于只有用户B才拥有保密的解密密钥，而且由公开的加密密钥在计算上不能推出保密的解密密钥，所以只有用户B才能获得明文M，从而确保了数据的秘密性。然而，该通信协议并不能保证数据的真实性。因为PKDB是共享的，任何人都可以查到B公开的加密密钥，因此任何人都可以冒充A发送假数据给B，而不被B发现。2.基本工作方式502）确保数据的真实性A：用自己保密的解密密钥解密M，得到密文C

把C发给BB：从PKDB中查A公开的加密密钥用A公开的加密密钥加密C得到密文M由于只有A才拥有保密的解密密钥，而且由A公开的加密密钥在计算上不能推出保密的解密密钥，所以只有用户A才能发送数据M，任何人都不能冒充A发送M，从而保证了数据的真实性。但是，因为PKDB是共享的，任何人都可以获得A公开的加密密钥，所以任何人都可以获得数据M3）同时确保数据的秘密性和真实性A：用自己保密的解密密钥解密M，得到中间密文S

从PKDB中查B公开的加密密钥用B公开的加密密钥加密S得到密文C把C发给BB：用自己保密的解密密钥解密C，得到中间密文S从PKDB中查A公开的加密密钥，并用之加密S，得到明文M2）确保数据的真实性512.3.3RSA密码RonaldL.RivestLeonardM.AdlemanRSA（Rivest,Shamir,Adleman）算法是1978年由R.Rivest、A.Shamir和I.Adleman提出的一种基于数论方法、也是理论上最为成熟的公开密钥体制，并已经得到广泛应用。AdiShamir

2.3.3RSA密码RonaldL.RivestL52RSA数学基础1.费尔玛（Fermat）定理描述1：若p是素数，a是正整数且不能被p整除，则ap-1≡1modp。描述2：对于素数p，若a是任一正整数，则ap≡a（modp）。例2.1设p=3，a=2，则23-1=4≡1（mod3）或23=8≡2（mod3）。例2.2设p=5，a=3，则35-1=81≡1（mod5）或35=243≡3（mod5）。RSA数学基础1.费尔玛（Fermat）定理532.欧拉函数欧拉（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(modm)例2.4设a=3，m=7，则有φ(7)=6，36=729，729≡1(mod7)例2.5设a=4，m=5，则有φ(5)=2，42=16，16≡1(mod5)2.欧拉函数54RSA密钥的产生基本过程：①选两个保密的大素数p和q（保密）。②计算n=pq（公开），φ(n)=(p-1)(q-1)（保密）。③随机选取一整数e，满足1<e<φ(n)且gcd(φ(n),e)=1（公开）。④计算d，满足de≡1(modφ(n))（保密）。⑤得到一对密钥：公开密钥：{e,n}，秘密密钥：{d,n}。例子：①选择两个素数p=7，q=17②计算n=pq=7×17=119计算n的欧拉函数φ(n)=(p-1)(q-1)=6×16=96。③从[0，95]间选一个与96互质的数e=5④根据式5d=1mod96解出d=77，因为ed=5×77=385=4×96+1≡1mod96⑤得到公钥PK=(e,n)={5,119}，密钥SK={77,119}。RSA密钥的产生基本过程：55RSA加密/解密过程基本过程：1）明文数字化，即将明文转换成数字串2）分组。将二进制的明文串分成长度小于log2n的分组3）加密算法Ci=Mie（modn）最后得到的密文C由长度相同的分组Ci组成4）解密算法D(C)≡Cd(modn)RSA加密/解密过程基本过程：56RSA加密/解密过程例子：1）产生密钥设：p=43,q=59,n=43×59=2537,

φ(n)=42×58=2436取e=13（与φ(n)没有公因子）解方程de≡（mod2436）,2436=13×187+5,5=2436-13×187：13=2×5+3，3=13-2×51=3-2=3-(5-3)=2×3-5=2×(13-2×5)-5=2×13-5×5=2×13-5×(2436-13×187)=(187×5+2)×13-5×2436=937×13-5×2436即：937×13≡1(mod2436)故e=13，d=9372）加/解密明文：publickeyencryptions明文分组：publickeyencryptions明文数字化（按字母序，令a=00,b=01,c=02,…，y=24,z=25）：1520011108021004240413021724151908141418加密按照算法Mie（modn）=Ci，如152013（mod2537）=0095得到密文0095164814101299136513792333213217511289解密：按照算法Cie（modn）=Mi，如009513（mod2537）=1520。RSA加密/解密过程例子：57RSA密钥的安全性小合数的因子分解是容易的，但大合数的因子分解却是十分困难的。密码分析者攻击RSA密码的一种可能的途径是截获密文C，从而求出明文M。因为M≡Cd(modn),n是公开的，要从C中求出明文M，必须先求出d，而d是保密。又因为ed≡1(modφ(n)),而e又是公开的，要从中求出d，必须先求出φ(n)，而φ(n)是保密的。又因为φ(n)=(p-1)(q-1)，则要从中求出必须先求出p和q，而p和q是保密的。又因为n=pq，这样要从n中求出p和q，只有对n进行因子分解。而当n足够大时，这是很困难的RSA密钥的安全性小合数的因子分解是容易的，但大合数的因子分582.4PGP2.4PGP592.5社会工程学密码分析器2.5社会工程学密码分析器60本讲可选题1.古典密码加解密算法的实现，要求如下：①具有置换密码、单表替代密码中的加法密码、乘法密码和仿射密码、Vigenere密码以及代数密码的加密和解密功能；②具有加解密速度统计功能；③具有良好的人机界面。2.古典密码破译算法的实现，要求如下：①具有置换密码、单表替代密码中的加法密码、乘法密码和仿射密码、Vigenere密码以及代数密码的破解算法；②具有破解速度统计功能；③具有良好的人机界面。3.以DES作为加密算法开发文件加密软件系统，软件要求如下：①具有文件加密和解密功能；②具有加解密速度统计功能；③具有良好的人机界面。本讲可选题1.古典密码加解密算法的实现，要求如下：614.密钥管理，要求如下：①陈述现有的各种密钥管理机制，并比较其优劣；②陈述正确、条理清晰，具有反映个人思考所得的内容。5.数据完整性：HASH函数①陈述数据完整性的基本概念，比较各种HASH函数的优劣；②陈述正确、条理清晰，具有反映个人思考所得的内容。6.数字签名①陈述数字签名的基本概念，并在此基础上陈述如何利用公钥实现数字签名，就不可否认签名和盲签名机制进行讨论②比较美国数字签名标准DSS和俄罗斯数字签名标准GOST；③陈述正确、条理清晰，具有反映个人思考所得的内容。7.认证①陈述身份认证、站点认证、报文认证的基本知识，并就Kerberos认证系统进行探讨；②陈述正确、条理清晰，具有反映个人思考所得的内容。4.密钥管理，要求如下：62演讲完毕，谢谢观看！演讲完毕，谢谢观看！63第2讲密码学及其工具2.1密码学基本概念2.2古典密码2.3DES与RSA2.4PGP2.5社会工程学密码分析器第2讲密码学及其工具2.1密码学基本概念642.1密码学基本概念2.1.1密码体制2.1.2密码分析2.1.3密码学的理论基础2.1密码学基本概念2.1.1密码体制65密码学(Cryptology)是一门古老的科学。大概自人类社会出现战争便产生了密码，以后逐渐形成了一门独立的学科。在密码学形成和发展历程中，科学技术的发展和战争的刺激都起了积极的推动作用。电子计算机一出现便被用于密码破译，使密码进入电子时代，其后有几个值得关注的里程碑：1949年香农发表《保密系统的通信理论》，把密码学置于坚实的数学基础上，标志着密码学作为一门科学的形成；1976年W.Diffie和M.Hellman提出公开密钥密码，从而开创了一个密码新时代；1977年美国联邦政府颁布数据加密标准DES；1994年美国联邦政府颁布密钥托管加密标准EES，同年颁布数字签名标准DSS，2001年颁布高级加密标准AES；目前，量子密码因其具有可证明的安全性，同时还能对窃听行为进行检测，从而研究广泛；生物信息技术的发展也推动了DNA计算机和DNA密码的研究密码学(Cryptology)是一门古老的科学。大概自人类社66自古以来，密码主要用于军事、政治、外交等要害部门，因而密码学的研究工作本身也是秘密进行的。后来，随着计算机网络的普及，电子政务、电子商务和电子金融等对确保信息安全的需求的增加，民间出现了一些不从属于保密机构的密码学者。实践证明，正是这种公开研究和秘密研究相结合的局面促进了今天密码学得空前繁荣。研究密码编制的科学称为密码编制学(Cryptography)；研究密码破译的科学称为密码分析学(Cryptannalysis)；密码编制学和密码分析学共同组成密码学(Cryptology)。自古以来，密码主要用于军事、政治、外交等要害部门，因而密码学67密码学的基本思想是伪装信息，使未授权者不能理解它的真实含义。所谓伪装就是对数据进行一组可逆的数学变换。伪装前的原始数据称为明文(Plaintext)，伪装后的数据称为密文(Ciphertext)，伪装的过程称为加密(Encryption)。加密在加密密钥(Key)的控制下进行。用于对数据加密的一组数学变换称为加密算法发信者将明文数据加密成密文，再将密文数据送入网络传输或存入计算机文件，而且只给合法收信者分配密钥。合法收信者接收到密文后，施行与加密变换相逆的变换，去掉密文的伪装恢复出明文，这一过程称为解密(Decryprion)。解密在解密密钥的控制下进行。用于解密的一组数学变换称为解密算法，而且解密算法是加密算法的逆。密码学的基本思想是伪装信息，使未授权者不能理解它的真实含义。682.1.1密码体制明文加密算法信道明文解密算法MM攻击者CC加密密钥加密密钥安全信道密钥KKeKd2.1.1密码体制明加信明解MM攻击者CC加密密钥加密密69一个密码系统通常简称为密码体制(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)一个密码系统通常简称为密码体制(Cryptosystem)，70如果一个密码体制的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)如果一个密码体制的Ke=Kd，或者由其中一个很容易推出另一个71而序列密码将明文和密钥都划分成为或字符的序列，并且对明文序列中的每一个位或字符都用密钥序列中的对应分量进行加密，即M=(m1,m2,…,mn) Ke=(ke1,ke2,…,ken) C=(c1,c2,…,cn)其中，ci=E(mi,kei)(i=1,2,…,n)分组密码每一次加密一个明文块，而序列密码每一次加密一位或一个字符。序列密码是要害部门使用的主流密码，而商用领域则多用分组密码。根据加密算法在使用过程中是否变化，可将密码体制分为固定算法密码体制和演化密码体制。固定算法密码体制的加解密算法固定不变；而演化密码体制将密码学和演化计算相结合，使得在加密过程中加密算法也不断演化。而序列密码将明文和密钥都划分成为或字符的序列，并且对明文序列72

2.1.2密码分析如果能够根据密文系统地确定出明文或密钥，或者能够根据明文-密文对系统地确定出密钥，则称这个密码是可破译的。研究密码破译的科学称为密码分析学。密码分析者攻击密码的方法主要有三种：1）穷举攻击穷举攻击是指密码分析者采用依次试遍所有可能的密钥对所获得的密文进行解密，直至得到正确的明文；或者用一个确定的密钥对所有可能的明文进行加密，直至得到所获得的密文。理论上，对于任何使用密码只要有足够的资源都可以用穷举攻击将其攻破。从平均角度讲，采用穷举攻击破译一个密码必须试遍所有可能密钥的一半。穷举攻击所花费的时间等于尝试次数乘以一次解密或加密所需的时间。可以通过增大密钥量或加大解密或加密算法的复杂性来对抗穷举攻击。

2.1.2密码分析如果能够根据密文系统地确定出明文或密732）统计分析攻击统计分析攻击是指密码分析者通过分析密文和明文的统计规律来破译密码。统计分析攻击在历史上为破译古典密码作出过很大贡献。对抗统计分析攻击的方法是设法使明文的统计特性不带入密文。这样，密文不带有明文的痕迹，从而使统计分析攻击成为不可能。3）数学分析攻击数学分析攻击是指密码分析者对加解密算法的数学基础和某些密码学特性，通过数学求解的方法来破译密码。数学分析攻击是对基于数学难题的各种密码的主要威胁，为此，应当选用具有坚实数学基础和足够复杂的加解密算法。2）统计分析攻击74此外，根据密码分析者可利用的数据资源来分类，可将攻击密码的类型分为以下四种：1）仅知密文攻击仅知密文攻击是指密码分析者仅根据截获的密文来破译密码。2）已知明文攻击已知明文攻击是指密码分析者根据已知的某些明文-密文对来破译密码。3）选择明文攻击选择明文攻击是指密码分析者能够选择明文并获得相应的密文。4）选择密文攻击选择密文攻击是指密码分析者能够选择密文并获得相应的明文。这种攻击主要攻击公开密钥密码体制，特别是攻击其数字签名。此外，根据密码分析者可利用的数据资源来分类，可将攻击密码的类75一个密码，如果无论密码分析者截获多少密文和用什么技术方法进行攻击都不能被攻破，则称该密码是绝对不可破译的。绝对不可破译的密码在理论上是存在的，这就是著名的“一次一密”密码。但是，由于密钥管理上的困难，“一次一密”密码是不实用的。理论上，如果能够获得足够的资源，那么任何实际可使用的密码又都是可破译的。如果一个密码，不能被密码分析者根据可利用的资源所破译，则称其是计算上不可破译的。因为任何秘密都有其时效性，因此，对我们更有意义的是在计算上不可破译的密码。一个密码，如果无论密码分析者截获多少密文和用什么技术方法进行762.1.3密码学的理论基础1949年，shannon发表的《保密系统的通信理论》从信息论的角度对信息源、密钥、加密和密码分析进行了数学分析，用不确定性和唯一解距离来度量密码体制的安全性，阐明了密码体制、完善保密、纯密码、理论保密和实际保密等重要概念，把密码置于坚实的数学基础之上，标志着密码学作为一门独立学科的形成。从此，信息论成为密码学重要的理论基础之一。Shannon建议采用扩散、混淆和乘积迭代的方法设计密码，并且以“揉面团”的过程形象地比喻扩散、混淆和乘积迭代的概念。所谓扩散就是将每一位明文和密钥数字的影响扩散到尽可能多得密文数字中。理想状态下，明文和密钥的每一位都影响密文的每一位，一般称这种情形达到“完备性”。所谓混淆就是是密文和密钥之间的关系复杂化。密文和密钥之间的关系越复杂，则密文和明文之间、密文和密钥之间的统计相关性越小，从而使统计分析不能奏效。设计一个复杂密码一般是比较困难的，利用乘积迭代方法对简单密码进行组合迭代，可以得到理想的扩散和混淆，从而可以得到安全的密码。2.1.3密码学的理论基础1949年，shannon发表77计算复杂性理论是密码学的另一个理论基础。为计算求解一类问题，总需要一定量的时间资源和空间资源。消耗资源的多少取决于要求解问题的规模大小。设要求解的问题规模（如，输入变量的个数或输入长度）为n，若对于所有的n和所有长度为n的输入，计算最多要用f(n)步完成，则称该问题的计算复杂度为f(n)。若f(n)为n的多项式，则称其为多项式复杂度。粗略的讲，计算机可以在多项式时间复杂度内解决的问题称为P类问题；否则，为NP类问题。P类问题是计算机可计算的，而NP问题是计算机不可计算的困难问题。NP问题中最难得问题称为NP完全问题，即NPC问题。Shannon指出设计一个安全的密码本质上就是要寻找一个难解的问题。这样，计算复杂性理论的发展将直接影响密码的安全。此外，密码的设计应该遵循公开设计原则。密码体制的安全仅依赖于密钥的保密，而不应依赖于对算法的保密。当然，密码设计的公开原则并不等于所有的密码在应用时都要公开加密算法。也就是说，在公开的原则下设计密码，在实际使用时对算法保密，将会更加安全。计算复杂性理论是密码学的另一个理论基础。为计算求解一类问题，782.2古典密码2.2.1置换密码2.2.2替代密码2.2.3代数密码2.2.4古典密码的统计分析2.2古典密码2.2.1置换密码792.2.1置换密码把明文中的字母重新排列，字母本身不变，但其位置改变，这样编成的密码称为置换密码。最简单的置换密码是把明文中字母顺序颠倒过来，然后截成固定长度的字母组作为密文。例如：明文：明晨5点发动反攻。 mingchenwudianfadongfangong密文：gnognafgnodafnaiduwnehcgnim倒序的置换密码显然是很弱的。另一种置换密码是把明文按某一顺序排成一个矩阵，其中不足部分用Ф填充，而Ф是明文中不会出现的一个符号；然后按另一个顺序选出矩阵中的字母以形成密文，最后截成固定长度的字母组作为密文。2.2.1置换密码把明文中的字母重新排列，字母本身不变，80明文：WHATCANYOULEARNFROMTHISBOOK”明文矩阵：举例明文WHATCANYOULEARNFROMTHISBOOKФФФФФ选出顺序：按列密文：WOROHUOOALMKTETФCAHФARIФNNSФYFBФ可以看出，改变矩阵的大小和选出顺序可以得到不同形式的密码。一种巧妙的方法：首先选一个词语作为密钥，去掉重复字母；然后按字母的字典顺序给密钥字母编号，并按照密钥的长度把明文排列成矩阵；最后按照数字序列中的数字顺序按列选出密文明文：WHATCANYOULEARNFROMTHI81密钥：k=computer明文：WHATCANYOULEARNFROMTHISBOOK”按密钥排列明文：举例密钥COMPUTER顺序号14358726明文WHATCANYOULEARNFROMTHISBOOKФФФФФ密文：WORONNSФALMKHUOOTETФYFBФARIФCAHФ密钥：k=computer举例密钥COMPUTER顺序号822.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))2.2.2替代密码首先构造一个或多个密文字母表，然后用密831）加法密码加法密码的映射函数：f(ai)=bi=aj，j=i+kmodn,k是0<k<n的正整数著名的加法密码是古罗马的凯撒大帝使用的密码Caesar密码取k=3，因此其密文字母表就是把明文字母表循环右移3位后得到的字母表。2）乘法密码乘法密码的映射函数：f(ai)=bi=aj，j=ikmodn其中，要求k和n互素。因为仅当(k,n)=1时，才存在两个整数x,y，使得xk+yn=1，才能有xk=1modn，才有i=xjmodn，密码才能正确解密。例如，当用英文字母表作为明文字母表而取k=13时，因为(13,26)=13≠1，会出现：f(A)=f(C)=f(E)=……=f(Y)=Af(B)=f(D)=f(F)=……=f(Z)=N这样，密文字母表变为B={A,N,A,N,A,N,……A,N}1）加法密码843）仿射密码乘法密码和加法密码相结合就构成了仿射密码。仿射密码的映射函数：f(ai)=bi=aj，j=ik1+k0modn其中，要求k1和n互素，0<=k0<n,且不允许同时有k1=1k0=0。4）密钥词语替代密码首先随机选用一个词组或短语作为密钥，去掉重复字母，把结果作为矩阵的第一行；其次，在明文字母表中去掉矩阵第一行中的字母，并将剩余字母依次写入矩阵的其余行；最后按某一顺序从矩阵中取出字母构成密文字母表。例如：密钥：HONGYE矩阵：HONGYE 选出顺序：按列ABCDFIJKLMPQ RSTUVW XZ3）仿射密码852.多表替代密码简单替代密码很容易被破译，提高替代密码强度的一种方法是采用多个密文字母表，使明文中的每个字母都有很多种可能的字母来替代。构造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