RSA攻击大全及其实现

文章目录

1. RSA攻击大全
   1. 模数分解
   2. 针对指数进行攻击
   3. 针对私钥进行攻击
   4. Coppersmith相关攻击
2. 攻击工具
   1. RsaCtfTool
   2. yafu
   3. 在线分解因子网站

RSA攻击大全

模数分解

• Small q：模数N有小素数因子；
• fermat：模数N的因子p与q非常接近；
• 模不互素：给出多组公钥，但是其中的模数共用了素因子；

针对指数进行攻击

• 小公钥指数攻击：指数很小；
• 低加密指数广播攻击：相同的消息发送给多个接收者，且加密指数较低；

针对私钥进行攻击

• 维纳攻击：指数很大(理论上$d<N^{0.25}$此攻击起作用)；
• Boneh-Durfee攻击：同样针对指数很大的情形，理论上$d<N^{0.29}$此攻击起作用；

Coppersmith相关攻击

Coppersmith算法用于求解模$N$多项式$F(X)$($X$为单变量、二元变量甚至多元变量)所有小整数根($\big|X\big|<cN^{\beta^{2}/\delta}$，其中$\delta$为多项式$F$的次数，假设$N$具有不小于$N^{\beta}$的因子)

• 明文高位泄露：明文的二进制位表示为$m_{b} \cdots m_{t+1}m_{t} \cdots m_{1}$，其高位$m_{b} \cdots m_{t+1}$泄露，记$m’=m_{b} \cdots m_{t+1}0 \cdots 0$，则$m’$已知，但$\Delta m=m_{t} \cdots m_{1}$未知；由$c \equiv m^{e}\ \textrm{mod}\ N$，则$\Delta m$是模多项式$F(X)=(m’+X)^{e}\ \textrm{mod}\ N$的小整数根。接下来使用Coppersmith算法求解。

• 因子低位泄露：因子的二进制位表示为$p_{b} \cdots p_{t+1}p_{t} \cdots p_{1}$，其高位$p_{b} \cdots p_{t+1}$泄露，记$p’=p_{b} \cdots p_{t+1}0 \cdots 0$，则$p’$已知，但$\Delta p=p_{t} \cdots p_{1}$未知；由$p \cdot q=N$，则$\Delta p$是模多项式$F(X)=(p’+X)\ \textrm{mod}\ N$的小整数根。接下来使用Coppersmith算法求解。

• 明文低位泄露：明文的二进制位表示为$m_{b} \cdots m_{t+1}m_{t} \cdots m_{1}$，其低位$m_{t} \cdots m_{1}$泄露，记$m’=m_{t} \cdots m_{1}$，则$m’$已知，但$\Delta m=m_{b} \cdots m_{t+1}$未知；由$c \equiv m^{e}\ \textrm{mod}\ N$，则$\Delta m$是模多项式$F(X)=(m’+2^{t}X)^{e}\ \textrm{mod}\ N$的小整数根。接下来使用Coppersmith算法求解。

• 因子低位泄露：因子的二进制位表示为$p_{b} \cdots p_{t+1}p_{t} \cdots p_{1}$，其低位$p_{t} \cdots p_{1}$泄露，记$p’=p_{t} \cdots p_{1}$，则$p’$已知，但$\Delta p=p_{b} \cdots p_{t+1}$未知；由$p \cdot q=N$，则$\Delta p$是模多项式$F(X)=(p’+2^{t}X)\ \textrm{mod}\ N$的小整数根。接下来使用Coppersmith算法求解。

GithHub实现链接

攻击工具

RsaCtfTool

GitHub链接：RsaCtfTool

在Ubuntu18.04下的安装RsaCtfTool(进入RsaCtfTool目录下)：

apt install -y libgmp-dev
apt install -y libmpfr-dev
apt install -y libmpc-dev
pip3 install gmpy2 -i https://pypi.douban.com/simple
pip3 install -r requirements.txt -i https://pypi.douban.com/simple

yafu

我认为最强大的分解因子的工具。

在线分解因子网站

factordb