信息加密与密码分析

1、信息加密与密码分析信息加密与密码分析 内容提要内容提要密码学的基本概念，加密类型，混合加密方法以及消密码学的基本概念，加密类型，混合加密方法以及消息一致性息一致性 密码学应用，密码分析与攻击密码学应用，密码分析与攻击 加密领域中两种主流加密技术：加密领域中两种主流加密技术： des加密（加密（data encryption standard） rsa加密（加密（rivest-shamir-adleman） 加密工具加密工具pgp（pretty good privacy）2.1密码学概述密码学概述 密码学密码学是一门古老而深奥的学科，对一般是一门古老而深奥的学科，对一般人来说是非常陌生的。长期以

2、来，只在很人来说是非常陌生的。长期以来，只在很小的范围内使用，如军事、外交、情报等小的范围内使用，如军事、外交、情报等部门。计算机密码学是研究计算机信息加部门。计算机密码学是研究计算机信息加密、解密及其变换的科学，是数学和计算密、解密及其变换的科学，是数学和计算机的交叉学科，也是一门新兴的学科。随机的交叉学科，也是一门新兴的学科。随着计算机网络和计算机通信技术的发展，着计算机网络和计算机通信技术的发展，计算机密码学得到前所未有的重视并迅速计算机密码学得到前所未有的重视并迅速普及和发展起来。普及和发展起来。2.1.1密码学的发展密码学的发展 密码学的历史比较悠久。密码学的历史比较悠久。在四千年前

3、，古埃及人在四千年前，古埃及人就开始使用密码来保密传递消息。两千多年前，就开始使用密码来保密传递消息。两千多年前，罗马国王罗马国王julius caesar（恺撒）就开始使用（恺撒）就开始使用目前称为目前称为“恺撒密码恺撒密码”的密码系统。但是密码的密码系统。但是密码技术直到技术直到20世纪世纪40年代以后才有重大突破和年代以后才有重大突破和发展。特别是发展。特别是20世纪世纪70年代后期，由于计算年代后期，由于计算机、电子通信的广泛使用，现代密码学得到了机、电子通信的广泛使用，现代密码学得到了空前的发展。空前的发展。密码学相关科学大致可以分为密码学相关科学大致可以分为3个方面个方面：密码学密

4、码学（cryptology）是研究信息系统安全保密的）是研究信息系统安全保密的科学，科学，密码编码学密码编码学（cryptography）主要研）主要研究对信息进行编码，实现对信息的隐藏。究对信息进行编码，实现对信息的隐藏。密码密码分析学分析学（cryptanalytics）主要研究加密消息）主要研究加密消息的破译或消息的伪造。的破译或消息的伪造。n密码学的发展大致经过密码学的发展大致经过3个阶段个阶段（ 略略 ）第一阶段是第一阶段是1949年之前，密码学是一门艺术，这阶段的研年之前，密码学是一门艺术，这阶段的研究特点是：究特点是：1. 密码学还不是科学，而是艺术密码学还不是科学，而是艺术2.

5、 出现一些密码算法和加密设备出现一些密码算法和加密设备3. 密码算法的基本手段出现，主要针对字符密码算法的基本手段出现，主要针对字符4. 简单的密码分析手段出现，数据的安全基于算法的保密。简单的密码分析手段出现，数据的安全基于算法的保密。该阶段具有代表性的事件是：该阶段具有代表性的事件是：1883年年kerchoffs第一次明第一次明确的提出了编码的原则：确的提出了编码的原则： 加密算法应建立在算法的公开加密算法应建立在算法的公开且不影响明文和密钥的安全的基础上。这个原则得到广且不影响明文和密钥的安全的基础上。这个原则得到广泛承认，成为判定密码强度的衡量标准，实际上也成为泛承认，成为判定密码强

6、度的衡量标准，实际上也成为传统密码和现代密码的分界线。传统密码和现代密码的分界线。第二阶段是第二阶段是1949-1975年，密码学成为一门独立的科学，年，密码学成为一门独立的科学，该阶段计算机的出现使基于复杂计算的密码成为可能。该阶段计算机的出现使基于复杂计算的密码成为可能。主要研究特点是：数据安全基于密钥而不是算法的保密。主要研究特点是：数据安全基于密钥而不是算法的保密。第三阶段是第三阶段是1976年以后，密码学中公钥密码学成为主要年以后，密码学中公钥密码学成为主要研究方向，该阶段具有代表性的事件是：研究方向，该阶段具有代表性的事件是：1976年，年，diffie和和hellman提出了不对

7、称密钥。提出了不对称密钥。1977年，年，rivest等提出了等提出了rsa公钥算法。公钥算法。1977年，年，des算法出现。算法出现。80年代，出现年代，出现idea和和cast等算法。等算法。90年代，对称密钥密码算法进一步成熟，年代，对称密钥密码算法进一步成熟，rijndael，rc6等出现，逐步出现椭圆曲线等其他公钥算法。等出现，逐步出现椭圆曲线等其他公钥算法。2001年，年，rijndael成为成为des算法的替代者。算法的替代者。2004年年8月，山东大学信息安全所所长王小云在国际会议月，山东大学信息安全所所长王小云在国际会议上首次宣布了她及她的研究小组对上首次宣布了她及她的研究

