由浅入深，着重介绍攻击手段。本篇主要讲解一些经典的 textbook RSA 攻击方法。

• 基本原理
  • Tools
    • openssl
    • 分解整数工具
    • Python 库
      • gmpy2
      • primefac
  • Some conclusions
• n,p,q-related Attacks
  • 暴力分解N
  • p & q 不当分解N
    • |p-q|很大
    • |p-q|很小
      • Fermat factorization
    • p-1 光滑
      • 原理
      • 实操方法
      • 参考链接
    • p+1 光滑
      • 前置知识
      • 原理
      • 实操方法
      • 参考链接
  • 模不互素
  • 共模攻击
  • dp,e,n,c泄露
  • dp,dq,p,q,c泄露
• e-ralated Attacks
  • 小公钥指数攻击
    • 穷举
    • 低加密指数广播攻击
    • Rabin 算法
  • e和$\phi(n)$不互素
    • BV算法
    • Another method
    • AMM
      • 原理
      • implement
      • 参考文献
• d-ralated Attacks
  • d 泄露攻击
  • Wiener’s Attack
    • 连分数
    • Theorem (Poincaré)
    • 方法
    • 证明
  • Boneh and Durfee attack
• Chosen Plain Cipher Attacks
  • 选择明文攻击
  • 任意密文解密（RSA的同态性）
  • RSA Parity Oracle（都是利用同态）
    • 原理
    • 过程
  • RSA Byte Oracle
    • 原理
    • 过程
  • RSA Length Oracle
    • 原理
• OTHERS
  • Related Message Attack
  • quadratic residue known on n
  • p = xB + y, q = yB + x
  • $gcd(\phi(p),\phi(q))=\beta$

分而解之。

基本原理

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))$

• $(N,e)$ 为公钥，$(N,d)$ 为私钥

• $m$ 为明文，$c$ 为密文，$s$ 为签名

• \[a^{\phi(b)}\equiv1\ (mod\ b)\]

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

Tools

openssl

• 查看公钥文件

  openssl rsa -pubin -in pubkey.pem -text -modulus
  

• 解密

  openssl rsautl -decrypt -inkey private.pem -in flag.enc -out flag
  

分解整数工具

• 网站分解，factor.db
• yafu

Python 库

gmpy2

• gmpy2.iroot(a, b)，返回一个元组 (x, y)，其中 x 为 a 开 b 次方的值，y 是判断 x 是否为整数的布尔型变量

primefac

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

Some conclusions

• 

• 若p,q为质数，有

  \[p^q\equiv\ p\ (mod\ p*q)\]

• 若a,b互素，有

  \[a^{\phi(b)}+b^{\phi(a)}\equiv1\ (mod\ a*b)\]

• 若p为质数，有

  \[(p-1)!\ \equiv -1\ (mod\ p)\\\]

• 若p为质数，且 $p\equiv 3\ (mod\ 4)$，有

  \[({p-1 \over 2})!\equiv ±-1\ (mod\ p)\]

• 二次剩余

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$

由

则找到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$ 光滑，则 $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}$ 继续操作

参考链接

• Mathematical attack on RSA

• Smooth As Silk

p+1 光滑

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

前置知识

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

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

则我们有如下公式：

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

原理

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

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

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

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

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

这样我们就能在 $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$

可得

• 若幂数为负，需把 $c$ 转化为逆元，则 $c^s={1\over c}^{-s}$

dp,e,n,c泄露

条件：$e$ 在一个可枚举的范围内；

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

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

故直接枚举 $({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泄露

为了加速解密

e-ralated Attacks

小公钥指数攻击

穷举

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

枚举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$使用中国剩余定理（CRT），然后暴力开次方。

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

• 令$N=\Pi{n_i}$，求得$t_i$满足${N\over n_i}t_i\equiv1\ (mod\ n_i)$，则可得一特解为$x=\sum_{i=1}^{num}c_i{N\over n_i}t_i$，通解为$x+i*N$。（前提：$n_i$ 两两互素）

  • 这里取 $\sum\limits_{i=1}^{num} c_i{N\over n_i}^{\phi_{n_i}}$ 亦可。

Rabin 算法

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

条件：e = 2，p，q

已知：

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\equiv q\equiv 3\ (mod\ 4)$ 使$c^ {(p+1)\over 4} $为整数，如此才可使$c ^ {(p+1)\over 4} \equiv 1\ (mod\ p)$，$q$ 同理

若 $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’$ 次计算，耗时较长)

• 对于拥有多个 $n$ 的情况，可以选择 $b’$ 最小的一组 $p,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 找到一个特解：一种是改变 modulus，一种是改变 $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$

• 原理如下：

  \[t=i·2^{s}\\ Suppose:\\g^t\equiv 1\ (mod\ n)\\which\ means:\\ (g^{t \over 2} - 1)·(g^{t \over 2} + 1)\equiv 0\ (mod\ n)\\\]

  若 $gcd(g^{t\over 2}-1,n)$ 是 $n$ 的一个非平凡因子，则可分解出 $n$

  即，若 g 对 p, q 的阶对2的底不同，是 $2^ia,2^jb,i>j$，则当 $j\le t < i$，有 $g^t\ne 1\%p,g^t=1\%q$，则 g^t - 1 (%n) 的因子仅包含 q 而无 p，故可分解。（xialow哥哥yyds）

  • 实操中无需验证 $g^t$

• 如果一次随机选取 $g$ 难以找到，那么就多来几次，或者直接让 $g$ 从 2 开始枚举。

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} - {a\over b} \arrowvert <{1\over 2b^2}$，那么 ${a\over b} $ 是 $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步或得到正确答案

• 原理如下：

  \[ed-k\phi(N)=1\\ {e\over \phi(N)}-{k\over d}={1\over d\phi(N)}\\ ({1\over d\phi(N)}\ is\ a\ small\ value)\\ \phi(N)=(p-1)(q-1)=N-p-{N\over p}+1\\ p^2-(N+1-\phi(N))p-N=0\]

证明

所以，利用上面的定理可以知道 ${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) $

原理

利用模域的特性

• $n$ 是奇数，$(2^tm) ^e$ 是偶数

第一次发送 $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) 为例：

原理

• $n$ 是奇数，$(256^tm) ^e$ 是偶数

• 前提： $m<n$，$gcd(256,n)=1$。

由于 $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

Related Message Attack

利用了 $(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 很大，我们尝试通过 $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

条件：已知 $\beta$

$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})$。