HackTheBox’s Lost Modulus RSA Crypto Challenge simple writeup

Description:

I encrypted a secret message with RSA but I lost the modulus. Can you help me recover it?

Task Files:

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

Analysis:

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 ofRon 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

Solution:

Add the below lines to challenge.py to Decrypt

Make Sure to Importbinasciibefore 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}