2011网络安全与对抗(第二章密码学理论)-1

1、第二章 密码学理论密码技术在网络安全中的作用信息窃取信息传递信息冒充信息篡改信息抵赖加密技术完整性技术认证技术数字签名主要内容2.1 密码学基本知识2.2.1 古典密码体制2.2.2 对称密码技术2.2.3 公钥密码技术2.2.4 报文鉴别和HASH函数2.2.5 数字签名2.2 密码学基本技术2.1 密码学基础知识2.1.1 密码学发展历史2.1.2 密码学的基本概念2.1.3 密码体制的分类2.1.4 密码分析学2.1.5 密码体制的安全性2.1 密码学基础知识2.1.1 密码学发展历史2.1.2 密码学的基本概念2.1.3 密码体制的分类2.1.4 密码分析学2.1.5 密码体制的安全性

2、2.1.1 密码学发展历史古典密码时期近代密码时期现代密码时期密码学发展大致分为三个阶段：古典密码时期起始时间：从古代到19世纪末，长达 几千年密码体制：纸、笔或者简单器械实现的替代及换位通信手段：信使隐写术（古希腊:公元前440年）举例： 王先生： 来信收到，盛情难以 报答，我 已在昨天到达广州。秋雨绵绵，每 天需备伞才能上街，苦矣。大约本 月中旬返乡，到时再联络。 Scytale（斯巴达:公元前400年）黑帮行话、藏头诗、网格式密码等举例： 王先生： 来信收到，盛情难以 报答，我 已在昨天到达广州。秋雨绵绵，每 天需备伞才能上街，苦矣。大约本 月中旬返乡，到时再联络。 建立一张表，使每一个

3、字符对应一对,， 是该字符所在行标号，是列标号。这样 将明文变成形式为一串数字的密文。 1 2345 1 A BCDE 2 F GHI JK 3 L MNOP 4 Q RSTU 5 V WXYZ棋盘密码近代密码时期起始时间：从20世纪初到20世纪50年代，即一战及二战时期密码体制：手工或电动机械实现的复杂的替代及换位（单表、多表、转轮密码等）通信手段：电报通信现代密码时期起始时间：从20世纪50年代至今密码体制：分组密码、序列密码以及公开密钥密码，有坚实的数学理论基础通信手段：无线通信、有线通信、计算网络等现代密码学的重要事件1949年，Shannon发表了保密通信的信息理论，首先用信息论的观

4、点对信息保密问题作了全面的论述，为密码系统建立了理论基础，从此密码学成了一门科学。1977年，美国国家标准局公布实施了数据加密标准（DES），公开其加密算法，批准用于非机密单位和商业上的保密通信。DES的公布使密码学的研究公开，密码学得到了迅速发展。（第一次飞跃）1976年，Diffie和Hellman提出公开密钥的密码体制，保密通信问题得到广泛研究。研究领域扩展到数字签名、消息认证、身份识别、抗欺骗协议等。1978年,由Rivest、Shamire和Adleman 提出第一个比较完善的公钥密码体制算法RSA。1984年，C.H.Bennett和G.Brassard首次提出量子密码技术（现称为

5、BB84协议），它是一种基于量子定律的密码技术，可以发现窃听，抗击具有无限计算能力的攻击。1989年，R.Mathews等首次将混沌理论用于序列密码中，为序列密码的研究开辟了一条新的途径。（第二次飞跃）1997年,美国国家标准局征集高级加密加密标准（AES），选择比利时密码学家设计Rijndael算法作为标准草案。公钥密码领域中，椭圆曲线由于安全性高、计算速度快引起人们的普遍关注。1991年,美国国家标准局制定数字签名标准，1995年，又制定安全Hash算法。未来，混沌密码、量子密码逐步走向实用化。2.1.2 密码学的基本概念密码编码学(Cryptography): 主要研究对信息进行编码,实

