数据加密算法--详解DES加密算法原理与实现

DES算法简介

DES(Data Encryption Standard)是⽬前最为流⾏的加密算法之⼀。DES是对称的，也就是说它使⽤同⼀个密钥来加密和解密数据。DES还是⼀种分组加密算法，该算法每次处理固定长度的数据段，称之为分组。DES分组的⼤⼩是位，如果加密的数据长度不是位的倍数，可以按照某种具体的规则来填充位。

从本质上来说，DES的安全性依赖于虚假表象，从密码学的术语来讲就是依赖于“混乱和扩散”的原则。混乱的⽬的是为隐藏任何明⽂同密⽂、或者密钥之间的关系，⽽扩散的⽬的是使明⽂中的有效位和密钥⼀起组成尽可能多的密⽂。两者结合到⼀起就使得安全性变得相对较⾼。

DES算法具体通过对明⽂进⾏⼀系列的排列和替换操作来将其加密。过程的关键就是从给定的初始密钥中得到16个⼦密钥的函数。要加密⼀组明⽂，每个⼦密钥按照顺序（1-16）以⼀系列的位操作施加于数据上，每个⼦密钥⼀次，⼀共重复16次。每⼀次迭代称之为⼀轮。要对密⽂进⾏解密可以采⽤同样的步骤，只是⼦密钥是按照逆向的顺序（16-1）对密⽂进⾏处理。

计算16个⼦密钥

上⾯提到DES算法的第⼀步就是从初始密钥中计算得出16个⼦密钥。图⽰1展⽰了这个过程。DES使⽤⼀个56位的初始密钥，但是这⾥提供的是⼀个位的值，这是因为在硬件实现中每8位可以⽤于奇偶校验，在软件实现中多出的位只是简单的忽略掉。要获得⼀个56位的密钥，可以执照表1的⽅式执⾏密钥转换。解释⼀下表1，按照从左往右从上往下的⽅式看，表格中每个位置P包含初始密钥中位在转换后的密钥中所占的位置。⽐如，初始密钥中的第57位就是转换后的密钥中的第1位，⽽初始密钥中的第49位则变成转换后的密钥中的第2位，以此类推...。（数据位的计数顺序按照从左到右从1开始的）表1：DES中密钥的转换表（DesTransform[56]）

将密钥转换为56位后，接下来计算⼦密钥。⾸先，将56位的密钥分为两个28位的组。然后，针对每个⼦密钥，根据⼦密钥的序列值（也就是16个⼦密钥中的第⼏个）旋转这两组值（旋转的位数见表2），然后重新合并。之后，再按照表3所⽰对重组后的密钥进⾏置换，使56位的⼦密钥缩⼩为48位（注意表3只有48位，丢弃了8位）。这个排列过程就称为置换选择。

针对16个⼦密钥，每个⼦密钥重复⼀次该过程。这⾥的⽬的是保证将初始密钥中的不同位在每⼀轮排列后应⽤于加密的数据上。表2：针对DES⼦密钥每⼀轮的旋转次数（Round轮，Rotations旋转次数）(DesRotations)

表3：DES⼦密钥的置换选择(Despermuted[48])

图1：在DES中计算⼦密钥的过程

加密和解密数据块

经过上述过程，我们已经准备好了⼦密钥。接着就可以加密和解密数据块了。图2展⽰了这个过程。图2：DES中加密和解密数据块

从表4所⽰的⽅式置换位的数据块开始，该置换过程称为初始置换。该过程并不会增加DES的安全性，但这种做法在16位和32位的总线出现之前将使得数据更容易加载到DES芯⽚中。虽然这种处理已经不合时宜，但该置换过程仍然保留以满⾜DES标准。表4：DES中数据的初始置换（DesInitial[]）

经过初始置换后，位的数据块分为两个32位的组，L0和R0。

完成初始置换后，数据块将重复执⾏16轮⼀系列的操作。每⼀轮操作（i）的⽬的是计算出Li和Ri ，这些结果将⽤在下⼀轮操作中直到最终得到数据R16和L16。

每⼀轮以Li-1和Ri-1开始，然后根据表5所⽰进⾏扩展置换，将Ri-1从32位扩展到48位。该置换的主要⽬的是在加密数据的过程中制造⼀些雪崩效应，使⽤数据块中的1位将在下⼀步操作中影响更多位，从⽽产⽣扩散效果。

