2021.9 HUSTOJ 密码学课程设计第一题——时间优化思路请直接跳转至【优化方法】

题目简介

值得一提的是，这道题的限时在1000ms…


输入为N个key与plaintext的组合，输出则为相对应的ciphertext与末尾比特取反解密得到的fliped_plaintext；

SPN密码体系

课本样例

问题分析

单就实现SPN加密解密算法已有许多前辈的文章分析和代码分析，在借鉴前辈的实现思路后发现对于下边这种👇
再感受一下第7个样例点的输入数据👇

👆这样的数据数量级以及时间要求，按照传统的思路是无法达到1000ms的真实的，因此在群（da）友（lao）们的帮助下，通过适当的优化通过了OJ。

AC代码

#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>

int EnTable[65536] = {/*65536 int plaintexts in Encryption Process*/};
int DeTable[65536] = {/*65536 int plaintexts in Decryption Process*/};
// PBox and DecrySBox from textbook 3.2 example 3.1
const int DecrySBox[16] = {0xE, 0x3, 0x4, 0x8, 0x1, 0xC, 0xA, 0xF, 0x7, 0xD, 0x9, 0x6, 0xB, 0x2, 0x0, 0x5};
const int EncrySBox[16] = {0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7};
const int PBox[16] = { 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16 };
unsigned int htoi_read(void);			// hex to int Fast Read
void itoh_print(unsigned short resnum);	// int to hex Print
void SPN(void);							// Substitution-Permutation Network

int main() {
	SPN();
	return 0;
}

unsigned int htoi_read(void) { 
	int retint = 0;
	char c = getchar();
	while ((c >= 48 && c <= 57) || (c >= 97 && c <= 102)) {
		if (c >= 48 && c <= 57)retint = (retint << 4) + c - 48;
		else if (c >= 97 && c <= 102)retint = (retint << 4) + c - 87;
		c = getchar();
	}
	return retint; 
}
void itoh_print(unsigned short resnum) {	
	for (int i = 3; i >= 0; i--) {
		int c = (resnum >> (i << 2)) & 0xF;
		if (c >= 0 && c <= 9) putchar(48 + c);
		else if (c >= 10 && c <= 15) putchar(87 + c);
	}
}
void SPN(void) {
	int key, key_32bit, k1, Ntimes, tmp;
	register int plaintext;
	scanf("%d", &Ntimes);
	getchar();
	
	while (Ntimes--) {
		key_32bit = htoi_read();
		plaintext = htoi_read();
		// SPN Encryption begins
		key = key_32bit;
		// Three rounds with PermutationBox
		for (int times = 0; times < 3; ++times) {
			plaintext = EnTable[plaintext ^ ((key & 0xffff0000) >> 16)];
			key = key << 4;	
		}
		// Forth round without PermutationBox
		plaintext = plaintext ^ ((key & 0xffff0000) >> 16);
		plaintext = (plaintext << 4) | EncrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | EncrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | EncrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | EncrySBox[(plaintext & 0xf000) >> 12];
		
		key = key << 4;
		k1 = (key & 0xffff0000) >> 16;
		plaintext = plaintext ^ k1;
		
		itoh_print(plaintext);
		putchar(' ');
		// Encryption done

		// SPN Decryption begins as: last bit flips
		plaintext = plaintext ^ 0x0001;
		k1 = key_32bit;

		tmp = k1 & 0x0000ffff;
		plaintext = plaintext ^ tmp;
		k1 = k1 >> 4;
		plaintext = (plaintext << 4) | DecrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | DecrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | DecrySBox[(plaintext & 0xf000) >> 12];
		plaintext = (plaintext << 4) | DecrySBox[(plaintext & 0xf000) >> 12];

		for (int times = 0; times < 3; ++times) {
			tmp = k1 & 0x0000ffff;
			plaintext = plaintext ^ tmp;
			k1 = k1 >> 4;
			plaintext = DeTable[plaintext & 0x0000ffff];
		}
		plaintext = plaintext ^ (k1 & 0x0000ffff);

		itoh_print(plaintext);
		putchar('\n');
		// Decryption done
	}
}

优化方法

默认未优化的SPN算法下，对于第7个样例点的时间大概为1900ms~2000ms
（1）#pragma GCC optimize(3,"Ofast","inline")
在没有进行其他优化时，开启-O3、-Ofast优化，对效率有一定的提升（大概100~200ms）；

（2）使用快读、快写
由于第7个样例点有4000000行输入数据，因此采用cin/cout、scanf/printf在时间上会显得捉襟见肘，于是采用仅次于文件读写速度的getchar/putchar，完成hex to int的快读函数与int to hex的快写函数，才能够应付大量的数据输入输出（300~500ms）；

（3）乘法运算转换为位运算、字符运算转换为整数运算
例如代码中htoi_read()快读函数中：

unsigned int htoi_read(void) { 
	int retint = 0;
	char c = getchar();
	while ((c >= 48 && c <= 57) || (c >= 97 && c <= 102)) {
		if (c >= 48 && c <= 57)retint = (retint << 4) + c - 48;
		else if (c >= 97 && c <= 102)retint = (retint << 4) + c - 87;
		c = getchar();
	}
	return retint; 
}

retint << 4即是 retint * 16（b << x 相当于 b * 2的x次方）；

retint = (retint << 4) + c - 87;相当于retint = (retint << 4) + c - 'a' + 10;；

这种优化思路的实际效果比较佛系，一定程度上取决于你提交代码时在线OJ的心情（；

（4）加密解密过程对plaintext打表
打表的优化思路可以说是空间换时间的典型了，代码中的int EnTable[65536]与int DnTable[65536]即为在加密过程中与解密过程中的表，可以省去大量的操作（大概300ms）。

由于plaintext的长度限制为16位，因此plaintext总共的可能情况只有2 ** 16 = 65536种，根据这个条件，可以在原算法未涉及key操作的地方，如果仅有plaintext与P盒/S盒的操作，故可以将65536种计算可能转化为空间，再在调用过程中仅有一次数组定位的时间消耗。

plaintext = EnTable[plaintext ^ ((key & 0xffff0000) >> 16)];

对于EnTable，它包括了plaintext与S盒的代换操作（原4次循环）和P盒的置换操作（原32次循环）；

plaintext = DeTable[plaintext & 0x0000ffff];

对于DeTable，它包括了cyphertext与S盒的4次操作（刚刚发现，AC代码中有一部分DecryS盒的操作可以被DeTable替换）；

最后

代码中贴不下的

int EnTable[65536] = {/*65536 int plaintexts in Encryption Process*/};
int DeTable[65536] = {/*65536 int plaintexts in Decryption Process*/};

的下载链接放在这里，提取码为fele

以下是参考博客：
GCC中-O1 -O2 -O3 优化的原理是什么？
SPN实现
C++的速度优化
C++手动开启O2优化（以及-O -O1 -O2 -O3优化的知识点）（竞赛可用）