Clue

Krafty Kat implemented an RSA encryption. Can you spot a weakness, and decrypt the flag?

Hint

Perhaps this guy can help you?

Approach

This was a tricky one. The key was the modulus in the public key. To get the modulus, we can use OpenSSL to print it out:

openssl rsa -noout -inform PEM -modulus -pubin -in ../content/key.pem

Modulus=800000000040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000473

Converting that number to decimal gives us:

258536048570605626988915097172641057803353415992887757589736645808726151727194085610744190012322229640908553929414833022731988789391928353742297595957524280335918484224592037842886381777837922164216258913020883767452162759055614423529478656392491416399318604362756647059576165428708885769576577464120568116338612287783043168328279883802253392551292712278925133675758884573430117126518137049529478694956180472120065649305066144792948879520988172974401270565515875720597321219813209954571652637983550511681618170361995093036165713586725018263017699754932627926751512891645482818654590419836934782173099306176053375927411

Looking that number up in FactorDB tells us that it is prime.

The modulus is supposed to be the factor of two prime numbers (p and q). Since the modulus is prime, that means our numbers are that really large number above and 1. At this point it just takes math to get the other values needed for the RSA algorithm. Luckily there are tools out there that do this for you. One example is the RSACtfTool. *Note: This tool was actually updated during this CTF to solve our particular challenge, because it did not handle the modulus being prime prior to this competition.

Running the tool with our p and q:

 ./RsaCtfTool.py -p 0x800000000040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000473 -q 1 --uncipherfile ../flag.enc --publickey ../key.pem

Clear text : b'cm19-rRRr-SSSs-AaaA-f41l'

Since the tool also uses FactorDB to lookup the modulus, the command line can be even more simplified:

./RsaCtfTool.py --uncipherfile ../flag.enc --publickey ../key.pem
[+] Clear text : 'cm19-rRRr-SSSs-AaaA-f41l'

Return to the full breakdown of the Codemash CTF