⼀旦扩展置换完成，计算出48位的结果值与这⼀轮⼦密钥Ki的异或值（XOR，符号计为⊕）。这将产⽣48位的中间值，记为Rint。如果将E计为扩展置换的结果，则本轮到⽬前为⽌的操作可以表⽰为：Rint = E（Ri-1) ⊕ Ki

表5：DES中数据块的扩展置换（DesExpansion[48]）

下⼀步，Rint 需要通过8个单独的S盒执⾏8次替换操作。每个S盒（j）从Rint的6j 到 6j+6 的位置取出6位，并为其在表6中查出1个4位的值，将该值写到缓冲区的4j位置处（如图3）。图3：DES中的8个S盒

读表6，查找S盒（j）。通过前⾯取出的6位值，根据第1位和最后1位组成的2位值找到表6中的⾏号，⽽根据中间剩下的4位来确定表6中的列号。⽐如，在图3中，Rint中的第3个6位组是101011。因此，在表6中查找到的第3个S盒是9。因为⾏号等于112 = 3，列号等于01012 =5（查表时从索引0开始计数）。S盒为数据增加了不确定性，除了给DES带来安全性外，没什么特别的。表6：DES中数据块的S盒替换

⼀旦完成了S盒替换，得到的结果⼜变为⼀个32位的值。接下来再通过P盒来置换。如下表7所⽰。表7：DES中数据块的P盒置换

到⽬前为⽌，我们把这⼀轮的操作想象为⼀个函数，⼀般记为f。如果 bj 代表Rint中的第j个6位组，Sj 代表第j个S盒，⽽P代表P盒置换，则该函数可以定义为：

f = P(S1(b1),S2(b2),...,S8(b8))

每⼀轮的最后⼀个操作是计算 f 的32位结果值与传⼊本轮操作的原始数据的左分组Li-1之间的异或值。⼀旦完成，将左右两个分组交换然后开始下⼀轮。在最后⼀轮中，不⽤交换左右分组。

把所有的步骤连起来，在每⼀轮中计算Li和Ri的步骤可以精确表⽰为：Li = Ri-1

Ri = Li-1 ⊕ f(Ri-1,Ki)

当全部的16轮操作都结束后，将最后的右分组R16和最后剩下的左分组L16连接起来，组成⼀个位的分组R16L16。（回顾⼀下，在最后⼀轮中左右分组并没有交换。最后的右分组在左边⽽最后的左分组在右边。）

最后⼀步是将R16L16按照表8所⽰的置换进⾏置换。简⽽⾔之，就是撤消之前的初始置换。加密数据时，最终结果就是⼀个位的密⽂，⽽当解密数据时，最终结果就是位的明⽂了。表8：DES中数据块的最终置换

DES的接⼝定义

des_encipher

void des_encipher(const unsigned char *plaintext, unsigned char *ciphertext, unsigned char *key);返回值：⽆

描述：采⽤DES算法，将明⽂plaintext的⼀个位的明⽂组加密。在key中指定位的密钥（最后8位将被忽略掉，实际得到56位的密钥）。ciphertext是返回的位的密⽂组。

由调⽤者负责管理ciphertext所需要的空间。要加密⼀段较⼤的数据，可以按照分组加密模式调⽤des_encipher。为了得到较⾼的效率，des_encipher可以重⽤之前的调⽤中计算出来的⼦密钥，这可以通过在之后的调⽤中将NULL传给key，以此来开启这种功能。复杂度：O（1）des_decipher

void des_decipher(const unsigned char *ciphertext, unsigned char *plaintext, unsigned char *key);返回值：⽆

描述：采⽤DES算法将密⽂ciphertext的⼀个位分组解密。该函数假设ciphertext包含的是通过des_encipher加密过的密⽂。在key中指定位的密钥（最后8位将被忽略掉，实际得到56位的密钥）。plaintext是返回的位的明⽂组。由调⽤者负责管理plaintext所需要的空间。要解密⼀⼤段的数据，可以按照分组加密模式调⽤des_decipher。为了获得较⾼的效率，des_decipher可以重⽤之前调⽤中计算出来的⼦密钥。可以在随后的调⽤中将NULL传给key，以此来开启这种功能。复杂度：O（1）

