DES算法的C语言从头实现

DES算法的C语言详解

我们后期再补充DES算法的逻辑，我先把C语言代码放上面，后期打算做个视频讲解一下从逻辑到代码，因为我们要实现在HLS部署，所以代码要非常原始，包括数组的设定和操作，所以总共600多行。

加密部分

首先定义一下我们程序中需要存储数据的数组，并解释他们的含义。

FILE* out;文件指针
int left[17][32], right[17][32];//一共16轮置换每一轮存储一下，第一轮0是初始，不动，第一次置换结果索引为1
int IPtext[64];//初始置换的结果
int EXPtext[48];
int XORtext[48];
int X[8][6];//S盒中48选32bit，这48bit被分成8*6=48
int X2[32];
int R[32];
int key56bit[56];
int key48bit[17][48];
int CIPHER[64];
int encrypted[64];

先来讲解C语言代码的含义。

首先要从文件之中读取明文！

void convert_char_to_bit(long int n)
{
    FILE* inp = fopen("input.txt", "rb");//打开文件,将字符按位转换为二进制表示然后写入bits文件
    out = fopen("bits.txt", "wb+");
    char ch;
    int i = n * 8;//字符的数量是i，因为在后面主函数中故意把字符长度/8了，所以这里乘回来

    while(i)//也就是i=0就不执行了
    {
        ch = fgetc(inp);//一次获取一个字符，并且返回它的ASCII码，也就是ch为ASCII码
        if(ch == -1)
        {
            break;
        }
        i--;
        convert_to_binary(ch);//注意ch应该是输入，将字符的ASCII码转化为二进制0101的形式并以0101字符写入文件
    }
    fclose(out);
    fclose(inp);
}

其中我们看到最重要的部分就是将ASCII码转换为二进制码，我们用了convert_to_binary函数。下面生命这个函数。

void convert_to_binary(int n)//因为我们传入的是ASCII码
{
	int k, m;
	for(int i = 7; i >= 0; i--)
	{
		m = i << i;//判断i位是不是1还是0就要先找一个掩码
		k = n & m;//k就是本位1或者0
		if(k == 0)
		{
			fprint(out, "0");//把字符串0写进去
		}
		else
		{
			fprint(out, "1");//写入到了bits.txt，下次该从这个文件中读取
		}
	}
}

显然现在都换成bit形式了，我们该开始加密了！

因为我们知道，在DES算法中，每次只能处理64位的数据块。所以我们要把所有的bit分成64位的数据块，分块加密。

void encrypt_n_blocks(long int n)//表示要处理多少个64位的数据块
{
    FILE* in = fopen("bits.txt", "rb");//上面字符串被转换成bits了，现在读取bits进行加解密操作
    long int plain[n * 64];//意味着可以存储n个64位的数据块
    int i = -1;//用于迭代plain数据的索引
    char ch;

    while((ch = fgetc(in)) != EOF)
    {
        ch = getc(in);//每次读取一个字符病返回ASCII值
        plain[++i] = ch - 48;//'0'变成整形0，'1'变为整形1，存入plain也就是明文中。++i也就是读取一个字符就加1，第一个字符正好是索引0
    }
    for(int i = 0; i < n; i++)//迭代n次，对每个64位块进行加密
    {
        encryption(plain + 64 * i);//因为传参要求是数组首地址，所以只需要传入每个64位块的首地址即可！
    }
    fclose(in);
}

这里我们看到了函数的套用，也就是用for循环，但是每次都要对64位的数据块进行加密，这个套用其实非常消耗资源。

那么这里的encryption加密函数显然就是针对64位的，这是重要的函数。

