时间戳

首页 > 技术文章 > 攻防世界-密码学-equation-2

攻防世界-密码学-equation-2

coming1890 2020-08-24 19:29 原文

1. 题目信息

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

2. 分析

2.1.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编码。

2.2.利用已知信息恢复私钥

截图可见编码为

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\)；

3. 解题

实现的Python脚本如下：

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可能情况太少。

程序运行结果如下：

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

推荐阅读