search

模数相关攻击

hashtag
暴力分解 N

hashtag
攻击条件

在 N 的比特位数小于 512 的时候，可以采用大整数分解的策略获取 p 和 q。

hashtag
JarvisOJ - Easy RSA

这里我们以 "JarvisOJ - Easy RSA" 为例进行介绍，题目如下

还记得 veryeasy RSA 吗？是不是不难？那继续来看看这题吧，这题也不难。 已知一段 RSA 加密的信息为：0xdc2eeeb2782c 且已知加密所用的公钥： N=322831561921859 e = 23 请解密出明文，提交时请将数字转化为 ascii 码提交 比如你解出的明文是 0x6162，那么请提交字符串 ab 提交格式：PCTF{明文字符串}

可以看出，我们的 N 比较小，这里我们直接使用 factordb 进行分解，可以得到

322831561921859=13574881×23781539322831561921859 = 13574881 \times 23781539

进而我们简单编写程序如下

import gmpy2
p = 13574881
q = 23781539
n = p * q
e = 23
c = 0xdc2eeeb2782c
phin = (p - 1) * (q - 1)
d = gmpy2.invert(e, phin)
p = gmpy2.powmod(c, d, n)
tmp = hex(p)
print tmp, tmp[2:].decode('hex')

结果如下

hashtag
p & q 不当分解 N

hashtag
攻击条件

当 RSA 中 p 和 q 选取不当时，我们也可以进行攻击。

hashtag
|p-q| 很大

当 p-q 很大时，一定存在某一个参数较小，这里我们假设为 p，那么我们可以通过穷举的方法对模数进行试除，从而分解模数，得到保密参数与明文信息。基本来说，不怎么可行。

hashtag
|p-q| 较小

首先

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

既然 |p-q| 较小，那么 $\frac{(p-q)^2}{4}$ 自然也比较小，进而 $\frac{(p+q)^2}{4}$ 只是比 N 稍微大一点，所以 $\frac{p+q}{2}$ 与 $\sqrt{n}$ 相近。那么我们可以按照如下方法来分解

  • 顺序检查 $\sqrt{n}$ 的每一个整数 x，直到找到一个 x 使得 $x^2-n$ 是平方数，记为 $y^2$

  • 那么 $x^2-n=y^2$，进而根据平方差公式即可分解 N

hashtag
p - 1 光滑

  • 光滑数(Smooth number)：指可以分解为小素数乘积的正整数

  • 当$p$是$N$的因数，并且$p-1$是光滑数，可以考虑使用Pollard's p-1算法来分解$N$

  • 根据费马小定理有

    若p∤a, 则ap−1≡1(modp)若p\nmid a,\ 则a^{p-1}\equiv 1\pmod{p}

    则有

    at(p−1)≡1t≡1(modp)a^{t(p-1)}\equiv 1^t \equiv 1\pmod{p}

    即

    at(p−1)−1=k∗pa^{t(p-1)} - 1 = k*p

  • 根据Pollard's p-1算法：

    如果$p$是一个$B-smooth\ number$，那么则存在

    M=∏q≤Bq⌊log⁡qB⌋M = \prod_{q\le{B}}{q^{\lfloor\log_q{B}\rfloor}}

    使得

    (p−1)∣M(p-1)\mid M

    成立，则有

    gcd⁡(aM−1,N)\gcd{(a^{M}-1, N)}

    如果结果不为$1$或$N$，那么就已成功分解$N$。

    因为我们只关心最后的gcd结果，同时N只包含两个素因子，则我们不需要计算$M$，考虑$n=2,3,\dots$，令$M = n!$即可覆盖正确的$M$同时方便计算。

  • 在具体计算中，可以代入降幂进行计算

  • Python代码实现

