RSA 与 算法 返回首页

发表于 2020-04-15 | 本文共 738 字

What is RSA

RSA

How is RSA

RSA

RSA 的计算过程:

这时引入欧拉函数:

举例:

Private Key and Public Key

Public Key = (N, e)

Private Key = (N, d)

where,

所以,我们可以这么表示RSA:

加密解密过程

对于任意的信息m:

举例:

简单的证明

用剩余类证明,略

安全性

通过公钥和密文,攻击者知道的有: N,e,c=$m^e \bmod N$

gcd()

快速取模

long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m; //当b的当前二进制最低位为1时,即对应着二进制指数不为0时的Xi
    a = a * a % m;
    b >>= 1; //b除2
  }
  return res;
}

乘法逆元

快速幂法

扩展欧几里得法

int Exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  int d = Exgcd(b, a % b, x, y);
  int t = x;
  x = y;
  y = t - a / b * y;
  return d;
}