RSA.rar_RSA 素数_RSA素数_大素数

#include<iostream> #include<stdlib.h> #include<time.h> using namespace std; int main() { long p,q,a,b,x,y; //////////////////////////////以下产生俩不同大素数 long prime(); do { p=prime(); do {q=prime();} while(p==q); }while((p*q)<16383); cout<<"p="<<p<<endl<<"q="<<q<<endl; /////////////////////////////Euclidean算法求最大公因子，以确定符合条件的b值 long Euclidean(long a,long b); long ExtendedEuclidean(long a,long b); srand((unsigned)time(NULL)); do { b=(long)rand(); }while((Euclidean((p-1)*(q-1),b)!=1)||(b<=1)||(b>=(p-1)*(q-1))||(ExtendedEuclidean((p-1)*(q-1),b)==0)); cout<<"b="<<b<<endl; ////////////////////////////Extended Euclidean算法求b的乘法逆 a=ExtendedEuclidean((p-1)*(q-1),b); cout<<"a="<<a<<endl; cout<<endl; ////////////////////////////Square_and_Multiply算法来加密明文 long Square_and_Multiply(long x,long c,long n); cout<<"My Number is 090909"<<endl; x=9; y=Square_and_Multiply(x,b,p*q); if(y<0) y=y+p*q; cout<<"After being enciphered y="<<y<<","; x=2263; y=Square_and_Multiply(x,b,p*q); if(y<0) y=y+p*q; cout<<y<<endl; cout<<endl; cout<<"Please input any positive integer in decimal: "; cin>>x; y=Square_and_Multiply(x,b,p*q); if(y<0) y=y+p*q; cout<<"After being enciphered y="<<y<<endl; cout<<endl; x=(long)rand(); cout<<"Random integer number is "<<x<<endl; y=Square_and_Multiply(x,b,p*q); if(y<0) y=y+p*q; cout<<"After being enciphered y="<<y<<endl; cout<<endl; char A; cout<<"When you finished,please press any char,then Enter it"<<endl; cin>>A; return 0; } int* randomnum() { srand((unsigned)time(NULL)); int a[100];//接收byte序列 int L[6];//接收随机数byte序列 int i=0,j=-1; while(i<6) { if(j<=31) { j++; a[j]=(rand()%2); if((j>=1)&&((j-1)%2==0)&&(a[j-1]==1)) {L[i]=a[j];i++;} } else { j++; a[j]=((a[j-2]+a[j-3]+a[j-7]+a[j-32])%2); if(((j-1)%2==0)&&(a[j-1]==1)) {L[i]=a[j];i++;} } } return L; } bool isprime(long n) { int m=n-1,a=1,i=1; while(m%2==0) m=m/2; srand((unsigned)time(NULL)); do { a=rand(); }while((a<1)||(a>=n)); /* long b=a; for(i=1;i<m;i++) {b=b*a;b=b%n;} */ long Square_and_Multiply(long x,long c,long n); long b=a; b=Square_and_Multiply(a,m,n); if(b%n==1) return true; else { for(i=1;i<=100;i++) { if(b%n==-1) {break;return true;} else {b=b*b;b=b%n;} } if(i>100) return false; } } long prime() { int* randomnum(); bool isprime(long n); long prime; int *z=NULL; do { prime=1; z=randomnum(); for(int i=0;i<6;i++) prime=prime*2+(*(z+i)); prime=prime*2+1; }while(!isprime(prime)); return prime; } long Euclidean(long a,long b) { int m=1; long r[100]={a,b},q[101]={0}; while(r[m]!=0) { q[m]=(int)r[m-1]/(int)r[m]; r[m+1]=r[m-1]-q[m]*r[m]; m++; } m--; return r[m]; } long ExtendedEuclidean(long a,long b) { long a0=a,b0=b,t0=0; int t=1,q,r,temp; q=(int)a0/(int)b0; r=(int)(a0-q*b0); while(r>0) { temp=((int)(t0-q*t))%a; if(temp<0) temp=temp+a; t0=t; t=temp; a0=b0; b0=r; q=(int)a0/(int)b0; r=(int)(a0-q*b0); } if(b0!=1) return 0; else return t; } long Square_and_Multiply(long x,long c,long n) { long z=1; int d=(int)c; int l=0; int b[40]; while(d) { b[l]=d%2; l++;d=d/2; } for(int i=l-1;i>=0;i--) { z=z*z; z=z%n; if(b[i]==1) {z=z*x;z=z%n;} } return z; }