分而解之。

由浅入深,着重介绍攻击手段。

基本原理

  1. 选取两个(多个)大质数 $p,q$,计算 $N = p * q$

    • 关键在于使 $p,q$ 难以得到
  2. 求得 $ \phi(N) = \phi(p) * \phi(q) = (p - 1) * (q - 1)$
    • 特殊情况如下:
    \[N = p * q^3, \phi(N)=(p-1)*(q-1)*q^2\\\]
  3. 选择 $e<\phi(N)$,且 $ gcd(e,\phi(N)) = 1$,求得 $ed \equiv 1\ (mod\ \phi(N))$
\[c\equiv m^e\ (mod\ N)\\m\equiv c^d\ (mod\ N)\\s\equiv m^d\ (mod\ N)\]

BREAK 的关键,很多时候在于找到仅属于 某个因子的特征。(perhaps probabilistic sometimes)

Tools

openssl

分解整数工具

Python 库

gmpy2

primefac

整数分解库,包含了很多整数分解的算法。

Some conclusions

n,p,q-related Attacks

暴力分解N

N比较小的时候(看 k-bits 安全性了)可用

p & q 不当分解N

|p-q|很大

穷举、yafu 等。

|p-q|很小

Fermat factorization

复杂度 $O({\Delta^2\over 4n^{1\over 2} }),\Delta=\arrowvert p- q \arrowvert$,也就是说对于 $\Delta < n^{1\over 4}$ 都能很快分解 $n$

\[\frac{(p+q)^2}{4}-n=\frac{(p+q)^2}{4}-pq=\frac{(p-q)^2}{4}\]

则找到x>=$\sqrt{n}$,依次枚举,直到找到一个x使得$x^2\ -\ n\ =\ y^2$

质数$(x\ -\ y),(x\ +\ y)$即为p,q

光滑:由小因子构成;

以下的两个方法本质在于:能够找到 $r\ s.t.\ s\mid r$,其中 $s$ 是素数 $p$ 的某个特征,通过特征 $s$ 能够获取 $p$ 的倍数,从而获得 $gcd(n,ip) = p$。

p-1 光滑

使用 Pollard’s p − 1 算法来分解 N

原理

$p-1$ 即 $\phi(p)$ 的素因子全为小素数

  1. 找到 $r={p^{k_1}_1}…{p^{k_i}_i}$,则 $(p-1)\mid r$
  2. 选取 $a\in (1,p-1)$,由费马小定理 $a^r\equiv 1\ (mod\ p)$
  3. $gcd(a^r-1,n)=p\ if\ gcd(a^r-1,n)\in (1,n)$

实操方法

  1. 选取一系列小素数
  2. 对各个素数 $p_i$,append for j times that ${p^j_i}≤sqrt(n)\ and\ {p^{j+1}_i}>sqrt(n)$
  3. 选取 $a$,$a^{p_i}\equiv b\ (mod\ n)$ (此模域下得到的 $a$ 在求 $p$ 方面与原 $a$ 等价)
  4. 若 $gcd(b-1,n) !=1$,则求得 $p$,否则令 $a=b$,返回第3步对 $p_{i+1}$ 继续操作

参考链接

p+1 光滑

使用 Williams’ p + 1 算法来分解 N

前置知识

令 $\alpha , \beta $ 满足 $x^2 -Px +Q =0$,则定义 Lucas Functions

\[\begin{cases} U_n(P,Q)={(\alpha ^n - \beta ^n)\over(\alpha - \beta)}\\ V_n(P,Q) = (\alpha ^n + \beta ^n) \end{cases}\]

我们同时定义 $\Delta = (\alpha - \beta)^2 = P^2-4Q$,知 $P = \alpha + \beta, Q = \alpha \beta$

则我们有如下公式:

Lucas_Functions

并且引入一个定理:(可参考 An Extended Theory of Lucas’ Functions)

\[If\ p\ is\ an\ odd\ prime,\ p\nmid Q\ and\ the\ Legendre\ symbol\ ({\Delta \over p})=\epsilon\ then\\ U_{(p-\epsilon)m}(P,Q)\equiv 0\ (mod\ p)\\ V_{(p-\epsilon)m}(P,Q)\equiv 2Q^{m(1-\epsilon)\over 2}\ (mod\ p)\]

原理

首先定义一个 $R = {q^{k_1}_1}…{q^{k_i}_i}$,则 $(q+1)\mid R$

