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

对称加密也称为常规加密、单钥加密,在非对称加密(公钥加密)开发之前是唯一使用的加密类型,直到现在,它也仍然是使用最广泛的加密类型之一。最常见对称加密算法是: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)密钥个数每微秒执行一次解密所需要的时间每微妙执行一百万次解密所需要的时间
56256 = 7.2*1016255μs=1142年10.01小时
随着软硬件技术的发展,多核CPU、分布式计算、量子计算等理论的实现,DES在穷举方式的暴力攻击下还是相当脆弱的,因此很多人想办法用某种算法替代它,面对这种需求广泛被采用的有两种方案:

  1. 设计一套全新的算法,例如AES,这个在后面会说到。
  2. 为了保护已有软硬件的投资,仍使用DES,但使用多个密钥进行多次加密,这就是多重DES加密。

    双重加密

    双重加密是多重加密最简单的形式,使用两个密钥。使用表达式叙述如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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年在一篇论文中被证实存在下面的情况:

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

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

使用两个密钥的三重加密

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

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

使用三个密钥的三重加密

1
2
3
4
加密过程:
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()来设置随机数种子,我们就用这两个函数来实现一个流加密算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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算法征集的入围者,更多内容点击这里