6、现对信息的加密或认证等要求。密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造。这两个分支既相互对立又相互依存，正是由于这种对立统一关系，才推动了密码学自身的发展。密码学（Cryptology）是结合数学、计算机科学、电子与通讯等诸多学科于一体的交叉学科，是研究信息系统安全保密的一门科学。加密通信模型密码系统（体制）五元组（M,C,K,E,D)满足条件:明文（Plaintext）空间M：所有可能明文的集合密文（Ciphertext)空间C：所有可能密文的集合密钥（Key）空间K：所有可能密钥的集合,k=(ke,kd)加密（Encryption）算法: 所有 集合，

7、任意ke,有一个加密算法，使得eke(M)=C 解密（Decryption）算法:所有 集合， 任意kd,有一个解密算法，使得dkd(C)=M，且满足dkd(eke(M)=M。Kerchhoff假设 这是现代密码学中针对信息保密的一个重要的假设：这意味着算法细节可以公开，甚至可以当成一个标准加以公布。 算法难以改变,同一算法要使用很长一段时间 没人为两个用户建立一个密码系统 防止设计者窃密 公开的算法更安全假设敌手知道使用的密码算法，即 密码体制的安全性在于密钥!一个密码系统要实际可用，必须满足如下特性：（1）加密和解密过程都能有效的计算； （2）破译者取得密文后将不能在有效的时间内破译密钥和

8、明文。具体加密的手段有硬件加密和软件加密。 硬件加密的效率和安全性高，但硬件设备需要专用件，成本较高； 软件加密的优点是使用灵活、成本低，但安全性一般不如硬件高。注：一个密码系统是安全的必要条件是穷举搜索密钥不可行，即密钥空间足够大。2.1.3 密码体制的分类 按对明文的划分（加密的方式）分为： 分组密码： 把明文分成等长的组分别加密 流密码 按字符和位处理按密钥对密码体制的分类对称密码体制（Symmetric System） 加密密钥和解密密钥相同，或者虽然不相同，但由其中的任意一个可以很容易地推出另一个，又称传统密码体制、秘密密钥体制或单密钥体制。 非对称密码体制（Asymmetric S

9、ystem） 加密密钥和解密密钥不相同，且从一个很难推出另一 个，其中加密密钥可以公开，成为公开密钥(pulic key)，简称公钥；解密密钥保密,成为私人密钥 （private key）,简称私钥。因此又称公开密钥体制或 双密钥体制。 对称密码体制对称密码体制主要研究问题：密钥产生(Key generation)密钥管理(Key management)分类：流密码(Stream cipher)分组密码(Block cipher)对称密码体制不仅可用于数据加密，也可用于消息的认证。非对称密码体制（公钥密码体制）每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进

10、行注册公布无需事先分配密钥，加密和解密能力分开可以实现多个用户加密的消息只能由一个用户解读（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签名）2.1.4 密码分析学 密码分析学：研究如何分析或破解各种密码编码体制的一门科学。 根据攻击者拥有的信息分为以下4类： 唯密文攻击 （ciphertextonly attack） 已知明文攻击（knownplaintext attack） 选择明文攻击（chosenplaintext attack） 选择密文攻击（chosenciphertext attack）唯密文攻击 密码破译者除了拥有截获的

11、密文，以及对密码体制和密文信息的一般了解外，没有什么其它可以利用的信息用于破译密码。在这种情况下进行密码破译是最困难的，经不起这种攻击的密码体制被认为是完全不保密的。已知明文攻击密码破译者不仅掌握了相当数量的密文，还有一些已知的明-密文对（通过各种手段得到的）可供利用。现代的密码体制（基本要求）不仅要经受得住唯密文攻击，而且要经受得住已知明文攻击。选择明文攻击 密码破译者不仅能够获得一定数量的明-密文对，还可以用它选择的任何明文，在同一未知密钥的情况下能加密相应的密文。 密码破译者暂时控制加密机。选择密文攻击密码破译者能选择不同的被加密的密文，并还可得到对应的解密的明文，据此破译密钥及其它密文

12、。 密码破译者暂时控制解密机。破译算法的分类（递减）全部破译 密码分析者找到密钥Key。全盘推导 密码分析者找到一个代替算法A，在不知道密钥Key的情况下，等价于Dkey(C)=P。实例（或局部）推导 密码分析者从截获的密文中找出明文。信息推导 密码分析者获得一些有关密钥或明文的信息。这些信息可能是密钥的几个位、有关明文格式的信息等。 攻击密码方法穷举破译法统计分析法数学分析法 穷举破译法 对截收的密文依次用各种可能的密钥试译，直到得到有意义的明文；或在不变密钥下，对所有可能的明文加密直到得到与截获密报一致为止，此法又称为完全试凑法(Complete trial-and-error Metho

13、d)。只要有足够多的计算时间和存储容量，原则上穷举法总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都通过增大密钥量和加大解密算法的复杂度来使这一方法在实际上是不可行的。 统计分析法 利用明文的已知统计规律进行破译的方法。密码破译者对截收的密文进行统计分析，总结出其间的统计规律，并与明文的统计规律进行对照比较，从中提取出明文和密文之间的对应或变换信息。 密码设计者可使明文的统计特性不带入到密文中来对抗统计分析攻击。 数学分析法针对密码算法的所使用的数学依据通过数学求解的方法来破译。密码算法的设计者通过构造数学难题来抵御分析攻击。2.1.5 密码体制的安全性 无条件安全 计算上安全 可

14、证明安全无条件安全又称为绝对不可破译不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。计算上安全计算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。 破译算法的代价大于加密数据的价值 破译算法所需的时间比数据保密的时间更长 用同一密钥加密的数据量比破译算法需要的数据量少的多可证明的安全从理论上证明破译它的计算量不低于解已知难题的计算量。注：是一种特殊的计算上的安全。密码体制的基本原则密码体制的安全性是依赖密钥

15、的保密，而不是依赖于对加密算法的保密；加密和解密算法适用于密钥空间中的所有元素；密码体制既易于实现又便于使用。密码体制是不可破的（理论上不可破，实际上不可破）；密钥空间应足够大，使得试图通过穷举密钥空间进行搜索的方式在计算上不可行。2.2 密码学基本技术2.2.1 古典密码体制2.2.2 对称密码体制2.2.3 公钥密码体制2.2.4 报文鉴别和哈希函数2.2.5 数字签名2.2 密码学基本技术2.2.1 古典密码体制2.2.2 对称密码体制2.2.3 公钥密码体制2.2.4 报文鉴别和哈希函数2.2.5 数字签名2.2.1 古典密码体制古典密码体制是指那些比较简单的、大多数采用手工或机械操作

16、对明文进行加密、对密文进行解密的密码体制。其技术、思想以及破译方法虽然很简单，但是反映了密码设计和破译的思想，是学习密码学的基本入口，对于理解、设计和分析现代密码仍然具有借鉴的价值。两个基本方法 置换（Permutation）:保持明文中所有字母不变，利用置换打乱明文字母的位置和次序，即在消息内变换字母的位置。 代替（Substitution）:明文中每一个字符被替换成密文中的另外一个字符。接收者对密文进行逆替换就恢复出明文来。1.置换密码（permutation） (1)列置换加密 明文以固定的宽度水平写出，密文按垂直方向读出。 明文：COMPUTERSYSTEMSECURITY密文：CTS

17、ETOETCYMREUPSMRUYSI COMPU TERSY STEMS ECURI TY（2）双重置换明文：attack at tomorrow密文：atkcmootowrrtata(3)周期置换加密 分组倒置 明文: This is not secure thi sis not sec ure 密文: ihtsistonceseru 2.代替密码(subtitution) 单表代替密码：将明文的一个字符用相应的一个密文字符代替。 多表代替密码：单个明文字符可以映射成几个密文字符之一，由多个单表代替密码构成，例如，可能有4个不同的简单代替密码。例如A可能对应于5、13、25或56，“B”可

18、能对应于7、19、31或42，等等。 多字母代替密码：字符块被成组的加密，例如“ABA”可能对应于“RTQ”，ABB可能对应于“SLL”等。 单表密码（恺撒密码,乘积密码,仿射密码） 多表密码(维吉尼亚） 多字母代换密码 (希尔密码）(1) 同余理论1)模运算:即求余,记为mod（即5+10000除以7的余数）即：10000天后是星期二 2)同余定义:m正整数,m除a,b余数同,称 a,b为模m同余,记为a=b mod m例:假设今天是星期五，请问10000天后是星期几？3)同余满足自反性、对称性、传递性； a=a mod n； 若a=b mod n，则b=a mod n； 若a=b mod