我们假设 $Q= 1\ and\ ({\Delta \over q})=-1$(此时 $\Delta = P^2 - 4$ ),那么由以上定理可知:

\[\begin{cases} q\mid U_R(P,1)\\ q\mid (V_R(P,1)-2) \end{cases}\]

那么我们只要求得 $V_R(P,1)$,问题就迎刃而解了。

而由定义知 $V_0(P,1)=2,\ V_1(P,1)=P$,由上面的公式推得,当 $Q=1$ 时有如下公式:

\[\begin{cases} V_{2f-1}\equiv V_f V_{f-1} - P\\ V_{2f}\equiv V^2_f - 2\\ V_{2f+1}\equiv PV^2_f - V_fV_{f-1} -P\\ \end{cases}\]

接下来我们表示 $ R =( \zeta_{k-1} \zeta_{k-2} … \zeta_0 )2 $ ,定义 $ R_i =( \zeta{k-1} \zeta_{k-2} … \zeta_{k-i} )_2 $,那么:

\[(V_{R_i}, V_{R_{i+1}-1})= \begin{cases} (V_{2R_i}, V_{2R_i-1})\ when\ \zeta_{k+1} =0\\ (V_{2R_i+1}, V_{2R_i})\ when\ \zeta_{k+1} =1 \end{cases}\]

这样我们就能在 $O(log(R))$ 时间复杂度内算出 $V_R$,从而获得 $q$

实操方法

  1. 选取一系列小素数

  2. 对各个素数 $p_i$, $R\ *= p_i$ for j times that ${p^j_i}≤sqrt(n)\ and\ {p^{j+1}_i}>sqrt(n)$

    (这里的 $sqrt(n)$ 只是一个大致范围)

  3. 选取 $P$,计算 $V_R$。(这里的 $\Delta$ 有约 50% 的几率是 $q$ 的非二次剩余,故无需担心概率问题)

  4. 若 $gcd(V_R-2,n)\in (1,n)$,则求得 $q$,否则返回第 3 步重新选择 $P$ 继续操作

参考链接

Implementing and Cracking the RSA Cryptosystem

A p+1 Method of Factoring

模不互素

两个/多个 N 不互素

直接求得gcd($N_1,N_2$)

共模攻击

对于同一密文 $m$

条件: $e_1,e_2$ 互素

已知

\(c_1\equiv m^{e_1}\ (mod\ N)\\c_2\equiv m^{e_2}\ (mod\ N)\) 使用exgcd求出$re_1+se_2=1$

可得

\[\begin{align*} c_{1}^{r}c_{2}^{s} &\equiv m^{re_1}m^{se_2}\ (mod\ n)\\ &\equiv m^{(re_1+se_2)}\ (mod\ n)\\ &\equiv m\ (mod\ n) \end{align*}\]

dp,e,n,c泄露

条件:$e$ 在一个可枚举的范围内;

$d_p: d_p\equiv d\ (mod\ \phi_p)$

为容易理解,以下将同余式直接写为方程形式:

\[d_p+{k_1}·\phi(p)=d\\ e·(d_p+{k_1}·\phi(p))=ed=1+{k_2}·\phi(p)·\phi(q)\\ ed_p=1+{k_2}·\phi(p)·\phi(q)-{k_1}·\phi(p)=1+\phi(p)·({k_2}·\phi(q)+{k_1})\\ and:\\ d_p<\phi(p)\\ so:\\ ed_p<e·\phi(p)\\ {1\over \phi(p)}+({k_2}·\phi(q)+{k_1})<e\]

故直接枚举 $({k_2}·\phi(q)+{k_1}) \in [0,e]$ 得到 $\phi(p) = { {ed_p-1}\over ( {k_2}·\phi(q)+{k_1} ) }$

dp,dq,p,q,c泄露

为了加速解密

\[d_p=d\ (mod\ \phi(p))\\ d_q=d\ (mod\ \phi(q))\\ m_1=c^{d_p(d)}\ (mod\ p)\\ m_2=c^{d_q(d)}\ (mod\ q)\\ Suppose\ k\ which\ makes:\ m_2+kq=m\equiv m_1\ (mod\ p)\\ So\ that:\ k\equiv q_{inv_p}(m_1-m_2)\ (mod\ p)\\ m=m_2+kq\]

e-ralated Attacks

小公钥指数攻击