hashtag
p + 1 光滑

  • 当$p$是$N$的因数，并且$p+1$是光滑数，可以考虑使用Williams's p+1算法来分解$N$

  • 已知$N$的因数$p$，且$p+1$是一个光滑数

    p=(∏i=1kqiαi)+1p = \left(\prod_{i=1}^k{q_i^{\alpha_i}}\right)+1

    $q_i$即第$i$个素因数且有$q_i^{\alpha_i}\le B_1$, 找到$\beta_i$使得让$q_i^{\beta_i}\le B_1$且$q_i^{\beta_i+1}> B_1$，然后令

    R=∏i=1kqiβiR = \prod_{i=1}^k{q_i^{\beta_i}}

    显然有$p-1\mid R$且当$(N, a) = 1$时有$a^{p-1}\equiv 1 \pmod{p}$，所以有$a^R\equiv 1\pmod{p}$，即

    p∣(N,aR−1)p\mid(N, a^R-1)

  • 令$P,Q$为整数，$\alpha,\beta$为方程$x^2-Px+Q=0$的根，定义如下类卢卡斯序列

    Un(P,Q)=(αn−βn)/(α−β)Vn(P,Q)=αn+βn\begin{aligned} U_n(P, Q) &= (\alpha^n -\beta^n)/(\alpha - \beta)\\ V_n(P, Q) &= \alpha^n + \beta^n \end{aligned}

    同样有$\Delta = (\alpha - \beta)^2 = P^2-4Q$，则有

    {Un+1=PUn−QUn−1Vn+1=PVn−QVn−1(2.2)\begin{cases} U_{n+1} &= PU_n - QU_{n-1}\\ V_{n+1} &= PV_n - QV_{n-1} \end{cases}\tag{2.2}
    {U2n=VnUnV2n=Vn2−2Qn(2.3)\begin{cases} U_{2n} &= V_nU_n\\ V_{2n} &= V_n^2 - 2Q^n \end{cases}\tag{2.3}
    {U2n−1=Un2−QUn−12V2n−1=VnVn−1−PQn−1(2.4)\begin{cases} U_{2n-1} &= U_n^2 - QU_{n-1}^2\\ V_{2n-1} &= V_nV_{n-1} - PQ^{n-1} \end{cases}\tag{2.4}
    {ΔUn=PVn−2QVn−1Vn=PUn−2QUn−1(2.5)\begin{cases} \Delta U_{n} &= PV_n - 2QV_{n-1}\\ V_{n} &= PU_n - 2QU_{n-1} \end{cases}\tag{2.5}
    {Um+n=UmUn+1−QUm−1UnΔUm+n=VmVn+1−QVm−1Vn(2.6)\begin{cases} U_{m+n} &= U_mU_{n+1} - QU_{m-1}U_n\\ \Delta U_{m+n} &= V_mV_{n+1} - QV_{m-1}V_n \end{cases}\tag{2.6}
    {Un(Vk(P,Q),Qk)=Unk(P,Q)/Uk(P,Q)Vn(Vk(P,Q),Qk)=Vn(P,Q)(2.7)\begin{cases} U_{n}(V_k(P, Q), Q^k) &= U_{nk}(P, Q)/U_k(P, Q)\\ V_{n}(V_k(P, Q), Q^k) &= V_n(P, Q) \end{cases}\tag{2.7}

    同时我们有如果$(N, Q) = 1$且$P^{'}Q\equiv P^2-2Q\pmod{N}$，则有$P^{'}\equiv \alpha/\beta + \beta/\alpha$以及$Q^{'}\equiv \alpha/\beta + \beta/\alpha = 1$，即

    U2m(P,Q)≡PQm−1Um(P′,1)(modN)(2.8)U_{2m}(P, Q)\equiv PQ^{m-1}U_m(P^{'}, 1)\pmod{N}\tag{2.8}

    根据扩展卢卡斯定理

    如果p是奇素数，$p\nmid Q$且勒让德符号$(\Delta/p) = \epsilon$，则

    U(p−ϵ)m(P,Q)≡0(modp)V(p−ϵ)m(P,Q)≡2Qm(1−ϵ)/2(modp)\begin{aligned} U_{(p-\epsilon)m}(P, Q) &\equiv 0\pmod{p}\\ V_{(p-\epsilon)m}(P, Q) &\equiv 2Q^{m(1-\epsilon)/2}\pmod{p} \end{aligned}

  • 第一种情况：已知N的因数p，且p+1是一个光滑数

    p=(∏i=1kqiαi)−1p = \left(\prod_{i=1}^k{q_i^{\alpha_i}}\right)-1

    有$p+1\mid R$，当$(Q, N)=1$且$(\Delta/p) = -1$时有$p\mid U_R(P, Q)$，即$p\mid (U_R(P, Q), N)$

    为了找到$U_R(P, Q)$，Guy和Conway提出可以使用如下公式

    U2n−1=Un2−QUn2−1U2n=Un(PUn−2QUn−1)U2n+1=PU2n−QU2n−1\begin{aligned} U_{2n-1} &= U_n^2 - QU_n^2 - 1\\ U_{2n} &= U_n(PU_n - 2QU_{n-1})\\ U_{2n+1} &= PU_{2n} - QU_{2n-1} \end{aligned}

    但是上述公式值太大了，不便运算，我们可以考虑如下方法

    如果$p \mid U_R(P, 1)$，根据公式2.3有$p\mid U_{2R}(P, Q)$，所以根据公式2.8有$p \mid U_R(P^{'}, 1)$，设$Q=1$，则有

    V(p−ϵ)m(P,1)≡2(modp)V_{(p-\epsilon)m}(P, 1) \equiv 2\pmod{p}

    即，如果$p\mid U_R(P, 1)$，则$p\mid(V_R(P, 1) -2)$.

    第一种情况可以归纳为：

    让$R = r_1r_2r_3\cdots r_m$，同时找到$P_0$使得$(P_0^2-4, N) = 1$，定义$V_n(P) = V_n(P, 1), U_n(P) = U_n(P, 1)$且

    Pj≡Vrj(Pj−1)(modN)(j=1,2,3,…,m)P_j \equiv V_{r_j}(P_{j-1})\pmod{N}(j = 1,2,3,\dots,m)

    根据公式2.7，有

    Pm≡VR(P0)(modN)(3.1)P_m \equiv V_R(P_0)\pmod{N}\tag{3.1}

    要计算$V_r = V_r(P)$可以用如下公式

    根据公式2.2，公式2.3，公式2.4有

    {V2f−1≡VfVf−1−PV2f≡Vf2−2V2f+1≡PVf2−VfVf−1−P(mod()N)\begin{cases} V_{2f-1}&\equiv V_fV_{f-1}-P\\ V_{2f}&\equiv V_f^2 - 2\\ V_{2f+1}&\equiv PV_f^2-V_fV_{f-1}-P\pmod(N) \end{cases}

    令

    r=∑i=0tbt2t−i    (bi=0,1)r = \sum_{i=0}^t{b_t2^{t-i}}\ \ \ \ (b_i=0,1)

    $f_0=1, f_{k+1}=2f_k+b_{k+1}$，则$f_t=r$，同样$V_0(P) = 2, V_1(P) = P$，则最终公式为

    (Vfk+1,Vfk+1−1)={(V2fk,V2fk−1)    if bk+1=0(V2fk+1,V2fk)    if bk+1=1(V_{f_{k+1}}, V_{f_{k+1}-1}) = \begin{cases} (V_{2f_k}, V_{2f_k-1})\ \ \ \ if\ b_{k+1}=0\\ (V_{2f_k+1}, V_{2f_k})\ \ \ \ if\ b_{k+1}=1 \end{cases}

  • 第二种情况：已知p+1是一个光滑数

    p=s(∏i=1kqiαi)−1p = s\left(\prod_{i=1}^k{q_i^{\alpha_i}}\right)-1

    当$s$是素数，且$B_1<s\le B_2$，有$p\mid(a_m^s-1, N)，$定义$s_j$和$2d_j$

    2dj=sj+1−sj2d_j = s_j+1-s_j

    如果$(\Delta/p) = -1$且$p\nmid P_m-2$，则根据公式2.7和公式3.1有$p\mid(U_s(P_m), N)$。

    令$U[n] \equiv U_n(P_m), V[n]\equiv V_n(P_m)\pmod{N}$，计算$U[2d_j-1], U[2d_j], U[2d_j+1]$通过

    U[0]=0,U[1]=1,U[n+1]=PmU[n]−U[n−1]U[0] = 0, U[1] = 1, U[n+1] = P_mU[n] - U[n-1]

    计算

    T[si]≡ΔUsi(Pm)=ΔUsiR(P0)/UR(P0)(modN)T[s_i] \equiv \Delta U_{s_i}(P_m) = \Delta U_{s_iR}(P_0)/U_R(P_0)\pmod{N}

    通过公式2.6，公式2.7和公式3.1有

    {T[s1]≡PmV[s1]−2V[s1−1]T[s1−1]≡2V[s1]−PmV[s1−1](modN)\begin{cases} T[s_1]&\equiv P_mV[s_1]-2V[s_1-1]\\ T[s_1-1]&\equiv 2V[s_1]-P_mV[s_1-1]\pmod{N} \end{cases}

    即

    {T[si+1]≡T[si]U[2di+1]−T[si−1]U[2di]T[si+1−1]≡T[si]U[2di]−T[si−1]U[2di−1](modN)\begin{cases} T[s_{i+1}]&\equiv T[s_i]U[2d_i+1]-T[s_i-1]U[2d_i]\\ T[s_{i+1}-1]&\equiv T[s_i]U[2d_i]-T[s_i-1]U[2d_i-1]\pmod{N} \end{cases}

    计算$T[s_i], i=1,2,3\dots$，然后计算

    Ht=(∏i=0cT[si+t],N)H_t = (\prod_{i=0}^c{T[s_{i+t}], N})

    其中$t = 1, c+1, 2c+1, \dots, c[B_2/c]+1$，我们有$p\mid H_i$当$(\Delta/p)=-1$

  • python代码实现

hashtag
2017 SECCON very smooth

该程序给了一个 HTTPS 加密的流量包，首先从其中拿到证书

这里分别查看三个证书，三个模数都一样，这里只给一个例子

可以看出模数只有 1024 比特。而且，根据题目名 very smooth，应该是其中一个因子比较 smooth，这里我们利用 primefac 分别尝试 Pollard's p − 1 与 Williams's p + 1 算法，如下

可以发现当使用 Williams's p + 1 算法时，就直接分解出来了。按道理这个因子是 p-1 似乎更光滑，但是却并不能使用 Pollard's p − 1 算法分解，这里进行进一步的测试

可以看出，对于 p-1 确实有很多小因子，但是个数太多，这就会使得进行枚举的时候出现指数爆炸的情况，因此没有分解出来。

进而根据分解出来的数构造私钥

最后，将私钥导入到 wireshark 中即可得到明文（Edit -> Preferences -> Protocols -> SSL -> RSA Key List）。

hashtag
扩展

关于更多的一些分解模数 N 的方法可以参考 https://en.wikipedia.org/wiki/Integer_factorization。

hashtag
模不互素

hashtag
攻击原理

当存在两个公钥的 N 不互素时，我们显然可以直接对这两个数求最大公因数，然后直接获得 p，q，进而获得相应的私钥。

hashtag
SCTF RSA2

这里我们以 SCTF rsa2 为例进行介绍。直接打开 pcap 包，发现有一堆的消息，包含 N 和 e，然后试了试不同的 N 是否互素，我试了前两个

结果发现竟然不互素。

那么我们就可以直接来解密了，这里我们利用第一对公钥密码。代码如下

最后解密如下

解压压缩包即可。

hashtag
共模攻击

hashtag
攻击条件

当两个用户使用相同的模数 N、不同的私钥时，加密同一明文消息时即存在共模攻击。

hashtag
攻击原理

设两个用户的公钥分别为 $e_1$ 和 $e_2$，且两者互质。明文消息为 $m$，密文分别为：

c1=me1 mod Nc2=me2 mod Nc_1 = m^{e_1}\bmod N \\ c_2 = m^{e_2}\bmod N

当攻击者截获 $c_1$ 和 $c_2$ 后，就可以恢复出明文。用扩展欧几里得算法求出 $re_1+se_2=1\bmod n$ 的两个整数 $r$ 和 $s$，由此可得：

c1rc2s≡mre1mse2 mod n≡m(re1+se2) mod n≡m mod n\begin{align*} c_{1}^{r}c_{2}^{s} &\equiv m^{re_1}m^{se_2}\bmod n\\ &\equiv m^{(re_1+se_2)} \bmod n\\ &\equiv m\bmod n \end{align*}

hashtag
XMan 一期夏令营课堂练习

题目描述：

题目来源：XMan 一期夏令营课堂练习

可以看出两个公钥的 N 是一样的，并且两者的 e 互素。写一个脚本跑一下：

得到

这时候需要考虑当时明文是如何转化为这个数字了，一般来说是 16 进制转换，ASCII 字符转换，或者 Base64 解密。这个应该是 ASCII 字符转换，进而我们使用如下代码得到 flag

这里之所以使用 1 来判断是否为三位长度，是因为 flag 一般都是明文字符，而 1 开头的长度为 1 或者 2 的数字，一般都是不可见字符。

flag

hashtag
题目

  • Jarvis OJ very hard RSA

Previous公钥指数相关攻击NextBleichenbacher's attack

Last updated