Tags: cryptography-rsa
Rating:
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 *
k=RSA.importKey(open('pub.key').read())
c = open('enc.message','rb').read()
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')
```