//先进行初始置换，然后二分，进入16轮加密（需要计算16个key），然后左右交换，再进行最后的置换
void encryption(long int plain[])//整体加密过程，先初始置换，再左右二分，进入16轮加密，然后再左右交换，再进行最后置换
{
    out = fopen("cipher.txt", "ab+");
    for(int i = 0; i < 64; i++)//也就说明plain也就是是64位
    {
        initial_permutation(i, plain[i]);//结果存入IPtext中了
    }

    for(int i = 0; i < 32; i++)
    {
        left[0][i] = IPtext[i];//也就是左边第0轮。把初始置换的结果分成左右两边
    }

    for(int i = 32; i < 64; i++)
    {
        right[0][i - 32] = IPtext[i];
    }

    for(int k = 1; k < 17; k++)//从第一轮到第16轮，开始。
    {
        round_cipher(k, 0);//也就是加密模式,带入每一轮加密函数。
        for(int i = 0; i < 32; i++)
        {
            left[k][i] = right[k-1][i];//这个很明显，左边部分就是原来的右边上一轮的部分，这是原理之一。
        }

    }
    
    for(int i = 0; i < 64; i++)
    {
        if(i < 32)
        {
            CIPHER[i] = right[16][i];
        }
        else 
        {
            CIPHER[i] = left[16][i - 32];//因为16轮迭代之后还要变换左右32bit!
        }
        final_permutation(i, CIPHER[i]);//变换完左右32bit之后再进行最后的置换
    }

    for(int i = 0; i < 64; i++)
    {
        fprintf(out, "%d", encrypted[i]);//输出最终置换过后的结果,写入out也就是cipher.txt文件中！注意encrypted数组中虽然存的是字符的ASCII码
    }
    fclose(out);
}

注意，我们得到16轮加密的结果之后，要对最后左右两边的结果进行置换，也就是RIGHT的部分到了前32个位置。然后进行最后的final_permutation，这里用一个64位的for循环即可实现！然后结果输出到了cipher.txt文件中，注意，是bit的0110的形式。

注意：这里两个部分还没有给出，第一个是RIGHT数组部分，也就是右半边的16轮加密的结构我们都不知道。另一个是encrypted数组是什么？

给出解答：

1.encrypted数组是final_permutation的结果，先存在数组里面，再由数组写入文件。这里显然有些冗余了。这个步骤后期我们改正的时候一定要去掉它。

我们给出final_permutation函数

void final_permutation(int pos, int text)//传入参数为索引和索引对应的元素
{
	int i;
	for(i = 0; i < 64; i++)
	{
		if(inverse_P[i] == pos + 1)//因为pos + 1才是真正的位置，而在置换表中的数就代表真正的位置
		{
			break;
		}
	}
	encrypted[i] = text;//一共要完成64次置换
}

2.下面我们给出RIGHT数组是如何产生的，也就是16轮加密中，每一轮的右半部分。

我们把它叫做每一轮的加密函数round_cipher

void round_cipher(int Round, int mode)//mode代表是加密还是解密过程，0表示加密，1表示解密
{
	for(int i = 0; i < 32; i++)
	{
		expansion_function(i, right[Round - 1][i]);//要得到本轮，上一轮的32位要先进行扩展，扩成48位，方法很简单，48位就是从32位中按照扩展表选48下，存储到EXPtext中。
	}
	for(int i = 0; i < 48; i++)
	{
		if(mode == 0)
		{
			XORtext[i] = XOR(EXPtext[i], key48bit[Round][i]);//我们要对扩展好的48位，用每一轮的key进行异或运算，结果存储到XORtext中了。
		}
		else
		{
			XORtext[i] = XOR(EXPtext[i], key48bit[17-Round][i]);//解密模式与秘钥异或的时候秘钥出场顺序相反。
		}
	}
	
	Sbox(XORtext);//送进S盒中，进行48位选32位的运算，最后仍然得出32位，结果存储在X2中。
	for(int i = 0; i < 32; i++)
	{
		PBox(i, X2[i]);把X2中的结果进行P盒32-32位置换，结果存在R中
	}
	for(int i = 0; i < 32; i++)
	{
		right[Round][i] = XOR(left[Round-1][i], R[i])//最后用左边部分上一轮结果，与，刚才得到的，右半部分上一轮数经过一大堆置换得到的结果，进行异或。
	}
}

其中，涉及到了expansion_function,XOR,Sbox,Pbox等函数，expansion就是扩展到48位的函数，XOR是因为key是48位，所以刚才扩展到48位之后，和key做异或。然后Sbox从48位中选出32位，再经过Pbox32位选32位，最后就得到了32位。

先给出expansion_function函数

void expansion_function(int pos, int text)//把32位中每一位的索引和值传入。
{
	for(int i = 0; i < 48; i++)
	{//E[]是转换表，6*8的，其中每个值都<32因为都是从32位的块里面取数，索引不能超过32，所以就会出现重复。
		if(E[i] == pos + 1);//如果置换表中某个值对应上了我们的索引+1（也就是数在32位中的位置）
		{
			EXPtext[i] = text;//就把它选出来作为48位的其中一位。为什么不用break?因为E[i]不同i可能出现重复的值，此时就是从32位块中重复选出一个值了。所以单单找到一次不能直接break。
		}
	}
}

