RSA基础公式&正确性证明

基本原理

公钥与私钥的产生

1. 随机选择两个不同大质数 $p$ 和 $q$，计算  $N=p\times q$
2. 根据欧拉函数，求得 $\phi(N)=\phi(p)\phi(q)=(p-1)(q-1)$
3. 选择一个小于 $\phi(N)$ 的整数 $e$，使 $e$ 和 $\phi(N)$ 互质。并求得 $e$ 关于 $\phi(N)$ 的模反元素，命名为 $d$，有 $ed \equiv 1 \pmod{\phi(N)}$
4. 将 $p$ 和 $q$ 的记录销毁

此时，$(N,e)$ 是公钥，$(N,d)$ 是私钥。

消息加密

首先需要将消息 以一个双方约定好的格式转化为一个小于 $N$，且与 $N$ 互质的整数 $m$ 。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：

$$ m^{e} \equiv c \pmod N $$

消息解密

利用密钥 $d$ 进行解密。

$$ c^{d} \equiv m \pmod N $$

共模攻击

攻击条件

当两个用户使用相同的模数 N、不同的私钥时，加密同一明文消息时即存在共模攻击。
#题目链接 BUU-SameMod

$$ \begin{cases} c_1 \equiv m^{e_1} \pmod N \\ c_2 \equiv m^{e_2} \pmod N \end{cases} $$

当攻击者截获 $c_1$ 和 $c_2$ 后，就可以恢复出明文。用扩展欧几里得算法求出 $r e_1 + s e_2 = 1$ 的两个整数 $r$ 和 $s$，由此可得：

$$ \begin{align} c_1^{r}c_2^{s} \equiv& m^{r e_1} m^{s e_2} \pmod N \\ \equiv& m^{r e_1 + s e_2} \pmod N \\ \equiv& m \pmod N \end{align} $$

python技巧
[[RSA解密技巧]]
[[z3库解方程 & mpz()超高精度]]
CTFwiki_RSA