跳转至

模数相关攻击

暴力分解 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):指可以分解为小素数乘积的正整数

  • pN的因数,并且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)}

    如果结果不为1N,那么就已成功分解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 光滑

  • pN的因数,并且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_1q_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) = 1P^{'}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)GuyConway提出可以使用如下公式

    \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.3p\mid U_{2R}(P, Q),所以根据公式2.8p \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_j2d_j

    2d_j = s_j+1-s_j

    如果(\Delta/p) = -1p\nmid P_m-2,则根据公式2.7公式3.1p\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_1e_2,且两者互质。明文消息为 m,密文分别为:

c_1 = m^{e_1}\bmod N \\ c_2 = m^{e_2}\bmod N

当攻击者截获 c_1c_2 后,就可以恢复出明文。用扩展欧几里得算法求出 re_1+se_2=1\bmod n 的两个整数 rs,由此可得:

\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