暴力分解 N
攻击条件
在 N 的比特位数小于 512 的时候，可以采用大整数分解的策略获取 p 和 q。
JarvisOJ - Easy RSA
这里我们以 "JarvisOJ - Easy RSA" 为例进行介绍，题目如下
还记得 veryeasy RSA 吗？是不是不难？那继续来看看这题吧，这题也不难。
已知一段 RSA 加密的信息为：0xdc2eeeb2782c 且已知加密所用的公钥：
N=322831561921859 e = 23
请解密出明文，提交时请将数字转化为 ascii 码提交
比如你解出的明文是 0x6162，那么请提交字符串 ab
提交格式：PCTF{明文字符串}
可以看出，我们的 N 比较小，这里我们直接使用 factordb 进行分解，可以得到
322831561921859 = 13574881 × 23781539 322831561921859 = 13574881 \times 23781539 322831561921859 = 13574881 × 23781539 进而我们简单编写程序如下
Copy 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') 结果如下
Copy ➜ Jarvis OJ-Basic-easyRSA git:(master) ✗ python exp.py
0x33613559 3a5Y p & q 不当分解 N
攻击条件
当 RSA 中 p 和 q 选取不当时，我们也可以进行攻击。
|p-q| 很大
当 p-q 很大时，一定存在某一个参数较小，这里我们假设为 p，那么我们可以通过穷举的方法对模数进行试除，从而分解模数，得到保密参数与明文信息。基本来说，不怎么可行。
|p-q| 较小
首先
( p + q ) 2 4 − n = ( p + q ) 2 4 − p q = ( p − q ) 2 4 \frac{(p+q)^2}{4}-n=\frac{(p+q)^2}{4}-pq=\frac{(p-q)^2}{4} 4 ( p + q ) 2 − n = 4 ( p + q ) 2 − pq = 4 ( p − q ) 2 既然 |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
p - 1 光滑
光滑数(Smooth number)：指可以分解为小素数乘积的正整数
当$p$是$N$的因数，并且$p-1$是光滑数，可以考虑使用Pollard's p-1算法来分解$N$
根据费马小定理有
若 p ∤ a , 则 a p − 1 ≡ 1 ( m o d p ) 若p\nmid a,\ 则a^{p-1}\equiv 1\pmod{p} 若 p ∤ a , 则 a p − 1 ≡ 1 ( mod p )
则有
a t ( p − 1 ) ≡ 1 t ≡ 1 ( m o d p ) a^{t(p-1)}\equiv 1^t \equiv 1\pmod{p} a t ( p − 1 ) ≡ 1 t ≡ 1 ( mod p )
即
a t ( p − 1 ) − 1 = k ∗ p a^{t(p-1)} - 1 = k*p a t ( p − 1 ) − 1 = k ∗ p
根据Pollard's p-1算法：
如果$p$是一个$B-smooth\ number$，那么则存在
M = ∏ q ≤ B q ⌊ log q B ⌋ M = \prod_{q\le{B}}{q^{\lfloor\log_q{B}\rfloor}} M = ∏ q ≤ B q ⌊ l o g q B ⌋
使得
( p − 1 ) ∣ M (p-1)\mid M ( p − 1 ) ∣ M
成立，则有
gcd ( a M − 1 , N ) \gcd{(a^{M}-1, N)} g cd( a M − 1 , N )
如果结果不为$1$或$N$，那么就已成功分解$N$。
因为我们只关心最后的gcd结果，同时N只包含两个素因子，则我们不需要计算$M$，考虑$n=2,3,\dots$，令$M = n!$即可覆盖正确的$M$同时方便计算。
在具体计算中，可以代入降幂进行计算
a^{n!}\bmod{N}=\begin{cases} (a\bmod{N})^2\mod{N}&n=2\\ (a^{(n-1)!}\bmod{N})^n\mod{N}&n\ge{3} \end{cases}$$
Python代码实现
Copy from gmpy2 import *
a = 2
n = 2
while True:
a = powmod(a, n, N)
res = gcd(a-1, N)
if res != 1 and res != N:
q = N // res
d = invert(e, (res-1)*(q-1))
m = powmod(c, d, N)
print(m)
break
n += 1 p + 1 光滑
当$p$是$N$的因数，并且$p+1$是光滑数，可以考虑使用Williams's p+1算法来分解$N$
已知$N$的因数$p$，且$p+1$是一个光滑数
p = ( ∏ i = 1 k q i α i ) + 1 p = \left(\prod_{i=1}^k{q_i^{\alpha_i}}\right)+1 p = ( i = 1 ∏ k q i α i ) + 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 = 1 k q i β i R = \prod_{i=1}^k{q_i^{\beta_i}} R = i = 1 ∏ k q i β i 显然有$p-1\mid R$且当$(N, a) = 1$时有$a^{p-1}\equiv 1 \pmod{p}$，所以有$a^R\equiv 1\pmod{p}$，即
p ∣ ( N , a R − 1 ) p\mid(N, a^R-1) p ∣ ( N , a R − 1 ) 令$P,Q$为整数，$\alpha,\beta$为方程$x^2-Px+Q=0$的根，定义如下类卢卡斯序列
U n ( P , Q ) = ( α n − β n ) / ( α − β ) V n ( 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} U n ( P , Q ) V n ( P , Q ) = ( α n − β n ) / ( α − β ) = α n + β n 同样有$\Delta = (\alpha - \beta)^2 = P^2-4Q$，则有
{ U n + 1 = P U n − Q U n − 1 V n + 1 = P V n − Q V n − 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} { U n + 1 V n + 1 = P U n − Q U n − 1 = P V n − Q V n − 1 ( 2.2 ) { U 2 n = V n U n V 2 n = V n 2 − 2 Q n (2.3) \begin{cases} U_{2n} &= V_nU_n\\ V_{2n} &= V_n^2 - 2Q^n \end{cases}\tag{2.3} { U 2 n V 2 n = V n U n = V n 2 − 2 Q n ( 2.3 ) { U 2 n − 1 = U n 2 − Q U n − 1 2 V 2 n − 1 = V n V n − 1 − P Q n − 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} { U 2 n − 1 V 2 n − 1 = U n 2 − Q U n − 1 2 = V n V n − 1 − P Q n − 1 ( 2.4 ) { Δ U n = P V n − 2 Q V n − 1 V n = P U n − 2 Q U n − 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} { Δ U n V n = P V n − 2 Q V n − 1 = P U n − 2 Q U n − 1 ( 2.5 ) { U m + n = U m U n + 1 − Q U m − 1 U n Δ U m + n = V m V n + 1 − Q V m − 1 V n (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} { U m + n Δ U m + n = U m U n + 1 − Q U m − 1 U n = V m V n + 1 − Q V m − 1 V n ( 2.6 ) { U n ( V k ( P , Q ) , Q k ) = U n k ( P , Q ) / U k ( P , Q ) V n ( V k ( P , Q ) , Q k ) = V n ( 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} { U n ( V k ( P , Q ) , Q k ) V n ( V k ( P , Q ) , Q k ) = U nk ( P , Q ) / U k ( P , Q ) = V n ( P , Q ) ( 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$，即
U 2 m ( P , Q ) ≡ P Q m − 1 U m ( P ′ , 1 ) ( m o d N ) (2.8) U_{2m}(P, Q)\equiv PQ^{m-1}U_m(P^{'}, 1)\pmod{N}\tag{2.8} U 2 m ( P , Q ) ≡ P Q m − 1 U m ( P ′ , 1 ) ( mod N ) ( 2.8 ) 根据扩展卢卡斯定理
如果p是奇素数，$p\nmid Q$且勒让德符号$(\Delta/p) = \epsilon$，则
U ( p − ϵ ) m ( P , Q ) ≡ 0 ( m o d p ) V ( p − ϵ ) m ( P , Q ) ≡ 2 Q m ( 1 − ϵ ) / 2 ( m o d p ) \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} U ( p − ϵ ) m ( P , Q ) V ( p − ϵ ) m ( P , Q ) ≡ 0 ( mod p ) ≡ 2 Q m ( 1 − ϵ ) /2 ( mod p ) 第一种情况：已知N的因数p，且p+1是一个光滑数
p = ( ∏ i = 1 k q i α i ) − 1 p = \left(\prod_{i=1}^k{q_i^{\alpha_i}}\right)-1 p = ( i = 1 ∏ k q i α i ) − 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提出可以使用如下公式
U 2 n − 1 = U n 2 − Q U n 2 − 1 U 2 n = U n ( P U n − 2 Q U n − 1 ) U 2 n + 1 = P U 2 n − Q U 2 n − 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} U 2 n − 1 U 2 n U 2 n + 1 = U n 2 − Q U n 2 − 1 = U n ( P U n − 2 Q U n − 1 ) = P U 2 n − Q U 2 n − 1 但是上述公式值太大了，不便运算，我们可以考虑如下方法
如果$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 ( m o d p ) V_{(p-\epsilon)m}(P, 1) \equiv 2\pmod{p} V ( p − ϵ ) m ( P , 1 ) ≡ 2 ( mod 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)$且
P j ≡ V r j ( P j − 1 ) ( m o d N ) ( j = 1 , 2 , 3 , … , m ) P_j \equiv V_{r_j}(P_{j-1})\pmod{N}(j = 1,2,3,\dots,m) P j ≡ V r j ( P j − 1 ) ( mod N ) ( j = 1 , 2 , 3 , … , m ) 根据公式2.7，有
P m ≡ V R ( P 0 ) ( m o d N ) (3.1) P_m \equiv V_R(P_0)\pmod{N}\tag{3.1} P m ≡ V R ( P 0 ) ( mod N ) ( 3.1 ) 要计算$V_r = V_r(P)$可以用如下公式
根据公式2.2，公式2.3，公式2.4有
{ V 2 f − 1 ≡ V f V f − 1 − P V 2 f ≡ V f 2 − 2 V 2 f + 1 ≡ P V f 2 − V f V f − 1 − P ( m o d ( ) 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} ⎩ ⎨ ⎧ V 2 f − 1 V 2 f V 2 f + 1 ≡ V f V f − 1 − P ≡ V f 2 − 2 ≡ P V f 2 − V f V f − 1 − P ( mod ( ) N ) 令
r = ∑ i = 0 t b t 2 t − i ( b i = 0 , 1 ) r = \sum_{i=0}^t{b_t2^{t-i}}\ \ \ \ (b_i=0,1) r = i = 0 ∑ t b t 2 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$，则最终公式为
( V f k + 1 , V f k + 1 − 1 ) = { ( V 2 f k , V 2 f k − 1 ) i f b k + 1 = 0 ( V 2 f k + 1 , V 2 f k ) i f b k + 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} ( V f k + 1 , V f k + 1 − 1 ) = { ( V 2 f k , V 2 f k − 1 ) i f b k + 1 = 0 ( V 2 f k + 1 , V 2 f k ) i f b k + 1 = 1 第二种情况：已知p+1是一个光滑数
p = s ( ∏ i = 1 k q i α i ) − 1 p = s\left(\prod_{i=1}^k{q_i^{\alpha_i}}\right)-1 p = s ( i = 1 ∏ k q i α i ) − 1 当$s$是素数，且$B_1<s\le B_2$，有$p\mid(a_m^s-1, N)，$定义$s_j$和$2d_j$
2 d j = s j + 1 − s j 2d_j = s_j+1-s_j 2 d 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 ] = P m U [ n ] − U [ n − 1 ] U[0] = 0, U[1] = 1, U[n+1] = P_mU[n] - U[n-1] U [ 0 ] = 0 , U [ 1 ] = 1 , U [ n + 1 ] = P m U [ n ] − U [ n − 1 ]
计算
T [ s i ] ≡ Δ U s i ( P m ) = Δ U s i R ( P 0 ) / U R ( P 0 ) ( m o d N ) T[s_i] \equiv \Delta U_{s_i}(P_m) = \Delta U_{s_iR}(P_0)/U_R(P_0)\pmod{N} T [ s i ] ≡ Δ U s i ( P m ) = Δ U s i R ( P 0 ) / U R ( P 0 ) ( mod N ) 通过公式2.6，公式2.7和公式3.1有
{ T [ s 1 ] ≡ P m V [ s 1 ] − 2 V [ s 1 − 1 ] T [ s 1 − 1 ] ≡ 2 V [ s 1 ] − P m V [ s 1 − 1 ] ( m o d N ) \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 [ s 1 ] T [ s 1 − 1 ] ≡ P m V [ s 1 ] − 2 V [ s 1 − 1 ] ≡ 2 V [ s 1 ] − P m V [ s 1 − 1 ] ( mod N ) 即
{ T [ s i + 1 ] ≡ T [ s i ] U [ 2 d i + 1 ] − T [ s i − 1 ] U [ 2 d i ] T [ s i + 1 − 1 ] ≡ T [ s i ] U [ 2 d i ] − T [ s i − 1 ] U [ 2 d i − 1 ] ( m o d N ) \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 + 1 ] T [ s i + 1 − 1 ] ≡ T [ s i ] U [ 2 d i + 1 ] − T [ s i − 1 ] U [ 2 d i ] ≡ T [ s i ] U [ 2 d i ] − T [ s i − 1 ] U [ 2 d i − 1 ] ( mod N ) 计算$T[s_i], i=1,2,3\dots$，然后计算
H t = ( ∏ i = 0 c T [ s i + t ] , N ) H_t = (\prod_{i=0}^c{T[s_{i+t}], N}) H t = ( 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代码实现
Copy def mlucas(v, a, n):
""" Helper function for williams_pp1(). Multiplies along a Lucas sequence modulo n. """
v1, v2 = v, (v**2 - 2) % n
for bit in bin(a)[3:]: v1, v2 = ((v1**2 - 2) % n, (v1*v2 - v) % n) if bit == "0" else ((v1*v2 - v) % n, (v2**2 - 2) % n)
return v1
for v in count(1):
for p in primegen():
e = ilog(isqrt(n), p)
if e == 0: break
for _ in xrange(e): v = mlucas(v, p, n)
g = gcd(v-2, n)
if 1 < g < n: return g # g|n
if g == n: break 2017 SECCON very smooth
该程序给了一个 HTTPS 加密的流量包，首先从其中拿到证书
Copy ➜ 2017_SECCON_verysmooth git:(master) binwalk -e s.pcap
DECIMAL HEXADECIMAL DESCRIPTION
--------------------------------------------------------------------------------
2292 0x8F4 Certificate in DER format (x509 v3), header length: 4, sequence length: 467
4038 0xFC6 Certificate in DER format (x509 v3), header length: 4, sequence length: 467
5541 0x15A5 Certificate in DER format (x509 v3), header length: 4, sequence length: 467
➜ 2017_SECCON_verysmooth git:(master) ls
s.pcap _s.pcap.extracted very_smooth.zip 这里分别查看三个证书，三个模数都一样，这里只给一个例子
Copy ➜ _s.pcap.extracted git:(master) openssl x509 -inform DER -in FC6.crt -pubkey -text -modulus -noout
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDVRqqCXPYd6Xdl9GT7/kiJrYvy
8lohddAsi28qwMXCe2cDWuwZKzdB3R9NEnUxsHqwEuuGJBwJwIFJnmnvWurHjcYj
DUddp+4X8C9jtvCaLTgd+baSjo2eB0f+uiSL/9/4nN+vR3FliRm2mByeFCjppTQl
yioxCqbXYIMxGO4NcQIDAQAB
-----END PUBLIC KEY-----
Certificate:
Data:
Version: 1 (0x0)
Serial Number: 11640506567126718943 (0xa18b630c7b3099df)
Signature Algorithm: sha256WithRSAEncryption
Issuer: C=JP, ST=Kawasaki, O=SRL
Validity
Not Before: Oct 8 02:47:17 2017 GMT
Not After : Oct 8 02:47:17 2018 GMT
Subject: C=JP, ST=Kawasaki, O=SRL
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
Public-Key: (1024 bit)
Modulus:
00:d5:46:aa:82:5c:f6:1d:e9:77:65:f4:64:fb:fe:
48:89:ad:8b:f2:f2:5a:21:75:d0:2c:8b:6f:2a:c0:
c5:c2:7b:67:03:5a:ec:19:2b:37:41:dd:1f:4d:12:
75:31:b0:7a:b0:12:eb:86:24:1c:09:c0:81:49:9e:
69:ef:5a:ea:c7:8d:c6:23:0d:47:5d:a7:ee:17:f0:
2f:63:b6:f0:9a:2d:38:1d:f9:b6:92:8e:8d:9e:07:
47:fe:ba:24:8b:ff:df:f8:9c:df:af:47:71:65:89:
19:b6:98:1c:9e:14:28:e9:a5:34:25:ca:2a:31:0a:
a6:d7:60:83:31:18:ee:0d:71
Exponent: 65537 (0x10001)
Signature Algorithm: sha256WithRSAEncryption
78:92:11:fb:6c:e1:7a:f7:2a:33:b8:8b:08:a7:f7:5b:de:cf:
62:0b:a0:ed:be:d0:69:88:38:93:94:9d:05:41:73:bd:7e:b3:
32:ec:8e:10:bc:3a:62:b0:56:c7:c1:3f:60:66:a7:be:b9:46:
f7:46:22:6a:f3:5a:25:d5:66:94:57:0e:fc:b5:16:33:05:1c:
6f:f5:85:74:57:a4:a0:c6:ce:4f:fd:64:53:94:a9:83:b8:96:
bf:5b:a7:ee:8b:1e:48:a7:d2:43:06:0e:4f:5a:86:62:69:05:
e2:c0:bd:4e:89:c9:af:04:4a:77:a2:34:86:6a:b8:d2:3b:32:
b7:39
Modulus=D546AA825CF61DE97765F464FBFE4889AD8BF2F25A2175D02C8B6F2AC0C5C27B67035AEC192B3741DD1F4D127531B07AB012EB86241C09C081499E69EF5AEAC78DC6230D475DA7EE17F02F63B6F09A2D381DF9B6928E8D9E0747FEBA248BFFDFF89CDFAF4771658919B6981C9E1428E9A53425CA2A310AA6D760833118EE0D71 可以看出模数只有 1024 比特。而且，根据题目名 very smooth，应该是其中一个因子比较 smooth，这里我们利用 primefac 分别尝试 Pollard's p − 1 与 Williams's p + 1 算法，如下
Copy ➜ _s.pcap.extracted git:(master) python -m primefac -vs -m=p+1 149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897
149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897: p+1 11807485231629132025602991324007150366908229752508016230400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 12684117323636134264468162714319298445454220244413621344524758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897
Z309 = P155 x P155 = 11807485231629132025602991324007150366908229752508016230400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 x 12684117323636134264468162714319298445454220244413621344524758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897 可以发现当使用 Williams's p + 1 算法时，就直接分解出来了。按道理这个因子是 p-1 似乎更光滑，但是却并不能使用 Pollard's p − 1 算法分解，这里进行进一步的测试
Copy ➜ _s.pcap.extracted git:(master) python -m primefac -vs 1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002
1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002: 2 7 43 503 761429 5121103123294685745276806480148867612214394022184063853387799606010231770631857868979139305712805242051823263337587909550709296150544706624823
Z154 = P1 x P1 x P2 x P3 x P6 x P142 = 2 x 7 x 43 x 503 x 761429 x 5121103123294685745276806480148867612214394022184063853387799606010231770631857868979139305712805242051823263337587909550709296150544706624823
➜ _s.pcap.extracted git:(master) python -m primefac -vs 1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
Z154 = P1^185 x P1^62 x P1^97 = 2^185 x 3^62 x 5^97 可以看出，对于 p-1 确实有很多小因子，但是个数太多，这就会使得进行枚举的时候出现指数爆炸的情况，因此没有分解出来。
进而根据分解出来的数构造私钥
Copy from Crypto.PublicKey import RSA
import gmpy2
def main():
n = 149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897L
p = 11807485231629132025602991324007150366908229752508016230400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001L
q = 12684117323636134264468162714319298445454220244413621344524758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897L
e = 65537L
priv = RSA.construct((n, e, long(gmpy2.invert(e, (p - 1) * (q - 1)))))
open('private.pem', 'w').write(priv.exportKey('PEM'))
main() 最后，将私钥导入到 wireshark 中即可得到明文（Edit -> Preferences -> Protocols -> SSL -> RSA Key List）。
Copy <html>
<head><title>Very smooth</title></head>
<body>
<h1>
Answer: One of these primes is very smooth.
</h1>
</body>
</html> 扩展
关于更多的一些分解模数 N 的方法可以参考 https://en.wikipedia.org/wiki/Integer_factorization。
模不互素
攻击原理
当存在两个公钥的 N 不互素时，我们显然可以直接对这两个数求最大公因数，然后直接获得 p，q，进而获得相应的私钥。
SCTF RSA2
这里我们以 SCTF rsa2 为例进行介绍。直接打开 pcap 包，发现有一堆的消息，包含 N 和 e，然后试了试不同的 N 是否互素，我试了前两个
Copy import gmpy2
n1 = 20823369114556260762913588844471869725762985812215987993867783630051420241057912385055482788016327978468318067078233844052599750813155644341123314882762057524098732961382833215291266591824632392867716174967906544356144072051132659339140155889569810885013851467056048003672165059640408394953573072431523556848077958005971533618912219793914524077919058591586451716113637770245067687598931071827344740936982776112986104051191922613616045102859044234789636058568396611030966639561922036712001911238552391625658741659644888069244729729297927279384318252191421446283531524990762609975988147922688946591302181753813360518031
n2 = 19083821613736429958432024980074405375408953269276839696319265596855426189256865650651460460079819368923576109723079906759410116999053050999183058013281152153221170931725172009360565530214701693693990313074253430870625982998637645030077199119183041314493288940590060575521928665131467548955951797198132001987298869492894105525970519287000775477095816742582753228905458466705932162641076343490086247969277673809512472546919489077884464190676638450684714880196854445469562733561723325588433285405495368807600668761929378526978417102735864613562148766250350460118131749533517869691858933617013731291337496943174343464943
print gmpy2.gcd(n1, n2) 结果发现竟然不互素。
Copy ➜ scaf-rsa2 git:(master) ✗ python exp.py
122281872221091773923842091258531471948886120336284482555605167683829690073110898673260712865021244633908982705290201598907538975692920305239961645109897081011524485706755794882283892011824006117276162119331970728229108731696164377808170099285659797066904706924125871571157672409051718751812724929680249712137 那么我们就可以直接来解密了，这里我们利用第一对公钥密码。代码如下
Copy from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5, PKCS1_OAEP
import gmpy2
from base64 import b64decode
n1 = 20823369114556260762913588844471869725762985812215987993867783630051420241057912385055482788016327978468318067078233844052599750813155644341123314882762057524098732961382833215291266591824632392867716174967906544356144072051132659339140155889569810885013851467056048003672165059640408394953573072431523556848077958005971533618912219793914524077919058591586451716113637770245067687598931071827344740936982776112986104051191922613616045102859044234789636058568396611030966639561922036712001911238552391625658741659644888069244729729297927279384318252191421446283531524990762609975988147922688946591302181753813360518031
n2 = 19083821613736429958432024980074405375408953269276839696319265596855426189256865650651460460079819368923576109723079906759410116999053050999183058013281152153221170931725172009360565530214701693693990313074253430870625982998637645030077199119183041314493288940590060575521928665131467548955951797198132001987298869492894105525970519287000775477095816742582753228905458466705932162641076343490086247969277673809512472546919489077884464190676638450684714880196854445469562733561723325588433285405495368807600668761929378526978417102735864613562148766250350460118131749533517869691858933617013731291337496943174343464943
p1 = gmpy2.gcd(n1, n2)
q1 = n1 / p1
e = 65537
phin = (p1 - 1) * (q1 - 1)
d = gmpy2.invert(e, phin)
cipher = 0x68d5702b70d18238f9d4a3ac355b2a8934328250efd4efda39a4d750d80818e6fe228ba3af471b27cc529a4b0bef70a2598b80dd251b15952e6a6849d366633ed7bb716ed63c6febd4cd0621b0c4ebfe5235de03d4ee016448de1afbbe61144845b580eed8be8127a8d92b37f9ef670b3cdd5af613c76f58ca1a9f6f03f1bc11addba30b61bb191efe0015e971b8f78375faa257a60b355050f6435d94b49eab07075f40cb20bb8723d02f5998d5538e8dafc80cc58643c91f6c0868a7a7bf3bf6a9b4b6e79e0a80e89d430f0c049e1db4883c50db066a709b89d74038c34764aac286c36907b392bc299ab8288f9d7e372868954a92cdbf634678f7294096c7
plain = gmpy2.powmod(cipher, d, n1)
plain = hex(plain)[2:]
if len(plain) % 2 != 0:
plain = '0' + plain
print plain.decode('hex') 最后解密如下
Copy ➜ scaf-rsa2 git:(master) ✗ python exp.py
sH1R3_PRlME_1N_rsA_iS_4ulnEra5le 解压压缩包即可。
共模攻击
攻击条件
当两个用户使用相同的模数 N、不同的私钥时，加密同一明文消息时即存在共模攻击。
攻击原理
设两个用户的公钥分别为 $e_1$ 和 $e_2$，且两者互质。明文消息为 $m$，密文分别为：
c 1 = m e 1 m o d N c 2 = m e 2 m o d N c_1 = m^{e_1}\bmod N \\ c_2 = m^{e_2}\bmod N c 1 = m e 1 mod N c 2 = m e 2 mod N 当攻击者截获 $c_1$ 和 $c_2$ 后，就可以恢复出明文。用扩展欧几里得算法求出 $re_1+se_2=1\bmod n$ 的两个整数 $r$ 和 $s$，由此可得：
c 1 r c 2 s ≡ m r e 1 m s e 2 m o d n ≡ m ( r e 1 + s e 2 ) m o d n ≡ m m o d 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*} c 1 r c 2 s ≡ m r e 1 m s e 2 mod n ≡ m ( r e 1 + s e 2 ) mod n ≡ m mod n XMan 一期夏令营课堂练习
题目描述：
Copy {6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,773}
{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,839}
message1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
message2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535 题目来源：XMan 一期夏令营课堂练习
可以看出两个公钥的 N 是一样的，并且两者的 e 互素。写一个脚本跑一下：
Copy import gmpy2
n = 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249
e1 = 773
e2 = 839
message1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
message2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535
# s & t
gcd, s, t = gmpy2.gcdext(e1, e2)
if s < 0:
s = -s
message1 = gmpy2.invert(message1, n)
if t < 0:
t = -t
message2 = gmpy2.invert(message2, n)
plain = gmpy2.powmod(message1, s, n) * gmpy2.powmod(message2, t, n) % n
print plain 得到
Copy ➜ Xman-1-class-exercise git:(master) ✗ python exp.py
1021089710312311910410111011910111610410511010710511610511511211111511510598108101125 这时候需要考虑当时明文是如何转化为这个数字了，一般来说是 16 进制转换，ASCII 字符转换，或者 Base64 解密。这个应该是 ASCII 字符转换，进而我们使用如下代码得到 flag
Copy i = 0
flag = ""
plain = str(plain)
while i < len(plain):
if plain[i] == '1':
flag += chr(int(plain[i:i + 3]))
i += 3
else:
flag += chr(int(plain[i:i + 2]))
i += 2
print flag 这里之所以使用 1 来判断是否为三位长度，是因为 flag 一般都是明文字符，而 1 开头的长度为 1 或者 2 的数字，一般都是不可见字符。
flag
Copy ➜ Xman-1-class-exercise git:(master) ✗ python exp.py
flag{whenwethinkitispossible} 题目