下面我们再给出XOR函数

int XOR(int a, int b)
{
	return (a^b);
}

下面我们给出Sbox函数

int Sbox(int XORtext[])//传参传入48bit函数
{
	int k = 0;
	for(int i = 0; i < 8; i++)//因为我们要将48位分成8组，每组6个bit，这样每组进行6选4，8组就是8*4=32位了
	{
		for(int j = 0; j < 6; j++)
		{
			X[i][j] = XORtext[k++];//先进行赋值
		}
	}
	int value;
	for(int i = 0; i < 8; i++)
	{
		value = F(1);//这里是把8组X[i]每个6bits都送进去以后，随着i取不同值，F1会对不同的8bit对应到不同的盒子，取出小于16的值
		ToBits(value);把小于16的值转为4bits。这样8个下来就形成了32位值，存入X2中。
	}
}

下面我们给出Pbox函数，也就是一个简单的32-32位置换函数

void Pbox(int pos, int text)//输入索引和值
{
	int i;
	for(i = 0; i < 32; i++)
	{
		if(P[i] == pos + 1)
		{
			break;
		}
	}
	R[i] = text;//结果存到R[i]中。
}

刚才在Sbox中，我们发现了F函数和ToBits函数，其中F函数负责根据传入的第几个8bit来选出不同的小于16的值，代码如下：

int F(int i)//i表示第几个6bit,一共8个
{
	int r, c, b[6];//b[6]存放该6bits.
	for(int j = 0; j < 6; j++)
	{
		b[j] = X[i][j];//第i个6bit
	}
	r = b[0] * 2 + b[5];//我们要把这6bit收尾两位用于确定行，最多4行
	c = 8 * b[1] + 4 * b[2] + 2 * b[3] + b[4];//中间四位确定列，一共16列。
	
	if(i == 0)
	{
		return S1[r][c];//因为一共8个盒子，对应传入不同的6bits
	}
	else if(i == 1)
	{
		return S2[r][c];
	}
	else if(i == 2)
	{
		return S3[r][c];
	}
	else if(i == 3)
	{
		return S4[r][c];
	}
	else if(i == 4)
	{
		return S5[r][c];
	}
	else if(i == 5)
	{
		return S6[r][c];
	}
	else if(i == 6)
	{
		return S7[r][c];
	}
	else if(i == 7)
	{
		return S8[r][c];
	}
}

下面就是简单的ToBits函数负责将小于16的数转换为4位二进制。

int ToBits(int value)//将value每32位转换成整形bit存储在x2中，value是48位经过S盒转换出来的32位
{
	int k, j, m;//显然要用掩码
	static int i;//整个程序执行周期都存在该变量。
	if(i % 32 == 0)//限制只处理32位，因为到32就变成0了，索引就是0-31.
	{
		i = 0;
	}
	for(j = 3; j >= 0; j--)//表示当前处理的位数
	{
		m = 1 << j;//首先是4位，最后到1位。从8到1
		k = value & m;//检查value中当前位是否为1，因为value是4位，所以不用考虑抹掉高位，如果位数多才用抹掉高位。
		if(k == 0)
		{
			X2[3 - j + i] = '0' - 48;//也就是当value中当前位是0时，就将X2中对应位置字符设置为0
		}
		else
		{
			X2[3- j + i] = '1' - 48;//否则设置为1
		}
	}
	i = i + 4;//4位4位的移动，比如i=0时，j从3开始，X2[0], X2[1],,,X2[3]，正好4位，i+4给F函数的下一个结果使用。
}

最后处理加密的结果！

注意，结果在上面我们提到了，经过最后的final_permutation之后，结果存储在encrypted[i]数组中。所以只需要将数组中的二进制数转为char即可。

void bit_to_char()
{
	out = fopen("result.txt", "ab+");
	for(int i = 0; i < 64; i = i + 8)//因为加密都是每64位做一次。
	{
		convert_to_bits(&encrypted[i]);//经过最终置换的结果，也就是64bit，8位8位转换成字符写入结果文件，每次都取出8位，这个取法很巧妙
	}
	fclose(out);//调用convert_to_bits之后会写入这个固定文件指针也就是results.txt
}

显然这里我们有疑惑，我们对encrypted数组分割成8位8位的，并把每8位的子数组传入convert_to_bits函数，下面给出convert_to_bits函数。

