DES算法实现
实验目标
完成一个DES 算法的详细设计,内容包括：
- 算法概述；
- 总体结构；
- 数据结构。
实验概述
算法原理
DES（Data Encryption Standard）是一种用于电子数据加密的对称密钥块加密算法.它以64位为分组长度，64位一组的明文作为算法的输入，通过一系列复杂的操作，输出同样64位长度的密文。DES 同样采用64位密钥，但由于每8位中的最后1位用于奇偶校验，实际有效密钥长度为56位。密钥可以是任意的56位的数，且可随时改变。
DES 使用加密密钥定义变换过程，因此算法认为只有持有加密所用的密钥的用户才能解密密文。DES的两个重要的安全特性是混淆和扩散。其中混淆是指通过密码算法使明文和密文以及密钥的关系非常复杂，无法从数学上描述或者统计。扩散是指明文和密钥中的每一位信息的变动，都会影响到密文中许多位信息的变动，从而隐藏统计上的特性，增加密码的安全。
DES算法的基本过程是换位和置换。如图，有16个相同的处理阶段，称为轮。还有一个初始和最终的排列，称为 IP 和 FP，它们是反向的 (IP 取消 FP 的作用，反之亦然)。
在主轮之前，块被分成两个32位的一半和交替处理；这种纵横交错的方案被称为Feistel 方法。Feistel 结构确保了解密和加密是非常相似的过程——唯一的区别是在解密时子键的应用顺序是相反的。其余的算法是相同的。这大大简化了实现，特别是在硬件中，因为不需要单独的加密和解密算法。
符号表示异或（XOR）操作。Feistel 函数将半块和一些键合在一起。然后，将Feistel 函数的输出与块的另一半组合在一起，在下一轮之前交换这一半。在最后一轮之后，两队交换了位置；这是 Feistel 结构的一个特性，使加密和解密过程类似。
image
数据结构
Initial permutation (IP)
IP 置换表指定64位块上的输入排列。其含义如下：输出的第一个比特来自输入的第58位;第二个位来自第50位，以此类推，最后一个位来自第7位输入。
image
Final permutation ( 
)
最后的排列是初始排列的倒数。
image
Expansion function (E)
展开函数被解释为初始排列和最终排列。注意，输入的一些位在输出时是重复的;输入的第5位在输出的第6位和第8位中都是重复的。因此，32位半块被扩展到48位。
image
Permutation (P)
P排列打乱了32位半块的位元。
image
Permuted choice 1 ( PC-1 )
表的“左”和“右”部分显示了来自输入键的哪些位构成了键调度状态的左和右部分。输入的64位中只有56位被选中；剩下的8（8、16、24、32、40、48、56、64）被指定作为奇偶校验位使用。
image
Permuted choice 2 ( PC-2 )
这个排列从56位键调度状态为每轮选择48位的子键。
image
S-box
这个表列出了DES中使用的8个S-box，每个S-box用4位的输出替换6位的输入。给定一个6位输入，通过使用外部的两个位选择行，以及使用内部的四个位选择列，就可以找到4位输出。例如，一个输入“011011”有外部位“01”和内部位“1101”。第一行为“00”，第一列为“0000”，S-box S5对应的输出为“1001”(=9)，即第二行第14列的值。
image
image
基本流程
DES算法的基本流程图如下：
image
DES算法是典型的对称加密算法，在输入64比特明文数据后，通过输入64比特密钥和算法的一系列加密步骤后，可以得到同样为64比特的密文数据。反之，我们通过已知的密钥，可以将密文数据转换回明文。我们将算法分为了三大块：IP置换、16次T迭代和IP逆置换，加密和解密过程分别如下：
| 符号 | 释意 |
|---|---|
| M | 算法输入的64位明文块 |
| E | 描述以K 为密钥的加密函数，由连续的过程复合构成 |
| IP | 64位初始置换 |
| 一系列的迭代变换 | |
| W | 为64位置换，将输入的高32位和低32位交换后输出 |
| 是IP的逆置换 | |
| C | 算法输出的64位密文块 |
实验过程
实验的设计模式是自顶向下的结构，用C语言去分别是先各个函数的功能，最后通过主函数将所有函数进行整合，让算法更加清晰客观。
表置换
通过IP置换表，根据表中所示下标，找到相应位置进行置换。
const char IP_Table[64]={
58,50,42,34,26,18,10,2,
60,52,44,36,28,20,12,4,
62,54,46,38,30,22,14,6,
64,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
};
void TablePermute(bool *DatOut,bool *DatIn,const char *Table,int Num)
{
int i=0;
static bool Temp[256]={0};
for(i=0;i<Num;i++)
{
Temp[i]=DatIn[Table[i]-1];
}
BitsCopy(DatOut,Temp,Num);
}
对于16次 迭代，我们先将传入的经过 IP 混淆过的64位明文的左右两部分，分别为32位的
和32位的
。之后我们将
和
进行交换，得到作为IP逆置换的输入：
，
生成子密钥
子密钥的生成，经历下面一系列步骤：首先对于64位密钥，进行置换选择，因为将用户输入的64 位经历压缩变成了56位，所以我们将左面和右面的各28位进行循环位移。左右两部分分别按下列规则做循环移位：当，循环左移1位；其余情况循环左移2位。最后将得到的新的左右两部分进行连接得到56位密钥。
static char Move_Table[16]={
1, 1, 2, 2, 2, 2, 2, 2,
1, 2, 2, 2, 2, 2, 2, 1
};
void SetKey(char KeyIn[8])
{
int i=0;
static bool KeyBit[64]={0};
static bool *KiL=&KeyBit[0],*KiR=&KeyBit[28];
ByteToBit(KeyBit,KeyIn,64);
TablePermute(KeyBit,KeyBit,PC1_Table,56);
for(i=0;i<16;i++)
{
LoopMove(KiL,28,Move_Table[i]);
LoopMove(KiR,28,Move_Table[i]);
TablePermute(SubKey[i],KeyBit,PC2_Table,48);
}
}
Feistel 函数
image
对半块的 Feistel 操作分为以下五步：
- 展开：32位的半块通过重复一半位的展开排列扩展到48位。输出由8个6位（48位）块组成，每个块包含4个相应的输入位的副本，加上从每个输入块到任意一侧的相邻位的副本。
- 密钥混合：结果与使用 XOR 操作的子密钥结合。16个48位的子键（每个轮一个）由主键派生，使用下面描述的键调度。
- 替换：将子键混合后，将块分割成8个6位的块，再用 S-box 或替换盒进行处理。根据一个非线性变换，八个 S-box 中的每一个都用四个输出位替换了它的六个输入位。S-box 提供了 DES 安全的核心，如果没有它们，密码就会是线性的，而且容易被破解。
- 排列：根据一个固定的排列，即 P-box，将s -box的32个输出重新排列。这样设计的目的是，经过排列后，这一轮中每个 S-box 输出的比特被分散到下一轮的4个不同的 S-box 上。
- 置换：最后的 IP 逆置换同之前的 IP 置换基本相同，我们通过 IP 逆置换表，根据表中所示下标，找到相应位置进行置换。
const char IPR_Table[64]={
40,8,48,16,56,24,64,32,
39,7,47,15,55,23,63,31,
38,6,46,14,54,22,62,30,
37,5,45,13,53,21,61,29,
36,4,44,12,52,20,60,28,
35,3,43,11,51,19,59,27,
34,2,42,10,50,18,58,26,
33,1,41, 9,49,17,57,25
};
void F_Change(bool DatIn[32],bool DatKi[48])
{
static bool MiR[48]={0};
TablePermute(MiR,DatIn,E_Table,48);
Xor(MiR,DatKi,48);
S_Change(DatIn,MiR);
TablePermute(DatIn,DatIn,P_Table,32);
}
实验结果
如下三图展示了实验的结果（黄色代表明文，蓝色代表暗码，红色表示密码，绿色表示结果）
正确解码
image
image
如上二图表明，在给出正确的密码后，可以得到对应的明文。
密码错误
image
若密码错误，将解码出错误答案。
实验参考
【3】深入理解并实现DES算法
【4】DES算法原理完整版