8、小组对md5、haval-128、md4和和ripemd等四个著名密码算法的破译结果，引等四个著名密码算法的破译结果，引起世界轰动。这阶段的主要特点是：公钥密码使得发送起世界轰动。这阶段的主要特点是：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能。端和接收端无密钥传输的保密通信成为可能。2.1.2 密码技术简介密码技术简介 计算机网络的广泛应用，计算机网络的广泛应用，产生了大量的电子数据，这些电子产生了大量的电子数据，这些电子数据需要传输到网络的许多地方。有意的计算机犯罪和无意数据需要传输到网络的许多地方。有意的计算机犯罪和无意的数据破坏对这些数据产生了很大的威胁。国家机密、企业的数据

9、破坏对这些数据产生了很大的威胁。国家机密、企业经济信息、银行网上业务等中的任何差错都会使国家安全、经济信息、银行网上业务等中的任何差错都会使国家安全、企业经营受到巨大的损害。原则上来说对电子数据的攻击有企业经营受到巨大的损害。原则上来说对电子数据的攻击有两种形式。两种形式。（1）被动攻击。被动攻击。非法从传输信道上截取信息，或从存储载非法从传输信道上截取信息，或从存储载体上偷窃信息。体上偷窃信息。（2）主动进攻。主动进攻。对传输或存储的数据进行恶意的删除、修对传输或存储的数据进行恶意的删除、修改等。改等。虽然对这些行为已经建立相应的法律，但由于这种犯罪形式虽然对这些行为已经建立相应的法律，但由

10、于这种犯罪形式的特殊性，对于它的监督、甚至量刑都是很困难的。因此在的特殊性，对于它的监督、甚至量刑都是很困难的。因此在不断完善相应法律和监督的同时，还需要加强不断完善相应法律和监督的同时，还需要加强自我保护，密自我保护，密码技术码技术是一种有效而经济的方法。是一种有效而经济的方法。经典的密码学经典的密码学是关于加密和解密是关于加密和解密，主要用于保密通信，主要用于保密通信。目前，已经不再是单一的加解密技术，已被有效、系目前，已经不再是单一的加解密技术，已被有效、系统地用于保证电子数据的统地用于保证电子数据的保密性、完整性和真实性保密性、完整性和真实性。保密性保密性就是对数据进行加密，使非法用户

11、无法读懂数据就是对数据进行加密，使非法用户无法读懂数据信息，而合法用户可以应用密钥读取信息。信息，而合法用户可以应用密钥读取信息。完整性完整性是对数据完整性的鉴别，以确定数据是否被非法是对数据完整性的鉴别，以确定数据是否被非法篡改，保证合法用户得到正确、完整的信息。篡改，保证合法用户得到正确、完整的信息。真实性真实性是数据来源的真实性、数据本身真实性的鉴别，是数据来源的真实性、数据本身真实性的鉴别，可以保证合法用户不被欺骗。可以保证合法用户不被欺骗。现代密码技术现代密码技术的应用已经深入到数据处理过程的各个环的应用已经深入到数据处理过程的各个环节，包括：数据加密、密码分析、数字签名、信息鉴节，

12、包括：数据加密、密码分析、数字签名、信息鉴别、零知识认证、秘密共享等。别、零知识认证、秘密共享等。密码学的数学工具密码学的数学工具也更加广泛，有概率统计、数论、代也更加广泛，有概率统计、数论、代数、混沌和椭圆曲线等。数、混沌和椭圆曲线等。密码学专业术语包括密码学专业术语包括：消息和加密、鉴别、完整性和抗：消息和加密、鉴别、完整性和抗抵赖性、算法和密钥、对称算法和非对称算法（公开抵赖性、算法和密钥、对称算法和非对称算法（公开密钥算法）等等。密钥算法）等等。2.1.3 消息和加密消息和加密 加密：加密：可翻译成可翻译成“encipher” 或或“ encrypt”，用某种，用某种方法伪装消息以隐藏

13、它的内容的过程，方法伪装消息以隐藏它的内容的过程，解密：解密：可翻译成可翻译成“decipher” 或或“decrypt”，把密文转，把密文转变为明文的过程。变为明文的过程。明文：明文：未加密消息，未加密消息，密文：密文：加了密的消息，加了密的消息，图图2-1表明了加密和解密的过程。表明了加密和解密的过程。加密加密解密解密明文明文密文密文原始明文原始明文明文用明文用m（message,消息）或消息）或p（plaintext,明文）表示明文）表示,它可能是比特流、文本文件、位图、数字化的语音流或它可能是比特流、文本文件、位图、数字化的语音流或者数字化的视频图像等。者数字化的视频图像等。密文用密文

14、用c（cipher）表示）表示,也是二进制数据，有时也是二进制数据，有时c=m。通过压缩和加密的结合，通过压缩和加密的结合，c0)可能依赖于可能依赖于k，0，x0，x1，xi-1等参数。等参数。分组密码无记忆。分组密码无记忆。2.3常用加密算法常用加密算法目前加密算法很多，具有代表性的加密算法：目前加密算法很多，具有代表性的加密算法： des算法、算法、idea算法、算法、aes算法、算法、rc5算法、算法、rc4序列序列算法、算法、rsa算法与椭圆曲线算法。算法与椭圆曲线算法。2.3.1 idea 算法算法国际加密标准国际加密标准idea是一个对称迭代分组密码，是一个对称迭代分组密码，分组长

