实施RSA算法的C ++程序

RSA是一种非对称密码算法，它对两个密钥（公钥和私钥）起作用。

演算法

Begin
   1. Choose two prime numbers p and q.
   2. Compute n = p*q.
   3. Calculate phi = (p-1) * (q-1).
   4. Choose an integer e such that 1 < e < phi(n) and gcd(e, phi(n)) = 1; i.e., e and phi(n) are coprime.
   5. Calculate d as d ≡ e−1 (mod phi(n)); here, d is the modular multiplicative inverse of e modulo phi(n).
   6. For encryption, c = me mod n, where m = original message.
   7. For decryption, m = c d mod n.
End

示例

#include<iostream>
#include<math.h>
using namespace std;
//找到gcd-
int gcd(int a, int b) {
   int t;
   while(1) {
      t= a%b;
      if(t==0)
      return b;
      a = b;
      b= t;
   }
}
int main() {
   //2个随机质数
   double p = 13;
   double q = 11;
   double n=p*q;//calculate n
   double track;
   double phi= (p-1)*(q-1);//calculate phi
   //公钥
   //e代表加密
   double e=7;
   //for checking that 1 < e < phi(n) and gcd(e, phi(n)) = 1; i.e., e and phi(n) are coprime.
   while(e<phi) {
      track = gcd(e,phi);
      if(track==1)
         break;
      else
         e++;
   }
   //私钥
   //d代表解密
   //选择d使其满足d * e = 1 mod phi-
   double d1=1/e;
   double d=fmod(d1,phi);
   double message = 9;
   double c = pow(message,e); //encrypt the message
   double m = pow(c,d);
   c=fmod(c,n);
   m=fmod(m,n);
   cout<<"Original Message = "<<message;
   cout<<"\n"<<"p = "<<p;
   cout<<"\n"<<"q = "<<q;
   cout<<"\n"<<"n = pq = "<<n;
   cout<<"\n"<<"phi = "<<phi;
   cout<<"\n"<<"e = "<<e;
   cout<<"\n"<<"d = "<<d;
   cout<<"\n"<<"Encrypted message = "<<c;
   cout<<"\n"<<"Decrypted message = "<<m;
   return 0;
}

输出结果

p = 13
q = 11
n = pq = 143
phi = 120
e = 7
d = 0.142857
Original Message = 9

Encrypted message = 48
Decrypted message = 9