## Clue

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

## 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'
``````