Tags: cryptography-rsa

Rating: 0

This was classic RSA as well but with 2 small twists:
1) The flag was not in typical format
2) The original message was padded in such a way that decoding it as hex gives some weird characters

n was easily factored in this case, p and q being quite close. From there it is trivial to get the message as an int and encode as hex. After that you had to add a leading 0 to make sure it's not an odd lenght string. Decoding that just gave weird characters but I could see that the end of the message looked suspiciously like base64. The string was separated by \x00 which made the rest easy.

Full script:


from Crypto.PublicKey import RSA
from Arithmetic import *

p = '12779 877140 635552 275193 974526 927174 906313 992988 726945 426212 616053 383820 179306 398832 891367 199026 816638 983953 765799 977121 840616 466620 283861 630627 224899 026453'.replace(' ','')
q = '12779 877140 635552 275193 974526 927174 906313 992988 726945 426212 616053 383820 179306 398832 891367 199026 816638 983953 765799 977121 840616 466620 283861 630627 224899 027521'.replace(' ','')

p = int(p)
q = int(q)

n = p*q

phi = (p-1)*(q-1)

d = modinv(k.e,phi)

c_int = int(c.encode('hex'),16)

mess = pow(c_int,d,n)

mess = hex(mess)[2:-1]
mess = '0' + mess
mess = mess.decode('hex')

mess = mess.split('\x00')

print mess[-1].strip('\n').decode('base64')