穷举

条件:$e=3$ (very small)

\[\begin{align*} m &= \sqrt[3]{c+k\times n} \end{align*}\]

枚举k直到开出整数为止

for k in range(130000000):
    a , b = gmpy2.iroot(c + k * n,e)
    if(b == 1):
    	print(a)
    	exit(0)

低加密指数广播攻击

“今有物不知其数,三三数之剩二(除以3余2),五五数之剩三(除以5余3),七七数之剩二(除以7余2),问物几何?”

对于同一密文 $m$

条件:$e$ 相同,多个 $n$ 不同且互素

则变为对$m^e$使用中国剩余定理,然后暴力开次方。

中国剩余定理其实就一句话:

Rabin 算法

e 和 $\phi(n) $ 不互质,无法直接求逆元

条件:e = 2,p,q

已知:

\[c=m^2\ (mod\ n)\]
  1. 计算出

    \[m_p=c^{(p+1)\over 4}\ (mod\ p) \\m_q=c^{(q+1)\over 4}\ (mod\ q)\]

    也即(这里是一种象征性的写法)

    \[\\m_p= ±\sqrt{c}\ (±m) \ (mod\ p) \\m_q= ±\sqrt{c}\ (±m) \ (mod\ q)\]
  2. 利用中国剩余定理求得

    \[y_p·p\ +\ y_q·q = 1\]
  3. 明文即下列四项之一(可通过两边同时平方证明)

    \[\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*}\]
    • $m^2\equiv (n-m)^2\ (mod\ n)$

      • 在模域下, $a$ 并非唯一特解,也可能是$b,c,d$。

      • 通俗地说,$a,b,c,d$ 对应 $m,n-m\ (mod\ n)$

若 $p\ or\ q \equiv 1\ (mod\ 4)$,则获得 $m^2\equiv c_{p,q} \ mod(p,q)$ 解出二次剩余再用 CRT 联立即可。

e和$\phi(n)$不互素

讲了好几种算法,但 AMM 一套带走

  1. 假设 $gcd(e,\phi(n))=b$,则可表示 $e=ab$

  2. 求得 $d’=invert(a,\phi(n))$,则可求得 $m^b\equiv (m^b)^{ad’}\equiv c^{d’}\ (mod\ n)$

  3. 若 $b$ 较小可直接爆破,否则,介绍以下两种方法:(以下对 $p,q$ 均使用)

    共有 $b^ { ‘ }$组 $m \in [1,p] $ 满足

    1. 依照上面的 1、2 求得 $m^{b’} \equiv c^{d’ }\ (mod\ p)$
    2. 使用 $BV$ 求得 $m\ (mod\ p)$ 的一个特解
    3. 随机 $a$,求出模域 $p$ 的 $b’ $次单位根,即 $r_i=a^{ {p-1} \over b’ }\ (mod\ p)$,直到这 $ b’$个单位根选择完毕 (包括 1 )(可以将 $r_i^k\ mod\ p$ 也添加进 set() 直到已有重复)
    4. 对于每一组 $m_p * r_i,m_q * r_j$ 使用 $CRT$ 计算得到 $m$ (共有 $b_p’ * b_q’$ 次计算,耗时较长)

对于任意素数,其模域内均有生成元 $g$, $ord_p(g)=\phi(p)$,使得 $g^i\ne g^j $ 故对于 $q\mid \phi(p)$, 有 q 个根 $h_i=g^{i·{\phi(p)\over q } }$。

BV算法

在此仅讨论当 $r$ 不可逆时求 $r$ 次根的情况

适用条件:在有限域 $F_{p^k}$ 上,若 $r\ \mid\mid\ \phi(p^k)$ ,其中 $p$ 为素数。

如果并不 $r\ \mid\mid\ \phi(p^k)$ ,比如 $r^2\ \mid\mid\ \phi(p^k)$,那我 $c’=pow(c,r,p^k)$ 就行了。但是这样大大扩大了解集的范围,就算验证,也增加了大量时间复杂度。

可知 $(r,{ { \phi(p^k) }\over r } ) = 1$ ,求出逆元 $v$ 满足 $rv\equiv 1\ (mod\ { {\phi(p^k) }\over r } )$,求出 $m\equiv m^{rv} \equiv c ^ v\ (mod\ p^k)$ 并且对 $ m^r \equiv c\ (mod\ p^m)$ 进行验证,若成立则为解,否则解不存在。

