spn加密及解密.cpp

SPN加密解密

/*程序：实现SPN的加密解密以及通过对SPN的大量随机激励计算随机变量G的偏差。*/
/*在SPN中，理论上要用到m×N个S盒，为方便起见，这些S盒都基于同样的置换*/
#include<stdio.h>
#include<math.h>
#include<time.h>
#include<string.h>
#include<stdlib.h>
#define l 4//S盒长度
#define m 4//每轮加密的S盒个数
#define size 16//
#define N 4//N+1是加密轮数
#define T 8000//对于线性密码分析，需有T对明－密文，这里利用随机函数生成
int pis[size],pip[size];//S盒以及P盒
int K[N+1][size];//密钥
int x[size],y[size];//二进制表示的明－密文

int G;//教材P71的随机变量
int count;//计数器，对SPN做足够多次的随机激励，每当G＝0时加1
double prG;//在大量的随机激励中，G＝0出现的频率
double e;//e=prG-0.5是随机变量G的偏差

void Generate_Key()
/*随机生成一个01序列，然后由该序列生成SPN中各轮子密钥，
因为加密轮数是N+1，故需要N+1个子密钥*/
{
	int i,j,temp[32];
	srand((unsigned)time(NULL));
	for(i=0;i<32;i++) temp[i]=rand()%2;
	for(i=0;i<N+1;i++){//按照教材P63的方法选取轮密钥
		for(j=0;j<16;j++) K[i][j]=temp[i*m+j];
	}
}

void Key()//教材P63的密钥
{
	int i,j,temp[32]={0,0,1,1, 1,0,1,0, 1,0,0,1, 0,1,0,0, 1,1,0,1, 0,1,1,0, 0,0,1,1, 1,1,1,1};
	for(i=0;i<N+1;i++){
		for(j=0;j<16;j++) K[i][j]=temp[i*m+j];
	}
}

void Build_S_Box()//随机生成的S盒
/*因为S盒长度为4，其输出是0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F的一个排列，
共有16!种不同的排列，这里用随机函数生成S盒输出的排列*/
{
	int i,j,flag[size];
	for(i=0;i<size;i++) flag[i]=0;
	srand((unsigned)time(NULL));
	for(i=0;i<size;i++){
		j=rand()%size;
		while(flag[j])
			j=(j+1)%size;
		pis[i]=j; 
		flag[j]=1;
	}
}

void pi_s()//教材P63的S盒
{
	int i,temp[16]={14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7};
	for(i=0;i<16;i++) pis[i]=temp[i];
}

void Build_P_Box()//随机生成的P盒
/*因为P盒长度为4，其输出是1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16的
一个排列，共有16!种不同的排列，这里用随机函数生成P盒输出的排列*/
{
	int i,j,flag[size];
	for(i=0;i<size;i++) flag[i]=0;
	srand((unsigned)time(NULL));
	for(i=0;i<size;i++){
		j=rand()%16;
		while(flag[j])
			j=(j+1)%16; 
		pip[i]=j;
		flag[j]=1;
	}
}

void pi_p()//教材P63的P盒
{
	int i,temp[16]={0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15};
	for(i=0;i<16;i++) pip[i]=temp[i];
}

void untwistPis()//解密用到的S盒，是加密S盒的逆
{
	int i,temp[size];
	for(i=0;i<size;i++) temp[pis[i]]=i;
	for(i=0;i<size;i++) pis[i]=temp[i];
}

void untwistPip()//解密用到的P盒，是加密P盒的逆
{
	int i,temp[size];
	for(i=0;i<size;i++) temp[pip[i]]=i;
	for(i=0;i<size;i++) pip[i]=temp[i];
}

void untwistKey()//解密用到的轮密钥
{
	int i,j,temp[N+1][size];
	for(i=0;i<N+1;i++)
		for(j=0;j<size;j++) temp[i][j]=K[i][j];
	for(i=0;i<N+1;i++){
		if(i==0||i==N){
			for(j=0;j<size;j++) K[i][j]=temp[N-i][j];
		}
		else{
			for(j=0;j<size;j++) K[i][j]=temp[N-i][pip[j]];
		}
	}
}

void Print()//显示轮密钥，S盒，以及P盒
{
	int i,j;
	printf("轮密钥:\n");
	for(i=0;i<N+1;i++){
		printf("K%d:",i+1);
		for(j=0;j<size;j++){
			if(j>0&&j%4==0) printf(" ");
			printf("%d",K[i][j]);
		}
		printf("\n");
	}
	printf("\n\nS盒:\n");
	for(i=0;i<size;i++){
		if(i<10) printf("%3d",i);
		else printf("%3c",i+'A'-10);
	}
	printf("\n");
	for(i=0;i<size;i++){
		if(pis[i]<10) printf("%3d",pis[i]);
		else printf("%3c",pis[i]+'A'-10);
	}
	printf("\n\nP盒:\n");
	for(i=0;i<size;i++) printf("%3d",i+1);
	printf("\n");
	for(i=0;i<size;i++) printf("%3d",pip[i]+1);
	printf("\n\n");
}

int decimal(int *bit,int len)
/*二进制整数转换成十进制整数，按基值重复相乘法*/
{
	int i=0,s=0;
	while(i<len){s=s*2+bit[i]; i++;}
	return s;
}

void bit(int dec,int *bit,int &len)
/*十进制整数转换成二进制整数，重复相除法*/
{
	int i,temp[8]; len=0;
    while(dec!=0){
		temp[len]=dec%2; 
		len++; 
		dec=dec/2;
	}
	for(i=0;i<len;i++) bit[i]=temp[len-1-i];
}

