We get two pieces of information; what looks like an RSA public key:
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhALYtzp8lgWNXI9trGI8S8EacvuDLxdrL
NsNuDJa26nv8AgMBAAE=
-----END PUBLIC KEY-----
and what appears to be an encrypted message:
kPmDFLk5b/torG53sThWwEeNm0AIpEQek0rVG3vCttc=
The description mentions that:
- we’ll want to decrypt the message with the missing private key
- there is a missing 1 bit
- we might want to do prime factorisation.
So let’s take a closer look at the public key using Python:
from Crypto.PublicKey import RSA
pubkey = RSA.importKey(open('PublicKey.pem').read())
print 'n =', pubkey.nwhich gives us the key's modulus as
n = 82401872610398250859431855480217685317486932934710222647212042489320711027708
This looks to be 256-bit (easily factorable), but it doesn't look right; the modulus should be the product of two 128-bit primes, yet it's even?!
So what about that missing 1 bit... well there are two ways we could throw in a 1 bit (in a useful way that makes the modulus no longer even, that is). We could append a 1 to the end of the modulus:
(n << 1) | 1 = 164803745220796501718863710960435370634973865869420445294424084978641422055417
Unfortunately WolframAlpha tells us this is prime, so not a great modulus! We could also try replacing the least-significant bit with 1:
n | 1 =
82401872610398250859431855480217685317486932934710222647212042489320711027709
WolframAlpha doesn't tell us anything about its factors, so they probably aren't too small (and thus hopefully non-trivial); we'll have to use something a bit more heavy-duty to factor it though, like msieve.
./msieve 82401872610398250859431855480217685317486932934710222647212042489320711027709
This takes a couple of minutes to factor, but we eventually get (from msieve.log) that our modified modulus has factors
p = 279125332373073513017147096164124452877
q = 295214597363242917440342570226980714417
which looks promising! Let's try making a private key out of these and decrypting the message:
from Crypto.PublicKey import RSA
import gmpy
msg = "kPmDFLk5b/torG53sThWwEeNm0AIpEQek0rVG3vCttc="
# factors of the modified modulus, from msieve
p = 279125332373073513017147096164124452877L
q = 295214597363242917440342570226980714417L
n = p*q
e = 65537L # standard e, was also in the public key we were given
# calculate d based on the factors; thank you gmpy
d = long(gmpy.invert(e, (p-1)*(q-1)))
privkey = RSA.construct((n,e,d,p,q))
print repr(privkey.decrypt(msg.decode('base64')))which gives us
'\x02\xd8T\xf1v\xea\xa0y!\x00TMCTF{$@!zbo4+qt9=5}\n'
and hence we have our flag
TMCTF{$@!zbo4+qt9=5}
Yay!