密钥生成:
公钥e,n放在publicKey.txt中,私钥d,p,q放在private.txt中
因为要按字符(0-255)处理,所以素数表从17开始,以确保n大于256
#include <iostream> #include <fstream> #include <time.h> #include <cstdlib> using namespace std; //素筛法得出的大素数表 long long int primeTable[162]={17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127 ,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233 ,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353 ,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467 ,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607 ,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739 ,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877 ,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997 }; int gcd(int a,int b) { int temp; if(a<b) { temp=a; a=b; b=temp; } int r=1; while(r) { r=a%b; a=b; b=r; } return a; } long long int ExtendedEuclid( long long int f,long long int d ,long long int *result) { long long int x1,x2,x3,y1,y2,y3,t1,t2,t3,q; x1 = y2 = 1; x2 = y1 = 0; x3 = ( f>=d )?f:d; y3 = ( f>=d )?d:f; while( 1 ) { if ( y3 == 0 ) { *result = x3; /* 两个数不互素则result为两个数的最大公约数,此时返回值为零 */ //if(*result<0)*result=*result+x3; return 0; } if ( y3 == 1 ) { *result = y2; /* 两个数互素则resutl为其乘法逆元,此时返回值为1 */ //if(*result<0)*result=*result+y2; return 1; } q = x3/y3; t1 = x1 - q*y1; t2 = x2 - q*y2; t3 = x3 - q*y3; x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; } } int main() { ofstream out1("publicKey.txt"); ofstream out2("private.txt"); long long int p,q,d,e,n; srand(time(NULL)); int index1,index2; index1=rand()%162; p=primeTable[index1]; //确保p,q互异 index2=rand()%162; while(index2==index1) { index2=rand()%162; } q=primeTable[index2]; n=p*q; long long int fai_n=(p-1)*(q-1); long long int temp; while(!(temp>0 && temp<fai_n && gcd(fai_n,temp)==1)) { temp=rand()%fai_n; } e=temp; long long int _e; ExtendedEuclid(e,fai_n,&_e); d=_e%fai_n; if(d<0)d=d+fai_n; out1<<e<<" "<<n; out2<<d<<" "<<p<<" "<<q; out1.close(); out2.close(); return 0; }
加密解密算法:
因为是按字节处理,所以可以加密解密任何格式文件,默认的是明文为p.txt,加密结果放在encode.txt中,解密结果放在decode.txt中
//RSA #include <iostream> #include <fstream> #include <cstdlib> using namespace std; long long int modexp(long long int a,long long int b,long long int n) { long long int ret=1; long long int tmp=a; while(b) { if(b&0x1) ret=ret*tmp%n; tmp=tmp*tmp%n; b>>=1; } return ret; } int main() { long long int p,q,n,e,d; ifstream in1("publicKey.txt"); ifstream in2("private.txt"); in1>>e>>n; in2>>d>>p>>q; in1.close(); in2.close(); //cout<<e<<" "<<n<<" "<<d<<" "<<p<<" "<<q<<endl; //encode ifstream pinput("p.txt",ios::binary); ofstream outc("encode.txt"); unsigned char temp; while(pinput.read((char*)&temp,1)) { outc<<modexp(temp,e,n)<<" "; } pinput.close(); outc.close(); //decode long long int c; ifstream cinput("encode.txt"); ofstream outr("decode.txt",ios::binary); long long int result; while(cinput>>c) { result=modexp(c,d,n); outr.write((char*)&result,1); } cinput.close(); outr.close(); return 0; }