模数相关攻击

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