数据结构与算法老师讲义zyw

1、数据的加密解密密码学简介密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律，并应用其编制密码以保守通信秘密的，称为编码学 应用于破译密码以获取通信情报的，称为破译学 密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。 变明文为密文，称为加密变换； 变密文为明文，称为脱密变换。 随着通信技术的发展，对语音、图像、数据等都可实施加、脱密变换。密码学是在编码与破译的斗争实践中逐步发展起来的，并随着先进科学技术的应用，已成为一门综合性的尖端技术科学。它与语言学、数学、电子学、声学、信息论、计算机科学等有着广泛而密切的联系。目录1、为什么要进行加密？-2500年的历史2、AES

2、(高级加密标准Advanced Encryption Standard)3、公匙加密4、密码学在现代的应用5、使用公匙还是密匙-找出合适的方案一、为什么要进行加密？-2500年的历史密码学的起源可能要追溯到人类刚刚出现，并且尝试去学习如何通信的时候。他们不得不去寻找方法确保他们的通信的机密。但是最先有意识的使用一些技术的方法来加密信息的可能是公元六年前的古希腊人。他们使用的是一根叫scytale的棍子。送信人先绕棍子卷一张纸条，然后把要写的信息纵写在上面，接着打开纸送给收信人。如果不知道棍子的宽度（这里作为密匙）是不可能解密里面的内容的。后来，罗马的军队用凯撒密码（三个字母表轮换）进行通信。

3、在随后的19个世纪里面，主要是发明一些更加高明的加密技术，这些技术的安全性通常依赖于用户赋予它们多大的信任程度。在19世纪Kerchoffs写下了现代密码学的原理。其中一个的原理提到：加密体系的安全性并不依赖于加密的方法本身，而是依赖于所使用的密匙。二、AES(高级加密标准Advanced Encryption Standard)2000年10月，NIST（美国国家标准和技术协会）宣布通过从15种侯选算法中选出的一项新的密匙加密标准。新的标准将会代替密匙长度变的太短的旧的DES（数据加密标准）算法。Rijndael被选中成为将来的AES（美国电子学会）。Rijndael这个名字是从它的两个发明

4、者Rijmen和Daemen的名字得来的。 这个加密体系据说是一种分组加密方法，因为信息的内容是以128位长度的分组为加密单元的。加密密匙长度有128，192或256位多种选择。正象你所知的那样，DES加密的分组长度是64位，而密匙长度只有64位。三重DES加密的分组长度通常是64位，而密匙长度上112位。 图一: AES 迭代图一描述了AES的操作模式。首先密匙K0和待加密信息按位相与。然后所有要加密的分组都用一个函数F进行迭代计算，计算用的子密匙是由一个密匙扩展函数产生的，初始的密匙是主密匙。 对于AES 函数F要迭代10次。 图2描述的是加密过程中函数F是如何被迭代的。一个128位的分组

5、转换成16个字节，作为下面处理的输入。首先，每一个字节分别经过替换函数S的处理，然后，用第二个置换函数P对16个字节进行处理。然后这个结果就和匙扩展函数产生的子匙进行位与。 匙Ki是用匙扩展函数从第K(i-1)轮的子匙和第K0的密匙得到的。图三描述了匙扩展函数。16个字节的被分成4组，每组4个字节，进行处理。最后的一组的4个字节由替换函数S（这个S和用F函数进行迭代处理时的S是一样的）来进行替换处理。最初的4个字节的结果和系数相加，这个系数是与轮数相关的，它是预先定义的。最后，为了得到Ki，把得到的4个字节的结果和K(i-1)匙的最初4个字节按位相加，然后得到的结果又和K(i-1)匙的下面的4

6、个字节按位相加，如此类推。因为AES仅仅在基于简单的位操作运算，这有两个主要的优点:即使是纯粹的软件实现，AES也是很快的。例如，用C+在奔腾200的电脑上实现的AES的加密速度可达到70M位/秒三、公匙加密 公匙体系最好例子在1978年出现了。它是由Rivest, Shamir 和Adleman发明的，所以也被称为RSA（公用关键字加密系统）。RSA算法建立在对整数的分解的数学难题上的。私匙是由三个数(p,q,d)组成，其中p和q是两个素数（具有大致相同的大小），而d和（p-1）*（q-1）互质。公匙由两个数（n，e）组成，其中n=pq，而e是(p-1)(q-1)取d为模的倒数， 例如：ed

