密码学安全算法--对称加密算法

对称加密也称为常规加密、单钥加密，在非对称加密(公钥加密)开发之前是唯一使用的加密类型，直到现在，它也仍然是使用最广泛的加密类型之一。最常见对称加密算法是：DES、3DES、AES、RC4。

对称加密算法基本原理

先上图，对称加密工作过程

在整个工作过程中涉及到以下几个概念

• 明文：也就是原始信息或者说原始数据。也就是上图中的A。
• 加密算法：对明文进行各种替换或转换操作的一种算法。也就是①过程执行的算法。
• 密钥：密钥也是加密算法的输入，加密算法进行替换或转换的具体操作依赖于这个密钥。也就是上图中描述的密钥Key。
• 密文：经过加密算法打乱的消息输出。密文的输出取决于明文与密钥，对于相同的明文，不同的密钥会产生不同的密文。也就是上图中的B。
• 解密算法：本质上来说就是加密算法的逆过程，算法输入的是密文和加密时使用的同一密钥。

对称加密的分类：流加密与分组加密

1. 流加密每次加密数据流的一位(bit)或者一个字节(byte)。如RC4。
2. 分组加密(通常也成为块加密)是将明文进行分组，加密算法对每个分组分别加密，通常明文分组和加密后得到的密文分组等长。典型的分组大小是64bit或128bit。如DES，3DES，AES。

DES

Data Encryption Standard 数据加密标准，该标准中的数据加密算法(Data Encryption Algorithm)，简称DEA，国内对DES和DEA两个术语的使用有点混乱。DES是IBM公司发明的，在1977年应征作为美国国家密码标准方案。随着CPU计算速度的提升，以及硬件成本的下降，1999年美国国家标准技术研究所颁布新标准，规定DES只能用于历史遗留系统以及3DES中。
DES采用64bit分组长度和56bit密钥长度，经过一系列变换得到64bit的密文输出。解密使用相同的密钥对密文进行解密运算。

3DES

密钥大小(bit)	密钥个数	每微秒执行一次解密所需要的时间	每微妙执行一百万次解密所需要的时间
56	256 = 7.2*1016	255μs=1142年	10.01小时

随着软硬件技术的发展，多核CPU、分布式计算、量子计算等理论的实现，DES在穷举方式的暴力攻击下还是相当脆弱的，因此很多人想办法用某种算法替代它，面对这种需求广泛被采用的有两种方案： 1. 设计一套全新的算法，例如AES，这个在后面会说到。 2. 为了保护已有软硬件的投资，仍使用DES，但使用多个密钥进行多次加密，这就是多重DES加密。

双重加密

双重加密是多重加密最简单的形式，使用两个密钥。使用表达式叙述如下：

C：		代表加密后的密文(crypted)
E：		代表加密算法(encrypt)
D：		代表解密算法(decrypt)
K1,K2：	代表两个密钥(key)
P：		代表明文(proclaimed)

		加密过程：
		C = E( K2, E( K1, P ) )
		解密过程：
		P = D( K1, D( K2, C) )

双重DES加密表面上进行了两次加密，从而密钥长度为56×2=112bit，密码强度增加了，但是在1992年在一篇论文中被证实存在下面的情况：

E(K2, E(K1, P)) = E(K3, P)

也就是说存在密钥K3能解密经过K1，K2进行双重加密的密文，这意味着双重DES退化成了单重DES了。显然这种方式是不安全的。

使用两个密钥的三重加密

