adworld-crypto-equation-2

参考：大佬的题解
拿到了一张上半部分被遮掉的RSA的私钥照片，以及一份密文

openssl私钥结构

version | pad | n | pad | e | pad | d | pad | p | pad | q | pad | x1 | pad | x2 | pad | x3

其中 pad 表示填充信息，用来表示接下来的大数所占字节数等信息
pad 以 '\x02’开头，后接信息有两种情况

• ‘\x81’或’\x82’ + length表示接下来的length所占字节数为1或2，length表示后面的数据所占字节数，例如’\x02\x81\x30’，表示后面的大数占用0x30个字节
• length，例如’\x02\x30’，表示后面的大数占用0x30个字节

x 1 = d    %    ( p − 1 ) x_1 = d\; \%\;(p-1) x1​=d%(p−1)
x 2 = d    %    ( q − 1 ) x_2 = d\; \%\;(q-1) x2​=d%(q−1)
x 3 = q − 1    %    p x_3=q^{-1}\;\%\;p x3​=q−1%p，大佬的题解中这一块似乎写的不对

利用已知信息恢复私钥

已知信息

Os9mhOQRdqW2cwVrnNI72DLcAXpXUJ1HGwJBANWiJcDUGxZpnERxVw7s0913WXNtV4GqdxCzG0pG5EHThtoTRbyX0aqRP4U/hQ9tRoSoDmBn+3HPITsnbCy67VkCQBM4xZPTtUKM6Xi+16VTUnFVs9E4rqwIQCDAxn9UuVMBXlX2Cl0xOGUF4C5hItrX2woF7LVS5EizR63CyRcPovMCQQDVyNbcWD7N88MhZjujKuSrHJot7WcCaRmTGEIJ6TkU8NWt9BVjR4jVkZ2EqNd0KZWdQPukeynPcLlDEkIXyaQx

将其用base64解码后得到：

b':\xcff\x84\xe4\x11v\xa5\xb6s\x05k\x9c\xd2;\xd82\xdc\x01zWP\x9dG\x1b
\x02A\x00\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
\x02@\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
\x02A\x00\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'

以上信息是我已经将\x02分出来之后的信息

我们会发现最后一段里面含有’\x02’，为什么它不能作为pad呢？
该’\x02’后接了’i’
‘i’ 的 ascii 码为105，意味着后面大数所占字节数为105，然后后面的数据长度不足105，所以该’\x02’并不是pad

那么根据上面的信息，我们已经得出来了x1, x2, x3

d ∗ e ≡ 1    %    ( p − 1 ) ( q − 1 ) d * e \equiv 1\;\%\;(p-1)(q-1) d∗e≡1%(p−1)(q−1)
d ∗ e ≡ 1    %    ( p − 1 ) d*e \equiv 1\;\%\;(p-1) d∗e≡1%(p−1)
d ∗ e ≡ 1    %    ( q − 1 ) d*e \equiv 1\;\%\;(q-1) d∗e≡1%(q−1)
x 1 ∗ e ≡ 1    %    ( p − 1 ) x_1*e \equiv 1\;\%\;(p-1) x1​∗e≡1%(p−1), 因为 x 1 = d    %    ( p − 1 ) x_1=d\;\%\;(p-1) x1​=d%(p−1)
x 1 ∗ e − 1 = r 1 ∗ ( p − 1 ) x_1*e - 1 = r_1*(p-1) x1​∗e−1=r1​∗(p−1)
因为 x 1 < p − 1 x_1<p-1 x1​<p−1，所以近似的 r 1 < e r_1 < e r1​<e
同理可得 r 2 < e r_2 < e r2​<e
那么有 p = ( x 1 ∗ e − 1 ) / r 1 + 1 p = (x_1*e-1)/r_1+1 p=(x1​∗e−1)/r1​+1, q = ( x 2 ∗ e − 1 ) / r 2 + 1 q = (x_2*e-1)/r_2+1 q=(x2​∗e−1)/r2​+1
且要保证 x 3 = q − 1    %    p x_3 = q^{-1}\;\%\;p x3​=q−1%p

e的常见值有3, 65537。
这里若是e=3的话，情况太少，所以选择e=65537试探

import gmpy2
import base64
import sys

from Crypto.Util.number import isPrime, inverse
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5


# sys.stdout = open('./data/x.txt', 'w')


# s = 'Os9mhOQRdqW2cwVrnNI72DLcAXpXUJ1HGwJBANWiJcDUGxZpnERxVw7s0913WXNtV4GqdxCzG0pG5EHThtoTRbyX0aqRP4U/hQ9tRoSoDmBn+3HPITsnbCy67VkCQBM4xZPTtUKM6Xi+16VTUnFVs9E4rqwIQCDAxn9UuVMBXlX2Cl0xOGUF4C5hItrX2woF7LVS5EizR63CyRcPovMCQQDVyNbcWD7N88MhZjujKuSrHJot7WcCaRmTGEIJ6TkU8NWt9BVjR4jVkZ2EqNd0KZWdQPukeynPcLlDEkIXyaQx'
# print(base64.b64decode(s.encode('utf8')))

# Crypto自带的bytes_to_long一直报错，就自己写了一个 
def bytes_to_int(x):
    ans = 0
    for data in x:
        ans <<= 8
        ans += ord(data)
    return ans

x1 = bytes_to_int('\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_int('\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_int('\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')

def genKey(x1, x2, x3):
    e = 65537
    n1 = x1 * e - 1
    n2 = x2 * e - 1
    p = 0; q = 0
    # 尝试求 r1
    for r in range(e - 1, 0, -1):
        if n1 % r == 0:
            p = (n1 // r) + 1
            if gmpy2.is_prime(p):
                break
    # 尝试求 r2
    for r in range(e - 1, 0, -1):
        if n2 % r == 0:
            q = (n2 // r) + 1
            if gmpy2.is_prime(q):
                break
    print(p)
    print(q)
    n = p * q
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    assert inverse(q, p) == x3
    return RSA.construct((n, e, int(d), p, q))

def solve():
    rsa_key = genKey(x1, x2, x3)
    key = PKCS1_v1_5.new(rsa_key)
    with open('./data/flag.enc', 'rb') as fp:
        return key.decrypt(fp.read(), '')
    
if __name__ == "__main__":
    print(solve())