关于超大数的RSA加密

/** * Copyright by HuangGuoWei * RSA加解密机制 * 并没有加入随机生成一个大数并判断其是否为素数的功能，p,q是直接输入的。 * 有待补充，不解释 */ #include<iostream.h> #include"BigNum.h" #define Maxsize 500 BigNum static S, T, Gcd; //存放最大公因子，和s，t BigNum model(BigNum b, BigNum n, BigNum m) { int i,j; i = 0; BigNum flag0, flag1, flag2 ; // 存放字符串“0”、“1” flag0 = "0"; flag1 = "1"; flag2 = "2"; BigNum temp; //BigNum C[ Bit_Maxsize ]; //存放大数b的二进制形式 int C[Maxsize]; //由于感觉使用BigNum存放一个0,1码过于浪费，所以用int代替 BigNum result; while(n >= flag1) //将b二进制化 { temp = n % flag2; if(temp == flag0) C[i] = 0; else C[i] = 1; n = n / flag2; i ++; } result = flag1; //模幂算法 for(j = i-1;j > 0 ;j--) { if(C[j] == 1) { result = result * b; result = result % m; } result = result * result; result = result % m; } if(C[0] == 1) { result = result * b; result = result % m; } //cout<<"Output the result is:"; //result.CoutBigNum(); return result; } void gcd(BigNum a, BigNum b) { int i, j; // i_ = i % 3; 使得s,t数组的3个元素可以循环使用 int flag = 0; BigNum s[3]; BigNum t[3]; //为了尽量节约内存空间，s,t数组只需要3个空间即可 BigNum a1, b1, temp; BigNum r[Maxsize], q[Maxsize]; s[0] = "1"; s[1] = "0"; t[0] = "0"; t[1] = "1"; a1 = a.ABS(); b1 = b.ABS(); if(a1.cmp(b1) >= 0); else { temp = a1; a1 = b1; b1 = temp; temp = a; a = b; b = temp; flag = 1; } r[0] = a1; r[1] = b1; temp = "0"; i=1; for(i=1;r[i]!=temp;i++) { q[i] = r[i - 1] / r[i]; r[i + 1] = r[i - 1] % r[i]; } j = 2; while(j<i) { s[j%3] = s[(j - 2)%3] - q[j - 1]*s[ (j - 1)%3]; t[j%3] = t[(j - 2)%3] - q[j - 1]*t[ (j - 1)%3]; j++; } //以下是判断s,t的符号问题 j = ( j - 1) % 3; temp = "0"; if(a.cmp1(a1) != 0&&b.cmp1(b1) != 0) { s[j] = temp - s[j]; t[j] = temp - t[j]; } if(a.cmp1(a1) != 0 && b.cmp1(b1) == 0) s[j] = temp - s[j]; if(b.cmp1(b1) != 0 && a.cmp1(a1) == 0) t[j ] = temp - t[j]; if(flag ==1) { temp = s [j]; s[j] = t[j]; t[j]=temp; } Gcd = r[i - 1]; S = s[j]; T = t[j]; } BigNum reverse(BigNum a,BigNum m) { BigNum flag0,flag1; flag0 = "0"; flag1 = "1"; gcd(a,m); if(Gcd != flag1) { cout<<"There is no reverse root,errro!"<<endl; return flag0; //如果没有逆元，则返回0 } while(S < flag0)S = S + m; S = S % m; return S; } void main() { char str[Maxsize]; BigNum flag0,flag1; BigNum p, q; BigNum n, n_; //n_就是(p - 1)*(q - 1) BigNum e, d; //e为随机输入，d为e的逆元mod(p - 1)*(q - 1) BigNum m, m_; //m为加密之前的明文，m_为解密以后的明文 BigNum C; //密文 flag0 = "0"; flag1 = "1"; d = "1"; cout<<"Please input the two bignumbers p:"; cin>>str; p.CinBigNum(str); cout<<"Please input the two bignumbers p:"; cin>>str; q.CinBigNum(str); n = p * q; n_ = n - q - p + flag1; p = "0"; q = "0"; //计算完以后直接销毁p,q cout<<"Please input the public key e:"; cin>>str; e.CinBigNum(str); while(1) { d = reverse(e, n_); //求公钥的私钥 if(d == flag0) { cout<<"The chosen number e can't match! Please repeat again!"<<endl; cout<<"Please input the public key e:"; cin>>str; e.CinBigNum(str); } else break; } cout<<"Please input plaintext m:"; cin>>str; m.CinBigNum(str); C = model(m, e, n); //加密工作 cout<<"The Cipertext C is:"; C.CoutBigNum(); cout<<endl; m_ = model(C, d, n); //解密工作 cout<<"The plaintext is m:"; m_.CoutBigNum(); cout<<endl; if(m_.cmp(m) == 0) // 比较加密之前和解密之后的明文m是否一致 { cout<<"The plaintext check is right!"<<endl; } else { cout<<"There must be a problem in the RSA,please check it again!"<<endl; } }