19、n，b=c mod n，则a=c mod n4)所有与a同余的整数所组成的集合称为a的同余类 所有同余类所形成的集合记为 5)同余的性质：若a =b mod n， c =d mod n，则 （1）a+c=b+d mod n （2） ac=bd mod n(a mod n) +(b mod n)mod n=(a + b) mod n； - - * * 6)若ax mod n =1，则称a与x对于模n互为逆元。 (用Euclid算法求乘法逆元) 例：152 mod 12=(3*3)mod 12=9注：若a和n互素，则a在模n下有逆元。(2)单表密码1)恺撒密码(加法密码、移位密码)明文 26个字母

20、密文 26个字母加密 Ek(m)=m+k=c mod n (n=26)当k=3,每个字母使用其后第3个(循环)代替明文 meet me after class密文 PHHW PH DIWHU FODVV解密 Dk(c)=c-k=m mod n密钥量为n-1应用同余性质（1）2) 乘法密码加密: c (m X k) mod n 解密: m (c X k-1) mod n 要求k和n互素 (n=26)Euler函数：(n)=与n互素的、小于n的正整数的个数，n1。 例：(3)= (4) = (6) =2，(5)=4，(7) =6 ,(12)=4 密钥量为Euler函数(n)-1应用同余性质（2）以

