# Basics - Crypto - RSA

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.

## How it works

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 values``

and compute the original message from the ciphertext as:

``m = pow(c, d, N) # Decryption, d is a private value``

### Setup

However, 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.

### Example

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

### Notes

• Due to using modular arithmetic, any message `m` that we want to encrypt must be smaller than the value of `N`.
• Due to using modular arithmetic, we can add `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.

## Challenge

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."""
try:
message = int(message, 16)
except Exception as ex:

# Decrypt signed message using the public key e
message = pow(message, e, N)