[攻防世界crypto]equation-2
图片中信息
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 isPrime
x1="0xd5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d386da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed59"
x2="0x1338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b953015e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3"
x3="0xd5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded6702691993184209e93914f0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431"
x1=int(x1,16)
x2=int(x2,16)
x3=int(x3,16)
print(x1)
def genKey(X1,X2):
e=65537
N1=X1*e-1
N2=X2*e-1
print(N1)
for r in range(e):
if N1%(e-r)==0:
p=int(N1//(e-r)+1)
if isPrime(p)==1:
print("r1=",r)
break
for r in range(e):
if N2%(e-r)==0:
q=int(N2//(e-r)+1)
if isPrime(q):
print("r2=",r)
break
n=p*q
phi=(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)