15、度为分组长度为64比特，密钥比特，密钥长度为长度为128比特。比特。idea的软件实现速度与的软件实现速度与des差不多。差不多。但硬件实现速度要比但硬件实现速度要比des快得多，快将近快得多，快将近10倍。设计者倍。设计者们声称由们声称由eth zurich开发的一种芯片，采用开发的一种芯片，采用idea算法算法的加密速率可达到的加密速率可达到177m比特比特/秒。秒。idea密码中使用了以下三种不同的运算：密码中使用了以下三种不同的运算： 1.逐比特异或运算；逐比特异或运算； 2.模模2加运算；加运算； 3.模模2+1乘运算，乘运算，0与与2对应。对应。idea算法算法是是由由8圈迭代和随

16、后的一个输出变换组成。圈迭代和随后的一个输出变换组成。它将它将64比特的数据分成比特的数据分成4个子块，每个个子块，每个16比特，比特，令这四个子块作为迭代第一轮的输出，全部共令这四个子块作为迭代第一轮的输出，全部共8圈圈迭代。每圈迭代都是迭代。每圈迭代都是4个子块彼此间以及个子块彼此间以及16比特比特的子密钥进行异或，的子密钥进行异或，mod2加运算，加运算，mod2+1乘乘运算。任何一轮迭代中，第三和第四子块互换。运算。任何一轮迭代中，第三和第四子块互换。该算法所需要的该算法所需要的“混淆混淆”可通过连续使用三个可通过连续使用三个“不相容不相容”的群运算于两个的群运算于两个16比特子块来获

17、得，比特子块来获得，并且该算法所选择使用的并且该算法所选择使用的ma-（乘加）结构可提（乘加）结构可提供必要的供必要的“扩散扩散”。idea有多达有多达2的的51次方个弱密钥，这些弱密钥是否次方个弱密钥，这些弱密钥是否会威胁它的安全性还是一个迷。但毫无疑问，会威胁它的安全性还是一个迷。但毫无疑问，idea密码能够抵抗差分分析和线性分析。密码能够抵抗差分分析和线性分析。2.3.2 aes 算法（略）算法（略） 2000年年10月，月，nist（美国国家标准和技术研究院）宣（美国国家标准和技术研究院）宣布通过从布通过从15种候选算法中选出的一项新的密钥加密标种候选算法中选出的一项新的密钥加密标准。

18、新的标准将会代替密钥长度变的太短的旧的准。新的标准将会代替密钥长度变的太短的旧的des算法。算法。rijndael被选中成为将来的被选中成为将来的aes(高级加密标准高级加密标准advanced encryption standard)。aes有如下优点：可变的密钥长度、混合的运算、数据有如下优点：可变的密钥长度、混合的运算、数据相关的圈数、密钥相关的圈数、密钥相关的相关的圈数、密钥相关的圈数、密钥相关的s盒、长密盒、长密钥调度算法、变量钥调度算法、变量f、可变长明文、可变长明文/密文块长度、可变密文块长度、可变圈数、每圈操作作用于全部数据、圈数、每圈操作作用于全部数据、这个加密体系是一种对称

19、分组加密方法，因为信息的内这个加密体系是一种对称分组加密方法，因为信息的内容是以容是以128位长度的分组为加密单元的。加密密钥长位长度的分组为加密单元的。加密密钥长度有度有128，192或或256位多种选择。位多种选择。2.3.3 rc5算法（省）算法（省） rc5是对称加密算法，由是对称加密算法，由rsa公司的首席科学家公司的首席科学家r.rivest于于1994年设计，年设计，1995年正式公开的一个很实用的加密算法。它年正式公开的一个很实用的加密算法。它主要通过数据循环来实现数据的扩散和混淆。每次循环的次数主要通过数据循环来实现数据的扩散和混淆。每次循环的次数都依赖于输入数据，事先不可预

20、测。都依赖于输入数据，事先不可预测。rc5实际上是由三个参数决定的一组加密算法，即分组长度实际上是由三个参数决定的一组加密算法，即分组长度w，密钥长度密钥长度b和轮数和轮数r，见下表。，见下表。参数定义允许值w字的bit数大小。rc5加密的基本单位为2个字块16,32,64r轮数0,1, ,255b密钥字节的长度（8-bit bytes)0,1, ,255nrc5加密明文块的长度为加密明文块的长度为32，64，128 bits。并且对应。并且对应同样长度的密文。密钥长度为从同样长度的密文。密钥长度为从0到到2040 bits。一个特。一个特定的定的rc5表示为：表示为： rc5-w/r/b。r

21、ivest建议使用的标建议使用的标注注rc5为：为：rc5-32/12/16（明文分组长度（明文分组长度64，加密轮，加密轮数数12，密钥长度，密钥长度128 bits)。rc5算法的特点是：算法的特点是：n适用于软件或者硬件实现；适用于软件或者硬件实现；n运算速度快；运算速度快；n能适应于不同字长的程序（一个字的能适应于不同字长的程序（一个字的bit数是数是rc5的一个的一个参数；不同字长派生出相异的算法）；参数；不同字长派生出相异的算法）；n加密的轮数可变（轮数是加密的轮数可变（轮数是rc5的第二个参数，这个参数的第二个参数，这个参数用来调整加密速度和安全性的程度）；用来调整加密速度和安全

