基本原理 ¶
公钥与私钥的产生 ¶
- 随机选择两个不同大质数 $p$ 和 $q$，计算 $N=p×q$
- 根据欧拉函数，求得 $φ(N)=φ(p)φ(q)=(p−1)(q−1)$
- 选择一个小于 $φ(N)$ 的整数 $e$，使 $e$ 和 $φ(N)$ 互质。并求得 $e$ 关于 $φ(N)$ 的模反元素，命名为 $d$，有 $ed≡1(modφ(N))$
- 将 $p$ 和 $q$ 的记录销毁
此时，$(N,e)$ 是公钥，$(N,d)$ 是私钥。
消息加密 ¶
首先需要将消息 以一个双方约定好的格式转化为一个小于 $N$，且与 $N$ 互质的整数 $m$ 。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：
$$me≡c(modN)$$
消息解密 ¶
利用密钥 $d$ 进行解密。
$$cd≡m(modN)$$
共模攻击 ¶
攻击条件 ¶
当两个用户使用相同的模数 N、不同的私钥时，加密同一明文消息时即存在共模攻击。
#题目链接 BUU-SameMod
$$\left{\begin{matrix}
c1=m^{e1}modN\
c2=m^{e2}modN
\end{matrix}\right.$$
当攻击者截获 $c1$ 和 $c2$ 后，就可以恢复出明文。用扩展欧几里得算法求出 $re1+se2=1modn$ 的两个整数 $r$ 和 $s$，由此可得：
$$\begin{align}
c^r_1c^s_2≡&M^{re1}M^{se2}modN \
≡&M^{re1+se2}modN \
≡&MmodN
\end{align}$$
python技巧
[[RSA解密技巧]]
[[z3库解方程 & mpz()超高精度]]
CTFwiki_RSA