应用密码学中的几个重要算法(课程设计报告)

1、应用密码学中的几个重要算法谢泽源 2013012613 信记1302密码学（英语：cryptology）是研究如何隐密地传递信息的学科。密码学的首要目的是隐藏信息的涵义，并不是隐藏信息的存在。如何将可理解的信息转换成难以理解的信息，并且使得有秘密信息的人能够逆向回复，但缺乏秘密信息的拦截者或窃听者则无法解读。这是古典密码学和部分现代密码学的基本思想，例如：DES、AES。DES算法：DES是一种分组密码协议，有两个基本指导思想扩散（Diffusion）和混乱（Confusion）,以保证密码算法能满足要求，所以DES的具体实现是依赖于多次迭代进行乘积密码加密变换。这个算法的核心是Feistel

2、密码，由于其设计的巧妙，加密解密都用一个函数。它的算法是对称的，既可用于加密又可用于解密。DES 使用一个 56 位的密钥以及附加的 8 位奇偶校验位，产生最大 64 位的分组大小。这是一个迭代的分组密码，使用称为 Feistel 的技术，其中将加密的文本块分成两半。使用子密钥对其中一半应用循环功能，然后将输出与另一半进行“异或”运算；接着交换这两半，这一过程会继续下去，但 最后一个循环不交换。DES 使用 16 个循环，使用异或，置换，代换，移位操作四种基本运算。DES的流程基本是执行16轮下面的运算：1 初始变换Initial Permutation2 右边32位f函数2.1 E置换2.2

3、 与轮密钥XOR2.3 S盒替换2.4 P置换2.5 和左边32位XOR3 左右交换，最终变换final permutation需要特别注意的是，最后一轮是不需要做左右交换这一部的。从具体实现看DES有几个已知的方面存在脆弱性：1，加密协议半公开化 2，密钥太短 3，软件的实现的性能较低。随着计算机的处理能力的提高，只有56位密钥的DES算法不再被认为是安全性的，故现在一般的方案是三重DES，既3DES。AES 算法AES（The Advanced Encryption Standard）是一种非Feistel 的对称分组密码体制，和DES的基本指导思想一样都是多次混淆，所不同的是非线性层的由

4、16个S盒进行并置混淆。AES具有安全可靠、效率高等优点。AES加密过程是在一个4×4的字节矩阵上运作，这个矩阵又称为“状态（state）”，其初值就是一个明文区块（矩阵中一个元素大小就是明文区块中的一个Byte）。（Rijndael加密法因支持更大的区块，其矩阵行数可视情况增加）加密时，各轮AES加密循环（除最后一轮外）均包含4个步骤： 1. AddRoundKey 矩阵中的每一个字节都与该次轮秘钥（round key）做XOR运算；每个子密钥由密钥生成方案产生。 2. SubBytes 通过个非线性的替换函数，用查找表的方式把每个字节替换成对应的字节。 3. ShiftRows

5、将矩阵中的每个横列进行循环式移位。 4. MixColumns 为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每列的四个字节。AddRoundKey步骤在AddRoundKey步骤中，将每个状态中的字节与该回合密钥做异或（）。AddRoundKey步骤，回合密钥将会与原矩阵合并。在每次的加密循环中，都会由主密钥产生一把回合密钥（通过Rijndael密钥生成方案产生），这把密钥大小会跟原矩阵一样，以与原矩阵中每个对应的字节作异或（）加法。SubBytes步骤在SubBytes步骤中，矩阵中各字节被固定的8位查找表中对应的特定字节所替换,S; bij = 

6、;S（aij）.在SubBytes步骤中，矩阵中的各字节通过一个8位的S-box进行转换。这个步骤提供了加密法非线性的变换能力。S-box与GF（28）上的乘法反元素有关，已知具有良好的非线性特性。为了避免简单代数性质的攻击，S-box结合了乘法反元素及一个可逆的仿射变换矩阵建构而成。此外在建构S-box时，刻意避开了固定点与反固定点，即以S-box替换字节的结果会相当于错排的结果。此条目有针对S-box的详细描述：Rijndael S-boxShiftRows步骤在ShiftRows步骤中，矩阵中每一行的各个字节循环向左方位移。位移量则随着行数递增而递增。ShiftRows描述矩阵的行操作。

7、在此步骤中，每一行都向左循环位移某个偏移量。在AES中（区块大小128位），第一行维持不变，第二行里的每个字节都向左循环移动一格。同理，第三行及第四行向左循环位移的偏移量就分别是2和3。128位和192比特的区块在此步骤的循环位移的模式相同。经过ShiftRows之后，矩阵中每一竖列，都是由输入矩阵中的每个不同列中的元素组成。Rijndael算法的版本中，偏移量和AES有少许不同；对于长度256比特的区块，第一行仍然维持不变，第二行、第三行、第四行的偏移量分别是1字节、3字节、4位组。除此之外，ShiftRows操作步骤在Rijndael和AES中完全相同。MixColumns步骤在MixCo

