RSA算法

SSL 协议就采用了这个算法

设定 $m < n$

加密： $c \equiv m^{e} (m o d n)$

解密： $m \equiv c^{d} (m o d n)$

下面证明正确性：

要证明：

m \equiv m^{e d} (m o d n)

因为：

e d \equiv 1 (m o d φ (n))

e d = 1 + k φ (n)

即证：

m^{k φ (n) + 1} \equiv m (m o d n)

如果 m 和 n 互素，由欧拉定理得肯定成立：（两边再乘一次 m 就是了）

m^{k φ (n)} \equiv 1 (m o d n)

如果 m 和 n 不互素（这种概率可以忽略不计了）：

那么 m 一定是 p 或 q 的倍数

不妨设 $m = c p$

这时 $(m, q) = 1$

有

m^{k φ (q)} \equiv 1 (m o d q)

m^{k φ (n)} \equiv 1 (m o d q)

存在 r 使得：

m^{k φ (n) + 1} = m + rc pq = m + rc n

即：

m^{k φ (n) + 1} \equiv m (m o d n)

已知 $e$ ， $d$ 和 $n$ ，分解 $n$

所以密钥组中泄露任意一个都是能够推出所有东西的

如果已知两组 n e c ，其中 n 相等，e 互素，利用共模攻击可以求出 m

x e_{1} + y e_{2} = 1

c_{1}^{x} c_{2}^{y} = m^{x e_{1}} m^{y e_{2}} = m^{x e_{1} + y e_{2}} \equiv m (m o d n)

🪴 Cyril