I had a bit of inspiration recently with Fermat’s Attack on RSA and
decided to make an RSA demonstrator. It shows all the steps in
performing an RSA encryption using 2 known primes. It might be useful
during a CTF when trying to determine small RSA keys by hand. I’ll
eventually post a follow up for implementing that attack for small p
and q.
RSA is one of the oldest public key cryptosystems out there. It was
initially described to the public in 1977. It uses a lot of prime
numbers and modular arithimatic. Since this is a public key cryptosystem
it only encrypts integers, since any text value could be considered an
integer. It should also be noted that the largest message that can be
encrypted is the product of p and q. To send larger messages,
typically a symetric cipher would be used and the key encrypted using
RSA.
You can find the source code on my GitHub. You should not use this as an example of good cryptography code. It’s probably vulnerable to all kinds of timing attacks and poor selection, but it will show the steps that RSA takes to encrypt and decrypt an integer. It’s important to note that you should never roll your own crypto in production. There’s a lot of ways that it can be gotten wrong especially with poor prime selection and timing attacks.
The default values were choosen from the example on Wikipedia.