CANARYPWN'S NATÏVE BLOG

RSA 与 算法

RSA, Prime numbers, EEA and gcd.
Canarypwn
Apr 15, 2020
It takes 11 minutes to read this article.

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的逆元