rsarsarsa.txt

实现MT算发 实现MT算发 实现MT算发 实现MT算发

#include<iostream.h>
#include<math.h>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include <Windows.h>
#define NULL 0
//数据结构
struct Node{
	int data;//存储二进制数
	struct Node *next;
};
//输出函数
void PRINT(struct Node *head){
	struct Node *p;
	p=head;
	cout<<"各个节点的值依次是:"<<endl;
	if(head!=NULL)
		do{
			cout<<p->data<<"  ";
			p=p->next;
		}while(p!=NULL);
}
//欧基里德算法Euclid
long EUCLID(long a,long b){
	long temp,A,B,R;
	A=a;
	B=b;
	if(A<B) {
		temp=A;
		A=B;
		B=temp;
	}
LABEL:if(B==0) return A;
	  R=A%B;
	  A=B;
	  B=R;
	  goto LABEL;
}
//扩展欧基里德算法EEuclid
long EEUCLID(long m,long b){
	long A1,A2,A3,B1,B2,B3,T1,T2,T3,Q;
	A1=1;
	A2=0;
	A3=m;
	B1=0;
	B2=1;
	B3=b;
LABEL:if(B3==0) return A3;//返回最大公因子
	  if(B3==1) {//返回乘法逆元
		  B2=(B2+(B2/m)*m)%m;
		  return B2;
	  }
	  Q=A3/B3;
	  T1=A1-Q*B1;
	  T2=A2-Q*B2;
	  T3=A3-Q*B3;
	  A1=B1;
	  A2=B2;
	  A3=B3;
	  B1=T2;
	  B2=T2;
	  B3=T3;
	  goto LABEL;
}
//用加密,解密算法
long JIAMI(long a,long b,long n){
	long c=0,f=1;
	int i,k=0,temp=0;
	struct Node *head,*p,*q;
	head=p=q=NULL;
	while(b/2!=0){
		p=new (struct Node);
		p->data = b%2;
		p->next = q;
		q=p;
		b=b/2;
		k++;
	}
	p=new (struct Node);
	p->data = b;
	p->next = q;
	q=p;
	k=k+1;
	head=q;
//	PRINT(head);
	for(i=k;i>0;i--){
		temp++;
		if(temp==1){
			p=head;
	        q=p->next;
		}
		else {
			p=q;
		    q=q->next;
		}
		c=2*c;
		f=(f*f)%n;
		if(p->data==1){
			c=c+1;
			f=(f*a)%n;
		}
	}
	return f;
}
/*加密,解密函数（仅供参考—不正确）
long JIAMI(long m,long e,long n){ 
  long a, b, c; 

  a = m; 
  b = e; 
  c = 1; 

  while(b) 
  { 
    if ((b%2) == 0) 
        { 
        b = b/2;        //降阶 
        a = (a * a)%n; 
        } 
        else 
        { 
                b = b - 1; 
                c = (a * c)%n; 
        } 
  }        
    
  return c; 
} */
/*用私钥解密算法,求模（仅供参考—不正确）
long MOD(long C,long d,long n,long p,long q){
	long Vp,Vq,Xp,Xq,Ep,Eq,M;
	long i,p1,q1;//p1,q1分别是p和q的乘法逆元
	Ep=d%(p-1);
	Eq=d%(q-1);
	for(i=0;i<Ep;i++)
		C=C*C;
	Vp=C%p;
	for(i=0;i<Eq;i++)
		C=C*C;
	Vq=C%q;
	q1=EEUCLID(p,q);
	Xp=q*q1;
	p1=EEUCLID(q,p);
	Xq=p*p1;
	M=(Vp*Xp+Vq*Xq)%n;
	return M;
}*/
//产生一个与n互素的数
long HS(long n){
	long e;
	time_t t;
    srand((unsigned) time(&t));
LABEL:
	e=1+rand()%n;
	if(EUCLID(n,e)==1) return e;
	goto LABEL;
}
//素性测试(测试一个数是否是素数)
int TEST(long n){
	long a,k=0,i,j,m,e=1,q;
	m=n-1;
	if(n==2) return 1;
	if(n%2==0) return 0;//n为偶数
	while(m%2==0){
		q=m/2;
		m=m/2;
		k++;
	}
	a=2+rand()%(n-1);
	if(JIAMI(a,q,n)==1) return 1;//返回不确定，有可能是素数
	for(j=0;j<k-1;j++){
		for(i=0;i<j;i++)
			e=2*e;
		e=e*q;
		if(JIAMI(a,e,n)==n-1) return 1;
	}
	return 0;//是合数
}
//在2的n次方附近找一个素数
long SearchN(int n){
	int a,i=0,flag=1;
	long N,m=1;
	time_t t;
	srand((unsigned) time(&t));
	for(i=0;i<n;i++)
		m=2*m;
	for(N=m-long(log(m));N<m+long(log(m));N++){
		flag=0;
		if(N%2==0) continue;
		for(i=0;i<10;i++){
			flag=TEST(N);
			if(flag==1) break;
		}
		if(flag==1) return N;
	}
}
//主函数
void main(){
	long p,q,n,N,e,d,C,M;//C为密文，M为明文，N=(p-1)*(q-1)
	int Q1,Q2,Q11,Q22;//Q1，Q2为产生p，q的随机数种子当p,q为9和6时能加密到31048的数
	time_t t;
	srand((unsigned) time(&t));
	cout<<"输入产生p的随机数种子:";
	cin>>Q1;
	Q11=Q1;
	cout<<"输入产生q的随机数种子:";
	cin>>Q2;
	Q22=Q2;
LABEL:
	Q1=1+rand()%Q11;
	cout<<"Q1="<<Q1<<endl;
	Q2=1+rand()%Q22;
	cout<<"Q2="<<Q2<<endl;
	p=SearchN(Q1);
	q=SearchN(Q2);
	if((p==q)||(p<=1)||(q<=1)) goto LABEL;
	n=p*q;
	N=(p-1)*(q-1);
	e=HS(N);
	d=EEUCLID(N,e);
	if(e<=0||d<=0) goto LABEL;
	cout<<"公钥:("<<e<<","<<n<<")"<<"    "<<"私钥:("<<d<<","<<n<<")"<<endl;
	cout<<"输入要加密的明文(明文必须小于n):";
	cin>>M;
	C=JIAMI(M,e,n);//加密
	cout<<"密文为:"<<C<<endl;
	M=JIAMI(C,d,n);//解密
	cout<<"解密后的明文是:"<<M<<endl;
}