void convert_to_bits(int ch[])//传入上面所述的8位二进制数
{
	int value = 0;
	for(int i = 7; i >= 0; i--)
	{
		value += (int)pow(2, i) * ch[7 - i];//也就是把这个数组二进制数算成十进制
	}
	fprintf(out, "%c", value);将算出来的十进制看做ASCII码转换为字符，将字符写入out文件指针也就是result.txt文件。
}

这就是整个加密的过程！

解密部分补充

首先是我们要把所有的bit分成64位的数据块，和上面加密初始阶段做的事情相同

void decrypt_n_blocks(long int n)
{
	FILE* in = fopen("cipher.txt", "rb");//也就是把加密好的bit所有位，分成64位一块。
	long int plain[n * 64];
	int i = -1;
	char ch;
	
	while((ch = fgetc(in)) != EOF)
	{
		//从cipher.txt中读取字符的ASCII码存入明文数组plain，也就是1,0等的ASCII码
		plain[++i] = ch - 48;//因为plain是整形数组，所以修改格式为整形。
	}
	for(int i = 0; i < n; i++)
	{
		decryption(plain + i * 64)//传入每个要解密块的位置，每次的块生成的结果会先在encrypted数组中，然后此函数使其也写入decrypted.txt文件中了
		//注意encrypted数组中也是每个位置存放的0101
		bit_to_char();//调用convert_to_bits转换成char之后会写入bit_to_char()中的固定文件指针也就是results.txt文件中。
	}
	fclose(in);
}

解密的函数大多数和加密相同，只有个别函数有改动，比如，整体加密过程是encryption函数，这里我们修改为decryption函数，

void decryption(long int plain[])
{
    out = fopen("decrypted.txt", "ab+");
    for (int i = 0; i < 64; i++) {
        initial_permutation(i, plain[i]);
    }
 
    for (int i = 0; i < 32; i++) {
        left[0][i] = IPtext[i];
    }
 
    for (int i = 32; i < 64; i++) {
        right[0][i - 32] = IPtext[i];
    }
 
    for (int k = 1; k < 17; k++)
    {
        round_cipher(k, 1);//也就是这里模式选择1，对应的是函数round_cipher中的mode=1,//解密模式与秘钥异或的时候秘钥出场顺序相反。
 
        for (int i = 0; i < 32; i++) {
            left[k][i] = right[k - 1][i];
        }
    }
 
    for (int i = 0; i < 64; i++)
    {
        if (i < 32) {
            CIPHER[i] = right[16][i];
        } else {
            CIPHER[i] = left[16][i - 32];
        }
        final_permutation(i, CIPHER[i]);
    }
 
    for (int i = 0; i < 64; i++) {
        fprintf(out, "%d", encrypted[i]);//将encrypted数组写入解密后的结果文件decrypted.txt中
    }
 
    fclose(out);
}//解密与加密几乎完全相同！只有在轮密钥加的时候，密钥登场的顺序相反！非常容易理解！

秘钥生成

首先我们给出密钥生成全流程函数

void create16keys()
{
	FILE * pt = fopen("key.txt", "rb");
	unsigned int key[64];
	int i = 0, ch;
	while(!feof(pt))
	{
		ch = fgetc(pt);//通常可以和getc互换使用，
		key[i++] = ch - 48;//将字符0转换为0，1转换为1，也就是从文件中读取了key。
	}
	key64to48(key);
	fclose(pt);
}

显然这里面先读取了64位秘钥，首先我们要进行64到56位转换，函数如下：（此函数在下个函数被调用）

void key64to56(int pos, int text)//对于64位密钥，先进行选56位
{
    int i;
    for(int i = 0; i < 56; i++)
    {
        if(PC_1[i] == pos + 1)
        {
            break;
        }
    }
    key56bit[i] = text;//结果写入key56bit数组
}

然后我们用64转48位函数去操作秘钥，显然下面我们给出key64to48函数