21、及逆元的定义加密:选取k1，k2两个参数，其中 k1 与 n 互素 c(k1m + k2)mod n解密: mk1-1 (c - k2)mod n (n=26)密钥量为(n)-1)*(n-1)3) 仿射密码4)单表代替密码（单表置换）加密函数:abcdefghijklmDKVQFIBJWPESCnopqrstuvwxyzXHTMYAUOLRGZN解密函数: 明文: if we wish to replace letters密文: WI RF RWAJ UH YFTSDVF SFUUFYANOPQRSTUVWXYZzujdwlptcinryABCDEFGHIJKLMsgmakexofhbvq密钥

22、量：26！ 1025（约109年，接近宇宙年龄1010年）明文中各个字母出现的统计概率字母组合概率双字母组合：th、he、in、er三字母组合：the、ing、and单表代替无法抵御统计分析攻击！(2) 多表密码（维吉尼亚）多表密码是利用多个单表代替密码构成的密码体制。它在对明文进行加密的过程中依照密钥的指示轮流使用多个单表代替密码。M=(m1,m2,mn) K=(k1,k2,kn) C=(c1,c2,cn)加密变换：ci=Eki(mi)=mi+ki mod n解密变换： mi=Dki(mi)=ci - ki mod nwearediscoveredeceptivedecepZICVTWQNG

23、RZGVTdsaveyourselftivedeceptiveWAVZHCQYGLMGJ(3)多字母代换密码（希尔密码）加密变换：cKm mod n解密变换：m=cK-1 mod n 其中c和m分别是密文(c1,c2,cn)和明文=(m1,m2,mn)向量，K是密钥矩阵 c1k11 k12 k13 m1 c2 k21 k22 k32 m2 c3k31 k32 k33 m3即：c1 = k11*m1 + k12*m2 + k13*m3 mod n c2 = k21*m1 + k22*m2 + k32*m3 mod n c3 = k31*m1 + k32*m2 + k33*m3 mod n 注：矩