8、lumns步骤中，每个直行都在modulo 之下，和一个固定多项式c(x)作乘法。在MixColumns步骤，每一列的四个字节通过线性变换互相结合。每一列的四个元素分别当作的系数，合并即为GF（28）中的一个多项式，接着将此多项式和一个固定的多项式在modulo 下相乘。此步骤亦可视为Rijndael有限域之下的矩阵乘法。MixColumns函数接受4个字节的输入，输出4个字节，每一个输入的字节都会对输出的四个字节造成影响。因此ShiftRows和MixColumns两步骤为这个密码系统提供了扩散性。大致说来，AES 加密算法的核心有四个操作。AddRoundKey 使用从

9、种子密钥值中生成的轮密钥代替 4 组字节。SubBytes 替换用一个代替表 替换单个字节。ShiftRows 通过旋转 4字节行 的 4 组字节进行序列置换。MixColumns 用域加和域乘的组合来替换字节。有限域GF(28)的加法和乘法正如你所看到的，AES 加密算法使用相当简单明了的技术来代替和置换，除 MixColumns 例程以外。MixColumns 使用特殊的加法和乘法。AES 所用的加法和乘法是基于数学（译者注：近世代数）的域论。尤其是 AES 基于有限域GF(28)。GF(28)由一组从 0x00 到 0xff 的256个值组成，加上加法和乘法，因此是(28)。GF代表伽罗

10、瓦域，以发明这一理论的数学家的名字命名。GF(28) 的一个特性是一个加法或乘法的操作的结果必须是在0x00 . 0xff这组数中。虽然域论是相当深奥的，但GF(28)加法的最终结果却很简单。GF(28) 加法就是异或（XOR）操作。在GF(28)中用0x01的乘法是特殊的；它相当于普通算术中用1做乘法并且结果也同样任何值乘0x01等于其自身。现在让我们看看用0x02做乘法。和加法的情况相同，理论是深奥的，但最终结果十分简单。只要被乘的值小于0x80，这时乘法的结果就是该值左移1比特位。如果被乘的值大于或等于0x80，这时乘法的结果就是左移1比特位再用值0x1b异或。它防止了“域溢出”并保持乘

11、法的乘积在范围以内。一旦你在GF(28)中用0x02建立了加法和乘法，你就可以用任何常量去定义乘法。用0x03做乘法时，你可以将 0x03 分解为2的幂之和。为了用 0x03 乘以任意字节b， 因为 0x03 = 0x02 + 0x01，因此： b * 0x03 = b * (0x02 + 0x01) = (b * 0x02) + (b * 0x01)这是可以行得通的，因为你知道如何用 0x02 和 0x01 相乘和相加，用0x0d去乘以任意字节b可以这样做：b * 0x0d = b * (0x08 + 0x04 + 0x01) = (b * 0x08) + (b * 0x04) +