DES算法的实现

考虑到DES算法中涉及的位操作很多，因此DES算法通常都是在硬件中实现。DES算法中的图表和术语（通过线、框画的流程图，以及诸如S盒、P盒这样的术语）使其更倾向于在硬件中实现，当然，软件实现也有它的价值所在。在软件开发中，通过⼏种基本的指令操作来帮助实现DES中的各种置换、转换以及替换操作都是很有效的。des_encipher

函数des_encipher将明⽂的⼀个位的明⽂分组通过DES算法加密。

由于DES的⼀个很好的特点是同样的过程既能⽤来加密数据也能⽤来解密数据，因此des_encipher只需要简单的调⽤des_main，⽽des_decipher同样也只需要调⽤des_main即可。

函数des_main通过使⽤其参数direction来确定到参数source提供的数据是明⽂还是密⽂。direction参数只是简单地修改⼦密钥的顺序。在des_encipher中，direction设置为encipher。

函数des_main()⾸先检测参数key是否为NULL。这将允许des_encipher的调⽤者重⽤上⼀次调⽤时计算出来的⼦密钥。将⼦密钥数组subkeys声明为static类型。如果key不为NULL，将计算⼦密钥。

要计算⼦密钥，可以按照前⾯介绍过的步骤（计算16个⼦密钥）来执⾏。key的转换是通过函数permute来实现的，这⾥就是根据⼀个特定的表在⼀个缓冲区中置换位。假设表中的每个位置（i）上都存在⼀个值p，函数permute通过将位置p的位移动到位置（i）上来完成对传⼊的buffer的置换。

要置换密钥，将表Des_Transform（同表1）传给函数permute。必要的旋转操作可以通过调⽤位操作bit_rot_left来实现。该操作将buffer按照

指定的位数向左旋转。每⼀轮要正确旋转28位的⼦密钥分组，将表Des_Rotations（同表2）中合适的元素传给bit_rot_left。通过调⽤permute，并把传⼊表Des_permuted（同表3），来对每⼀个⼦密钥做置换选择。

要加密⼀个数据块，⾸先要执⾏初始置换。为实现这⼀步，⾸先调⽤函数permute并将表Des_Initial（同表4）传⼊。然后，将数据分为两个32位的分组：lblk以及rblk。回顾⼀下，加密数据的⼤部分⼯作都是将⼀系列的操作重复执⾏16轮。每⼀轮的主要⼯作都花在计算函数（f）的值上，将值保存在fblk中。

每⼀轮操作开始时，将对rblk执⾏⼀个扩展置换。为了实现这个步骤，将调⽤函数permute，并把表Des_Expansion（同表5）传⼊。然后，通过调⽤位操作bit_xor来计算扩展后的rblk和某个适当的⼦密钥的异或值。⽆论是加密还是解密数据，与本轮操作相关的⼦密钥都需要参与执⾏。⼀旦完成了异或计算，将对结果执⾏⼀系列的S盒替换操作。Des_Sbox（同表6）定义了8个⽤于DES算法中的S盒。对于当前fblk中的每个6位分组，第1位和最后1位联合起来确定Des_Sbox中的⾏号，⽽中间的4位⽤来确定列号。最后执⾏P盒置换来完成函数f的计算。通过调⽤permute函数并传⼊表Des_Pbox（同表7）来实现这个步骤。计算出lblk与函数f的值的异或结果，并交换lblk和rblk来结束⼀轮的操作。

将上述过程重复16次，每轮⼀次。当全部16轮操作完成后，将rblk拷贝到target的前32位中，将lblk拷贝到之后的32位中（按照要求，最后⼀轮不交换lblk和rblk）。最终，通过调⽤permute并把Des_Final（同表8）传⼊来完成最后的置换操作。des_encipher的时间复杂度是O（1），因为加密数据块的所有步骤都能在恒定的时间内完成。des_decipher