24、阵K得有逆KK-1=K-1K=I (K的行列式为非零)定理：k-1 存在等价于gcd|k|，261对于二阶矩阵 ，|A|例： ，|A|=27=27*1=1mod 26,则 注：a+b=0 mod 26, 即 a=-b mod 26 Hill密码举例密匙产生：首先决定所用矩阵的大小，譬如是22, 其中E的行列式值detE必须与26互质，否则不存在E的反矩阵。明文m=Hill 矩阵形态加密过程：密文c=pbwz 解密矩阵计算加密矩阵的反矩阵，再进行模运算（mod 26），得解密矩阵 解密过程 用唯密文攻击法分析多字母代换密码如Hill密码是比较困难的。Hill密码可抵抗频率分析，不能抵抗已知明文攻

25、击。 若得到n个不同的明密文对时，有明文：Friday , n=2密文：pocfkuHill密码已知明文攻击举例2.2.2 对称密码体制对称密码算法有时又叫传统密码算法，就是加密密钥和解密密钥相同，或者能够从一个密钥中推算出来另一个密钥。在大多数对称算法中，加密解密密钥是相同的。这些算法也叫秘密密钥算法或单密钥算法，它要求发送者和接收者在安全通信之前，商定一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加密解密。只要通信需要保密，密钥就必须保密。 对称密码算法的分类序列密码分组密码1. 序列密码序列密码主要用于政府、军事、外交等领域。序列密码的加密过程是先把明文转换成

26、二进制序列，然后同密钥序列进行逐位加密生成密文序列发送给接收者。接收者用相同的密钥序列对密文序列进行逐位解密以恢复出明文序列。例：Aice欲将明文m=OK，加密成密文c，传递给Bob。假设密钥为k=DA。加密：明文密钥密文解密：密文密钥明文表示XOR运算序列密码加解密框图序列密码特点安全强度取决于密钥序列的随机性和不可预测性，核心问题是密钥流生成器的设计。理论上能够产生周期为2|K|-1-1的伪随机序列，基于混沌理论产生的序列密码具有良好的随机性。可实现一次一密，达到理论上的安全性。加解密端的需要精确同步，不存在数据扩展和错误转播。实时性好，运算速度快，加密、解密易实现。目前流密钥序列的产生大

27、多数是基于硬件的移位寄存器来实现，其结构简单。2.分组密码分组密码（block cipher）是现代密码学中的重要体制之一，也是应用最为广泛、影响最大的一种密码体制。加密原理是将明文按照某一规定的n bit长度分组（最后一组长度不够时要用规定的值填充，使其成为完整的一组），然后使用相同的密钥对每一分组分别进行加密。分组密码框图明文空间:0,1序列,为2n密文空间:0,1序列,为2m通常取m=n。若mn，则为有数据扩展的分组密码；若mn，则为有数据压缩的分组密码。加密变换:0,1,2, 2n-1上的一个置换,不同可逆变换的个数有2n!个。分组密码算法要求 (1)分组长度n足够大。若分组太小,比如

28、只有8位,则和单表代替一样.对于大的分组类似于多字母代替方法,能抵抗频率分析。另外,使分组代换字母表中的元素个数2n足够大，防止明文穷举攻击法奏效,目前长度一般取128bit。（2）密钥量足够大。抵抗穷举攻击。但密钥又不能过长，以便于密钥的管理,一般取128bit 。（3）密码变换足够复杂。使攻击者除穷举攻击外，找不到其他快捷破译方法。 (4)加密和解密运算简单，易于软件和硬件高速实现。如将分组n化分为子段，每段长为8、16或者32，设计的算法采用规则的模块结构，如多轮迭代等，以便于软件和VLSI快速实现。用软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加