加密过程:
	C = E( K1, D( K2, E( K1, P ) )
解密过程:
	P = D( K1, E( K2, D( K1, C ) )

这个加密方式就有意思了，先用K1进行加密，然后对加密的密文用K2进行解密，解密后的密文再用K1进行加密；解密过程就与之相反，并且该算法当k1==k2时能与单重DES兼容。这个奇特的想法最后也成为了美国的加密标准之一X9.17。

使用三个密钥的三重加密

加密过程:
	C = E( K3, D( K2, E( K1, P ) )
解密过程:
	P = D( K3, E( K2, D( K1, C ) )

这种加密方式1998年被列为美国加密标准X9.52，并且已经广泛地替代了DES。过程很好理解。如果需要与DES进行兼容，只需设置K3=K2或K2=K1；如果需要与前面的双重密钥的三重加密兼容只需k1=k3。

知道了3DES与DES的关系，那我们就可以推出3DES的密钥长度应该为DES的三倍也就是168bit，输入的明文块和输出的密文块仍然是64bit的。

更多3DES的信息可以查看wiki

AES

3DES缺点是算法运行相对较慢。因为原来DEA是为70年代的硬件设计的，算法代码并不是很高效，而3DES是DEA算法的3轮迭代，因此更慢。而且DEA和3DES的分组大小都是64bit，3DES密钥长度却是168bit，处于加密效率和安全的考虑，需要更大的分组长度。于是AES应运而生。

Advanced Encryption Standard 高级加密标准，该标准是美国国家标准技术研究所于2001年颁布的。AES旨在取代DES成为广泛使用的标准，2006年AES已成为最流行的对称加密算法。

AES使用的分组大小为128bit，密钥长度可以为128、192、256 bit。最简单最常用的也就是128 bit的密钥。

AES的详细内容可以查看wiki

下面列个表，大致的总结一下分组加密算法。

分组(块)加密标准	分组大小	密钥长度
DES	64 bit = 8 byte	56 bit = 7 byte
3DES	64 bit = 8 byte	168 bit = 21 byte
AES	128 bit = 16 byte	128|192|256 bit =16|24|32 byte

流加密实现原理

真随机数，伪随机数

因为随机数在加密算法中相当重要，而且RC4中就使用了伪随机数生成算法。所以有必要理解什么是伪随机数，什么事真随机数。看一下Wiki中对真随机数和伪随机数的界定。

根据密码学原理，随机数的随机性检验可以分为三个标准：

1. 统计学伪随机性。统计学伪随机性指的是：在给定的随机比特流样本中，1的数量大致等于0的数量，同理，“10”“01”“00”“11”四者数量大致相等。类似的标准被称为统计学随机性。满足这类要求的数字在人类“一眼看上去”是随机的。
2. 密码学安全伪随机性。其定义为：给定随机样本的一部分和随机算法(RNG,Random number generator)，不能有效的演算出随机样本的剩余部分。
3. 真随机性。其定义为：随机样本不可重现。实际上只要给定边界条件，真随机数并不存在，可是如果产生一个真随机数样本的边界条件十分复杂且难以捕捉（比如计算机本身的辐射波动值），可以认为用这个方法演算出来了真随机数。

相应的，随机数也分为三类：

1. 伪随机数：满足第一个条件的随机数。
2. 密码学安全的伪随机数：同时满足前两个条件的随机数。可以通过密码学安全伪随机数生成器计算得出。
3. 真随机数：同时满足三个条件的随机数。

真正的随机数是使用物理现象产生的：比如掷钱币、骰子、使用电子元件的噪音、核裂变等等。这样的随机数生成器叫做物理性随机数生成器，它们的缺点是技术要求比较高。

在实际应用中往往使用伪随机数就足够了。这些数列是“似乎”随机的数，实际上它们是通过一个固定的、可以重复的算法产生的(只是重复的周期比较大)。它们不真正地随机，因为它们实际上是可以计算出来的，但是它们具有类似于随机数的统计特征(分布均匀)。这样的生成器叫做伪随机数生成器(PRNG, pseudo-random number generator)。

流加密的基本原理

流加密的原理很简单，用前面提到的伪随机数生成器(PRNG)根据秘钥来生成一个与明文长度一样的密钥流，然后将密钥流与明文流进行异或运算从而得到加密后的密文。解密时用同样的算法，根据密钥通过PRNG得到密钥流，将密钥流与密文进行异或运算即可。这里面遵循了一个很简单的原则：对一个数据进行两次相同的异或运算得到的还是原来的数据。

流加密的优缺点

优点：

1. 实现简单。流加密生成密钥流后，只要进行一次异或运算即可；而像DES这样的分组加密需要经过Feistel加密网络(16轮的置换操作)。
2. 速度更快。因为流加密的简单操作少，所以速度也比分组加密快。
3. 变长密钥。密钥只负责生成密钥流，密钥流的生成与密钥长度关系不大，这就使得流加密可以使用变长密钥。

自己实现一个简单的流加密

知道了上面的原理，我们可以实现一个简单的流加密算法，从而更深层的了解流加密算法的原理。

首先我们知道C语言stdlib.h函数库中有一个rand()函数可以生成0~0x7FFF范围内的伪随机数，而且可以通过srand()来设置随机数种子，我们就用这两个函数来实现一个流加密算法：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*加密算法：message被加密的消息，count消息长度，key加密密钥*/
void crypto(char message[], int length, int key);

/*将字符字节流转16进制*/
const char* toHexStr(const char* message, int length);

void main(int argc, char *argv[])
{
	char msg[] = "Hello World!";
	int key = 10;
	int length = strlen(msg);
	printf("before encryption:%s\n", toHexStr(msg, length));

	// 加密
	crypto(msg, sizeof(msg), key);
	printf("after encryption :%s\n", toHexStr(msg, length));

	// 解密
	crypto(msg, sizeof(msg), key);
	printf("after decryption :%s\n", toHexStr(msg, length));
	system("pause");
}

void crypto(char message[], int length, int key)
{
	char key_stream = 0;
	int i = 0;

	// 以密钥作为种子
	srand(key);

	for (i = 0; i < length; i++)
	{
		// 生成与密文长度一致的密钥流
		key_stream = rand() & 0x00FF;

		// 将明文与密钥流进行异或运算得到密文
		message[i] = message[i] ^ key_stream;
	}
}

const char* toHexStr(const char* message, int length)
{
#	define BUFFER_SIZE 4*1024+1
	static const char CHAR_TABLE[] = "0123456789ABCDEF";
	static char buffer[BUFFER_SIZE];
	int i = 0, j = 0;
	int high = 0, low = 0;

	memset(buffer, 0, sizeof(buffer));
	while (i < length && j < BUFFER_SIZE)
	{
		// char只占1个字节，所以可以直接计算高4位和低四位
		high = message[i] / 16;
		low = message[i] % 16;
		buffer[j++] = CHAR_TABLE[high & 0x000F];
		buffer[j++] = CHAR_TABLE[low & 0x000F];
		i++;
	}
	return buffer;
}

我们可以看一下运行结果：

上面的程序把“Hello World!”这个字符串进行了加密，密钥是个整数10。这个加密算法很简单，所以也有很多缺陷，比如它只能接受正整数的密钥，这些缺陷主要由于rand()这个随机数产生器导致的，而很多知名流加密算法就是在这个随机数产生器上做文章。

RC4

Rivest Cipher 4是RSA公司的成员Ron Rivest于1987年设计的(RSA是三个麻省理工大学的学生创立的，著名的非对称公钥加密算法RSA就是该公司发明的)。起初该算法是商业机密，直到1994年，才被公之于众。由于RC4具有算法简单，运算速度快，软硬件实现都十分容易等优点，使其在一些协议和标准里得到了广泛应用。比如：SSL/TLS(Secure Sockets Layer/Transport Layer Security)，无线局域网WEP(Wired Equivalent Privacy)协议和WPA(Wi-Fi Protected Access)中都有RC4的应用。

Ron Rivest共设计了六套加密算法，都以RC命名，其中RC4是流加密方式实现的，RC2是一种分组加密算法实现，RC6更是AES算法征集的入围者，更多内容点击这里