Another method

来源:ii (whuctf root hunt official wp) <- ranwen(hackergame 2019 十次方根)

whuctf official crypto writeup

条件:$m^e\equiv c\ (mod\ n)$,已知 $c,e,n,factor_n$。目的是在 $e\arrowvert \phi(n)$ 的情况下拿到正确(所有)的 m。

为了使 m 的指数与 $\phi(n)$ 互素,可以考虑转换 $e’=e+x\ (gcd(e’,\phi(n))=1)$ ,然后求出 $invert(e’,\phi(n) )$ 进行解密。

但问题在于,由于我们不知道 $m^x$,无法随意变换 $e’$。这个时候就需要找到一个迂回的方法,使得经过某种变换后能够拿到 $m^{e’}$ 的集。故我们选择 ${x\arrowvert x\arrowvert \phi(n),gcd(e+x,\phi(n))=1 }$ (也就是说选择 $x$ 的必要条件是 $x=\Pi p_i,gcd(p_i,e)=1$)。由此可得到一个 $y={\phi(n) \over x}$,使得 $m^{(e+x)y}\equiv c^y\ (mod\ n)$。那么模域下开根得 $m^{ (e+x) } \equiv cg^{k{\phi(n)\over y} }$,其中 $g$ 是生成元、$k\in [0,y)$。那么对这些 $m^{e’}$ 求逆元即可。(最后验证 assert pow(m, e, n) == c

但这里有些问题:

如果 $y$ 太大,复杂度太高。所以我们要尽可能使得 $x$ 变大,但是直接对 $\phi(n)$ 使用该方法显然有些难度。故我们可以分别对 $\phi(p^k)$ 采用该方法,最后进行 CRT 即可。

两种方法的核心都是找到在某种情况下把指数 $e$ 转换成 invertable 找到一个特解:一种是改变 modulos,一种是改变 $e$ 使其 invertable。总之,最后都需要与单位根联系起来求出多解。

AMM

用于求取 $X^r=\delta\ in\ F_q(F_{q^m} )$ 中的一个特解 $X$

适用范围: $r\arrowvert q-1\ (\phi(q^m))$,$r, q$ 都是素数

期望时间复杂度: $O(log^4q+rlog^3q)$ (包含乘法的时间度,这个 r 应该可以优化)

原理

若 $r\arrowvert q-1$,我们令 $q-1=r^ts$,其中 $(s,r)=1$。那么通过 exgcd 我们容易找到最小自然数 $\alpha$ 满足 $s\arrowvert r\alpha -1$ 。

那么,$(\delta ^{r\alpha -1})^{r^{t-1} }=1$。这里如果 $t=1$,那么 $\delta ^ \alpha$ 就是我们要找的特解。如果不等于 1,则如下:

随机给定一个非 $r$ 次残基 $\rho$,即 $(\rho ^ s)^ { r^ {t-1} } \ne 1$,那么我们有 $(\rho ^ s)^ { i·r^ {t-1} } \ne (\rho ^ s)^ { j·r^ {t-1} }$ where $i\ne j$。

(若相等,则 $(\rho ^ s)^ {k·r^{t-1} }\equiv 1,k\in [0,r)$,显然这是不可能的。这里利用了 $r$ 是素数。)

故设 $K={K_i=(\rho ^ s)^ { i·r^ {t-1} } },i \in [0,r-1)$。易知 $K^r_i\equiv 1$。又因为 $((\delta ^{r\alpha -1})^{r^{t-2} })^r=1$,由于仅有 $r$ 个 $r$ 次残基,那么必定有且仅有 $j_1\in [0,r)$ 使得 $(\delta ^{r\alpha -1})^{r^{t-2} } = K_{r-j_1}$,这里 $K_r=K_0=1$。

那么 $(\delta ^{r\alpha -1})^{r^{t-2} } K_{j_1}=(\delta ^{r\alpha -1})^{r^{t-2} } (\rho ^ s)^ { j_1·r^ {t-1} }=1$。我们枚举或者 BSGS 之类的拿到 $j_1$ 就行。

相似地,$((\delta ^{r\alpha -1})^{r^{t-3} } (\rho ^ s)^ { j_1·r^ {t-2} })^r=1$,又可求得 $j_2,…,t-1$。故最后可知 $({\delta ^\alpha})^r ({ (\rho^s)^{j_1+j_2·r+…+j_{t-1}·r^{t-2} } } )^r=\delta$。那么 $X_0={\delta ^\alpha} { (\rho^s)^{j_1+j_2·r+…+j_{t-1}·r^{t-2} } } $ 就是一个特解。(当 $ord(\delta)>sr$ 时,有 $X_i=(\delta ^ s)^iX_0\ in\ F_q,i\in [0,r)$ 就是通解)

如果是 $F_{q^m}$ 也一样。

implement

  1. 随机选取模域 q 上的非二次剩余 ρ,并验证 $\rho ^{q-1\over r} \ne 1$。
  2. 计算 $q-1=r^ts,(r,s)=1$、最小自然数 $\alpha$ 满足 $s\arrowvert r\alpha - 1$。

设 $a=\rho^{s·r^{t-1} }, b=\delta ^{r\alpha -1}, c=\rho^s, h=1$

  1. 对于 i in range(1,t) :

    ​ 算出 $d=b^{r^{t-1-i} }$,若 d = 1, j = 0;

    ​ 否则:$j = -log_ad$(或者可以算一波逆元搞 index 降低复杂度)

    ​ $b=b·(c^r)^j,h=h·c^j,c=c^r$

最后 $\delta^\alpha·h$ 即为特解。

参考文献

Adleman-Manders-Miller Root Extraction Method Revisited, Zhengjun Cao ∗, …, …

d-ralated Attacks

d 泄露攻击

条件:已知e,d,n

  1. 设 $ed-1=k\phi(n)=t$
  2. 随机选取一个 $g \in [2,n-1]$,若 $t$ 为2的倍数,则 $t\ /=2,x=g^t$
  3. 若 $gcd(x-1,n)>1$,则 $p=gcd(x-1,n),q={n \over p}$
  4. 若直到 $t$ 为奇数都不能找到这样的 $p$,则返回第2步重新选择 $g$

Wiener’s Attack

条件:$d<{1\over 3}N^{1\over 4}$ ( $e$ is big),且 $q<p<2q$

连分数

连分数形式如下: \({a_1\over{q_1+{a_2\over{q_2+{a_3\over ...+{...\over {q_{N-1}+{a_N\over q_N} } } } } } } } = a_1/(q_1+a_2/(q_2+a_3/(...+.../(q_{N-1} + {a_N/q_N} ) ) ) )\) 我们要关注的是 $a_i=1$ 的情况,方便起见,我们定义: \(<q_0,...,q_N>=q_0+1/(q_1+1/(q_2+1/(...+.../(q_{N-1} + {1/q_N} ) ) ) ) = {a_N\over b_N}\) 若对于 $0 \le n \le N$,有 $<q_0,q_1,…,q_n>={a_n\over b_n}$ 那么称 $a_n\over b_n$ 为 $a_N\over b_N$ 的渐近连分数。

Theorem (Poincaré)

令 $u,v,a,b\in Z$, 其中 $v \ge 1, 1 \le b < v,gcd(u, v) = 1,gcd(a, b) = 1$。若 $\arrowvert {u\over v} - {p\over q} \arrowvert <{1\over 2q^2}$,那么 ${p\over q} $ 是 $u\over v$ 的一个渐近连分数。

方法

  1. 表示出 $e\over N$ 的连分数形式
  2. 用连分数的前 $i$ 项近似表示出 $e\over N$ ,即近似于 $k_i\over d_i$
  3. 验证 $k_i,d_i,etc.$ 正确性,并得到 $\phi(N)$
  4. 回到第2步或得到正确答案

证明

\[q<p<2q\ \rightarrow\ \sqrt{N}<p<\sqrt{2N}\\ so:\ N-\phi(N)=p+q-1=p+{N\over p} - 1<{3\sqrt{2}\over 2}\sqrt{N}<3\sqrt{N}\\ \begin{align} so:\ \arrowvert {e\over N}-{k\over d}\arrowvert &= \arrowvert {ed-(k\phi(N)-k\phi(N))-kN\over Nd }\arrowvert \\ &= \arrowvert {1+k(\phi(N)-N)\over Nd} \arrowvert \\ &\le \arrowvert {3k\sqrt{N}\over Nd} \arrowvert = \arrowvert {3k\over \sqrt{N}d}\arrowvert \end{align}\\ and:\ k\phi(N)=ed-1,e<\phi(N)\\ so:\ k<d<{1\over 3}N^{1\over 4}\\ so:\ \ \arrowvert {e\over N}-{k\over d}\arrowvert \le \arrowvert {3k\over \sqrt{N}d}\arrowvert < {1\over 3d^2} < {1\over 2d^2}\]

所以,利用上面的定理可以知道 ${k\over d}$ 完美覆盖 ${e\over N}$。(经实验测试,如果 $e>\phi(N)$,且满足其他条件,wiener 也是可行的。这说明以上准则只是充分条件。)

Boneh and Durfee attack

条件:$d≤N^{0.292}$

待补充

Chosen Plain Cipher Attacks

选择明文攻击

条件:可多次发送明文,返回密文;不知道 n, e。

$e$ 可以用 BSGS 恢复

获得 $n$ : 比如可以加密2,4,8,16,etc: \(c_2\equiv 2^e\ (mod\ n)\\ c_4\equiv 4^e\ (mod\ n)\\ c_8\equiv 8^e\ (mod\ n)\\ So:\\ c^2_2\equiv c_4\ (mod\ n)\\ c^2_3\equiv c_8\ (mod\ n)\\ So:\\ c^2_2-c_4=in\ (when\ c^2_2>n)\\ c^2_3-c_8=jn\ (so\ is\ it)\\ n\ may\ be\ gcd(c^2_2-c_4,c^2_3-c_8)\)

任意密文解密(RSA的同态性)

条件:可发送任意密文,返回明文;知道 $n,e$

已知:$c\equiv m^e\ (mod\ n)$,求 $m$

  1. 选择 $X,gcd(X,n)=1$
  2. 计算 $Y\equiv c·X^e\ (mod\ n)$
  3. 选择密文攻击得到:$Z\equiv Y^d\equiv m·X\ (mod\ n)$
  4. 求出 $X^{-1}\ (mod\ n)$,则 $m\equiv Z·X^{-1}\ (mod\ n)$

RSA Parity Oracle(都是利用同态)

条件:可多次发送密文,返回模域下明文的奇偶性,也即 least significant bit

复杂度: $O(logn) $

原理

利用模域的特性

第一次发送 $c*2^e\equiv (2m)^e\ (mod\ n)$,若返回奇数,说明 $2m>n$,即 $ {n\over 2} < m < n$;否则 $0<m < {n\over 2}$

假设返回奇数:

第二次发送 $(c*2^e) *2^e \equiv (2·2m)^e\ (mod\ n)$,若返回奇数,说明 $2·(2m-n)>n$,即 $ {3n\over 4} < m < n$;否则 ${n\over 2} <m< {3n\over 4}$

······

返回偶数同理。

过程

l = 0,r = n
mul = pow(2, e, n)
k = n.bit_length()
for i in range(k):
    c = c * mul % n
    rr.sendline(c)
    if rr.recvline(keepends = False) == '1':
        l = l + r >> 1
    else:
        r = l + r >> 1

RSA Byte Oracle

对于以上的拓展

假设返回最后 i bits,只需要 $log_{2^i}n$ 次即可求出明文。

下以返回最后 1 byte (8 bits / within 256) 为例:

原理

由于 $256m\ (mod\ n)=256m - kn,k \in [0,256)$,则对于不同的 $k_1,k_2$,有 $\vert k_1-k_2\vert \in (0,256)$,若 $gcd(n,256)=1$ 则有 $\vert k_1n-k_2n \vert \not\equiv 0\ (mod\ 256)$,也就是说 $256m - kn\ (mod\ 256)$ 得到的值是独一无二的。

则对于每一个 $k$,建立 $-kn\ (mod\ 256)\rightarrow k$ 的单射:

第一次发送 $c*256^e\equiv (256m)^e\ (mod\ n)$,返回 least 8 bits 也即 $256m\ (mod\ n)\ (mod\ 256)$,则找到对应的 $k$,说明 $256m \in [kn,(k+1)n)$,即 $m \in [{kn\over 256},{kn\over 256}+{n\over 256} )$

第二次发送 $(c*256^e) *256^e \equiv (256·256m)^e\ (mod\ n)$,返回 $ [256·(256m\ (mod\ n) ) ] \ (mod\ n) \ (mod\ 256)$,则找到对应的 $k’$,说明 $[256·(256m\ (mod\ n) ) ] \in [k’n,(k’+1)n)$,即 $m \in [{kn\over 256}+{k’n\over 256^2},{kn\over 256}+{k’n\over 256^2}+{n\over 256^2} )$

······

过程

mp = {}
for i in range(256):
    mp[((-i * n % 256) + 256) % 256] = i
mul = pow(256, e, n),div = 1,ans = 0
k = log(n, 256) + 1
for i in range(k):
    c = c * mul % n
    div *= 256
    rr.sendline(c)
    reminder = rr.recvline(keepends = False)
    ans += mp[reminder] * n // div

RSA Length Oracle

条件:可多次发送密文,返回模域下明文的长度。

原理

和上面这些差不多,只不过是 MSB。

OTHERS

利用了 $(a+b)^3$ 的系数为 1 3 3 1,当然平方也可。

已知: \(c_1=m^3\ (mod\ n)\\ c_2=(am+b)^3\ (mod\ n)\\ a,b\) 则有如下过程: \(c_2\equiv a^3b^3+3a^2m^2b+3amb^2+b^3\\ c_2-a^3m^3+2b^3\equiv 3b(a^2m^2+amb+b^2)\\ and:\ a^3m^3-b^3=(am-b)(a^2m^2+amb+b^2)\\ so:m\equiv { { {3b(a^3c_1-b^3)\over (c_2-a^3c_1+2b^3)}+b }\over a}\ (mod\ n)\)

当 e=5,有:

e=5

当 e 很大,我们尝试通过 $gcd(x^e-c_1,(ax+b)^e-c_2)$ 得到有关 x 的线性多项式求解。

当 e > 5, 可以用 Coppersmith’s short-pad attack,此处不提。

进一步的 attack:A New Related Message Attack on RSA

通解详见本篇博文,写的很好:https://xz.aliyun.com/t/6813

quadratic residue known on n

If we can get $r$ from the server s.t. $r^2\equiv A\ (mod\ n)$, then we have a large probability to factor n.

Because we can set $r$ to get A satisfying $r^2\equiv A\ (mod\ n)$ and get another $r’$ from the server with a probability about 3/4.

If $abs(r)!=abs(r’)$, then $gcd(r-r’,n)$ or $gcd(r+r’,n)$ might be one factor of n (2/3).

p = xB + y, q = yB + x

例如 $p=\stackrel{———}{abcd}, q=\stackrel{———}{cdba}$。参考自:https://crypto.stackexchange.com/questions/68562/rsa-danger-of-using-p-to-create-q

我们有:$n=xyB^2+(x^2+y^2)B+xy$

那么我们可以得到 $xy\ mod\ B = n\ mod\ B$

又有: \({(n - B^2(xy \bmod B)) \over B^3} = \lfloor{xy\over B} \rfloor + {x^2 \over B^2} + {y^2 \over B^2} + {xy \over B^3} \in (\lfloor{xy\over B} \rfloor, \lfloor{xy\over B} \rfloor+3)\) 那么我们得到 \(a=xy-iB=xy\ mod\ B\\ i=(xy/ B)={(n - B^2(xy \bmod B)) \over B^3} - \epsilon,\epsilon \in (0,3)\\ so:\ xy=a+iB\) 又:$(x±y)^2={n-xyB^2-xy\over B}±2xy$ 那么我们可以得到 $x,y$ 并且分解 $n$。

当然,(在某些情况下)也有更简单的做法,👴在此不想说了。

$gcd(\phi(p),\phi(q))=\beta$

FURTHER ATTACKS ON SERVER-AIDED RSA CRYPTOSYSTEMS

$p=x\beta+1,q=y\beta+1$;

故 $N=xy\beta^2+(x+y)\beta+1$,

故 ${(N-1)\over \beta}=xy\beta+(x+y)=u\beta+v,0\le v<\beta$($u,v\ are\ able\ to\ compute$),

故可设 $x+y=v+c\beta,xy=u-c$,故问题转换为寻找到 $c$,当 $p,q$ 接近时,$x,y\approx {\sqrt{N} \over \beta}$,又知 $c\beta \le x+y$,故可知 $c$ 的上界约为 $C={\sqrt{N}\over \beta^2 }$。

有 $\forall a^{u\beta}=a^{xy\beta+c\beta}\equiv (a^\beta)^c\ mod\ N$,这样一来 BSGS 就行。

时间复杂度是 $O({N^{1\over 4}\over \beta})$。