模數相關攻擊¶

暴力分解 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 \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')

結果如下

➜  Jarvis OJ-Basic-easyRSA git:(master) ✗ python exp.py
0x33613559 3a5Y

p & q 不當分解 N¶

攻擊條件¶

當 RSA 中 p 和 q 選取不當時，我們也可以進行攻擊。

|p-q| 很大¶

當 p-q 很大時，一定存在某一個參數較小，這裏我們假設爲 p，那麼我們可以通過窮舉的方法對模數進行試除，從而分解模數，得到保密參數與明文信息。基本來說，不怎麼可行。

|p-q| 較小¶

首先

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

p - 1 光滑¶

光滑數(Smooth number)：指可以分解爲小素數乘積的正整數
當 $p$ 是 $N$ 的因數，並且 $p-1$ 是光滑數，可以考慮使用Pollard's p-1算法來分解 $N$
根據費馬小定理有

$若p\nmid a,\ 則a^{p-1}\equiv 1\pmod{p}$

則有

$a^{t(p-1)}\equiv 1^t \equiv 1\pmod{p}$

即

$a^{t(p-1)} - 1 = k*p$
根據Pollard's p-1算法：

如果 $p$ 是一個 $B-smooth\ number$ ，那麼則存在

$M = \prod_{q\le{B}}{q^{\lfloor\log_q{B}\rfloor}}$

使得

$(p-1)\mid M$

成立，則有

$\gcd{(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代碼實現

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 = \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 = \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\mid(N, a^R-1)$
令 $P,Q$ 爲整數， $\alpha,\beta$ 爲方程 $x^2-Px+Q=0$ 的根，定義如下類盧卡斯序列

$\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$ ，則有

$\begin{cases} U_{n+1} &= PU_n - QU_{n-1}\\ V_{n+1} &= PV_n - QV_{n-1} \end{cases}\tag{2.2}$

$\begin{cases} U_{2n} &= V_nU_n\\ V_{2n} &= V_n^2 - 2Q^n \end{cases}\tag{2.3}$

$\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}$

$\begin{cases} \Delta U_{n} &= PV_n - 2QV_{n-1}\\ V_{n} &= PU_n - 2QU_{n-1} \end{cases}\tag{2.5}$

$\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}$

$\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$ ，即

$U_{2m}(P, Q)\equiv PQ^{m-1}U_m(P^{'}, 1)\pmod{N}\tag{2.8}$

根據擴展盧卡斯定理

如果p是奇素數， $p\nmid Q$ 且勒讓德符號 $(\Delta/p) = \epsilon$ ，則

$\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 = \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提出可以使用如下公式

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

$P_j \equiv V_{r_j}(P_{j-1})\pmod{N}(j = 1,2,3,\dots,m)$

根據公式2.7，有

$P_m \equiv V_R(P_0)\pmod{N}\tag{3.1}$

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

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

$\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 = \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$ ，則最終公式爲

$(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\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$

$2d_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_mU[n] - U[n-1]$

計算

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

$\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}$

即

$\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$ ，然後計算

$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代碼實現

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 加密的流量包，首先從其中拿到證書

➜  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

這裏分別查看三個證書，三個模數都一樣，這裏只給一個例子

➜  _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 算法，如下

➜  _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 算法分解，這裏進行進一步的測試

➜  _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 確實有很多小因子，但是個數太多，這就會使得進行枚舉的時候出現指數爆炸的情況，因此沒有分解出來。

進而根據分解出來的數構造私鑰

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）。

<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 是否互素，我試了前兩個

import gmpy2
n1 = 20823369114556260762913588844471869725762985812215987993867783630051420241057912385055482788016327978468318067078233844052599750813155644341123314882762057524098732961382833215291266591824632392867716174967906544356144072051132659339140155889569810885013851467056048003672165059640408394953573072431523556848077958005971533618912219793914524077919058591586451716113637770245067687598931071827344740936982776112986104051191922613616045102859044234789636058568396611030966639561922036712001911238552391625658741659644888069244729729297927279384318252191421446283531524990762609975988147922688946591302181753813360518031
n2 = 19083821613736429958432024980074405375408953269276839696319265596855426189256865650651460460079819368923576109723079906759410116999053050999183058013281152153221170931725172009360565530214701693693990313074253430870625982998637645030077199119183041314493288940590060575521928665131467548955951797198132001987298869492894105525970519287000775477095816742582753228905458466705932162641076343490086247969277673809512472546919489077884464190676638450684714880196854445469562733561723325588433285405495368807600668761929378526978417102735864613562148766250350460118131749533517869691858933617013731291337496943174343464943
print gmpy2.gcd(n1, n2)

結果發現竟然不互素。

➜  scaf-rsa2 git:(master) ✗ python exp.py
122281872221091773923842091258531471948886120336284482555605167683829690073110898673260712865021244633908982705290201598907538975692920305239961645109897081011524485706755794882283892011824006117276162119331970728229108731696164377808170099285659797066904706924125871571157672409051718751812724929680249712137

那麼我們就可以直接來解密了，這裏我們利用第一對公鑰密碼。代碼如下

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

最後解密如下

➜  scaf-rsa2 git:(master) ✗ python exp.py       
sH1R3_PRlME_1N_rsA_iS_4ulnEra5le

解壓壓縮包即可。

共模攻擊¶

攻擊條件¶

當兩個用戶使用相同的模數 N、不同的私鑰時，加密同一明文消息時即存在共模攻擊。

攻擊原理¶

設兩個用戶的公鑰分別爲 $e_1$ 和 $e_2$ ，且兩者互質。明文消息爲 $m$ ，密文分別爲：

$c_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$ ，由此可得：

$\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*}$

XMan 一期夏令營課堂練習¶

題目描述：

{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,773}

{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,839}

message1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349

message2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

題目來源：XMan 一期夏令營課堂練習

可以看出兩個公鑰的 N 是一樣的，並且兩者的 e 互素。寫一個腳本跑一下：

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

得到

➜  Xman-1-class-exercise git:(master) ✗ python exp.py
1021089710312311910410111011910111610410511010710511610511511211111511510598108101125

這時候需要考慮當時明文是如何轉化爲這個數字了，一般來說是 16 進制轉換，ASCII 字符轉換，或者 Base64 解密。這個應該是 ASCII 字符轉換，進而我們使用如下代碼得到 flag

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

➜  Xman-1-class-exercise git:(master) ✗ python exp.py
flag{whenwethinkitispossible}

題目¶

Jarvis OJ very hard RSA