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 as:
c = pow(m, e, N) # Encryption, e and N are public valuesand compute the original message from the ciphertext as:
m = pow(c, d, N) # Decryption, d is a private valueHowever, RSA does not work with any value for N, e and d.
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 p and 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 p and q.
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 p and q used to generate N if they are sufficiently large.
The fact that it is computationally infeasible to obtain p and q if we are only given N is the prime (pun intended) observation behind the RSA cryptosystem, because knowledge of p and q is required to create our private key d.
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 p and q and can therefore not be computed unless we know the values p and q.
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 e is 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
m that we want to encrypt must be smaller than the value of N.N to any message m and it will result in the same encryption, decryption as the original value of m. The same goes for the ciphertext, we can add N as many times as we want, we will still get the same decryption value.Our server implements the RSA-based sign and 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 FLAG?
# Imports
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
# Setup RSA
p = getPrime(2048)
q = getPrime(2048)
N = p*q # N = 565347863283825570507347599547652139827011191971933599606124804130778956353139418675649555252365740423245667070367065898087854040774470232306454250117334048367780612592640179611980961369293805317221465449315088740062685242505793843709273274842466380829834278369507228926131567210875512640022652447336529357050870921393438211866168130257109725841559226087325233882963401767966780497487555879167831874656542754752576827075926667003376042073056144854479088339874272771394740681856374946008428323688328527970429165774737962819480350763419860234645291161351682268814735984625216293324297276229379891254532262455906205813630445166130117830676619797805949970865292894892327892578096113320894043993985507801520075832059322181152777063766515559819642145317379487799787568390322961409539967168369761073640124258695773163020252887733580250110187306930478642159193775633100444771604116441374013396970386451646954528266708528365625927892649885024372634028684866887604207803825665979137824604947650906893251336908058399321796844194233382165633823826081068724837641181966472097288713579433991012326116734530865267137284473960585061926083860441150043285858999408590706498203241744455270430350931152664734584816552431764712595430492260448499103143631
e = 17
# Sign a message, only accessible to people with root access that know d
def sign(message, d, N):
"""Sign any given message using the private key d and modulo N."""
# Get message as bytes
message = bytes_to_long(message)
# Sign message using private key
signed = pow(message, d, N)
# Return signed message
return signed
# Send a GET request to https://vm-thijs.ewi.utwente.nl/ctf/challenge/rsa/verify/< message_to_verify >
def verify(message):
"""Verify whether the message has root access and is signed with the correct key."""
# Read message from hex
try:
message = int(message, 16)
except Exception as ex:
return {"error": "Can only read hexadecimal"}
# Decrypt signed message using the public key e
message = pow(message, e, N)
# Read message as bytes
message = long_to_bytes(message)
# Get the Null terminated string, for compatibility
message = message.split(b"\x00")[0]
# Check if user has root access
if message == b"Trust me, I have root access":
return {"flag": FLAG.hex()}
else:
return {"error": "Wait a minute, you don't have root access!"}