7、 = 1 mod(p-1)(q-1). 假如爱丽斯想对鲍勃的公匙(n,e)加密，传送一些文本。她首先会把明文转换成小于n的整数m，那么她就会这样处理： c = me mod n, 然后把结果c送给鲍勃。在鲍勃的这边，他就会用他的私匙(p,q,d)进行这样的处理: cd mod n = med mod n = m. 对于RSA，单向的机关函数是能够从一个小于n的整数x得到xe mod n. 从RSA（美国RSA实验室，以研究加密算法而著名）产生以来，又发明了许多其它的公匙体系.RSA算法的基本步骤是: 选择两个大质数户和p和q，每个都大于10100； 计算n p*q和z= （p一1）*（q一1）

8、； 选择一个与z 有关的质数，令其为d ；找到一个e使满足e*d=1（模z)。 d保密。事先计算好这些参数，我们就可以准备加密了。将明码（当作位串看待）划分成块，使得每个明码报文P落在0Pn之间，这可以通过将明码分成每块有k位的组来实现，并且屋是使得zkn成立的最大整数。加密一个报文P，计算C=Pe（mod n）.解密C，计算P=Cd（mod n）。可以证明，在确定的范围内，加密和解密函数是互逆的。为实现加密你需要e和n。为实现解密你需要d和n。所以公钥由（e，n）组成，私钥由（d，n）或只是d组成。现在我们就来看这两个简单的例子。例1： 例：选取p=3, q=5，则n=15，（p-1）*（q

9、-1）=8。选取e=11（大于p和q的质数），通过d * 11 = 1 mod 8，计算出d =3。 假定明文为整数13。则密文C为 C = Pe mod n = 1311 mod 15 = 1,792,160,394,037 mod 15 = 7 复原明文P为： P = Cd mod n = 73 mod 15 = 343 mod 15 = 13 我们选择了p=3，q=11，则n=33，z=（3-1）*（11-1）=20。d的一个适合的值是d=7，因为7和20没有公共因子。选定这些值后，e可以通过求解式7e1（模20）得出，即e=3。明码报文P的一个密码C，则由C=P3（模33）将密文解密。

10、例2：下图中给出明码“SUZANNE”的加密作为例子。因为我们的质数选择得很小，所以P必须小于33，因此，每个明码块只能包含一个字符。结果形成了一个单一字母表代换密码。因为e和d互逆，公开密钥加密方法也允许采用这样的方式对加密信息进行签名，以便接收方能确定签名不是伪造的。 明文密文解密字母序号P3P3 (mod 33)C7C7(mod 33)字母S19685928 19SU21926121180108854121UZ26175762012800000026ZA011111AN14274457812514NN14274457812514NE05125268031801765ERSA算法的安全性是

11、基于：加密变换：c=E k(m)=me mod n的单向性，即敌方从n 和e中无法求出脱密的密钥d ，产生这种单向性的原因是大整数分解在计算上的困难，如果能有效的分解n p*q那也就知道了z= （p-1）*（q-1）；从而就可以用穷尽的方法来求出脱密的密钥d，为保证足够的安全性， 一般认为现在的个人应用需要用384或512比特位的n，公司需要用1024比特位的n，极其重要的场合应该用2048比特位的n。在RSA中需要考虑的另一个问题是如何产生大素数？因为RSA的安全性是建立在分解大整数n=p*q困难的基础上的，所以n 至少应为超过150位的十进制数（512bit）故素数p,q应超过75位十进制

12、。常用的方法是随机产生大整数，然后检测其是否为素数，那就必须考虑素数在整数中的稠密度。依据素数定理：设x为正整数，记（x）为不超过x的素数个数，则有（x）x / ln x。长期以来，素性检测的问题没有有效的确定性算法，解决素性检测问题最有效的算法是概率算法，概率算法是指：算法中要使用随机数，从而对于相同的输入，每次运行得到的输出结果可能不同。Solovay-Sreassen 算法就是这样一个概率算法，它是指如果该算法判定N 是合数，则N必为合数，如果判定N是素数，则N是合数的概率是1/2k,当k足够大时可以认为N是一个素数。四、密码学在现代的应用实际上，公匙加密由于更容易的使用，以及能解决了目

13、前为止许多安全的问题，所以更为吸引人。说的更准确点的说，它解决了一些认证的问题： 身份认证: Alice在使用今天的匿名通信的时候，她想肯定她正在通信的对象并不是假扮Bob的。为了达到这样的目的，她使用了一个认证协议。现在有许多认证协议的存在，通常都是基于RSA或离散对数原理的。文档认证：:一个授权机关通过一个数字签名来认证一个文档。签名通常附加在消息后面，这些签名通常是把文档和授权机关的一些信息作为输入而得到的一些字节位，这些得到的签名通常是通过MD5或SHA等的哈希算法hash得到的。还有就是， 任何访问该文档的人都应该能够去检查签名是否真的由授权机关签发的。为了实现这个目的，使用了所谓的