29、、乘、移位等实现。用硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同而已。这样，加密和解密就可用同一器件实现。分组密码设计思想扩散混乱扩散所谓扩散（diffusion），是指要将算法设计得使每一比特明文的变化尽可能多地影响到输出密文序列的变化，以便隐蔽明文的统计特性；扩散的另一层意思是将每一位密钥的影响也尽可能迅速地扩展到较多的输出密文比特中去。即扩散的目的是希望密文中的任一比特都要尽可能与明文、密钥相关联，或者说，明文和密钥中任何一比特值得改变，都会在某种程度上影响到密文值的变化，以防止统计分析攻击。扩散的举例说明无扩散技术的加密 p1:00000000 c1:0000

30、0010 p2:00000001 c2:00000011有扩散技术的加密 p1:00000000 c1:01011010 p2:00000001 c2:11101011混乱所谓混乱(confusion)，是指在加密变换过程中是明文、密钥以及密文之间的关系尽可能地复杂化，使得输出是输入的非线性函数。通过复杂的非线性代替法实现，以防密码破译者采用统计分析法进行破译攻击。混乱可以用“搅拌机”来形象地解释，将一组明文和一组密文输入到算法中，经过充分混合，最后变成密文。同时要求，执行这种“混乱”作业的每一步都必须是可逆的，即明文混乱以后能得到密文，反之，密文经过逆向的混乱操作以后能恢复出明文。混乱的举例

31、说明典型的分组密码结构:Feistel结构(1973年）置换:代替过程完成后，再交换左、右两半数据。乘积密码:每轮结构相同,但以不同的子密钥Ki作为参数。代替:每轮中右半数据被作用于轮函数F后，再与左半数据进行异或运算。是Shannon提出的代替置换网络（substitution-permutation network, SPN）的特有形式。特点是每次只处理明文的一半。算法说明Ki：每级密钥不同 Li-1LiRi-1Ri Li-1 f(Ri-1 , Ki) （a）加密加密：F(Li-1Ri-1)=LiRi Li= Ri-1 Ri= Li-1 f(Ri-1,Ki)Li-1LiRi-1Ri Ri

32、f(Ri-1 , Ki) （b）解密RiRi-1LiLi-1 Ri f(Li , Ki) （c）等效解密P=两个子块左右交换Li-1Ri-1=PFP(LiRi)解密：Li-1Ri-1=F-1(LiRi)Ri-1=LiLi-1 = Ri f(Li,Ki)加密：F(Li-1Ri-1)=LiRi Li= Ri-1 Ri= Li-1 f(Ri-1,Ki)Feistel算法要求 （1）分组长度n足够大。（2）密钥量足够大。（3）循环次数越多越安全。（4）轮函数变换足够复杂。（5）子密钥产生算法。（6）快速软件实现。（4）算法容易分析，这样可容易发现弱点，并给出对其的更高安全级别的保障措施。Feistel

33、结构的加密和解密+K16+ K2+ K1+ K1+ K2+ K16L0R16L1R0R1L16L16R16R15L15R0L0数据加密标准DES DES（Data Encryption Standard）是对称分组密码体制典型代表。它于1977由美国国家标准技术研究所NIST在IBM公司的LUCIFER算法基础上进行修正制定而成。1981年，DES被美国商业组织所采纳，作为美国国家标准数据加密算法。该算法很快被用于政府的机密性目的和金融工业界的完整性目的，并被广泛地应用于各个领域。 数据加密标准DES的特点分组加密算法：明文和密文为64位分组长度。对称算法：加密和解密除密钥编排不同外，使用同一

34、算法。密钥长度：56位，但每个第8位为奇偶校验位，可忽略。密钥可为任意的56位数，但存在弱密钥，容易避开。采用混乱和扩散的组合，每个组合先替代后置换，共16轮。只使用了标准的算术和逻辑运算，易于实现。DES加密算法框图DES中的子密钥的生成循环移位压缩置换初始置换IP和初始逆置换IP-1 IP和IP-1直接置换DES的一轮迭代Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器选择扩展运算E48比特寄存器子密钥Ki（48比特）32比特寄存器选择压缩运算S置换运算PRi（32比特）Li=Ri-1扩展置换-盒32位扩展到48位加密函数f(Ri-1,Ki)压缩替代S-盒48位压缩到

35、32位共8个S盒S盒的规则S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒的输入和输出S盒是DES的最敏感部分，除此之外的计算都是线性的。S盒作为该密码体制的非线性组件对安全性至关重要。其原理至今未公开。美国国家安全局透露了S盒的几条设计准则：每行是015的一个排列,是列输入的非线性函数。1 .所有的S盒都不是它输入的线性仿射函数。就是没有一个线性方程能将四个输出比特表示成六个比特输入的函数。2 .改变S盒的1位输入，输出至少改变2位。这意味着S盒是经过精心设计的，它最大程度上增大了扩散量。3 .S盒的任意一位输入保持不变时，0 和1个数之差极小。即如果保持一位不变而改变

36、其它五位，那么其输出0和1的个数不应相差太多。置换p-盒的构造DES性能 1） DES雪崩效应：明文或密钥的微小变化引起密文的较大变化.若变化太小,会导致减小待搜索明文和密钥空间的大小。明文变化 密钥变化 循环 不同比特个数 循环不同比特个数 01001612221214335328163416252)对称性：3)存在弱密钥(4个)和半弱密钥 (12个)弱密钥：半弱密钥：4)运算效率:硬件:数字设备公司DEC开发DES芯片,加解密速度高达1GB/s,相当于1560万组每秒.软件:在IBM3090大型机可达到3.2万次每秒 DES算法的安全性分析1)穷举攻击 1997年开始，RSA公司发起了一个

