RSA 与 算法

What is RSA

RSA

  • RSA 包含了 密钥（公钥，私钥）生成， 加密， 和解密。

How is RSA

RSA

RSA 的计算过程:

  • 首先取两个互素的整数: m, N。

    • m即要加密的信息
    • 其中 m < N
    • 也可以理解为先找到一个正整数N, 让任意的m<N使m,N互素。
      • 其中，互素指最大公约数为1，即gcd(m,N) = 1。
    • 这也是RSA算法的真正过程

  • N的取法: N = pq, (p,q are prime numbers)

    • N 是凑出来的，为两个素数的积

这时引入欧拉函数: $$ \phi (n) = \mid \mathbb{Z}_n^* \mid $$

  • 构造函数$\phi(n)$表示小于等于 和 互质的数的个数
  • 当 $n=pq$ 时， $\phi(n) = (p-1)(q-1)$

举例：

  • 任意取两个素数p=7,q=13
  • 此时N=pq=91
  • 此时$\phi(n) = (p-1)(q-1)=6 \times 12 = 72$

Private Key and Public Key

Public Key = (N, e)

Private Key = (N, d)

where,

  • e是在$\mathbb{Z}_{\phi(n)}^*$中均匀分布的，随机的取一个数字
  • 比如在之前的条件中，e为$\mathbb{Z}_\psi(91)^* =\mathbb{Z}_{72}^* = {1,3,5,7,\dots,71}$中随意的数字，例如 5
  • $\mathbb{Z}_n^*$表示小于n且与n互素的数
  • （N和e）即 (91，5) 组成了公钥
  • 而私钥d的计算是 $e^{-1} = d$，即e的逆元
    • 乘法逆元: $e e^{-1} \bmod \psi(n) = 1$, $e^{-1}$即逆元
    • 对于 $\psi(91) = 72$的情况，e=5, $e^{-1} = 29$
    • 所以$d = e^{-1} = 29$

所以，我们可以这么表示RSA：

  • 公钥: (pq, $\mathbb{Z}_{\psi(pq)}$中的任何一个数字e)

  • 私钥: (pq, $e^{-1}$)

  • p,q 为任意素数

  • 在这里需要计算的有:

    • $\mathbb{Z}_{\psi(pq)}$中的任何一个数字e
      • 即小于 $\mathbb{Z}_{\psi(pq)}$ 且与之gcd()=1的数字
      • 即gcd()的算法
    • $e^{-1}$
      • 即求乘法逆元

加密解密过程

对于任意的信息m:

  • 公钥: (pq, $\mathbb{Z}_{\psi(pq)}$中的任何一个数字e) = (N,e)

  • 私钥: (pq, $e^{-1}$)

  • 密文 = $m^e \bmod N$

  • 明文 = $密文^{e^{-1}} \bmod N$

举例:

  • 要加密的信息m=2
  • 生成素数 p =7 q=13
  • 得出 N=pq = 91
  • 得出 e $\in$ $\mathbb{Z}{\psi(N)}^*$ = $\mathbb{Z}{72}^*$ = {1,2,3, … ,71}
    • $\psi(N)$ = (p-1)(q-1) = 72
    • e 要和 72 互素
    • 假设e取5
  • 密文 = $2^5 \bmod 91$ =32
  • 明文 = $32^{e^{-1}} \bmod N = 32^{29} \bmod 91 = 2$

简单的证明

用剩余类证明，略

安全性

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

  • 由于素数分解很难，攻击者无法得知p,q

  • 因此无法得知$\psi(n)$

  • 因此无法得出$e^{-1}$

gcd()

  • 最大公约数即为 Greatest Common Divisor，常缩写为 gcd。

  • 辗转相除法（欧几里得法）

    • 假设a,b(a>b) 有公约数c 满足 c|a c|b
    • 则a%b,b有同样的公约数c
      • 因为a= cm, b=cn
      • a % b = cm - cn$\cdot$l 依然是c的倍数
    • 所以我们有gcd(a, b)=gcd(b, $a \bmod b$)

  • Example:

    • 24 和 14 的最大公约数等效于
      • 14 和 10 的最大公约数
      • 10 和 4 的最大公约数
      • 4 和 2 的最大公约数
      • 2 和 0的 最大公约数
      • 得出最大公约数为2

  • 欧几里得算法（Euclidean algorithm）

    int gcd(int a, int b){
  if (b==0) return a;
  return gcd(b, a%b);
}

快速取模

  • 快速幂

    • $3^{13} = 3^{(1101)_2}=3^8\cdot3^4\cdot3^1$
    • $3^{13}\bmod n=(3^8\cdot3^4\cdot3^1) \bmod n=((3^8 \bmod n) \cdot(3^4 \bmod n)\cdot(3^1 \bmod n) )\bmod n$
    • 例子:
      • 计算 $2^{123} \bmod 35$
      • $a=2, b=123=(1111011)_2, m=35$
      • $x_0 = a = 2$
      • $x_1 = x_0^2 \bmod m = 4$
      • $x_2 = x_1^2 \bmod 35 = 16$
      • $\dots$
      • $x_6 = x_5^2 \bmod n =16$
      • $2^{123} \bmod 35 = x_0x_1x_3x_4x_5x_6 \equiv 8 \pmod {35}$

  • 代码

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;
}

乘法逆元

  • 如果一个线性同余方程$ax \equiv 1 \pmod b$ ，则 $x$称为$a \bmod b$ 的逆元，记作$a^{-1}$ 。

快速幂法

  • 费马小定理: 若 p 为质数， a 为正整数，且 a、 p互质，则 $a^{p-1} \equiv 1 \pmod p$。
  • 求解 $ax \equiv 1 \pmod b$
  • 由费马小定理得: $ax \equiv a^{b-1} \pmod b$
  • $x \equiv a^{b-2} \pmod b$
  • 因为p一定是质数，所以一定不能用于RSA

扩展欧几里得法

  • 裴蜀定理: 设 a,b 是不全为零的整数，则存在整数x,y , 使得 ax+by = gcd(a,b).

  • 扩展欧几里德定理（Extended Euclidean algorithm, EXGCD, EEA），常用于求 ax+by = gcd(a,b) 的一组可行解。

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;
}
  • 以a = 12345 b=123 为例
    • gcd(12345,123) = a$x_1$ + b$y_1$
    • gcd(123, 45) = b$x_2$ + $(a \bmod b )y_2$
    • $\dots$
    • gcd(7,0) = 7 + 0
    • 向上反解
  • 求乘法逆元
    • 方程 $ax+by=c$与方程 $ax \equiv c \pmod b$是等价的，有整数解的充要条件为 $gcd(a,b) \mid c$。
    • $ax \equiv 1 \pmod b$中x称为a的逆元
comments powered by Disqus