rsa.cpp

密码学大作业的内容

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 2050
#define L 6
#define LM 2

int compare(int a[],int b[]){
	int i;
	if(a[0]>b[0])
		return 1;
	else if(a[0]<b[0])
		return -1;
	else{
		for(i=a[0];i>0;i--){
			if(a[i]>b[i])
				return 1;
			else if(a[i]<b[i])
				return -1;
		}
		return 0;
	}
}
void copy(int a[],int b[]){
	int i;
	for(i=0;i<N;i++)
		a[i]=b[i];
}
void fix(int a[]){
	int i;
	for(i=1;i<a[0]+1;i++){
		if(a[i]<0){
			a[i]+=2;
			a[i+1]--;
		}
		if(a[i]>1){
			a[i]-=2;
			a[i+1]++;
		}
	}
}
void len(int a[]){
	int i;	
	for(i=a[0]+1;i>0;i--)
		if(a[i]!=0){
			a[0]=i;
			return;
		}
	a[0]=0;
}
int maxlen(int a[],int b[]){
	if(a[0]>=b[0])
		return a[0];
	else return b[0];
}
void plus(int a[],int b[]){
	int i;
	for(i=1;i<=a[0]||i<=b[0];i++)
		a[i]+=b[i];
	a[0]=maxlen(a,b);
	fix(a);
	len(a);
}
void minus(int a[],int b[]){
	int i;
	if(compare(a,b)==1||compare(a,b)==0){
	    for(i=1;i<=a[0]||i<=b[0];i++)
		    a[i]-=b[i];
	    a[0]=maxlen(a,b);
	    fix(a);
	    len(a);
	}
}
void mod(int a[],int b[]){
	int i;
	while(a[0]>b[0]){
		for(i=0;i<b[0];i++)
			a[a[0]-b[0]+i]-=b[i+1];
		fix(a);
		len(a);
	}
	if(compare(a,b)==1||compare(a,b)==0)
		minus(a,b);
	len(a);
}
void mul(int a[],int b[],int n[]){
	int i,j,k,*c;
    c=new int[N];
	for(i=0;i<N;i++)
		c[i]=0;
	c[0]=N-2;
	mod(a,n);
	mod(b,n);
	for(i=1;i<=b[0];i++){
		if(b[i]==1){
			for(j=i,k=1;k<=a[0];j++,k++){
		        c[j]+=a[k];
	            c[0]=maxlen(c,a);
	            fix(c);
				len(c);
				mod(c,n);
				c[0]=N-2;
			}
		}
	}
	for(i=0;i<N;i++)
		a[i]=c[i];
	len(a);
	delete []c; 
}
void div(int a[],int b[],int c[]){
    int i;
	for(i=0;i<N;i++)
		c[i]=0;
	c[0]=N-2;
	while(a[0]>b[0]){
		for(i=0;i<b[0];i++)
			a[a[0]-b[0]+i]-=b[i+1];
		c[a[0]-b[0]]++;
		fix(a);
		fix(c);
		len(a);
	}
	if(compare(a,b)==1||!compare(a,b)){
        c[1]++;
		minus(a,b);
		fix(c);
	}
	len(a);
	len(c);
}
void quick(int a[],int q[],int c[],int n[]){
    int i,*a1,*q1;
	a1=new int[N];
	q1=new int[N];
	for(i=0;i<N;i++){
		a1[i]=a[i];
		q1[i]=q[i];
	}
	mod(a1,n);
    mod(q1,n);
	for(i=2;i<N;i++)
		c[i]=0;
	c[0]=1;
	c[1]=1;
	for(i=q1[0];i>0;i--){
		mul(c,c,n);
		if(q1[i]==1)
			mul(c,a1,n);
	}
	delete[]a1;
	delete[]q1;
}
void randomarray(int a[],int n){//产生随机数，位数为n。
	int i;
	for(i=1;i<n;i++){
       a[i]=(rand()/(RAND_MAX/2)); 
   }
	a[0]=n;
	a[n]=1;
}
int get_kandq(int q[])
{
	int i,k=0;
	for(i=1;i<=q[0];i++){
		if(q[i]==0)
			k++;
		else break;
	}
	q[0]-=k;
	for(i=1;i<=q[0];i++){
		q[i]=q[i+k];
		q[i+k]=0;
	}

	return k;
}
int text(int n[],int q[],int k){
	int *a,*c,b[N]={2,0,1},a1[N]={1,1},*n1,i,j;
	a=new int[N];
	n1=new int[N];
	c=new int[N];
	for(i=0;i<N;i++)
		a[i]=c[i]=n1[i]=0;
	for(i=0;i<=n[0];i++)
		n1[i]=n[i];
	minus(n1,a1);
	do{
	    randomarray(a,n[0]);
	}while(!compare(a,n));
	mod(a,n);
	quick(a,q,c,n);
	if(compare(c,a1)==0){
		delete[]a;
		delete[]c;
		delete[]n1;
		return 1;
	}
	for(j=0;j<k;j++){
		if(compare(c,n1)==0){
		delete[]a;
		delete[]c;
		delete[]n1;
		return 1;
		}
	mul(c,c,n);
	}
	delete[]a;
	delete[]c;
	delete[]n1;
	return 0;
}
void get_prime(int n[],int m){
	int i,*n1;
	int k,j,b[N]={2,0,1};    
	n1=new int[N];
	for(i=0;i<N;i++)
		n1[i]=0;
	randomarray(n,m);
	n[1]=1;
	for(i=0;i<N;i++)
		n1[i]=n[i];
    n1[1]=0;
	k=get_kandq(n1);
	for(j=0;j<10;j++){
		if(text(n,n1,k)==1)
			continue;
		else{
			plus(n,b);
			for(i=0;i<N;i++)
		        n1[i]=n[i];
            n1[1]=0;
			k=get_kandq(n1);
			j=-1;
		}
	}
	delete[]n1;
	for(i=0;i<n[0]+1;i++)
		printf("%d ",n[i]);
	printf("\n");
}
void Euclid(int a[],int b[]){
    int *n,*n1,*n2,*n3,*n4,*n5,i,z1[N]={1,1},z0[N]={0};
	n=new int[N];
	n1=new int[N];
	n2=new int[N];
	n3=new int[N];
	n4=new int[N];
	n5=new int[N];
	for(i=0;i<N;i++){
		n[i]=a[i];
		n1[i]=b[i];
		n2[i]=n3[i]=n4[i]=n5[i]=0;
	}
	n3[0]=n3[1]=1;
    n5[0]=n5[1]=1;
	for(i=0;;i++){
		if(!(i%2)){
           div(n,n1,n4);
    	   mul(n5,n4,a);
		   plus(n2,n5);
		   copy(n5,n2);
		}
		else{
			div(n1,n,n4);
			mul(n5,n4,a);
			plus(n3,n5);
            copy(n5,n3);		
		}
		if(!compare(z1,n1)){
			copy(a,n5);
            break;
		}
		else if(!compare(z1,n)){
			minus(a,n5);
			break;
		}
		else if(!compare(z0,n)||!compare(z0,n1)){
			delete[]n;
        	delete[]n1;
    	    delete[]n2;
    	    delete[]n3;
    	    delete[]n4;
    	    delete[]n5;
			printf("没有逆元\n");
			exit(0);
		}
	}
    delete[]n;
	delete[]n1;
	delete[]n2;
	delete[]n3;
	delete[]n4;
	delete[]n5;
}
void RSA(int p[],int q[],int n[]){
	int i,*MAX;
	MAX=new int[N];
	for(i=0;i<N;i++)
        MAX[i]=1;
	MAX[0]=2048;
	printf("P: \n");
    get_prime(p,L);
	printf("Q: \n");
	get_prime(q,L);
	copy(n,p);
	mul(n,q,MAX);
	printf("N: \n");
	for(i=0;i<n[0]+1;i++)
		printf("%d ",n[i]);
	printf("\n");
	delete[]MAX;
}
void Enc(int n[],int C[]){
	int *M,*MAX,i;
	int e[N];
	e[0]=17;
	e[17]=e[1]=1;
	M=new int[N];
	MAX=new int[N];
	for(i=0;i<N;i++)
        MAX[i]=0;
	randomarray(M,LM);
	for(i=0;i<M[0]+1;i++)
		printf("%d ",M[i]);
	printf("\n");
	quick(M,e,C,n);
	for(i=0;i<C[0]+1;i++)
		printf("%d ",C[i]);
	printf("\n");
	delete[]M;
	delete[]MAX;
}
void Dec(int p[],int q[],int n[],int C[]){
	int e[N]={0},*d,a1[N]={1,1},M[N]={0},i;
	int *MAX,*p1,*q1;
	MAX=new int[N];
	p1=new int[N];
	q1=new int[N];
    d=new int[N];
	for(i=0;i<N;i++)
        MAX[i]=1;
	copy(p1,p);
	copy(q1,q);
	minus(p1,a1);
	minus(q1,a1);
	MAX[0]=2048;
	e[0]=17;
	e[17]=e[1]=1;
	copy(d,p1);
	mul(d,q1,MAX);
	Euclid(d,e);
	quick(C,d,M,n);
	for(i=0;i<M[0]+1;i++)
		printf("%d ",M[i]);
	printf("\n");
	delete[]MAX;
	delete[]d;
	delete[]p1;
	delete[]q1;
}
void main(){
	int n[N]={0},p[N]={0},q[N]={0},C[N]={0};
	srand((int)time(0));
    RSA(p,q,n);	
	Enc(n,C);
	Dec(p,q,n,C);
}