37、称作“向DES挑战”的竞技赛。1997年1月，用了96天时间，成功地破解了用DES加密的一段信息；一年之后，在第二届赛事上，这一记录41天 ；1998年7月， “第2-2届DES挑战赛（DES Challenge II-2）” 把破解DES的时间缩短到了只需56个小时； “第三届DES挑战赛（DES Challenge III）”把破解DES的时间缩短到了只需22.5小时 。这意味着随着计算能力的增长，必须相应地增加密钥的长度。2）差分分析(1990,Biham和Shamir以色列) 选择明文攻击,通过分析特定明文对的差值对密文对差值的影响来获得可能性最大的密钥, 尝试247次明文密文对,在分

38、析过程中经过237次DES运算。可用于评估算法安全性。（对破译17/18轮的DES所需时间与穷举搜索大致相等，但对8轮DES只需几分钟）3）线性分析(1993,Mitsuru Matsui日本) 已知明文攻击,通过选择充分多的明文密文对，寻找一个明文密文密钥之间近似的线性表达式来破解密钥, 尝试243次明文密文对。对DES更有效。1）二重DES （二个密钥，有效长度128-16=112位） 加密：C=Ek2Ek1(M) 解密：M=Dk1Dk2(C)对264个输入分组，总映射个数为 ,另一方面，对每个不同的密钥，DES都定义了一个映射，总映射数为2561017。因此，可假定用两个不同的密钥两次使用DES，可得一个新映射，而且这一新映射不出现在单重DES定义的映射中。这一假定已于1992年被证明。DES的发展即二重DES产生的映射不会等价于单重DES加密。但二重DES存在称为中途相遇攻击的攻击方案，这种攻击不依赖于DES的任何特性，可用于攻击任何分组密码。如果有 ,那么若已知一个明文密文对(P,C)，首先，用256个所有可能的K1对P加密，将加密结果存入一表，然后用256个所有可能的K2对C解密，在上述表中查找与C解密结果相匹配的项，如果找