加密算法浅谈

2005 Copyright reserved

by JamesJoo[NE365][CVC.GB]

以下的文章基于我读书的时候做REPORT和PRESENTATION的，本来打算全部不加改动的发布，但考虑到版面语言的统一，大部分我用中文重写了一下，但仍有部分是英文的。

Chapter 1(第一章)

The art of war teaches us to rely not on the likelihood of the enemy’s not coming, but on our own readiness to receive him; not on the chance of his not attacking, but rather on the fact that we have made our position unassailable.

---The Art of War, Sun Tzu

这篇文章并非讲解加密原理和机制的文章，有很多书会讲这些的，但我还是假设你有密码学的基本知识，分的清楚symmetric和asymmetric等基本概念，但如果你是密码学高手，建议略过本章。另，我有专门讨论加密算法设计和机制的文章会以后慢慢给出，我这里只讲一些算法，有些算法我会给出实现它们的原代码。

Part I.经典加密算法谈

（一）Substitution Techniques(替换)

1． Caeser Cipher

所谓的恺撒加密，是一种基于26个英文字母表的加密方式，很简单，可靠性在今天的计算性能面前几乎没有。Caeser的机理是C=E（P）=（P+K）MOD（26）

密文字母是明文字母在字母表的位置上循环后移K个位置得到的。如果key=3的时候，plaintext是m，ciphertext就是p。当然，如你所知它无法处理现代英语语言出现了各种标点符号和其他符号，甚至连大小写都无法区分，但我们把字母表扩充到128 ASCII或256 extension ASCII, 我们就可以用此方法处理各种计算机文件，当然纯正的caeser加密的key 只有25个（或者26个，如果K=0时也算一种）。

破解方法：brute force。就是暴力穷举破解，鉴于加密方式简单，在知道该算法被使用后暴力破解显得忧为合适。

2．Monoalphabetic Cipher（单字母表加密）

当我们把caeser的C=E（P）=（P+K）MOD（26）规则打破后，每个字母都使用任意的字母代替，这样，在同样使用26个字母表的同时，KEY的个数就比CAESER的25（或26）个，多出许多，有26!个可能的KEY了。举个例子，明文e可能被加密为p，明文d可能被加密为a，从中就找不出任何的共性了。这样，盲目的brute force就显得笨拙了。

破解方法：一味得brute force，不如来点常用的probability analysis，我们知道英语中英文字母e的出现频率最高为12.7%, t的出现频率为9.05%。这样，如果我们分析密文发现P的出现频率最高，那P的明文很有可能就是t。概率分析+语言词法分析就可以比较快地搞定此加密方法。

3．Playfair Cipher

说道playfair，怕是大家会想到鲁迅先生的费厄泼赖FAIR PLAY。其实Playfair是一个人名，这其中有些小误会，给出一段此算法的小历史：this cipher was actually invented by British scientist Sir Charles Wheatstone in 1854, but it bears the name of his friend Baron Playfair of St. Andrews, who championed the cipher at the British foreign office. 此算法基本就是构造一个5x5的字母矩阵。矩阵的构造方法是关键字（去掉重复字母）+剩余字母（I和J看成一个），从左到右，从上到下依次添入5X5的矩阵，这样5X5=25个位置就涵盖了26个字母。举个例子：假设关键字是jamesjoo,去掉重复的J和一个O成为jameso，然后按顺序把字母添入矩阵(I和J添入一个位置)：

i/j a    m    e    s

o    b    c    d    f

g    h    k    l    n

p    q    r    t    u

v    w    x    y    z

以上就是我们的5X5矩阵(阴影部分是关键字)。

加密步骤有4步， 1）由于此算法一次操作2个字符，在基数个明文单词字母配对时，有以下规则：碰到明文有相同字母的就插入一个另外的字母(不妨假设为X)。象balloon,先有2个L，假设我们插入X好了，这样单词就变成ba lx lo on。2）在矩阵中，如果明码字母对出现在同一行，把一对字母按照行顺序向右顺移一位，es就变为si(sj). 3)在矩阵中，如果明码字母对出现在同一列,就按列顺序向下移动一位，zs变为sf。4）在矩阵中，如果明码字母对没有出现在同一行和列，就按对方所在行或列交叉索引一下，ak就变为mh，sl就变为en.

此方法显著降低了密文字母频率与明文字母频率的对应关系，用概率分析也不容易找到规律了。此方法被广泛用于一战和二战，并在当时被认为是不可破解的。

破解方法：brute force+语言词义分析

4．Polyalphabetic Cipher

此方法根据使用不同字母表，有各种变化。一个著名的算法是vigenere cipher,该算法的字母表更是著名的Vigenere Tableau,很多打印机的字母打印测试就使用该表。此方法其实是简化了playfair的矩阵构成。

破解方法：brute force+语言词义分析

（二）Transposition Techniques换位

有别于替换，换位算法的密文字母和明文的一样，不会出现明文没出现的字母。最简单的例子: get=>teg

一个比较通用的算法是这样的：先确定一个KEY，假设是4312567，长度是7

将明文每7个字母换行，假设明文是you holycrap get the fuck away from me(不考虑空格和大小写)

key          4312567

plaintext    youholy

             crapget

             thefuck

             awayfro

             mme

密文就是按KEY的顺序从1到7，向下读取明文：uaeaehpfyorhwmyctamoguflecrytko

效果看起来就不错了。

破解方法：语言词义分析+brute force

Part II.DES加密算法谈

在着手学习DES算法前，我们可以先学习一下SDES作为小小的热身。

