rsa.rar_RSA image_RSA 加密解密_image rsa_rsa加密算法_图片 解密

#include<iostream> #include<time.h> #include "rsa.h" using namespace std; int getprime() { //----------------符合要求的素数表--------------------- int prime[19] = {151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251}; int a; srand(time(NULL)); a = rand()%19; return prime[a]; } int Generate_Prime() //生成(128~256)的奇素数 { int a; srand((unsigned)time(NULL)); a = rand()%UPPER_LIMIT; if(a%2 == 0) a += 1; while(a<LOWER_LIMIT || !Prime_test(a)) { a = rand()%UPPER_LIMIT; if(a%2 == 0) a += 1; } return a; //a是大奇素数 } bool Prime_test(int n) //因为需要判断的数是p、q，都在int范围内， { //所以是int类型 //Miller_Rabin(n)算法 实现的素性测试 //----------------n-1 = 2^k * m----------------------- int temp1, temp2, k = 0; temp1 = n - 1; temp2 = temp1%2; while(temp2 == 0) { temp1 = temp1 / 2; k++; temp2 = temp1%2; } // 此时获得的temp1就是奇数m //-----------------产生随机数 a = (1, n-1)------------- int a; srand((unsigned)time(NULL)); a = rand()%(n - 1) + 1; // 1<=a<=n-1 //----------------------------------------------------- int b = 1; for(int i=0; i<temp1; i++) //求a的m次方 { b = (b*a)%n; } if((b%n) == 1) // n is prime return true; for(i=0; i<k-1; i++) { if((b%n) == -1) return true; else b = (b*b)%n; } return false; } int gcd(unsigned int a, unsigned int b) //用扩展Euclidean算法实现求最大公约数 { unsigned int a0, b0; int t0, t, s0, s, r, temp, q; a0 = a; b0 = b; t0 = 0; t = 1; s0 = 1; s = 0; q = a0/b0; r = a0 - q*b0; while(r>0) { temp = t0 - q*t; t0 = t; t = temp; temp = s0 - q*s; s0 = s; s = temp; a0 = b0; b0 = r; q = a0/b0; r = a0 - q*b0; } r = b0; return (int)r; } unsigned int Inverse(unsigned int m, int b) { unsigned int a0, t, q; int t0, r, b0, temp; a0 = m; b0 = b; t0 = 0; t = 1; q = a0/b0; r = a0 - q*b0; while(r>0) { temp = (t0 - q*t)%m; t0 = t; t = temp; a0 = b0; b0 = r; q = a0/b0; r = a0 - q*b0; } if(b0 != 1) return -1; // b没有摸m的逆 else return t; } //------------------------------------------------------ unsigned int Reciprocal_u(unsigned int m, unsigned int u) { unsigned int n1=m; unsigned int n2=u; long b1=0; long b2=1; long t; unsigned int q; unsigned int r; do { q=n1/n2; r=n1-q*n2; if (r==0) break; n1=n2; n2=r; t=b2; b2=b1-q*b2; b1=t; } while (1); if (n2!=1) return (0); //不存在 if (b2<0) return (b2+m); else return (b2); } RSA_Key RSA_Para() //生成RSA参数 { int p, q; unsigned int n, m, a; int b; RSA_Key KEY; p = getprime(); A: q = p; while(q == p) q = getprime(); n = p*q; if(n<32768) { goto A; } m = (p-1)*(q-1); // m为 fi(n) srand(time(NULL)); b = 2; B: while(gcd(b, m) != 1) { b++; } // a = Inverse(m, b); //求b模m的逆 a = Reciprocal_u(m, b); if(a == -1) { b++; goto B; } if((a*b)%m != 1) { b++; goto B; } KEY.n = n; //公钥 KEY.b = b; KEY.a = a; //密钥 KEY.p = p; KEY.q = q; return KEY; } int BitsNum(unsigned int c) { int k=1; while((c/=2)!=0) k++; return k; } unsigned int Square_Multiply(unsigned int x, unsigned int c, unsigned int n) { unsigned int z = 1; int l = BitsNum(c); //计算c的长度 bool *tmp = new bool[l]; //将c转化成2进制数 if(c%2 == 0) tmp[0] = 0; else tmp[0] = 1; int i=1; while((c/=2) != 0) { if(c%2==0) tmp[i] = 0; else tmp[i] = 1; i++; } for(i=l-1; i>=0; i--) //执行平方乘算法 { z = (z*z)%n; if(tmp[i] == 1) z = (z*x)%n; } return z; } unsigned int MONmod(unsigned int x,unsigned int r,unsigned int n) { unsigned int a,b,c; a=x; b=r; c=1; while (b!=0) { if ((b&0x01)==0) { b=b/2; a=(a*a)%n; } else { b=b-1; c=(a*c)%n; } } return c; }