I encrypted a secret message with RSA but I lost the modulus. Can you help me recover it?
You can Download the task Files Here
1. challenge.py
#!/usr/bin/python3
from Crypto.Util.number import getPrime, long_to_bytes, inverse
flag = open('flag.txt', 'r').read().strip().encode()
class RSA:
def __init__(self):
self.p = getPrime(512)
self.q = getPrime(512)
self.e = 3
self.n = self.p * self.q
self.d = inverse(self.e, (self.p-1)*(self.q-1))
def encrypt(self, data: bytes) -> bytes:
pt = int(data.hex(), 16)
ct = pow(pt, self.e, self.n)
return long_to_bytes(ct)
def decrypt(self, data: bytes) -> bytes:
ct = int(data.hex(), 16)
pt = pow(ct, self.d, self.n)
return long_to_bytes(pt)
def main():
crypto = RSA()
print (‘Flag:’, crypto.encrypt(flag).hex())
if __name__ == ‘__main__’:
main()
2. output.txt
Flag: 05c61636499a82088bf4388203a93e67bf046f8c49f62857681ec9aaaa40b4772933e0abc83e938c84ff8e67e5ad85bd6eca167585b0cc03eb1333b1b1462d9d7c25f44e53bcb568f0f05219c0147f7dc3cbad45dec2f34f03bcadcbba866dd0c566035c8122d68255ada7d18954ad604965
Before getting into Analysis, you should need to know what is an RSA!
RSA is a public-key Crypto system that is widely used for secure data transmission. It is also one of the oldest.
The acronym “RSA” comes from the surnames of
Ron Rivest, Adi Shamir and Leonard Adleman
, who publicly described the algorithm in 1977.
Working Principle of RSA:
Check out the working principle of RSA here
Add the below lines to challenge.py
to Decrypt
Make Sure to Importbinascii
before Executing the Program inmain()
Unhexlify (hexstr) Return the binary data represented by the hexadecimal string hexstr
def main():
crypto = RSA()
flag= "05c61636499a82088bf4388203a93e67bf046f8c49f62857681ec9aaaa40b4772933e0abc83e938c84ff8e67e5ad85bd6eca167585b0cc03eb1333b1b1462d9d7c25f44e53bcb568f0f05219c0147f7dc3cbad45dec2f34f03bcadcbba866dd0c566035c8122d68255ada7d18954ad604965"
val = crypto.decrypt(binascii.unhexlify(output))
print(val.decode())
Final Code:
#!/usr/bin/python3
from Crypto.Util.number import getPrime, long_to_bytes, inverse
import binascii
class RSA:
def __init__(self):
self.p = getPrime(512)
self.q = getPrime(512)
self.e = 3
self.n = self.p * self.q
self.d = inverse(self.e, (self.p-1)*(self.q-1))
def encrypt(self, data: bytes) -> bytes:
pt = int(data.hex(), 16)
ct = pow(pt, self.e, self.n)
return long_to_bytes(ct)
def decrypt(self, data: bytes) -> bytes:
ct = int(data.hex(), 16)
pt = pow(ct, self.d, self.n)
return long_to_bytes(pt)
def main():
crypto = RSA()
output= “05c61636499a82088bf4388203a93e67bf046f8c49f62857681ec9aaaa40b4772933e0abc83e938c84ff8e67e5ad85bd6eca167585b0cc03eb1333b1b1462d9d7c25f44e53bcb568f0f05219c0147f7dc3cbad45dec2f34f03bcadcbba866dd0c566035c8122d68255ada7d18954ad604965”
val = crypto.decrypt(binascii.unhexlify(output))
print(val.decode())
if __name__ == ‘__main__’:
main()
Output:
Flag: HTB{n3v3r_us3_sm4ll_3xp0n3n7s_f0r_rs4}