22、性的程度）；n密钥长度是可变的（密钥长度是密钥长度是可变的（密钥长度是rc5的第三个参数）；的第三个参数）；nrc5形式简单，易于实现，加密强度可调节；形式简单，易于实现，加密强度可调节；n对记忆度要求不高（使对记忆度要求不高（使rc5可用于类似可用于类似smart card这类这类的对记忆度有限定的器件）；的对记忆度有限定的器件）；n高保密性（适当选择好参数）；高保密性（适当选择好参数）；n对数据实行对数据实行bit循环移位（增强抗攻击能力）；循环移位（增强抗攻击能力）；2.3.4 rc4序列算法（省） 序列算法体制是：密钥馈送给一个算法，序列算法体制是：密钥馈送给一个算法，产生一个无穷序列

23、产生一个无穷序列(这种算法通常称为序这种算法通常称为序列产生器或密钥流产生器列产生器或密钥流产生器)，但是，在实，但是，在实际应用中很难做到产生无穷序列际应用中很难做到产生无穷序列(此时称此时称one time pad),达到所谓的完全保密，达到所谓的完全保密，所以现在实际应用的序列密码体制都产所以现在实际应用的序列密码体制都产生伪随机密码序列。序列密码体制如图生伪随机密码序列。序列密码体制如图2-11所示。所示。 序 列 生 产 器 明 文 数 据 + 密 文 k（ 密 钥 ） 伪 随 机 序 列 加 ， 解 密 器 nrc4是目前使用较多，性能也较好的序列算法，它由是目前使用较多，性能也较

24、好的序列算法，它由ron rivest在在1987年为年为rsa公司开发，是可变密钥公司开发，是可变密钥长度的序列密码，该算法以长度的序列密码，该算法以ofb方式工作：密钥序列方式工作：密钥序列与明文互相独立。它有一个与明文互相独立。它有一个88的的s盒：盒：s0，s1，s255。所有项都是数字。所有项都是数字0到到255的置换，并的置换，并且这个置换是一个可变长度密钥的函数。它有两个计且这个置换是一个可变长度密钥的函数。它有两个计数器：数器：i和和j，初值为，初值为0。要产生一个随机字节，需要按。要产生一个随机字节，需要按下列步骤进行：下列步骤进行：ni=(i+1)mod256nj=(j+s

25、i)mod256n交换交换si和和sjnt=(si+sj)mod 256nk=stn字节字节k与明文异或产生密文，或者与密文异或产生明与明文异或产生密文，或者与密文异或产生明文。文。rc4的加密速度很快，大约是的加密速度很快，大约是des的的10倍。倍。rc4广泛应用于商业软件中，包括广泛应用于商业软件中，包括locus notes、苹果计、苹果计算机的算机的aoce、oracle的安全的安全sql数据库以及数据库以及adobe的的acrobat中。中。2.3.5 椭圆曲线算法（省）椭圆曲线算法（省） n在公钥密码算法中，在公钥密码算法中，1985年，年，n. koblitz和和v. mill

26、er分别独立提出分别独立提出了椭圆曲线密码体制了椭圆曲线密码体制(ecc)，其依据就是定义在椭圆曲线点群上的离，其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。他们并没有提出新的算法，只是把椭圆曲线运散对数问题的难解性。他们并没有提出新的算法，只是把椭圆曲线运用到已存在的公钥密码算法中，比如说用到已存在的公钥密码算法中，比如说elgamal加密算法。加密算法。n随后，随后，koyama等在等在crypto91、demytko在在eurocrypt93中分别中分别提出了新的基于椭圆曲线的单项限门函数，生成了类似于提出了新的基于椭圆曲线的单项限门函数，生成了类似于rsa的公钥的公钥密码算法。

27、椭圆曲线密码体制和密码算法。椭圆曲线密码体制和rsa体制比较起来，所需要的密钥量体制比较起来，所需要的密钥量小，安全程度高，比如小，安全程度高，比如rsa密码体制需要密码体制需要1024-bit的密钥才能达到的密钥才能达到的安全程度，利用椭圆曲线只需要的安全程度，利用椭圆曲线只需要160比特位的密钥就能够保证同样比特位的密钥就能够保证同样的安全，密钥长度的减少同时带来了计算速度的提高。即使是在剩余的安全，密钥长度的减少同时带来了计算速度的提高。即使是在剩余类环运用离散对数而构造的加密系统的安全程度也要低于椭圆曲线，类环运用离散对数而构造的加密系统的安全程度也要低于椭圆曲线，因此椭圆曲线系统不愧

28、为一个性质较好的密码系统。现在密码学界普因此椭圆曲线系统不愧为一个性质较好的密码系统。现在密码学界普遍认为它将替代遍认为它将替代rsa成为通用的公钥密码算法，成为通用的公钥密码算法，set( secure electronic transactions )协议的制定者已把它作为下一代协议的制定者已把它作为下一代set协协议中缺省的公钥密码算法。议中缺省的公钥密码算法。n在数字签名一节中详细地介绍的在数字签名一节中详细地介绍的dsa算法，被广泛应用在椭圆曲线上算法，被广泛应用在椭圆曲线上的变化，称为椭圆曲线数字签名算法的变化，称为椭圆曲线数字签名算法ecdsa，由，由ieee工作组和工作组和an

