Crypto 1 - RSA 详解

RSA

RSA 是一种经典的非对称加密, 其安全性基于大整数分解的困难性。

理论准备

  • 欧拉函数：

    • 在数论中, 用 $\phi(x)$ 来表示是满足 $gcd(n,k)= 1$, 其中 $k \in [1,x], k \in N$ 的 $k$ 的个数。

    • 对质数 $p$, 有: $$\phi(p)=p-1$$

    • 对任意 $p,q$ ,若有 $gcd(p,q)=1, m=pq$, 则:$$\phi(m)=(p-1)(q-1)$$

    • 欧拉定理: 当 $gcd(m,n)=1$时, $$m^{\phi(n)}=1\ \bmod\ n$$

  • 扩展欧几里得算法:
    • 设 $gcd(a,b)$ 用来表示 $a,b$ 的公约数个数。
    • 扩展欧几里得算法需要找到 $x,y$ 满足 $x>y$ , 且: $$ax+by=gcd(a,b)\ \bmod\ n$$
    • 当令 $b=0$, 则有: $$ax=1\ \bmod\ n$$此时也称 $x$ 为 $a$ 的乘法逆元。
  • 中国剩余定理:
    • 给定同余方程组:[
      \begin{cases}
      x \equiv a_1 \pmod{m_1} \
      x \equiv a_2 \pmod{m_2} \
      ;;\vdots \
      x \equiv a_n \pmod{m_n}
      \end{cases}
      ]
      其中 $m_1, m_2, \ldots, m_n$ 两两互质
    • 令$M = m_1 \times m_2 \times \cdots \times m_n$，则 存在唯一整数 $x_0$ 满足：$$0 \leq x_0 < M,$$且所有解可表示为：$$x = x_0 + kM \quad (k \in \mathbb{Z})$$.

RSA 算法流程

  1. 生成并发放秘钥
    选择两个大素数 $p$ 和 $q$ , 计算 $n=p \times q$, $\phi(n)=(q-1)(p-1)$。选择公钥指数 $e \in [1,\phi(n)]$ 且与 $\phi(n)$ 互质。

    一般来说, $e$ 取 65537。

    计算私钥指数 $$d = e^{-1}\ \bmod\ \phi(n)$$

    发放公钥指数 $(e,n)$, 私钥指数 $(d,n)$。

  1. 加密
    • 已知公钥：$(e,n)$ , (已处理的)明文 $m$, 且$0 \leq m<n$ 。
    • 加密流程: $$ c=m^{e}\ \bmod\ n$$
      $c$ 是加密后的密文。
  1. 解密
    • 已知私钥：$(d,n)$ , 密文 $c$ 。
    • 解密流程: $$ m’ = c^{d}\ \bmod n$$
  1. 验证
    • 现在只要验证 $m=m’$ 即可, 也就是需要证明

    $$m=(m^{e}\ \bmod\ n)^d\ \bmod n$$
    $$ m^{ed} = m\ \bmod\ n$$

    • 情况1: $m,n$ 互质, 即$gcd(m,n)=1$,则$$m^{\phi(n)}=1\ \bmod\ n,$$ 且又有$d = e^{-1}\ \bmod\ \phi(n)$, 则一定有 $$ed=k\phi(n)+1, \ k \in N,$$
      代入两式:
      $$m^{ed}=m^{k\phi(n)+1}={m^{\phi(n)}}^k\times m= 1^k \times m = m\ \bmod\ n,$$
      证毕;
    • 情况2: $m,n$ 不互质: 由于 $p,q$ 为质数, 则 $n$ 的因数为 ${1,p,q,n}$, 而 $m,n$ 不互质, 则 $m$ 一定为 $p$ 的倍数或者 $q$ 的倍数。由于 $p,q$ 是对等的, 这里不妨设 $m=0\ \bmod\ p,$ 则:
      $$m^{ed}=0=m\ \bmod\ p,$$
      又由费马小定理,
      $$m^{q-1}=1\ \bmod\ q,$$
      此时仍然有$ed=k\phi(n)+1=k(p-1)(q-1)+1$, 则:
      $$m^{ed}=m \times {(m^{q-1})}^{k(p-1)}=m\times1^{k(p-1)}= m\ \bmod\ q$$
      此时已有:
      $$
      \begin{cases}
      m^{ed} = m \pmod{p} \
      m^{ed} = m \pmod{q} \
      \end{cases}
      $$
      根据中国剩余定理, $$m^{ed}=m\ \bmod\ n,$$ 证毕。

RSA 的安全性

在 RSA 运作中, 通常会公开公钥 (e, n), 保留私钥 (d, n)

由于快速模幂算法, 通过二进制分解指数 (如平方-乘算法), 正向计算的时间复杂度为 $O(\log(n))$, 这在计算上是较为高效的。

而逆运算则需要根据 $n,e$ 来推算素因子 $p,q$, 这个问题的计算量非常大, 在计算上是不可行的, 这也是 RSA 的安全性由来——大数分解难题。

而 RSA 的安全程度也是由 $n$ 决定的, $n$越大, 算法越难破解。目前的 RSA 安全标准为 n 长2048位。

RSA 的数学一致性

RSA 既可以用于加密, 也可以用于数字签名, 这两套流程互为 逆运算。

简单来说, 对同一输入函数分别用 $e$ 和 $d$ 进行运算, 会返回原值, 而输入顺序与结果无关。

PRNG 生成攻击

通过利用伪随机数生成器的漏洞，预测或重现RSA密钥生成过程中使用的随机数，从而威胁密钥安全性。

RSA 的关键步骤: 生成 $n$ 时, 会先生成随机比特流, 从中筛选候选素数, 然后使用素性测试验证是否为素数。

如果 PRNG 存在缺陷, 可能:

  • 预测生成的素数：通过重现 PRNG 的输出序列推断 $p$ 和 $q$。
  • 降低密钥空间：利用弱随机性缩小素数搜索范围，加速大数分解。

end.jpg