[DES password writing]
1. Equipment
(1) operating system version : WIN 10
(2) CPU instruction set: x 64
(3) software : Visual Studio 2019
2. process
-
Problem background analysis
DES cipher writing
To write a DES cipher, you must first be familiar with the principle of DES. The basic process is to first divide the plaintext into 64-bit groups, and then input the 64-bit binary code into the cipher. Under the control of the 16 sub-keys generated by the master key, 16 rounds of product transformation are performed, and then inverse permutation is performed to obtain a 64-bit encrypted ciphertext. The flow chart of DES is as follows:
Among them, the DES algorithm plaintext block length is 64bit, and after encryption, 64bit ciphertext is obtained. The input initial seed key is 64bit, and the 8th, 16th, 24th, 32nd, 40th, 48th, 56th, and 64th are parity bits. The key length is 56 bits. The DES encryption process is done in three stages:
- The initial replacement IP is used to rearrange the 64-bit data of the plaintext packet. After initial permutation, a 64-bit input yields two 32-bit outputs.
- There are 16 iterations of the same structure, and each round has permutation and substitution operations. The output of the 16th round of transformation is divided into left and right halves, and the order is exchanged.
- After inverse initial permutation IP-1 (which is the inverse of IP), a 64-bit ciphertext is generated.
According to this idea, write the DES algorithm.
-
Solution
code:
#include <string.h>
#include <stdio.h>
#include <iostream>
#pragma warning(disable:4996)
using namespace std;
/*
* @Author:timerring
* @Date: 2021-11-01 19:17:32
* @LastEditTime: 2021-11-05 20:34:13
* @FilePath:c:\Users\timerring\DES.cpp
*/
class DES {
//Construct DES class
public:
~DES() {} //define destructor
void set_key(const unsigned char*); //key extension
void en_ctransform(const unsigned char*, unsigned char*); //cryptographic transformation
void de_ctransform(const unsigned char*, unsigned char*); //Decryption Transform
private:
bool enckey[16][48];//Store the encrypted subkey
bool deckey[16][48];//Store the decrypted subkey
const static unsigned char IP_Table[64];
//primary replacement
const static unsigned char IPR_Table[64];
//Inverse permutation
const static unsigned char E_Table[48];
//Table E
const static unsigned char P_Table[32];
//permutation selection
const static unsigned char PC1_Table[56];
//permutation option 1
const static unsigned char PC2_Table[48];
//permutation option 2
const static unsigned char LOOP_Table[16];
//Key shift (number of left shifts)
const static unsigned char S_Box[8][4][16];
// S box
};
const unsigned char DES::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
};
// primary replacement
const unsigned char DES::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
};
// inverse initial permutation
const unsigned char DES::E_Table[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
};
// Table E
const unsigned char DES::P_Table[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
};
// permutation selection
const unsigned char DES::PC1_Table[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
};
//permutation option 1
const unsigned char DES::PC2_Table[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
};
//permutation option 2
const unsigned char DES::LOOP_Table[16] = {
1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1
};
// Key shift (number of left shifts)
const unsigned char DES::S_Box[8][4][16] = {
//8 S boxes, each box is 4 rows and 16 columns
// Define S1 Box
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,
// Define the S2 box
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,
// Define S3 Box
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,
// Define S4 Box
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,
// Define S5 Box
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,
// Define S6 Box
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,
// Define S7 Box
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,
// Define S8 Box
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
};
void chaifen(char byte, int a[64], int q) {
int i;
for (i = 0; i < 8; i++) {
a[7 - i + q] = byte & 1;
byte >>= 1;
//Assign the value of byte shifted right by one to byte
}
}
void DES::set_key(unsigned char const* yonghu_key/*64-bit key first address entered by the user*/) {
//key expansion algorithm
int arr[64];
int ary[56];
int i, curry = 0;
for (i = 0; i < 8; i++) {
chaifen(yonghu_key[i], arr, curry);
curry = curry + 8;
}
for (i = 0; i < 56; i++) {
ary[i] = arr[PC1_Table[i] - 1];
}
for (i = 0; i < 16; i++) {
if (i == 0 || i == 1 || i == 8 || i == 15) {
int j, temp0, temp1;
temp0 = ary[0]; temp1 = ary[28];
for (j = 0; j < 28; j++) {
ary[j] = ary[j + 1];
ary[j + 28] = ary[j + 29];
}
ary[27] = temp0; ary[55] = temp1;
}
else {
int j, temp0, temp1;
temp0 = ary[0]; temp1 = ary[28];
for (j = 0; j < 28; j++) {
ary[j] = ary[j + 1];
ary[j + 28] = ary[j + 29];
}
ary[27] = temp0; ary[55] = temp1;
temp0 = ary[0]; temp1 = ary[28];
for (j = 0; j < 28; j++) {
ary[j] = ary[j + 1];
ary[j + 28] = ary[j + 29];
}
ary[27] = temp0; ary[55] = temp1;
}
int j;
for (j = 0; j < 48; j++)
enckey[i][j] = (bool)ary[PC2_Table[i] - 1];
}
}
void DES::en_ctransform(const unsigned char* In /*The first address of the 64-bit data to be decrypted*/, unsigned char* Out) {
//Encryption Transformation Algorithm
int arr[64];
int ary[64];
int i, j, curry = 0;
for (i = 0; i < 8; i++) {
chaifen(In[i], arr, curry);
curry = curry + 8;
}
for (i = 0; i < 64; i++) {
ary[i] = arr[IP_Table[i] - 1];
}
int larr[32];
int rarr[32];
for (i = 0; i < 32; i++) {
larr[i] = ary[i];
rarr[i] = ary[i + 32];
}
for (i = 0; i < 16; i++) {
int temp[32];
for (j = 0; j < 32; j++) {
temp[j] = larr[j];
larr[j] = rarr[j];
}
int i0, j0, q;
int e[48];
for (i0 = 0; i0 < 48; i0++)
e[i0] = rarr[E_Table[i0] - 1];
int w;
for (w = 0; w < 48; w++) {
e[w] = (e[w] + enckey[i][w]) % 2;
}
for (j0 = 0; j0 < 8; j0++) {
int hang = e[j0 * 6] * 2 + e[j0 * 6 + 5];
int lie = e[j0 * 6 + 1] * 8 + e[j0 * 6 + 2] * 4 + e[j0 * 6 + 3] * 2 + e[j0 * 6 + 4];
int num = S_Box[j0][hang][lie];
for (q = 0; q < 4; q++) {
rarr[j0 * 4 + 3 - q] = num & 1;
num >>= 1;
}
}
int temp0[32];
for (j = 0; j < 32; j++) {
temp0[j] = rarr[j];
}
for (j = 0; j < 32; j++) {
rarr[j] = temp0[P_Table[j] - 1];
}
for (j = 0; j < 32; j++) {
rarr[j] = ((rarr[j] + temp[j]) % 2);
}
}
int temp[32];
for (i = 0; i < 32; i++) {
temp[i] = larr[i];
larr[i] = rarr[i];
rarr[i] = temp[i];
}
for (i = 0; i < 32; i++) {
ary[i] = larr[i];
ary[i + 32] = rarr[i];
}
for (i = 0; i < 64; i++) {
arr[i] = ary[IPR_Table[i] - 1];
}
for (i = 0; i < 8; i++) {
Out[i] = arr[i * 8] * 128 + arr[i * 8 + 1] * 64 + arr[i * 8 + 2] * 32 + arr[i * 8 + 3] * 16 + arr[i * 8 + 4] * 8 + arr[i * 8 + 5] * 4 + arr[i * 8 + 6] * 2 + arr[i * 8 + 7];
}
}
void DES::de_ctransform(const unsigned char* In /*The first address of the 64-bit data to be encrypted*/, unsigned char* Out) {
//Decryption Transformation Algorithm
int arr[64];
int ary[64];
int i, j, curry = 0;
for (i = 0; i < 8; i++) {
chaifen(In[i], arr, curry);
curry += 8;
}
for (i = 0; i < 64; i++) {
ary[i] = arr[IP_Table[i] - 1];
}
int larr[32];
int rarr[32];
for (i = 0; i < 32; i++) {
larr[i] = ary[i];
rarr[i] = ary[i + 32];
}
for (i = 0; i < 16; i++) {
int temp[32];
for (j = 0; j < 32; j++) {
temp[j] = larr[j];
larr[j] = rarr[j];
}
int i0, j0, q;
int e[48];
for (i0 = 0; i0 < 48; i0++)
e[i0] = rarr[E_Table[i0] - 1];
int w;
for (w = 0; w < 48; w++) {
e[w] = (e[w] + enckey[15 - i][w]) % 2;
}
for (j0 = 0; j0 < 8; j0++) {
int hang = e[j0 * 6] * 2 + e[j0 * 6 + 5];
int lie = e[j0 * 6 + 1] * 8 + e[j0 * 6 + 2] * 4 + e[j0 * 6 + 3] * 2 + e[j0 * 6 + 4];
int num = S_Box[j0][hang][lie];
for (q = 0; q < 4; q++) {
rarr[j0 * 4 + 3 - q] = num & 1;
num >>= 1;
}
}
int temp0[32];
for (j = 0; j < 32; j++) {
temp0[j] = rarr[j];
}
for (j = 0; j < 32; j++) {
rarr[j] = temp0[P_Table[j] - 1];
}
for (j = 0; j < 32; j++) {
rarr[j] = ((rarr[j] + temp[j]) % 2);
}
}
int temp[32];
for (i = 0; i < 32; i++) {
temp[i] = larr[i];
larr[i] = rarr[i];
rarr[i] = temp[i];
}
for (i = 0; i < 32; i++) {
ary[i] = larr[i];
ary[i + 32] = rarr[i];
}
for (i = 0; i < 64; i++) {
arr[i] = ary[IPR_Table[i] - 1];
}
for (i = 0; i < 8; i++) {
Out[i] = arr[i * 8] * 128 + arr[i * 8 + 1] * 64 + arr[i * 8 + 2] * 32 + arr[i * 8 + 3] * 16 + arr[i * 8 + 4] * 8 + arr[i * 8 + 5] * 4 + arr[i * 8 + 6] * 2 + arr[i * 8 + 7];
}
}
int main() {
unsigned int seq[8];
unsigned char key[9]; //key
unsigned char plain[9]; //plaintext
unsigned char cipher[9];//ciphertext
char shuruzi[17]; //characters entered on the keyboard
char choice = ' ';
DES mydes; //kind
int i, j;
int s;
while (true) {
cout << "You are welcome to use the DES machine in SDU\n" << endl;
do {
cout << "Please enter the corresponding operation number:\n1.Encrypt\t2.Decrypt\t3.Quit" << endl;
scanf("\n%c", &choice);
} while (choice != '1' && choice != '2' && choice != '3');
switch (choice) {
case '1':
printf("Please enter the secret key (length = 16):\n");
scanf("%s", shuruzi);
sscanf(shuruzi, "%2x%2x%2x%2x%2x%2x%2x%2x", &seq[0], &seq[1], &seq[2], &seq[3], &seq[4], &seq[5], &seq[6], &seq[7]);
for (i = 0; i < 8; i++)
key[i] = seq[i];
//Store the entered characters in the key array in sequence
printf("\n");
printf("Please enter plaintext (length = 16):\n");
scanf("%s", shuruzi);
printf("\n");
sscanf(shuruzi, "%2x%2x%2x%2x%2x%2x%2x%2x", &seq[0], &seq[1], &seq[2], &seq[3], &seq[4], &seq[5], &seq[6], &seq[7]);
for (j = 0; j < 8; j++)
plain[j] = seq[j];
//Store the input characters in the plaintext array in sequence
mydes.set_key(key);
mydes.en_ctransform(plain, cipher);
//Call encryption algorithm function to complete encryption
for (s = 0; s < 8; s++)
seq[s] = cipher[s];
printf("ciphertext:\n%02x%02x%02x%02x%02x%02x%02x%02x\n", seq[0], seq[1], seq[2], seq[3], seq[4], seq[5], seq[6], seq[7]);
//Store the characters in the ciphertext array into the buffer array and output
printf("\n");
break;
case '2':
printf("Please enter the secret key (length = 16):\n");
scanf("%s", shuruzi);
sscanf(shuruzi, "%2x%2x%2x%2x%2x%2x%2x%2x", &seq[0], &seq[1], &seq[2], &seq[3], &seq[4], &seq[5], &seq[6], &seq[7]);
for (i = 0; i < 8; i++)
key[i] = seq[i];
//Store the input characters in the plaintext array in sequence
printf("\n");
printf("Please enter the ciphertext (length = 16):\n");
scanf("%s", shuruzi);
printf("\n");
sscanf(shuruzi, "%2x%2x%2x%2x%2x%2x%2x%2x", &seq[0], &seq[1], &seq[2], &seq[3], &seq[4], &seq[5], &seq[6], &seq[7]);
for (j = 0; j < 8; j++)
cipher[j] = seq[j];
//Store the input characters in sequence in the ciphertext array
mydes.set_key(key);
mydes.de_ctransform(cipher, plain);
//Call the decryption algorithm function to complete the decryption
for (s = 0; s < 8; s++)
seq[s] = plain[s];
printf("plaintext:\n%02x%02x%02x%02x%02x%02x%02x%02x\n", seq[0], seq[1], seq[2], seq[3], seq[4], seq[5], seq[6], seq[7]);
printf("\n");
break;
case '3':
return 0;
break;
}
}
}
Test sample:
It is assumed here that the test key is 1234567891234561, and the test plaintext is set to 7894561237894569. Encryption is performed to obtain the ciphertext, and then the ciphertext is decrypted. After verification, the plaintext can be obtained, and the DES program runs successfully.
3. summary and harvest
At the beginning of programming, I didn’t know where to start. After carefully reading the relevant principles of information security, I gradually got an idea and wrote the code according to the subdivision process of the entire algorithm. First replace the IP initially, define the S box, etc., and then write 16 rounds of iterations of the same structure. There are permutation and substitution operations in each round. The output of the 16th round of transformation is divided into left and right halves, and the order is exchanged. After the final reverse initial permutation IP-1 (the inverse of IP), a 64-bit ciphertext is generated.
When defining S_Box, at first I defined each box separately, and defined each S box as a 2-dimensional matrix, but this definition is not concise enough. When the 48-bit data is divided into groups of 6 bits, a total of It is 8 groups, and input into 8 boxes S1, S2, S3, S4, S5, S6, S7, S8 respectively, each box generates 4-bit output, and the output of each S box is spliced into 32-bit process , the call is error-prone. By consulting the information, I found a perfect solution to this problem. The S box is defined as a 3-dimensional array, and all elements in the S box can be added directly. Due to the characteristics of C++, it can be automatically classified according to the characteristics of the array. It is convenient for subsequent calls.
If you are a beginner in information security, there may be mistakes. Please feel free to enlighten me.
Due to the text, the related algorithm implementation projects in this article cannot be displayed. The resources have been uploaded, and you can click the link below to download by yourself.