29、si（amercian national standards institute）x9组织开发。组织开发。应用椭圆曲线的数应用椭圆曲线的数字签名同时可以字签名同时可以很容易地使用到很容易地使用到小的有限资源的小的有限资源的设备中，例如智设备中，例如智能卡。椭圆曲线能卡。椭圆曲线上的密码算法速上的密码算法速度很快，分别在度很快，分别在32位的位的pc机上机上和和16位微处理位微处理器上实现了快速器上实现了快速的椭圆曲线密码的椭圆曲线密码算法，其中算法，其中16位微处理器上的位微处理器上的edsa数字签名数字签名不足不足500ms。图图2-12为为rsa算法和椭圆曲线算法和椭圆曲线密码算法的难度密

30、码算法的难度比较。比较。2.4 des对称加密技术对称加密技术des（data encryption standard）算法于）算法于1977年得到年得到美国政府的正式许可，是一种用美国政府的正式许可，是一种用56位密钥来加密位密钥来加密64位位数据的方法。数据的方法。2.4.1 des算法的历史算法的历史des加密算法要达到的目的有加密算法要达到的目的有4点：点：（1）提供高质量的数据保护，防止数据未经授权的泄露和未被察觉）提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改；的修改；（2）具有相当高的复杂性，使得破译的开销超过可能获得的利益，）具有相当高的复杂性，使得破译的开销超过

31、可能获得的利益，同时又要便于理解和掌握；同时又要便于理解和掌握；（3）des密码体制的安全性应该不依赖于算法的保密，其安全性仅密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础；以加密密钥的保密为基础；（4）实现经济，运行有效，并且适用于多种完全不同的应用。）实现经济，运行有效，并且适用于多种完全不同的应用。1977年年1月，美国政府颁布采纳月，美国政府颁布采纳ibm公司设计的方案作为非机密数据公司设计的方案作为非机密数据的正式数据加密标准的正式数据加密标准des。 国内随着三金工程尤其是金卡工程的国内随着三金工程尤其是金卡工程的启动，启动，des算法在算法在atm、磁卡

32、及智能卡（、磁卡及智能卡（ic卡）、加油站、高速卡）、加油站、高速公路收费站等领域被广泛应用，以此来实现关键数据的保密。如信公路收费站等领域被广泛应用，以此来实现关键数据的保密。如信用卡持卡人的用卡持卡人的pin的加密传输，的加密传输，ic卡与卡与pos间的双向认证、金融交间的双向认证、金融交易数据包的易数据包的mac校验等，均用到校验等，均用到des算法。算法。2.4.2 des算法的安全性（略）算法的安全性（略）des算法正式公开发表后，引起了一场激烈的争论。算法正式公开发表后，引起了一场激烈的争论。1977年年diffie等人提等人提出了制造一个每秒能测试出了制造一个每秒能测试106个密

33、钥的大规模芯片，该芯片的机器大约个密钥的大规模芯片，该芯片的机器大约一天可搜索一天可搜索des算法的整个密钥空间，制造这一机器需要算法的整个密钥空间，制造这一机器需要2000万美元。万美元。1993年年r.session等人给出了一个非常详细的密钥搜索机器的设计方案，等人给出了一个非常详细的密钥搜索机器的设计方案，它基于并行的密钥搜索芯片，此芯片每秒测试它基于并行的密钥搜索芯片，此芯片每秒测试5107个密钥，当时这种个密钥，当时这种芯片的造价是芯片的造价是10.5美元，美元，5760个该芯片组成的系统需要个该芯片组成的系统需要10万美元，这万美元，这一系统平均一系统平均1.5天即可找到密钥，如

34、果利用天即可找到密钥，如果利用10个这样的系统，费用是个这样的系统，费用是100万美元，但搜索时间可降到万美元，但搜索时间可降到2.5小时。小时。可见这种机制是不安全的。可见这种机制是不安全的。des的的56位短密钥面临另外一个严峻问题是：国际互联网位短密钥面临另外一个严峻问题是：国际互联网internet的超级的超级计算能力。计算能力。1997.1.28，美国的，美国的rsa数据安全公司在互联网上开展了一数据安全公司在互联网上开展了一项名为项名为“密钥挑战密钥挑战”的竞赛，悬赏一万美元，破解一段用的竞赛，悬赏一万美元，破解一段用56位密钥加密位密钥加密的的des密文。计划公布后引起了网户的强

35、烈响应。一位名叫密文。计划公布后引起了网户的强烈响应。一位名叫rocke verser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织实施了一个称为序，组织实施了一个称为deshall的搜索行动，成千上万的志愿者加入的搜索行动，成千上万的志愿者加入到计划中，在计划实施的第到计划中，在计划实施的第96天，即挑战赛计划公布的第天，即挑战赛计划公布的第140天，天，1997.6.17晚上晚上10:39，盐湖城，盐湖城inetz公司职员公司职员michael sanders成功地成功地找到了密钥，在计算机上显示了明文：找到了密钥，

36、在计算机上显示了明文：“the unknown message is: strong cryptography makes the world a safer place”。世界在世界在internet面前变得不安全了。面前变得不安全了。internet仅应用闲散的资源，毫无代仅应用闲散的资源，毫无代价地破解了价地破解了des的密码，这是对密码方法的挑战，也是的密码，这是对密码方法的挑战，也是internet超级计超级计算能力的显示。尽管算能力的显示。尽管des有些不足，但作为第一个公开密码算法的密码有些不足，但作为第一个公开密码算法的密码体制成功地完成了它的使命，它在密码学发展历史上具有重要

