search

公钥指数相关攻击

hashtag
小公钥指数攻击

hashtag
攻击条件

e 特别小，比如 e 为 3。

hashtag
攻击原理

假设用户使用的密钥 $e=3$。考虑到加密关系满足：

c≡m3 mod Nc\equiv m^3 \bmod N

则：

m3=c+k×Nm=c+k×n3\begin{align*} m^3 &= c+k\times N\\ m &= \sqrt[3]{c+k\times n} \end{align*}

攻击者可以从小到大枚举 $k$，依次开三次根，直到开出整数为止。

hashtag
范例

这里我们以 XMan 一期夏令营课堂练习为例进行介绍（Jarvis OJ 有复现），附件中有一个 flag.enc 和 pubkey.pem，很明显是密文和公钥了，先用 openssl 读一下公钥。

看到 $e=3$，很明显是小公钥指数攻击了。这里我们使用 Crypto 库来读取公钥，使用 multiprocessing 来加快破解速度。

爆破时间有点长，，拿到 flag

hashtag
题目

hashtag
RSA 衍生算法——Rabin 算法

hashtag
攻击条件

Rabin 算法的特征在于 $e=2$。

hashtag
攻击原理

密文：

c=m2 mod nc = m^2\bmod n

解密：

  • 计算出 $m_p$ 和 $m_q$：

mp=c mod pmq=c mod q\begin{align*} m_p &= \sqrt{c} \bmod p\\ m_q &= \sqrt{c} \bmod q \end{align*}

  • 用扩展欧几里得计算出 $y_p$ 和 $y_q$：

yp⋅p+yq⋅q=1y_p \cdot p + y_q \cdot q = 1

  • 解出四个明文：

a=(yp⋅p⋅mq+yq⋅q⋅mp) mod nb=n−ac=(yp⋅p⋅mq−yq⋅q⋅mp) mod nd=n−c\begin{align*} a &= (y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \bmod n\\ b &= n - a\\ c &= (y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \bmod n\\ d &= n - c \end{align*}

注意：如果 $p \equiv q \equiv 3 \pmod 4$，则

mp=c14(p+1) mod pmq=c14(q+1) mod q\begin{align*} m_p &= c^{\frac{1}{4}(p + 1)} \bmod p\\ m_q &= c^{\frac{1}{4}(q + 1)} \bmod q \end{align*}

而一般情况下，$p \equiv q \equiv 3 \pmod 4$ 是满足的，对于不满足的情况下，请参考相应的算法解决。

hashtag
例子

这里我们以 XMan 一期夏令营课堂练习（Jarvis OJ 有复现）为例，读一下公钥。

$e=2$，考虑 Rabin 算法。首先我们先分解一下 p 和 q，得到

编写代码

拿到 flag，PCTF{sp3ci4l_rsa}。

hashtag
题目

PreviousCoppersmith 相关攻击Next模数相关攻击

Last updated