[攻防世界crypto]equation-2

参考RSA的pem文件结构

图片中信息
Os9mhOQRdqW2cwVrnNI72DLcAXpXUJ1HGwJBANWiJcDUGxZpnERxVw7s0913WXNtV4GqdxCzG0pG5EHThtoTRbyX0aqRP4U/hQ9tRoSoDmBn+3HPITsnbCy67VkCQBM4xZPTtUKM6Xi+16VTUnFVs9E4rqwIQCDAxn9UuVMBXlX2Cl0xOGUF4C5hItrX2woF7LVS5EizR63CyRcPovMCQQDVyNbcWD7N88MhZjujKuSrHJot7WcCaRmTGEIJ6TkU8NWt9BVjR4jVkZ2EqNd0KZWdQPukeynPcLlDEkIXyaQx

base64解密

解密后(标签头加粗)
3acf6684e41176a5b673056b9cd23bd832dc017a57509d471b024100d5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d386da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed5902401338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b953015e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3024100d5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded6702691993184209e93914f0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431

• d mod (p-1)=x1
  00d5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d386da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed59
• d mod (q-1)=x2
  1338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b953015e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3
• (q -1) mod p
  00d5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded6702691993184209e93914f0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431

数学推理

d?e≡1 mod (p?1)(q?1)
则有d?e≡1 mod (p?1)与d?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

• p=(x1?e?1)/r1+1
• q=(x2?e?1)/r2+1

猜测e的值为65537

破解脚本

• 浮点数会产生精度问题故不能用p=int(N1/(e-r)+1)

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)
print(x1)
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("flag.enc", "rb") as f:print(rsa.decrypt(f.read(), privatekey).decode())
genKey(x1,x2)