函数des_decipher将⼀个位的密⽂分组通过DES算法进⾏解密。同des_encipher⼀样，des_decipher实际通过调⽤des_main来完成解密任务，但这⾥direction需要设置为decipher。因此，des_decipher的⼯作⽅式同des_encipher⼀样，只是这⾥的⼦密钥需要以逆序的⽅式参与。具体来说，就是在des_main中，针对每⼀轮i（从0开始计数），参与计算的⼦密钥为subkeys数组中下标为（15-i）的元素。des_decipher的时间复杂度为O（1），因为解密数据块中的所有步骤都可以在恒定的时间内完成。⽰例1：数据加密的头⽂件（DES算法和RSA算法通⽤头⽂件）

/*encrypt.h*/

#ifndef ENCRYPT_H#define ENCRYPT_H

/*在⼀个安全实现中，Huge 最少要400位10进制数字*/typedef unsigned long Huge; /*为RSA公钥定义⼀个数据结构*/typedef struct RsaPubKey_{

Huge e; Huge n;}RsaPubkey;

/*为RSA私钥定义⼀个数据结构*/typedef struct RsaPriKey_{

Huge d; Huge n;}RsaPriKey;

/*函数声明*/

void des_encipher(const unsigned char *plaintext, unsigned char *ciphertext, const unsigned char *key);void des_decipher(const unsigned char *ciphertext, unsigned char *plaintext, const unsigned char *key);void rsa_encipher(Huge plaintext, Huge *ciphertext, RsaPubKey pubkey);void rsa_decipher(Huge ciphertext,Huge *plaintext, RsaPriKey prikey);#endif // ENCRYPT_H

⽰例2：DES算法的实现

/*des.c*/

#include #include #include #include \"bit.h\"

#include \"encrypt.h\"

/*定义⼀个密钥置换的映射*/

static const int DesTransform[56] ={

57,49,41,33,25,17,9,1,58,50,42,34,26,18, 10,2,59,51,43,35,27,19,11,3,60,52,44,36, 63,55,47,39,31,23,15,7,62,,46,38,30,22, 14,6,61,53,45,37,29,21,13,5,28,20,12,4};

/*定义⽤于计算⼦密钥的旋转次数*/static const int DesRotations[16] ={

1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1};

/*定义⽤于⼦密钥置换选择的映射*/static const int DesPermuted[48] ={

14,17,11,24,1,5,3,28,15,6,21,10, 23,19,12,4,26,8,16,7,27,20,13,2,

41,52,31,37,47,55,30,40,51,45,33,48, 44,49,39,56,34,53,46,42,50,36,29,32 };

/*定义⽤于数据块初始化转换的映射*/static const int DesInitial[] ={

58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4, 62,,46,38,30,22,14,6,,56,48,40,32,24,16,8, 57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3, 61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7};

/*定义⽤于数据块扩展转换的映射*/static const int DesExpansion[48] ={

32,1,2,3,4,5,4,5,6,7,8,9,

8,9,10,11,12,13,12,13,14,15,16,17, 16,17,18,19,20,21,22,23,24,25, 24,25,26,27,28,29,28,29,30,31,32,1};

/*定义⽤于数据块中S盒转换的S盒表*/static const int DesSbox[8][4][16] ={ {

{14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7}, {0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8}, {4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0}, {15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13}, }, {

{15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10}, {3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5}, {0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15}, {13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9}, }, {

{10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8}, {13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1}, {13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7}, {1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12}, }, {

{7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15}, {13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9}, {10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4}, {3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14}, }, {

{2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9}, {14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6}, {4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14}, {11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3}, }, {

{12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11}, {10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8}, {9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6}, {4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13}, }, {

{4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1}, {13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6}, {1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2}, {6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12}, }, {

{13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7}, {1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2}, {7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8}, {2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11}, }};

/*定义⽤于数据块转换的P盒映射表*/static const int DesPbox[32] ={

};

/*定义⽤于数据块最终转换的映射*/

static const int DesFinal[] ={};

/*定义⼀个枚举类型，⽤于选择是加密或是解密数据*/typedef enum DesEorD_ {encipher,decipher} DesEorD;

/*permute函数 ⽤于转换、改变位序列*/

