xctf攻防世界 CRYPTO高手进阶区 equation-2

0x01. 进入环境，下载附件

题目给的两个文件，一个enc加密文件，一个是一张图片，如图：

0x02. 问题分析

0x02_1. 对应字段

我们可以看到，整个私钥的上半段被加密了，只给了后半段。看到这里，我们首先必须了解私钥文件pem的结构类型，参考链接：http://blog.sina.com.cn/s/blog_4fcd1ea30100yh4s.html。如图：

其次，我们将图片所给的字段内容给拷贝出来，内容如下：

Os9mhOQRdqW2cwVrnNI72DLcAXpXUJ1HGwJBANWiJcDUGxZpnERxVw7s0913WXNtV4GqdxCzG0pG5EHThtoTRbyX0aqRP4U/hQ9tRoSoDmBn+3HPITsnbCy67VkCQBM4xZPTtUKM6Xi+16VTUnFVs9E4rqwIQCDAxn9UuVMBXlX2Cl0xOGUF4C5hItrX2woF7LVS5EizR63CyRcPovMCQQDVyNbcWD7N88MhZjujKuSrHJot7WcCaRmTGEIJ6TkU8NWt9BVjR4jVkZ2EqNd0KZWdQPukeynPcLlDEkIXyaQx

0x02_2. 转码得到数据

import base64s = 'Os9mhOQRdqW2cwVrnNI72DLcAXpXUJ1HGwJBANWiJcDUGxZpnERxVw7s0913WXNtV4GqdxCzG0pG5EHThtoTRbyX0aqRP4U/hQ9tRoSoDmBn+3HPITsnbCy67VkCQBM4xZPTtUKM6Xi+16VTUnFVs9E4rqwIQCDAxn9UuVMBXlX2Cl0xOGUF4C5hItrX2woF7LVS5EizR63CyRcPovMCQQDVyNbcWD7N88MhZjujKuSrHJot7WcCaRmTGEIJ6TkU8NWt9BVjR4jVkZ2EqNd0KZWdQPukeynPcLlDEkIXyaQx'
res = base64.b64decode(s).hex()
print(res)

输出16进制如下：

3acf6684e41176a5b673056b9cd23bd832dc017a57509d471b024100d5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d386da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed5902401338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b953015e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3024100d5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded6702691993184209e93914f0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431

结合字段的内容和标志（注意倒数第三个标签头应该是0241不是0240，写错了应该）：

将其放入winhex中，如图：

倒推标识头部，可以得到信息如下：

• d mod (p-1)=x1

00d5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d386da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed59

• d mod (q-1)=x2

1338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b953015e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3

• (q -1) mod p

00d5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded6702691993184209e93914f0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431

0x02_3. 数学推论

d⋅e ≡ 1 mod (p−1)(q−1) # RSA的私钥计算公式
则有：d⋅e ≡ 1 mod (p−1) 与 d⋅e ≡ 1 mod (q−1) 
即：x1⋅e ≡ 1 mod (p−1) ，x2⋅e ≡ 1 mod (q−1)
换成表达式：(p-1)|(x1e-1)(q-1)|(x2e-1)记：x1⋅e − 1 = r1⋅(p − 1)；由于 x1 = d mod (p−1)，则x1<(p−1)；     # 这里的推论真的看不懂
几乎可以看做 x1⋅e = r1⋅(p−1)
必有 r1 < e
同理 r2 < e
故e取65537    # 此处一脸懵逼

0x02_4. 解题脚本

参考大佬们的脚本：https://blog.csdn.net/weixin_44604541/article/details/111248278

import gmpy2
import rsa
from Crypto.Util.number import isPrimex1 = "0xd5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d386da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed59"
x2 = "0x1338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b953015e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3"
x3 = "0xd5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded6702691993184209e93914f0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431"
x1 = int(x1, 16)
x2 = int(x2, 16)
x3 = int(x3, 16)def genKey(X1, X2):e = 65537N1 = X1 * e - 1N2 = X2 * e - 1print(N1)for r in range(e):if N1 % (e - r) == 0:p = int(N1 // (e - r) + 1)if isPrime(p) == 1:print("r1=", r)breakfor r in range(e):if N2 % (e - r) == 0:q = int(N2 // (e - r) + 1)if isPrime(q):print("r2=", r)breakn = p * qphi = (p - 1) * (q - 1)d = int(gmpy2.invert(e, phi))privatekey = rsa.PrivateKey(n, e, d, p, q)with open('pic/flag.enc', 'rb') as file:print(rsa.decrypt(file.read(), privatekey).decode())genKey(x1, x2)

0x03. 总结

感觉RSA是非常重点的知识点，还有就是真的难。。。脚本自己写不出来，感觉做的很吃力！繼續努力吧！