void SPN_Encrypt(int *input,int *output)
/*SPN代换－置换算法，参照教材P62算法*/
{
	G=0;
	int i,j,r; 
	int *w=new int[l*m],*u=new int[l*m],*v=new int[l*m];
	for(i=0;i<l*m;i++) w[i]=input[i];
	for(r=0;r<N-1;r++){
		for(i=0;i<l*m;i++) u[i]=(w[i]+K[r][i])%2;
		for(i=0;i<m;i++){
			int len,dec,temp[4];
			for(j=0;j<4;j++) temp[j]=u[4*i+j];
			dec=decimal(temp,4);
			bit(pis[dec],temp,len);
			for(j=0;j<4-len;j++) v[4*i+j]=0;
			for(j=4-len;j<4;j++) v[4*i+j]=temp[j-4+len];
		}
		for(i=0;i<l*m;i++) w[i]=v[pip[i]];
		if(r==0) G+=(u[4]+u[6]+u[7]+v[5]);
		if(r==1) G+=(u[5]+v[5]+v[7]);
		if(r==2) G+=(u[5]+v[5]+v[7])+(u[13]+v[13]+v[15]);
	}
	for(i=0;i<l*m;i++) u[i]=(w[i]+K[N-1][i])%2;
	for(i=0;i<m;i++){
		int len,dec,temp[4];
		for(j=0;j<4;j++) temp[j]=u[4*i+j];
		dec=decimal(temp,4);
		bit(pis[dec],temp,len);
		for(j=0;j<4-len;j++) v[4*i+j]=0;
		for(j=4-len;j<4;j++) v[4*i+j]=temp[j-4+len];
	}
	for(i=0;i<l*m;i++) output[i]=(v[i]+K[N][i])%2;
}

void PlaintextCryptograph(int *input,int *output,int flag=0)
//输出明－密文对或密－明文对
{
	int i;
	if(!flag) printf("明文:");
	else printf("密文:");
	for(i=0;i<size;i++){
		if(i>0&&i%4==0) printf(" "); 
		printf("%d",input[i]);
	}
	printf("\n");
	if(!flag) printf("密文:");
	else printf("明文:");
	for(i=0;i<size;i++){
		if(i>0&&i%4==0) printf(" "); 
		printf("%d",output[i]);
	}
 	printf("\n");
}

void RandPlaintext()
/*用随机函数生成T个二进制明文，在线性密码分析时用到。
对于线性攻击来说，需要有T对明－密文。*/
{
	int i,j;
	count=0; prG=0; e=0;
	srand((unsigned)time(NULL));//设定种子，保证程序每次运行不会得到同一串明文
	for(i=0;i<T;i++){
		for(j=0;j<size;j++) x[j]=rand()%2;
		SPN_Encrypt(x,y);
		if(G%2==0) count++;
	}
	prG=(double)count/T;
	e=prG-0.5;
}

void untwist()//为解密需重新构造轮密钥，S盒以及P盒
{
	untwistPis();
	untwistPip();
	untwistKey();
}

int main()
{
	int choice;
	int i,j,length=0,temp[10000];
	char c='1';
	printf("(1)实现SPN加密:\n请选择密钥，S盒以及P盒的");
	printf("生成方式(0——教材P63例子，1——随机生成):");
	scanf("%d",&choice);
	if(!choice){
		Key();
		pi_s();
		pi_p();
	}
	else{
		Generate_Key();
		Build_S_Box();
		Build_P_Box();
	}
	Print();//显示密钥，S盒以及P盒
	printf("选择明文输入方式(0—键盘输入，1—随机生成T个明文):");
	scanf("%d%*c",&choice);
	if(!choice){
		printf("请输入二进制明文，以回车符为结束标志，");
		printf("若最后一段要加密的明文长度不够，程序会自动在后面补0:\n");
		while(c!='\n'){
			scanf("%c",&c);
			temp[length]=c-'0';
			length++;
		}
		length--;
		int ceiling=(int)ceil((double)length/(size));
		for(i=length;i<size*ceiling;i++) temp[i]=0;
		length=size*ceiling;
		printf("输出明－密文对:\n");
		for(i=0;i<length/size;i++){
			for(j=0;j<size;j++) x[j]=temp[i*size+j];
			SPN_Encrypt(x,y);
			PlaintextCryptograph(x,y,0);
		}
	}
	else RandPlaintext();
	printf("\n");
	
	printf("(2)通过对SPN的大量随机激励，计算教材P71中随机变量G的偏差:\n");
	if(!choice)	RandPlaintext();
	printf("教材P71近似方法得出的随机变量G的偏差是:%lf\n",-1.0/32);
	printf("程序中通过大量对SPN的随机激励，计算得出的随机变量G的偏差是:%lf\n\n",e);

	printf("(3)实现SPN解密(参考教材习题3.1):\n");
	untwist();
	Print();
	printf("请输入长度是16的整数倍的二进制密文，以回车符为结束标志:\n");
    length=0; c='1';
	while(c!='\n'){
		scanf("%c",&c);
		temp[length]=c-'0';
		length++;
	}
	length--;
	int ceiling=(int)ceil((double)length/(size));
	for(i=length;i<size*ceiling;i++) temp[i]=0;
	length=size*ceiling;
	printf("输出密－明文对:\n");
	for(i=0;i<length/size;i++){
		for(j=0;j<size;j++) y[j]=temp[i*size+j];
		SPN_Encrypt(y,x);
		PlaintextCryptograph(y,x,1);
	}
	printf("\n");

	return 0;
}