密码学课设 t1 SPN实现

题目

Description

内容：按照教材例3.1实现SPN加解密函数。
要求：
（1）正确实现算法的加解密过程
（2）快速实现算法

Input
第一行，一个正整数n,表示n组数据。
接下来n行，每行包含两个用空格分开的16进制字符串。第一个字符串长度为8，表示32比特密钥key，第二个字符串长度为4，表示16比特明文。

对1<=k<=6，第k个数据点满足n = 10^k。

对k=7，n = 4*10^6。

TIPS: 需要快速读入

Output
共n行，每行包含两个用空格分开的16进制字符串。第一个字符串表示对应行的明文加密后的密文，第二个字符串表示将密文最后1比特取反，解密后得到的明文。

sample input

1
3a94d63f 26b7

sample output

bcd6 070d

教材

思路

按照spn算法逐步实现，每四位放入一个int中，方便位运算。
使用数组存储代换。

初始代码

#include<cstdio>
using namespace std;
int x[4],key[8];
void readx()
{register int yy=0;register char c=getchar();while(1){if(c>='0'&&c<='9'){x[yy++]=c-'0';c=getchar();}else if(c>='a'&&c<='f'){x[yy++]=c-'a'+10;c=getchar();}else break;}
}
void readkey()
{register int yy=0;register char c=getchar();while(1){if(c>='0'&&c<='9'){key[yy++]=c-'0';c=getchar();}else if(c>='a'&&c<='f'){key[yy++]=c-'a'+10;c=getchar();}else break;}
}
int pais[16]={14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7};
int paiss[16]={14,3,4,8,1,12,10,15,7,13,9,6,11,2,0,5};
int n,chan[4];
int main()
{scanf("%d\n",&n);for(int i=1;i<=n;i++){readkey();readx();//加密 for(int j=0;j<=2;j++){for(int k=0;k<=3;k++)chan[k]=0;for(int k=0;k<=3;k++){x[k]^=key[k+j];x[k]=pais[x[k]];for(int w=3;w>=0;w--){chan[w]+=(x[k]&1)<<(3-k);x[k]>>=1;}}for(int k=0;k<=3;k++)x[k]=chan[k];}for(int k=0;k<=3;k++)x[k]^=key[k+3],x[k]=pais[x[k]];for(int k=4;k<=7;k++)x[k-4]^=key[k];for(int k=0;k<=3;k++)printf("%x",x[k]);putchar(' ');//解密x[3]^=1; for(int k=4;k<=7;k++)x[k-4]^=key[k];for(int k=0;k<=3;k++)x[k]=paiss[x[k]],x[k]^=key[k+3];for(int j=2;j>=0;j--){for(int k=0;k<=3;k++)chan[k]=0;for(int k=0;k<=3;k++){for(int w=3;w>=0;w--){chan[w]+=(x[k]&1)<<(3-k);x[k]>>=1;}	}for(int k=0;k<=3;k++)x[k]=chan[k];for(int k=0;k<=3;k++){x[k]=paiss[x[k]];x[k]^=key[k+j];}}for(int k=0;k<=3;k++)printf("%x",x[k]);putchar('\n');}
}

艰难的卡常

初始代码

最后一个点差不多2s

然后进行了一些卡常和简单的优化，比如说：

常用计数器设为register int；
输出建立新数组直接对应putchar()输出；
使用更加快速的快读（牺牲空间，并且之后无法正常读入char等）；
把一些可以展开的for循环展开，省去计数器++或–花费的时间。

虽然代码变丑了，但好歹是过了。

AC代码

#include<cstdio>
#include<cstring>
using namespace std;
int x[4],key[8];static char buf[100000],*pa=buf,*pd=buf;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
void readx()
{register int yy=0;register char c=(gc);while(1){if(c>='0'&&c<='9'){x[yy++]=c^48;c=(gc);}else if(c>='a'&&c<='f'){x[yy++]=c-'a'+10;c=(gc);}else break;}
}
void readkey()
{register int yy=0;register char c=(gc);while(1){if(c>='0'&&c<='9'){key[yy++]=c^48;c=(gc);}else if(c>='a'&&c<='f'){key[yy++]=c-87;c=(gc);}else break;}
}
int pais[16]={14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7};
int paiss[16]={14,3,4,8,1,12,10,15,7,13,9,6,11,2,0,5};
char output[16]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
int n,chan[4];
int main()
{scanf("%d\n",&n);register int i,j,k,w;for(i=1;i<=n;i++){readkey();readx();//加密 for(j=0;j<=2;j++){memset(chan,0,sizeof(chan));for(k=0;k<=3;k++){x[k]^=key[k+j];x[k]=pais[x[k]];chan[3]+=(x[k]&1)<<(3-k);x[k]>>=1;chan[2]+=(x[k]&1)<<(3-k);x[k]>>=1;chan[1]+=(x[k]&1)<<(3-k);x[k]>>=1;chan[0]+=(x[k]&1)<<(3-k);x[k]>>=1;}x[0]=chan[0];x[1]=chan[1];x[2]=chan[2];x[3]=chan[3];//for(k=0;k<=3;k++)x[k]=chan[k];}for(k=0;k<=3;k++)x[k]^=key[k+3],x[k]=pais[x[k]],x[k]^=key[k+4],putchar(output[x[k]]);putchar(' ');//解密x[3]^=1; for(k=0;k<=3;k++)x[k]^=key[k+4],x[k]=paiss[x[k]],x[k]^=key[k+3];for(j=2;j>=0;j--){memset(chan,0,sizeof(chan));for(k=0;k<=3;k++){chan[3]+=(x[k]&1)<<(3-k);x[k]>>=1;chan[2]+=(x[k]&1)<<(3-k);x[k]>>=1;chan[1]+=(x[k]&1)<<(3-k);x[k]>>=1;chan[0]+=(x[k]&1)<<(3-k);x[k]>>=1;}for(k=0;k<=3;k++){x[k]=paiss[chan[k]];x[k]^=key[k+j];}}//for(k=0;k<=3;k++)putchar(output[x[k]]);putchar(output[x[0]]);putchar(output[x[1]]);putchar(output[x[2]]);putchar(output[x[3]]);putchar('\n');}
}