S-DES (simplified Data Encryption Standard)

(这一部分需要感谢UCLA的David Morgan教授)。

顾名思义S-DES是简化的DES。我们知道DES使用56位KEY和64位数据块作为输入明码数据，最后的密文也是64位的。S-DES使用的KEY和数据都是8位的，而且使用的permutation表和S-BOX也是简化过的。需要说明的是DES作为一种symmetric的加密方式，其算法比较复杂，而且需要对SECRET KEY做妥善保护，否则一旦解密者有此SECRET KEY就可以轻易得到明码。让我们先认识两个术语: substitution（替换） and permutation（排列）.

Substitution: each element of the plaintext is mapped into another element.

Permutation: the elements in the plaintext are rearranged. Permutation is also called transposition.

Substitution examples:

Suppose that the 16 4-bit binary numbers are to be replaced by 2-bit values to which the following table corresponds them.

0000     01
0001     11
0010     00
0011     10
0100     11
0101     01
0110     10
0111     00
1000     00
1001     11
1010     10
1011     01
1100     01
1101     11
1110     11
1111     10

That constitutes a substitution cipher. Note it substitutes only 2 bits for 4. Many ciphers produce a ciphertext block of length equal to the plaintext block on which they operate. Those that do are called "block ciphers." Or, consider the Caesar cipher, wherein each letter of the alphabet is to be replaced by the letter that follows it 3 positions later in the alphabet. A replaced by D, B by E, C by F, and so on. Another substitution cipher.

Permutation example:

Suppose that the bits of a 4-bit binary number are to be re-ordered (or "transposed," or "permuted") such that the 2nd is promoted to 1st position, the 4th to 2nd. The 3rd is left alone, while the 1st is demoted to 4th. Then the 16 4-bit binary numbers, left column, get rearranged to the numbers shown, right column.学过数子电路的会对此表比较敏感，此真值表就是把第二位放到第一位，把第4位放到第2位，第3位不变，第一位放到第4位。

0000     0000
0001     0100
0010     0010
0011     0110
0100     1000
0101     1100
0110     1010
0111     1110
1000     0001
1001     0101
1010     0011
1011     0111
1100     1001
1101     1101
1110     1011
1111     1111

This permutation can be represented as "permutation P"

P

2
4
3
1

The numbers identify a bit from the input, and the table shows them as they are to be sequenced in the output. So given an input, pluck its second bit-- be it 1 or 0-- and write it down as the output's first bit. The input's 4th bit becomes the output's 2nd, and so on.

Most algorithms use both substitutions and permutations in combination, along with bitwise operations (e.g., XOR), and cascade them in a series of stages. Here is a diagram of the operational stages of S-DES.

下图表示了S-DES的加密和解密过程

Fixed Permutations used in S-DES:

S-DES involves several fixed operations involving particular permutations or other kids of operators. It starts by using the following 8-bit permutation, its "initial permutation," hence dubbed IP:

IP

2
6
3
1
4
8
5
7

S-DES also needs to make use of its inverse. Writing an inverse can be a little tricky. The inverse of a permutation is the one that "puts the bits back" where they came from. Given the output of the above permutation, since its 1st bit was originally (in the input) the 2nd bit, we construct an inverse whose output's 2nd bit shall be its input's 1st.

IP-1 (reverse permutation, under construction)

1
  
  
  
  
  
  

If we start with some input and subject it to IP, then take that result and subject it to IP-1, the original 2nd bit will have been "dislodged" to 1st position, but then "relodged" back to 2nd position.

Similarly, since the the IP output's 2nd bit used to be the input's 6th, we need an inverse permutation whose 6th bit will be its input's 2nd.

IP-1 (reverse permutation, under construction)

1
  
  
  
2
  
  

The original input's 6th bit travels to 2nd position under IP. Then that 2nd bit travels (back) to 6th position under IP-1.

Proceeding this way for the rest of the bits, the entire inverse permutation becomes:

IP-1

4
1
3
5
7
2
8
6

S-DES uses an "expansion" permutation whereby 2 separate permutations are applied to a 4-bit number, and the 2 results pasted together to form an 8-bit final output.

E/P

4
1
2
3
2
3
4
1

It also employs a 4-bit permutation P4:

P4

2
4
3
1

And it uses two so-called s-boxes, S0 and S1. Here is S0:

S0 =
  
c0
c1
c2
c3

r0
1
0
3
2

r1
3
2
1
0

r2
0
2
1
3

r3
3
1
3
2

And here is S1:

S1 =
  
c0
c1
c2
c3

r0
0
1
2
3

r1
2
0
1
3

r2
3
0
1
0

r3
2
1
0
3

Finally, it uses a swap operation called SW, wherein the right and left 4 bits of a byte are swapped. This is a permutation, and can be represented as such:

SW

5
6
7
8
1
2
3
4

These seven items, IP, IP-1, E/P, P4, S0, S1, and SW are invariant elements of S-DES. They are independent of its key and its input. Below is a diagram of S-DES's operation when encrypting a byte of plaintext. It corresponds to the leftmost column of the previous Figure 3.1, depicting the encryption process, with Figure 3.1's mysterious fK opened up and revealed in the gray boxes. The encircled plus sign symbolizes binary XOR. Notice the appearance at some stage in the diagram of each of the seven elements.

Notice also the presence of two other inputs to the process, K1 and K2. They are "subkeys." S-DES has a particular, single "main" key. Processing it by a set formula derives from it these two subkeys. So they vary. They are both, always 8 bits but their value depends on what value is chosen for the main key.