void key64to48(unsigned int key[])
{
	int k, backup[17][2];//存储中间结果
	int CD[17][56];//因为生成秘钥也经过了16轮移位。
	int C[17][28], D[17][28];//左右两个部分
	
  for(int i = 0; i < 64; i++)
  {
    key64to56(i, key[i]);//传入索引和值进行置换。结果存入key56bits
  }
  
	for(int i = 0; i < 56; i++)
	{
		if(i < 28)
		{
			C[0][i] = key56bit[i];
		}
		else
		{
			D[0][i-28] = key56bit[i];//一分为二！当然，首先秘钥经过了64选56！
		}
	}
	
	for(int x = 1; x < 17; x++)//因为初始C[0]和D[0]没有改变，先进行左移循环变成C[1]和D[1]之后才能置换生成48位k1。
	{
		int shift = shifts[x-1];//shifts是左移位数表，表示每一轮左移的位数。
		
		for(int i = 0; i < shift; i++)
		{
			backup[x - 1][i] = C[x - 1][i];//因为要左移，比如左移1位，那么就把因为左移消失的C[0]存起来
		}
		for(int i = 0; i < (28 - shift); i++)//一共28位，左移1位就是左边消失1位，然后剩下的28-1位整体左移
		{
    	C[x][i] = C[x-1][i + shift];//也就是上一轮的结果把每一个索引都加1就相当于左移了
    	//比如就左移1位，那么现在的0-26位就是原来的1-27位，而原来的第0位被移到最右端去了。
		}
		k = 0;
		for(int i = 28 - shift; i < 28; i++)//比如左移1位也就是i = 27，也就是找到被隐藏的位现在的位置
		{
			C[x][i] = backup[x-1][k++];//把存起来在backup中的数拿出来。
		}
		
		//对于右边也是同理
		for(int i = 0; i < shift; i++)
    {
        backup[x - 1][i] = D[x - 1][i];
    }
    for(int i = 0; i < (28 - shift); i++)
    {
        D[x][i] = D[x - 1][i + shift];
    }
    k = 0;
    for(int i = 28 - shift; i < 28; i++)
    {
        D[x][i] = backup[x - 1][k++];
    }//也就是先存起来移走的部分，再索引位移，最后把移走的部分赋值到最后。
    
    //合并左右
    for(int j = 0; j < 17; j++)
    {
    	for(int i = 0; i < 28; i++)
    	{
    		CD[j][i] = C[j][i];
    	}
    	for(int i = 28; i = 56; i++)
    	{
    		CD[j][i] = D[j][i - 28];//这里就非常易懂了。
    	}
    }
    
    //进行56-48bit转换。
    for(int j = 1; j < 17; j++)
    {
    	for(int i = 0; i < 56; i++)
    	{
    		key56to48(j, i, CD[j][i]);//从第一轮左移开始，每左移一次都把结果合并之后转换成48位，也就是生成K1，结果存储在k48bits中
    	}
    }
	}
}

显然我们需要知道最后出现的函数key56to48这样就可以知道是如何写进k48bits中的了。

函数如下

void key56to48(int round, int pos, int text)//秘钥选择每一轮最后都会有56到48的置换，所以要做16次置换
{
	int i;
	for(i = 0; i < 48; i++)
	{
		if(PC_2[i] == pos + 1)//一共两个表，第一个用PC_1作64到56位的置换，这个PC_2做56到48位的置换
		{
			break;
		}
	}
	key48bit[round][i] = text;
}

最后也就得出了16轮48位秘钥的值。

下面我们只需要写主函数和相关函数即可！

主函数部分

首先是文件大小函数（我们后期去掉文件操作就可以把它去掉了）

long int find_file_size()
{
    FILE* inp = fopen("input.txt", "rb");
    long int size;

    if(fseek(inp, 0L, SEEK_END))//0L 表示将文件指针偏移0字节，也就是不移动，仅用于定位文件末尾。
    //fseek 是用来在文件中移动文件指针的函数。在这里，它被用来将文件指针移动到文件的末尾，以便获取文件的大小。
    //SEEK_END表示相对于文件末尾进行偏移。如果 fseek 执行成功，它将返回0，跳转到else，否则返回非零值
    {
        perror("fseek() failed!");
    }
    else 
    {
        size = ftell(inp);//ftell 函数来获取文件指针的当前位置，也就是文件的大小。ftell 返回一个 long int 类型的值，表示文件指针的当前位置。
    }
    fclose(inp);
    return size;//size will contain number of chars in the input file.
}

主函数部分

int main()
{
    // destroy contents of these files (from previous runs, if any)
    out = fopen("result.txt", "wb+");
    fclose(out);
 
    out = fopen("decrypted.txt", "wb+");
    fclose(out);
 
    out = fopen("cipher.txt", "wb+");
    fclose(out);
 
    create16keys();
 
    long int n = find_file_size() / 8;
    convert_char_to_bit(n);
 
    encrypt_n_blocks(n);
    decrypt_n_blocks(n);
 
    return 0;
}