由浅入深,着重介绍攻击手段。本篇主要讲解一些经典的 textbook RSA 攻击方法。
分而解之。
基本原理
-
选取两个(多个)大质数 $p,q$,计算 $N = p * q$
- 关键在于使 $p,q$ 难以得到
- 求得 $ \phi(N) = \phi(p) * \phi(q) = (p - 1) * (q - 1)$
- 特殊情况如下:
- 选择 $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
分解整数工具
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$
由
\[\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$ 光滑,则 $p-1$ 即 $\phi(p)$ 的素因子全为小素数
- 找到 $r={p^{k_1}_1}…{p^{k_i}_i}$,则 $(p-1)\mid r$
- 选取 $a\in (1,p-1)$,由费马小定理 $a^r\equiv 1\ (mod\ p)$
- $gcd(a^r-1,n)=p\ if\ gcd(a^r-1,n)\in (1,n)$
实操方法
- 选取一系列小素数
- 对各个素数 $p_i$,append for j times that ${p^j_i}≤sqrt(n)\ and\ {p^{j+1}_i}>sqrt(n)$
- 选取 $a$,$a^{p_i}\equiv b\ (mod\ n)$ (此模域下得到的 $a$ 在求 $p$ 时与原 $a$ 等价)
- 若 $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:
\[U_n(P,Q)={(\alpha ^n - \beta ^n)\over(\alpha - \beta)}\\ V_n(P,Q) = (\alpha ^n + \beta ^n)\]我们同时定义 $\Delta = (\alpha - \beta)^2 = P^2-4Q$,知 $P = \alpha + \beta, Q = \alpha \beta$
则我们有如下公式:
并且引入一个定理:(可参考 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$ ),那么由以上定理可知:
\[q\mid U_R(P,1)\\ q\mid (V_R(P,1)-2)\]那么我们只要求得 $V_R(P,1)$,问题就迎刃而解了。
而由定义知 $V_0(P,1)=2,\ V_1(P,1)=P$,由上面的公式推得,当 $Q=1$ 时有如下公式:
\[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\\\]接下来我们表示 $ 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})= (V_{2R_i}, V_{2R_i-1})\ when\ \zeta_{k+1} =0\\ (V_{2R_i+1}, V_{2R_i})\ when\ \zeta_{k+1} =1\]这样我们就能在 $O(log(R))$ 时间复杂度内算出 $V_R$,从而获得 $q$
实操方法
-
选取一系列小素数
-
对各个素数 $p_i$, $R\ *= p_i$ for j times that ${p^j_i}≤sqrt(n)\ and\ {p^{j+1}_i}>sqrt(n)$
(这里的 $sqrt(n)$ 只是一个大致范围)
-
选取 $P$,计算 $V_R$。(这里的 $\Delta$ 有约 50% 的几率是 $q$ 的非二次剩余,故无需担心概率问题)
-
若 $gcd(V_R-2,n)\in (1,n)$,则求得 $q$,否则返回第 3 步重新选择 $P$ 继续操作
参考链接
Implementing and Cracking the RSA Cryptosystem
模不互素
两个/多个 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*}\]- 若幂数为负,需把 $c$ 转化为逆元,则 $c^s={1\over c}^{-s}$
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
小公钥指数攻击
穷举
\[\begin{align*} m &= \sqrt[3]{c+k\times n} \end{align*}\]条件:$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
已知:
\[c=m^2\ (mod\ n)\]-
计算出
\[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)\] -
利用中国剩余定理求得
\[y_p·p\ +\ y_q·q = 1\] -
明文即下列四项之一(可通过两边同时平方证明)
\[\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 一套带走
-
假设 $gcd(e,\phi(n))=b$,则可表示 $e=ab$
-
求得 $d’=invert(a,\phi(n))$,则可求得 $m^b\equiv (m^b)^{ad’}\equiv c^{d’}\ (mod\ n)$
-
若 $b$ 较小可直接爆破,否则,介绍以下两种方法:(以下对 $p,q$ 均使用)
共有 $b^ { ‘ }$组 $m \in [1,p] $ 满足
- 依照上面的 1、2 求得 $m^{b’} \equiv c^{d’ }\ (mod\ p)$
- 使用 $BV$ 求得 $m\ (mod\ p)$ 的一个特解
- 随机 $a$,求出模域 $p$ 的 $b’ $次单位根,即 $r_i=a^{ {p-1} \over b’ }\ (mod\ p)$,直到这 $ b’$个单位根选择完毕 (包括 1 )(可以将 $r_i^k\ mod\ p$ 也添加进 set() 直到已有重复)
- 对于每一组 $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 十次方根)
条件:$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
- 随机选取模域 q 上的非二次剩余 ρ,并验证 $\rho ^{q-1\over r} \ne 1$。
- 计算 $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$
-
对于 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
- 设 $ed-1=k\phi(n)=t$
- 随机选取一个 $g \in [2,n-1]$,若 $t$ 为2的倍数,则 $t\ /=2,x=g^t$
- 若 $gcd(x-1,n)>1$,则 $p=gcd(x-1,n),q={n \over p}$
- 若直到 $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$ 的一个渐近连分数。
方法
- 表示出 $e\over N$ 的连分数形式
- 用连分数的前 $i$ 项近似表示出 $e\over N$ ,即近似于 $k_i\over d_i$
- 验证 $k_i,d_i,etc.$ 正确性,并得到 $\phi(N)$
- 回到第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\]
证明
\[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$
- 选择 $X,gcd(X,n)=1$
- 计算 $Y\equiv c·X^e\ (mod\ n)$
- 选择密文攻击得到:$Z\equiv Y^d\equiv m·X\ (mod\ n)$
- 求出 $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})$。