12、 (b * 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02 * 0x02) + (b * 0x01)在加解密算法中，AES MixColumns 例程的其它乘法遵循大体相同的模式，如下所示：b * 0x09 = b * (0x08 + 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x01) b * 0x0b = b * (0x08 + 0x02 + 0x01) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02) + (b * 0x01) b * 0x0e = b * (0x08 + 0x0

13、4 + 0x02) = (b * 0x02 * 0x02 * 0x02) + (b * 0x02 * 0x02) + (b * 0x02)总之，在GF(28)中，加法是异或操作。其乘法将分解成加法和用0x02做的乘法，而用0x02做的乘法是一个有条件的左移1比特位。AES规范中包括大量 有关GF(28)操作的附加信息。在Java中的实现：/* * 解密AES加密过的字符串 * * param content * AES加密过过的内容 * param password * 加密时的密码 * return 明文 */ public static byte decrypt(byte content,

14、 String password) try KeyGenerator kgen = KeyGenerator.getInstance("AES");/ 创建AES的Key生产者 kgen.init(128, new SecureRandom(password.getBytes(); SecretKey secretKey = kgen.generateKey();/ 根据用户密码，生成一个密钥 byte enCodeFormat = secretKey.getEncoded();/ 返回基本编码格式的密钥 SecretKeySpec key = new SecretKeyS

15、pec(enCodeFormat, "AES");/ 转换为AES专用密钥 Cipher cipher = Cipher.getInstance("AES");/ 创建密码器 cipher.init(Cipher.DECRYPT_MODE, key);/ 初始化为解密模式的密码器 byte result = cipher.doFinal(content); return result; / 明文 catch (NoSuchAlgorithmException e) e.printStackTrace(); catch (NoSuchPaddingExce

16、ption e) e.printStackTrace(); catch (InvalidKeyException e) e.printStackTrace(); catch (IllegalBlockSizeException e) e.printStackTrace(); catch (BadPaddingException e) e.printStackTrace(); return null; RSA算法类似DES，AES等算法中双方都使用相同的密钥进行加密解密，我们把这种加解密都使用同一个密钥的密码体制称为对称密码体制。使用相同的密钥进行加密解密，密钥的传输是一个重要的问题。所以，在公

17、开的计算机网络上安全地传送和保管密钥是一个严峻的问题。于是，密码学家们构想了一个不一样的的密码体制来解决这一问题-公钥加密算法。公钥加密算法也称非对称密钥算法，用两对密钥：一个公共密钥和一个专用密钥。用户要保障专用密钥的安全；公共密钥则可以发布出去。公共密钥与专用密钥是有紧密关系的，用公共密钥加密的信息只能用专用密钥解密，反之亦然。由于公钥算法不需要联机密钥服务器，密钥分配协议简单，所以极大简化了密钥管理。除加密功能外，公钥系统还可以提供数字签名。 RSA是其中的一种有效实现。RSA的基本指导思想是设计有效的单向陷门函数，来使得正向加密计算容易、没有密钥下的反向计算几乎不可能。RSA

18、的安全性是建立在大整数分解的困难性上的。公钥与密钥的产生假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥：随意选择两个大的质数p和q，p不等于q，计算N=pq。根据欧拉函数，求得r = (p-1)(q-1)选择一个小于 r 的整数 e，求得 e 关于模 r 的模反元素，命名为d。（模反元素存在，当且仅当e与r互质）将 p 和 q 的记录销毁。(N,e)是公钥，(N,d)是私钥。Alice将她的公钥(N,e)传给Bob，而将她的私钥(N,d)藏起来。加密消息假设Bob想给Alice送一个消

19、息m，他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：ne  c (mod N)计算c并不复杂。Bob算出c后就可以将它传递给Alice。解密消息Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n：cd  n (mod N)得到n后，她可以将原来的信息m重新复原。解码的原理是：cd  n&

20、#160;e·d(mod N)以及ed  1 (mod p-1)和ed  1 (mod q-1)。由费马小定理可证明（因为p和q是质数）n e·d  n (mod p) 和 n e·d  n (mod q)这说明（因为p和q是不同的质数，所以p和q互质）n e·d  n (mod pq)签名消息RSA也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话，那么她可以为她的消息计算一个散列值(Message digest)，然后用她

21、的密钥(private key)加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么他就可以知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。Java实现加密和解密的过程：public class RSA             /*    

22、0; *  加密、解密算法      * param key 公钥或密钥      * param message 数据      * return      */      public 

23、static long rsa(int baseNum, int key, long message)          if(baseNum < 1 | key < 1)              return

24、60;0L;                    /加密或者解密之后的数据          long rsaMessage = 0L;           

25、         /加密核心算法          rsaMessage = Math.round(Math.pow(message, key) % baseNum;          return rsaMessage;  &#

26、160;                           public static void main(String args)          /基数  

27、60;       int baseNum = 3 * 11;          /公钥          int keyE = 3;         

28、0;/密钥          int keyD = 7;          /未加密的数据          long msg = 24L;        &#

29、160; /加密后的数据          long encodeMsg = rsa(baseNum, keyE, msg);          /解密后的数据          long decodeMsg =

30、0;rsa(baseNum, keyD, encodeMsg);                    System.out.println("加密前：" + msg);          System.out.println("

31、加密后：" + encodeMsg);          System.out.println("解密后：" + decodeMsg);                  RSA加密算法的安全性当p和q是一个大素数的时候，从它们的积pq去分解因子p和

32、q，这是一个公认的数学难题。然而，虽然RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。1994年彼得·秀尔（Peter Shor）证明一台量子计算机可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀尔的算法可以淘汰RSA和相关的衍生算法。（即依赖于分解大整数困难性的加密算法）另外，假如N的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的N。1997年后开发的系统，用户应使用1024位密钥，证书认证机构应用2048位或以上。RSA

33、加密算法的缺点虽然RSA加密算法作为目前最优秀的公钥方案之一，在发表三十多年的时间里，经历了各种攻击的考验，逐渐为人们接受。但是，也不是说RSA没有任何缺点。由于没有从理论上证明破译RSA的难度与大数分解难度的等价性。所以，RSA的重大缺陷是无法从理论上把握它的保密性能如何。在实践上，RSA也有一些缺点：产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密；分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，。SHA-1算法与其他算法不一样的是，SHA-1设计的出发点是用于数字签名，其本质是一种散列函数（HASH）。哈希（Hash）是将目标

34、文本转换成具有相同长度的、不可逆的杂凑字符串（或叫做消息摘要）由于哈希算法的定义域是一个无限集合，而值域是一个有限集合，将无限集合映射到有限集合，根据“鸽笼原理(Pigeonhole principle)”，每个哈希结果都存在无数个可能的目标文本，因此哈希不是一一映射，是不可逆的。Java实现：import java.security.*; public class myDigest public static void main(String args) myDigest my=new myDigest(); my.testDigest(); public void testDigest() try String myinfo="我的测试信息" /java.security.MessageDigest alg=java.security.MessageDigest.getInstance("MD5"); java.security.MessageDigest alga=java.security.MessageDigest.getInstance("SHA-1"); alga.update(myinfo.getBytes(); byte digesta=