文章目录
  1. 题目信息
  2. 分析
    1. OpenSSL私钥结构
    2. 利用已知信息恢复私钥
  3. 解题

题目信息

题目描述“RSA私钥上面的部分被屏蔽了请恢复私钥并解密文件”，附件给出私钥编码的截图，但是只能看见最后5行。

分析

OpenSSL私钥结构

私钥信息按如下顺序排列：
version | pad | n | pad | e | pad | d | pad | p | pad | q | pad | x1 | pad | x2 | pad | x3
其中，pad是填充信息，各pad并不同，$x_{1}= d\ \textrm{mod}\ (p-1),x_{2}= d\ \textrm{mod}\ (q-1),x_{3}=p^{-1}\ \textrm{mod}\ q$，填充pad用来注释接下来的大数的(字节)长度，\x02为pad开头的标记，有时后面接\x81或\x82，这用来标记长度值所占用的字节(\x81代表占用1个字节，\x82代表占用2个字节)，有时后面不接\x81或\x82而直接放置长度；
例：\x02\x03代表接下来的大数的字节长度为3个字节；\x02\x81\x80，首先，\x81代表长度占用1个字节，因此\x80就是长度值，即128，表明接下来的大数的字节长度为128个字节。

将私钥信息按照上述顺序排列好之后，再进行base64编码。

利用已知信息恢复私钥

截图可见编码为

1
Os9mhOQRdqW2cwVrnNI72DLcAXpXUJ1HGwJBANWiJcDUGxZpnERxVw7s0913WXNtV4GqdxCzG0pG5EHThtoTRbyX0aqRP4U/hQ9tRoSoDmBn+3HPITsnbCy67VkCQBM4xZPTtUKM6Xi+16VTUnFVs9E4rqwIQCDAxn9UuVMBXlX2Cl0xOGUF4C5hItrX2woF7LVS5EizR63CyRcPovMCQQDVyNbcWD7N88MhZjujKuSrHJot7WcCaRmTGEIJ6TkU8NWt9BVjR4jVkZ2EqNd0KZWdQPukeynPcLlDEkIXyaQx

解码后结合OpenSSL私钥结构分析可得：x1,x2,x3为已知；但是仅有x1,x2,x3并不能恢复出p,q与d，若我们假设e为常用的指数3,65537等等，则可试出p与q：

$d\cdot e\equiv 1\ \textrm{mod}\ (p-1)(q-1)$
则有$d\cdot e\equiv 1\ \textrm{mod}\ (p-1)$与$d\cdot e\equiv 1\ \textrm{mod}\ (q-1)$；
由$x_{1}$与$x_{2}$的定义可得$x_{1}\cdot e\equiv 1\ \textrm{mod}\ (p-1)$，$x_{2}\cdot e\equiv 1\ \textrm{mod}\ (q-1)$；
因此$(p-1)|(x_{1}\cdot e-1)$；
记$x_{1}\cdot e-1=r_{1}\cdot (p-1)$；
由于$x_{1}= d\ \textrm{mod}\ (p-1)$，则$x_{1}<(p-1)$；
几乎可以看做$x_{1}\cdot e=r_{1}\cdot (p-1)$，那么必有$r_{1}<e$；
同理可得$r_{2}<e$，其中$x_{2}\cdot e-1=r_{2}\cdot (q-1)$
可以看到，$r_{i}<e,i=1,2$，从而可使用试除法求出$r_{i},i=1,2$；
则$p=(x_{1}\cdot e-1)/r_{1}+1,q=(x_{2}\cdot e-1)/r_{2}+1$；

解题

实现的Python脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.Util.number import bytes_to_long,isPrime,inverse
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

def genKey(X1,X2,X3):
    e=65537L
    N1=X1*e-1
    N2=X2*e-1
    for r in range(e):
        if N1%(e-r)==0:
            p=N1/(e-r)+1
            if isPrime(p):
                break
    for r in range(e):
        if N2%(e-r)==0:
            q=N2/(e-r)+1
            if isPrime(q):
                break
    N=p*q
    phi=(p-1)*(q-1)
    d=inverse(e,phi)
    assert inverse(q,p)==X3
    return RSA.construct((N,e,long(d),p,q))

def solve():
    X1=bytes_to_long('\xd5\xa2%\xc0\xd4\x1b\x16i\x9cDqW\x0e\xec\xd3\xddwYsmW\x81\xaaw\x10\xb3\x1bJF\xe4A\xd3\x86\xda\x13E\xbc\x97\xd1\xaa\x91?\x85?\x85\x0fmF\x84\xa8\x0e`g\xfbq\xcf!;\'l,\xba\xedY')
    X2=bytes_to_long('\x138\xc5\x93\xd3\xb5B\x8c\xe9x\xbe\xd7\xa5SRqU\xb3\xd18\xae\xac\x08@ \xc0\xc6\x7fT\xb9S\x01^U\xf6\n]18e\x05\xe0.a"\xda\xd7\xdb\n\x05\xec\xb5R\xe4H\xb3G\xad\xc2\xc9\x17\x0f\xa2\xf3')
    X3=bytes_to_long('\xd5\xc8\xd6\xdcX>\xcd\xf3\xc3!f;\xa3*\xe4\xab\x1c\x9a-\xedg\x02i\x19\x93\x18B\t\xe99\x14\xf0\xd5\xad\xf4\x15cG\x88\xd5\x91\x9d\x84\xa8\xd7t)\x95\x9d@\xfb\xa4{)\xcfp\xb9C\x12B\x17\xc9\xa41')
    rsa_key=genKey(X1,X2,X3)
    key= PKCS1_v1_5.new(rsa_key)
    with open('flag.enc','rb') as f:
        return key.decrypt(f.read(),'')

if __name__=='__main__':
    print solve()[:-1]

注：这里之所以猜测e为65537而不是3是因为$r_{i}<e,i=1,2$，如果e=3可能情况太少。

程序运行结果如下：

1
2
$ python solve.py
0ctf{Keep_ca1m_and_s01ve_the_RSA_Eeeequati0n!!!}