DES算法C++程序设计和实现
1 算法原理概述
Data Encryption Standard (DES) 是一种典型的对称**算法，采用块加密方法，它以64位为分组长度，64位一组的明文作为算法的输入，通过与**运算和一系列复杂的操作，输出同样64位长度的密文，用同一**可以解密，所以该算法所有的保密性依赖于**，认为只有持有加密所用的**才能解密密文。DES采用64位**，但由于每8位中的最后1位用于奇偶校验，实际有效**长度为56位。DES算法的基本过程是换位和置换。
2 总体结构
C = Ek(M) = IP-1·W·T16·T15·…·T1·IP(M).
3 模块分解
C = DES(M, K)
流程：
- 初始置换IP -> M0 = IP(M) = L0R0
- 16轮迭代T-> L16R16 = T16(L0R0)
- T -> LiRi = T(Li-1Ri-1) 其中Li= Ri-1, Ri= Li-1⊕f(Ri-1, Ki), i = 1 … 16.
- f -> f(Ri-1, Ki) （Feistel轮函数）
- 将长度为32位的串Ri-1 作E-扩展 E(Ri-1)
- E(Ri-1)⊕Ki
- 子**的生成
- S-box 平均分成8个分组分别经过8个不同的S-盒进行 6-4 转换
- P-置换
- f -> f(Ri-1, Ki) （Feistel轮函数）
- T -> LiRi = T(Li-1Ri-1) 其中Li= Ri-1, Ri= Li-1⊕f(Ri-1, Ki), i = 1 … 16.
- 左右置换W
- 逆置换IP-1 -> C = IP-1(R16L16)
根据以上流程的包含关系，分解得到的主要模块为：
其中最主要的模块为子**生成和Feistel轮函数。
此外，从DES的功能上来分，可以分为加密和解密两个大的模块。
（其他具体细节见源代码）
4 数据结构
涉及到位操作的许多部分可以利用c++中的bitset方便进行；
此外，置换表可以用一维数组表示；
每个S_BOX为一个二维数组，所以S_BOX可以用三维数组表示；
5 编译运行结果
（1）对64位数据加密和解密，并将结果输出：
（2）对图片文件进行加密和解密
加密和解密后，文件下多出两个文件，分别是密文（16进制数据）和解密后的图片文件，他们的文件大小都相同，打开也能正确显示原图。
补充：DES 算法中，原始明文被分为64位的明文块进行加密，最后一块不足64位 ，则补齐为64位后再进行加密。本次实验没有进行填充处理，但实际上，原始明文消息按PKCS#5 (RFC 8018) 规范进行字节填充：原始明文消息最后的分组不够8个字节(64位) 时，在末尾以字节填满，填入的字节取值相同，取值都为需填充的字节数目；原始明文消息刚好分组完全时，在末尾填充8个字节(即增加一个完整分组)，字节取值都是08（因为填充了8个字节）。
6 源代码
DES.hpp
// DES.hpp
#include <bitset>
using std::bitset;
class DES
{
public:
DES();
bitset<64> encrypt(const bitset<64>& plain, const bitset<64>& key);
bitset<64> decrypt(const bitset<64>& plain, const bitset<64>& key);
~DES();
private:
bitset<48> subKeys[16];
static const int ip[64]; // 初始置换表
//**生成所用置换表
static const int PC_1[56]; // PC-1置换表
static const int PC_2[48]; // PC-2压缩置换表
// Feistel轮函数所用置换表
static const int E[48]; // 拓展置换表
static const int P[32]; // P置换表
static int S_BOX[8][4][16]; // 8个S-BOX
// initial permutation
bitset<64> IP(const bitset<64>& plain);
// IP逆置换
bitset<64> IP_1(const bitset<64>& bits);
// Feistel 轮函数
bitset<32> f(const bitset<32>& right, const bitset<48>& subKey);
// 生成子**
void generateSubKeys(const bitset<64>& key);
};
DES.cpp
// DES.cpp
#include "DES.hpp"
// 初始置换表
const int DES::ip[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 };
/*---------------------**生成所用置换表---------------------*/
// PC-1置换表
const int DES::PC_1[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, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29,
21, 13, 5, 28, 20, 12, 4};
// PC-2压缩置换表
const int DES::PC_2[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};
/*---------------------Feistel轮函数所用置换表---------------------*/
// 拓展置换表
const int DES::E[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,
20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29,
28, 29, 30, 31, 32, 1};
// P置换表
const int DES::P[32] = {16, 7, 20, 21,
29, 12, 28, 17,
1, 15, 23, 26,
5, 18, 31, 10,
2, 8, 24, 14,
32, 27, 3, 9,
19, 13, 30, 6,
22, 11, 4, 25 };
// 8个S-BOX
int DES::S_BOX[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}
}
};
DES::DES(){}
// 加密
bitset<64> DES::encrypt(const bitset<64>& plain, const bitset<64>& key){
bitset<32> left; // 记录上半部分
bitset<32> right; // 记录下半部分
bitset<32> nextLeft; // 作为16轮迭代的中间临时变量
bitset<64> current; // 记录每一步置换的结果
// 第一步：IP初始置换
current = IP(plain);
// 获取L和R
for(int i = 0; i < 32; i++)
left[i] = current[i + 32];
for(int i = 0; i < 32; i++)
right[i] = current[i];
// 第二步：16轮迭代T
generateSubKeys(key);//生成子**
for(int i = 0; i < 16; i++){
nextLeft = right;
right = left ^ f(right, subKeys[i]);
left = nextLeft;
}
// 第三步：交换置换
for(int i = 0; i < 32; i++)
current[i] = left[i];
for(int i = 0; i < 32; i++)
current[i + 32] = right[i];
// 第四步：IP_1逆置换
return IP_1(current);
}
// 解密
bitset<64> DES::decrypt(const bitset<64>& plain, const bitset<64>& key){
bitset<32> left; // 记录上半部分
bitset<32> right; // 记录下半部分
bitset<32> nextLeft; // 作为16轮迭代的中间临时变量
bitset<64> current; // 记录每一步置换的结果
// 第一步：IP初始置换
current = IP(plain);
// 获取L和R
for(int i = 0; i < 32; i++)
left[i] = current[i + 32];
for(int i = 0; i < 32; i++)
right[i] = current[i];
// 第二步：16轮迭代T
generateSubKeys(key);//生成子**
for(int i = 0; i < 16; i++){
nextLeft = right;
right = left ^ f(right, subKeys[15 - i]); // 子**调度顺序与加密时相反
left = nextLeft;
}
// 第三步：交换置换
for(int i = 0; i < 32; i++)
current[i] = left[i];
for(int i = 0; i < 32; i++)
current[i + 32] = right[i];
// 第四步：IP_1逆置换
return IP_1(current);
}
// initial permutation
bitset<64> DES::IP(const bitset<64>& plain){
bitset<64> M;
for(int i = 0; i < 64; i++)
M[i] = plain[ip[i] - 1];
return M;
}
// IP逆置换
bitset<64> DES::IP_1(const bitset<64>& bits){
bitset<64> cipher;
// 构造ip的逆置换
int ip_1[64];
for(int i = 0; i < 64; i++)
ip_1[ip[i] - 1] = i + 1;
for(int i = 0; i < 64; i++)
cipher[i] = bits[ip_1[i] - 1];
return cipher;
}
// Feistel 轮函数
bitset<32> DES::f(const bitset<32>& R, const bitset<48>& subKey){
bitset<48> current;
bitset<32> output;
// 第一步：E拓展置换 32->48
for(int i = 0; i < 48; i++)
current[i] = R[E[i] - 1];
// 第二步：与子**异或
current = current ^ subKey;
// 第三步：分为8组，经过S-BOX置换 6->4
for(int i = 0; i < 8; i++){
int head = 47 - i * 6; // 每一组的第一位的下标
int row = current[head] * 2 + current[head - 5];
int col = current[head - 1] * 8 + current[head - 2] * 4 + current[head - 3] * 2 + current[head - 4];
bitset<4> result(S_BOX[i][row][col]);
for(int j = 0; j < 4; j++)
output[31 - i * 4 - j] = result[3 - j];
}
// 第四步：P置换
bitset<32> temp = output;
for(int i = 0; i < 32; i++)
output[i] = temp[P[i] - 1];
return output;
}
// 循环左移函数
void leftShift(bitset<28>& bits, int shift){
bitset<28> temp = bits;
for (int i = 0; i < 28; ++i)
bits[i] = temp[(i - shift + 28) % 28];
}
// 生成子**
void DES::generateSubKeys(const bitset<64>& key){
bitset<56> current;
bitset<28> left;
bitset<28> right;
// 第一步：PC-1置换 64->56
for (int i = 0; i < 56; i++)
current[55 - i] = key[64 - PC_1[i]];
// 获取前后28位
for (int i = 0; i < 28; ++i)
left[i] = current[i + 28];
for (int i = 0; i < 28; ++i)
right[i] = current[i];
//第二步：16轮循环左移和压缩置换, 分别获得16个子**
int shiftBits[] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1}; //每次左移的位数
for(int round = 0; round < 16; round++){
// 循环左移
leftShift(left, shiftBits[round]);
leftShift(right, shiftBits[round]);
// 合并
for (int i = 0; i < 28; ++i)
current[i + 28] = left[i];
for (int i = 0; i < 28; ++i)
current[i] = right[i];
// 压缩置换获得48位子**
for(int j = 0; j < 48; j++)
subKeys[round][47 - j] = current[56 - PC_2[j]];
}
}
DES::~DES(){}
main.cpp
// main.cpp
#include <iostream>
#include "DES.hpp"
#include <string>
#include <fstream>
using namespace std;
bitset<64> charsToBitset(const char s[8])
{
bitset<64> bits;
for(int i = 0; i < 8; i++)
for(int j = 0; j < 8; j++)
bits[i * 8 + j] = ((s[7 - i] >> j) & 1);
return bits;
}
char* BitsetToChars(const bitset<64> bits){
char s[8];
bitset<8> c;
for(int i = 0; i < 8; i++){
for(int j = 0; j < 8; j++){
c[j] = bits[i * 8 + j];
}
s[7 - i] = c.to_ulong();
}
return s;
}
int main(){
DES des;
// 对64位数据加密和解密，并将结果输出
string p("Iloveyou");
string k("52013141");
bitset<64> plain = charsToBitset(p.c_str());
bitset<64> key = charsToBitset(p.c_str());
bitset<64> cipher = des.encrypt(plain, key);
cout << "plain: " << plain << "(" << p << ")" << endl << endl;
cout << "cipher: " << cipher << endl << endl;
string s = BitsetToChars(des.decrypt(cipher, key));
cout << "decrypt: " << s << endl << endl;
// 对文件进行加密和解密
cout << "Waiting to encrypt and decrypt the file \'E://sysu.jpg\'..." << endl;
cout << endl << "Encrypting..." << endl;
ifstream in;
ofstream out;
in.open("E://sysu.jpg", ios::binary);
out.open("E://cipher.txt", ios::binary);
bitset<64> file_data;
while(in.read((char*)&file_data, sizeof(file_data))){
bitset<64> cipher = des.encrypt(file_data, key);
out.write((char*)&cipher, sizeof(cipher));
file_data.reset(); // 置0
}
cout << "Finish! You can read the cipher in \'E://cipher.txt\'." << endl;
in.close();
out.close();
cout << endl << "Decrypting..." << endl;
in.open("E://cipher.txt", ios::binary);
out.open("E://sysu_decrypt.jpg", ios::binary);
while(in.read((char*)&file_data, sizeof(file_data)))
{
bitset<64> plain = des.decrypt(file_data, key);
out.write((char*)&plain, sizeof(plain));
file_data.reset(); // 置0
}
cout << "Finish! You can open the file \'E://sysu_decrypt.jpg\' to check." << endl;
in.close();
out.close();
return 0;
}