37、的地位。体制成功地完成了它的使命，它在密码学发展历史上具有重要的地位。2.4.3 des算法的原理（算法的原理（*） des算法的入口参数有算法的入口参数有3个：个： key、 data、 mode key为为8个字节共个字节共64位，是位，是des算法的工作密钥。算法的工作密钥。 data也为也为8个字节个字节64位，是要被加密或被解密的数据。位，是要被加密或被解密的数据。 mode为为des的工作方式有两种：加密或解密。的工作方式有两种：加密或解密。des算法的原理是：算法的原理是： 如如mode为加密，则用为加密，则用key把数据把数据data进行加密，生成进行加密，生成data的密码的

38、密码形式（形式（64位）作为位）作为des的输出结果；的输出结果； 如如mode为解密，则用为解密，则用key把密码形式的数据把密码形式的数据data解密，还原为解密，还原为data的明码形式（的明码形式（64位）作为位）作为des的输出结果。的输出结果。在通信网络的两端，双方约定一致的在通信网络的两端，双方约定一致的key，在通信的源点用，在通信的源点用key对核心数对核心数据进行据进行des加密，然后以密码形式在公共通信网（如电话网）中传输加密，然后以密码形式在公共通信网（如电话网）中传输到通信网络的终点，数据到达目的地后，用同样的到通信网络的终点，数据到达目的地后，用同样的key对密码数

39、据进对密码数据进行解密，便再现了明码形式的核心数据。这样，就保证了核心数据行解密，便再现了明码形式的核心数据。这样，就保证了核心数据（如（如pin，mac等）在公共通信网中传输的安全性和可靠性。通过定等）在公共通信网中传输的安全性和可靠性。通过定期在通信网络的源端和目的端同时改用新的期在通信网络的源端和目的端同时改用新的key，便能进一步提高数，便能进一步提高数据的保密性，这是现在金融交易网络的流行做法。据的保密性，这是现在金融交易网络的流行做法。2.4.4 des算法的实现步骤算法的实现步骤* des算法实现加密需要算法实现加密需要3个步骤。个步骤。第第1步步：变换明文。对给定的：变换明文。

40、对给定的64位的明文位的明文x，首先通过一个，首先通过一个置换置换ip表来重新排列表来重新排列x，从而构造出，从而构造出64位的位的x0，x0=ip(x)=l0r0，其中，其中l0表示表示x0的前的前32位，位，r0表示表示x0的后的后32位。位。第第2步：步：按规则迭代。规则为：按规则迭代。规则为： li = ri-1 ，ri = li f(ri-1,ki) （i=1,2,3, ,16） 经过第经过第1步变换已经得到步变换已经得到l0和和r0的值，其中符号的值，其中符号 表表示数学运算示数学运算“异或异或”，f表示一种置换，由表示一种置换，由s盒置换构成，盒置换构成，ki是一些由密钥编排函数

41、产生的比特块。是一些由密钥编排函数产生的比特块。f和和ki将在后面将在后面介绍。介绍。第第3步：对步：对l16r16利用利用ip-1作逆置换，就得到了密文作逆置换，就得到了密文y0加密过程如图加密过程如图2-13所示。所示。des加密需要加密需要4个关键点个关键点：ip置换表和置换表和ip-1逆置换表、函逆置换表、函数数f、子密钥子密钥ki、s盒盒 工作原理：工作原理：（1）ip置换表和置换表和ip-1逆置换表。逆置换表。 输入的输入的64位数据按位数据按ip表置换进行重新组合，并把输出分为表置换进行重新组合，并把输出分为l0和和r0两部分，两部分，每部分各每部分各32位位 。（设计如此）。（

42、设计如此）其其ip表置换表置换 16位位*45850123426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725ip-1逆置换表逆置换表16位位*4将输入的将输入的64位明文的第位明文的第58

43、位换到第位换到第1位，第位，第50位换到第位换到第2位，依此类推，最后一位是原来的位，依此类推，最后一位是原来的第第7位。位。l0和和r0则是换位输出后的两部分，则是换位输出后的两部分，l0是输出的左是输出的左32位，位，r0是右是右32位。比如：置位。比如：置换前的输入值为换前的输入值为d1d2d3d64，则经过初始，则经过初始置换后的结果为：置换后的结果为：l0=d58d50d8，r0=d57d49d7。经过经过16次迭代运算后。得到次迭代运算后。得到l16和和r16，将此作，将此作为输入进行逆置换，即得到密文输出。为输入进行逆置换，即得到密文输出。逆置换正好是初始置的逆运算，例如，第逆置

44、换正好是初始置的逆运算，例如，第1位经位经过初始置换后，处于第过初始置换后，处于第40位，而通过逆置换位，而通过逆置换ip-1，又将第，又将第40位换回到第位换回到第1位，其逆置换位，其逆置换ip-1规则表如规则表如2-4所示。所示。（2）函数函数f。它有两个输入：它有两个输入：32位的位的ri-1和和48位位ki，f函数的处理流程如图函数的处理流程如图2-14。e变换变换的算法是从的算法是从ri-1的的32位中选取某些位，位中选取某些位，构成构成48位，即位，即e将将32位扩展为位扩展为48位。变换位。变换规则根据规则根据e位选择表，如表位选择表，如表2-5。 16位*33212345456