14、签名模板（signature schemas）。其中一个最有名的模板是ElGamal模板，又是基于离散算法问题的。 五、谈数据加密数据加密的术语有：明文，即原始的或未加密的数据。通过加密算法对其进行加密，加密算法的输入信息为明文和密钥；密文，明文加密后的格式，是加密算法的输出信息。加密算法是公开的，而密钥则是不公开的。密文，不应为无密钥的用户理解，用于数据的存储以及传输。例：明文为字符串： AS KINGFISHERS CATCH FIRE （为简便起见，假定所处理的数据字符仅为大写字母和空格符）。假定密钥为字符串：ELIOT加密算法为： 1) 将明文划分成多个密钥字符串长度大小的块（空格符以

15、+表示） AS+KI NGFIS HERS+ CATCH +FIRE 2) 用0026范围的整数取代明文的每个字符，空格符=00，A=01，.，Z=26： 1407060919 3) 与步骤2一样对密钥的每个字符进行取代： 4) 对明文的每个块，将其每个字符用对应的整数编码与密钥中相应位置的字符的整数编码的和模27后的值取代： 5) 将步骤4的结果中的整数编码再用其等价字符替换： FDIZB SSOXL MQ+GT HMBRA ERRFY 如果给出密钥，该例的解密过程很简单。问题是对于一个恶意攻击者来说，在不知道密钥的情况下，利用相匹配的明文和密文获得密钥究竟有多困难？对于上面的简单例子，答案

16、是相当容易的，不是一般的容易，但是，复杂的加密模式同样很容易设计出。理想的情况是采用的加密模式使得攻击者为了破解所付出的代价应远远超过其所获得的利益。实际上，该目的适用于所有的安全性措施。这种加密模式的可接受的最终目标是：即使是该模式的发明者也无法通过相匹配的明文和密文获得密钥，从而也无法破解密文。 如果给出密钥，该例的解密过程很简单。问题是对于一个恶意攻击者来说，在不知道密钥的情况下，利用相匹配的明文和密文获得密钥究竟有多困难？对于上面的简单例子，答案是相当容易的，不是一般的容易，但是，复杂的加密模式同样很容易设计出。理想的情况是采用的加密模式使得攻击者为了破解所付出的代价应远远超过其所获得

17、的利益。实际上，该目的适用于所有的安全性措施。这种加密模式的可接受的最终目标是：即使是该模式的发明者也无法通过相匹配的明文和密文获得密钥，从而也无法破解密文。 假设A和B希望通过公开密钥加密方法进行数据传输，A和B分别公开加密算法和相应的密钥，但不公开解密算法和相应的密钥。 A和B的加密算法分别是ECA和ECB，解密算法分别是DCA和DCB，ECA和DCA互逆，ECB和DCB互逆。 若A要向B发送明文P，不是简单地发送ECB（P），而是先对P施以其解密算法DCA，再用加密算法ECB对结果加密后发送出去。 密文C为： C = ECB（DCA（P） B收到C后，先后施以其解密算法DCB和加密算法E

18、CA，得到明文P： ECA（DCB（C） = ECA（DCB（ECB（DCA（P） = ECA（DCA（P） /*DCB和ECB相互抵消*/ = P /*DCB和ECB相互抵消*/ ，这样B就确定报文确实是从A发出的，因为只有当加密过程利用了DCA算法，用ECA才能获得P，只有A才知道DCA算法，没有人，即使是B也不能伪造A的签名。用C加密文件文件加密技术一例 给文件加密的技术很多,其中又分为不同等级,以适合不同场合的需要.这里给出最简单的文件加密技术,即采用文件逐字节与密码异或方式对文件进行加密,当解密时,只需再运行一遍加密程序即可.下面是一个实例程序,能对任意一个文件进行加密,密码要求用户

19、输入,限8位以内(当然你可以再更改).程序有很好的容错设计,这是我们应该学习的. /* Turbo 2.0 pass. Give file a password! */#include#include#include#includevoid dofile(char *in_fname,char *pwd,char *out_fname);/*对文件进行加密的具体函数*/ void main(int argc,char *argv)/*定义main()函数的命令行参数*/char in_fname30;/*用户输入的要加密的文件名*/char out_fname30;char pwd8;/*用来保存密码*/if(argc!=4)/*容错处理*/printf(nIn-fname:n);gets(in_fname);/*得到要加密的文件名*/printf(Password:n);gets(pwd);/*得到密码*/printf(Out-file:n);gets(out_f