static void permute(unsigned char *bits, const int *mapping, int n){

unsigned char *temp[8]; int i;

/*使⽤n位映射映射缓冲区*/ memset(temp, 0, (int)ceil(n/8));

for(i=0; ibit_set(temp, i, bit_get(bits,mapping[i]-1)); memcpy(bits, temp, (int)ceil(n/8)); return;}

/*des_main函数 加密或解密数据的计算函数*/

static int des_main(const unsigned char *source, unsigned char *target, const char *key, DesEorD direction){

static unsigned char subkeys[16][7]; unsigned char temp[8], lkey[4], rkey[4], lblk[6], rblk[6], fblk[6], xblk[6], sblk; int row,col,i,j,k,p;

/*如果key等于NULL，重⽤上次调⽤时计算出来的⼦密钥，否则计算⼦密钥*/ if(key != NULL) {

/*创建⼀个key的副本*/ memcpy(temp,key,8);

/*将key转换并压缩⾄56位*/

permute(temp,DesTransform,56); /*将key分为两个28位的组*/ memset(lkey,0,4); memset(rkey,0,4);

for(j=0; j<28; j++)

bit_set(lkey, j, bit_get(temp,j)); for(j=0; j<28; j++)

bit_set(rkey, j, bit_get(temp,j+28)); /*计算每⼀轮的⼦密钥*/ for(i=0; i<16; i++) {

/*根据定义好的位数对每⼀块进⾏旋转*/ bit_rot_left(lkey,28,DesRotations[i]); bit_rot_left(rkey,28,DesRotations[i]); /*重新合并两个块*/ for(j=0; j<28; j++)

bit_set(subkeys[i],j,bit_get(lkey,j)); for(j=0; j<28; j++)

bit_set(subkeys[i],j+28,bit_get(rkey,j)); /*对⼦密钥做转换选择并压缩⾄48位*/ permute(subkeys[i],DesPermuted,48); } }

/*创建source参数的副本*/ memcpy(temp, source, 8); /*初始转换数据块*/

permute(temp, DesInitial, );

/*将源数据块分为⼤⼩为32位的左右两个数据块*/ memcpy(lblk, &temp[0], 4); memcpy(rblk, &temp[4], 4);

/*加密或解密源数据*/ for(i=0; i<16; i++) {

/*开始f缓冲冲的计算*/ memcpy(fblk,rblk,4);

/*置换、扩展右数据块的拷贝，使其达到48位*/ permute(fblk, DesExpansion, 48);

/*根据direction的值来应⽤适当的⼦密钥*/ if(direction == encipher) {

/*加密数据，⼦密钥组以递增的顺序应⽤*/ bit_xor(fblk, subkeys[i], xblk, 48); memcpy(fblk, xblk, 6); } else {

/*解密数据，⼦密钥组以递减的顺序应⽤*/ bit_xor(fblk, subkeys[15-i], xblk, 48); meycpy(fblk, xblk, 6); }

/*执⾏S盒替换*/ p=0;

for(j=0; j<8; j++) {

/*计算出S盒表中的⾏号和列号*/

row = (bit_get(fblk,(j*6)+0)*2) + (bit_get(fblk,(j*6)+5)*1); col = (bit_get(fblk,(j*6)+1)*8) + (bit_get(fblk,(j*6)+2)*4) + (bit_get(fblk,(j*6)+3)*2) + (bit_get(fblk,(j*6)+4)*1); /*为当前的6位数据块做S盒替换*/

sblk = (unsigned char)DesSbox[j][row][col]; for (k=4; k<8; k++) {

bit_set(fblk,p,bit_get(&sblk,k)); p++; } }

/*为f缓冲区执⾏P盒替换*/ permute(fblk, DesPbox, 32); /*计算左数据块与f缓冲区的异或值*/ bit_xor(lblk, fblk, xblk, 32); /*设置本轮的左数据块*/ memcpy(lblk, rblk, 4); /*设置本轮的右数据块*/ memcpy(rblk, xblk, 4); }

/*将⽬标正⽂设置为重新连接的左右两个数据块*/ memcpy(&target[0], rblk, 4); memcpy(&target[4], lblk, 4); /*执⾏最终置换*/

permute(target, DesFinal, ); return 0;}

/*des_encipher DES加密数据*/

void des_encipher(const unsigned char *plaintext, unsigned char *ciphertext, const unsigned char *key){

des_main(plaintext, ciphertext, key, encipher); return;}

/*des_decipher DES解密数据*/

void des_decipher(const unsigned char *ciphertext, unsigned char *plaintext, const unsigned char *key){

des_main(ciphertext, plaintext, key, decipher); return;}