RSA is a widely used public-key (also known as asymmetric-key) cryptosystem. This means that encryption and decryption use different components. For encryption, we use a public component that everybody can use to encrypt messages. For decryption, we use a private component that only the person who wants to decrypt messages may know. This is different from symmetric-key cryptosystems such as AES which use the same key for encryption and decryption.
RSA is based on modular exponentiation in a group
N such that if we have a message
m, a public key
e and a private key
d we can compute the ciphertext
c = pow(m, e, N) # Encryption, e and N are public values
and compute the original message from the ciphertext as:
m = pow(c, d, N) # Decryption, d is a private value
However, RSA does not work with any value for
Instead, we must specifically choose these values such that applying encryption and decryption actually yield the original message.
Choosing these values is based on Fermat's little theorem. Here, we will simply explain how to choose such keys.
As a first step, we construct
N by multiplying two randomly chosen prime numbers
q, such that
N = p * q.
Because of the Fundamental theorem of arithmetic, we know that the only way to write
N as the product of primes is using the unique combination of
It is straightforward to compute
N as it is a simple multiplication.
However, if we are only given a number
N, it is computationally infeasible to obtain the primes
q used to generate
N if they are sufficiently large.
The fact that it is computationally infeasible to obtain
q if we are only given
N is the prime (pun intended) observation behind the RSA cryptosystem, because knowledge of
q is required to create our private key
After we generated
N, we compute Charmichael's totient function
totient(N), which is defined as
totient(N) = (p-1) * (q-1).
We note that this totient function requires knowledge of
q and can therefore not be computed unless we know the values
Using this the
totient(N), we choose the public key
e such that
1 < e < totient(N) and the greatest common divisor,
gcd(e, totient(N)) == 1. A commonly used value for
pow(2, 16) + 1 = 65537.
Finally, we compute the value for
d such that
d = pow(e, -1, totient(N)).
This final step is crucial, because this will be the only value for
d that ensures decryption is possible.
Now that the setup is complete, we can publish the public values
(e, N), so that everybody can encrypt messages to us.
Once we receive a message, we decrypt it using our private value
d and read the original message.
Below, we present a simple example for encryption and decryption using RSA in python. We use the library pycryptodome.
# Imports, uses pycryptodome: pip install pycryptodome from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime # Setup p = getPrime(2048) # Generate a random large prime (should ALWAYS be kept PRIVATE) q = getPrime(2048) # Generate a random large prime (should ALWAYS be kept PRIVATE) N = p*q # Compute PUBLIC value N from PRIVATE primes p and q totient = (p-1)*(q-1) # Compute PRIVATE totient function of N from PRIVATE primes p and q e = 65537 # Choose PUBLIC key e such that 1 < e < totient and gcd(e, totient) == 1, common value is 65537 d = pow(e, -1, totient) # Compute PRIVATE key d as the inverse of e given the PRIVATE totient # Prepare message message = b"my_secret_message" # Message bytes to encrypt message = bytes_to_long(message) # Transform bytes to a number (long) so that we can apply RSA # Encryption ciphertext = pow(message, e, N) # Encrypt message using PUBLIC values e and N # Decryption plaintext = pow(ciphertext, d, N) # Decrypt ciphertext using PRIVATE key d plaintext = long_to_bytes(plaintext) # Transform number back to bytes
mthat we want to encrypt must be smaller than the value of
Nto any message
mand it will result in the same encryption, decryption as the original value of
m. The same goes for the ciphertext, we can add
Nas many times as we want, we will still get the same decryption value.
Our server implements the RSA-based
verify functions below.
To capture the
FLAG, please allow us to
verify that you have root access by sending a message to the website https://vm-thijs.ewi.utwente.nl/ctf/challenge/rsa/verify/< message_to_verify >.
Can you sign the message
Trust me, I have root access and send it to the server to receive the