题目简介

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


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

SPN密码体系

课本样例

问题分析

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

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

AC代码

#pragma GCC optimize(3,"Ofast","inline")#include 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.1const 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 Readvoid itoh_print(unsigned short resnum);	// int to hex Printvoid SPN(void);							// Substitution-Permutation Networkint 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优化的知识点）（竞赛可用）