45、789891011121312131415161716171819202120212223242524252627282928293031321ki是由密钥产生的是由密钥产生的48位比特串，具体的算法是：将位比特串，具体的算法是：将e的选的选位结果与位结果与ki作异或操作，得到一个作异或操作，得到一个48位输出。分成位输出。分成8组，组，每组每组6位，作为位，作为8个个s盒的输入。盒的输入。每个每个s盒盒输出输出4位，共位，共32位，位，s盒的工作原理将在第盒的工作原理将在第4步介步介绍。绍。s盒的输出作为盒的输出作为p变换的输入，变换的输入，p的功能是对输入的功能是对输入进行置换，进行置换，

46、p换位表如表换位表如表2-6所示。所示。 16位位*2（3 3）子密钥）子密钥 k ki i。设密钥为设密钥为k k，长度为，长度为6464位，但是其中第位，但是其中第8 8，1616，2424，3232，4040，4848，5656，6464用做用做奇偶校验位奇偶校验位，实际，实际上密钥长度为上密钥长度为5656位位。k k的下标的下标i i的取值范围是的取值范围是1 1到到1616，用用1616轮来构造轮来构造。构造过程如图。构造过程如图2-152-15 1672021291228171152326518311028241432273919133062211425首先，对于给定的密钥密钥k

47、，应用pc1变换进行选位，选定后的结果是56位，设其前28位为c0，后28位为d0。pc1选位如表2-7所示。 14位*45757494941413333252517179 91 158585050424234342626181810102 259595151434335352727191911113 3606052524444363663635555474739393131232315157 762625454464638383030222214146 661615353454537372929212113135 52828202012124 4第第1轮轮：对：对c0作左移作左移ls1得到得

48、到c1，对，对d0作左移作左移ls1得到得到d1，对，对c1d1应用应用pc2进行选位，得到进行选位，得到k1。其中。其中ls1是左移的位数，是左移的位数，ls、 pc2如下。如下。第第2轮轮：对：对c1和和d1作左移作左移ls2得到得到c2和和d2，进一步对，进一步对c2d2应用应用pc2进行选位，得到进行选位，得到k2。如此继续，分别得。如此继续，分别得到到k3，k4，k16。1 11 12 22 22 22 22 22 21 12 22 22 22 22 22 21 114141717111124241 15 53 3282815156 6212110102323191912124 42

49、6268 816167 72727202013132 2414152523131373747475555303040405151454533334848444449493939565634345353464642425050363629293232（4）s盒的工作原理。盒的工作原理。s盒以盒以6位作为输入，位作为输入，而以而以4位作为输出，位作为输出，现在以现在以s1为例说明为例说明其过程。假设输入为其过程。假设输入为a=a1a2a3a4a5a6，则，则a2a3a4a5所所代表的数是代表的数是0到到15之间的一个数，记为：之间的一个数，记为：k=a2a3a4a5；由；由a1a6所代表的数是所代

50、表的数是0到到3间的一个数，记为间的一个数，记为h=a1a6。在。在s1的的h行，行，k列找到一个数列找到一个数b，b在在0到到15之之间，它可以用间，它可以用4位二进制表示，为位二进制表示，为b=b1b2b3b4，这就是，这就是s1的输出。的输出。s盒盒由由8张数据表组成，张数据表组成，如表如表2-10所示。所示。2.4.5 des算法的应用误区（略）算法的应用误区（略） des算法具有比较高的安全性，到目前为止，除了用穷举搜算法具有比较高的安全性，到目前为止，除了用穷举搜索法对索法对des算法进行攻击外，还没有发现更有效的办法。算法进行攻击外，还没有发现更有效的办法。而而56位的密钥的穷举

51、空间为位的密钥的穷举空间为2的的56次方次方，这意味着如果一，这意味着如果一台计算机的速度是每秒钟检测一百万个密钥，则它搜索完台计算机的速度是每秒钟检测一百万个密钥，则它搜索完全部密钥就需要将近全部密钥就需要将近2285年年，可见难以实现。当然，随着，可见难以实现。当然，随着科学技术的发展，当出现超高速计算机后，可考虑把科学技术的发展，当出现超高速计算机后，可考虑把des密钥的长度再增长一些，以此来达到更高的保密程度。密钥的长度再增长一些，以此来达到更高的保密程度。des算法中只用到算法中只用到64位密钥中的位密钥中的56位，而第位，而第8,16,24,64位位8个位并未参与个位并未参与des

52、运算，这一点提出了一个应用上的要运算，这一点提出了一个应用上的要求，即求，即des的安全性是基于除了的安全性是基于除了8，16，24，64位外位外的其余的其余56位的组合变化位的组合变化2的的56才得以保证的。因此，在实才得以保证的。因此，在实际应用中，应避开使用第际应用中，应避开使用第8，16，24，64位作为有效位作为有效数据位，而使用其他的数据位，而使用其他的56位作为有效数据位，才能保证位作为有效数据位，才能保证des算法安全可靠地发挥作用。如果不了解这一点，把密算法安全可靠地发挥作用。如果不了解这一点，把密钥钥key的的8，16，24，64位作为有效数据使用，将不位作为有效数据使用，

53、将不能保证能保证des加密数据的安全性，对运用加密数据的安全性，对运用des来达到保密作来达到保密作用的系统产生数据被破译的危险，用的系统产生数据被破译的危险，这正是这正是des算法在应用算法在应用上的误区，留下了被人攻击、破译的极大隐患。上的误区，留下了被人攻击、破译的极大隐患。2.4.6 des算法的程序实现算法的程序实现 根据根据des算法的原理，可以方便地利用算法的原理，可以方便地利用c语言实现其加密和解密算法。程序在语言实现其加密和解密算法。程序在vc+6.0环境下测试通过。环境下测试通过。案例案例2-1 des加密算法研究加密算法研究 2.5 rsa公钥加密技术公钥加密技术 197

54、6年，年，diffie和和hellman在在“密码学新方向密码学新方向（new direction in cryptography）”文中首次提出了公开文中首次提出了公开密钥密码体制的思想。密钥密码体制的思想。1977年，年，rivest，shamir和和adleman三人三人(并以发明者并以发明者的名字命名的名字命名)实现了公开密钥密码体制，称为实现了公开密钥密码体制，称为rsa公开公开密钥体制，它是第一个既能用于数据加密也能用于数字密钥体制，它是第一个既能用于数据加密也能用于数字签名的算法。这种算法易于理解和操作。签名的算法。这种算法易于理解和操作。但但rsa的安全的安全性一直未能得到理论

55、上的证明。它经历了各种攻击，至性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。今未被完全攻破。2.5.1 rsa算法的原理算法的原理rsa算法是一种基于算法是一种基于大数不可能质因数分解假设大数不可能质因数分解假设的公钥体的公钥体系。简单地说，就是找两个很大的系。简单地说，就是找两个很大的质数质数/素数素数，一个公，一个公开给世界，称之为开给世界，称之为“公钥公钥”，另一个不告诉任何人，称，另一个不告诉任何人，称之为之为“私钥私钥”。两把密钥互补。两把密钥互补用公钥加密的密文可用公钥加密的密文可以用私钥解密，反过来也一样。假设以用私钥解密，反过来也一样。假设a寄信给寄信给b，他

56、们知，他们知道对方的公钥。道对方的公钥。a可用可用b的公钥加密邮件寄出，的公钥加密邮件寄出，b收到后收到后用自己的私钥解出用自己的私钥解出a的原文，这样就保证了邮件的安全的原文，这样就保证了邮件的安全性。性。 rsa体制可以简单描述如下：体制可以简单描述如下：（1）生成两个大素数）生成两个大素数p和和q； 11、7（2）计算这两个素数的乘积）计算这两个素数的乘积n=pq； 77（3）计算小于）计算小于n并且与并且与n互质互质的整数的个数，的整数的个数， 即欧拉函数即欧拉函数（n） =( p-1 ) ( q-1 )； 10 *6 = 60（4）选择一个随机数）选择一个随机数b满足满足1b(n)，

57、并且，并且b和和(n)互质，互质， 即即gcd（b,(n)）=1。（5）计算）计算ab=1 mod （n）；）； a=1/b（6）保密保密a，p和和q， 公开公开n和和b。利用利用rsa加密时，明文以分组的方式加密，即每一个分组的比特数应该小加密时，明文以分组的方式加密，即每一个分组的比特数应该小于于log2n。加密明文。加密明文x时，利用公钥时，利用公钥 （b, n）计算）计算c=xb mod n就可以就可以得到相应的密文得到相应的密文c。解密时，通过计算。解密时，通过计算c a mod n就可以恢复明文就可以恢复明文x。选取的素数选取的素数p和和q要足够大要足够大，从而乘积，从而乘积n足够

58、大，在事先不知道足够大，在事先不知道p和和q的情况的情况下分解下分解n是计算上不可行的。是计算上不可行的。常用的公钥加密算法包括：常用的公钥加密算法包括：rsa密码体制、密码体制、elgamal密码体制和散列函数密码体制（密码体制和散列函数密码体制（md4，md5等）。等）。2.5.2 rsa算法的安全性算法的安全性rsa算法的安全性算法的安全性依赖于大数分解依赖于大数分解，但是否等同于大数分解一直未能得，但是否等同于大数分解一直未能得到理论证明，因为没有证明破解，到理论证明，因为没有证明破解，rsa算法就一定需要作大数分解。算法就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可

59、以修改成为大数分解假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，算法。目前，rsa 算法的一些变种算法已被证明等价于大数分解。不算法的一些变种算法已被证明等价于大数分解。不管怎样，分解管怎样，分解n是最显然的攻击方法。人们已能分解多个十进制位的是最显然的攻击方法。人们已能分解多个十进制位的大素数。因此，模数大素数。因此，模数n必须选大一些，因具体适用情况而定。必须选大一些，因具体适用情况而定。2.5.3 rsa算法的速度算法的速度由于进行的都是大数计算，使得由于进行的都是大数计算，使得rsa算法最快的情况也比算法最快的情况也比des算法慢上算法慢上数倍，无论是软件还是

60、硬件实现，数倍，无论是软件还是硬件实现，速度一直是速度一直是rsa算法的缺陷，算法的缺陷，一般一般来说只用于少量数据加密。来说只用于少量数据加密。rsa算法是第一个能同时用于算法是第一个能同时用于加密和数字签名加密和数字签名的算法，的算法，也易于理解和操也易于理解和操作。也是被研究得最广泛的公钥算法，二十几年，经历了各种攻击的作。也是被研究得最广泛的公钥算法，二十几年，经历了各种攻击的考验，逐渐为人们接受，考验，逐渐为人们接受，被普遍认为是目前最优秀的公钥方案之一。被普遍认为是目前最优秀的公钥方案之一。2.5.4 rsa算法的程序实现算法的程序实现根据根据rsa算法的原理，可以利用算法的原理，