The RSA Cryptosystem

Introduction

In 1976, Whitfield Diffie and Martin Hellman introduced to the world the concept of public key cryptography also known as asymmetric cryptography. But it wasn’t till 1977 when three people Ronald Rivest, Adi Shamir and Leonard Adleman proposed the scheme which would become the most used public key algorithm today called RSA.

There are many applications of RSA, in fact it is not actually used for encryption very often. The best uses of RSA is for:

Key transportation over an insecure channel.
Digital signatures.

It’s important to note that RSA is not a substitute for symmetric cryptography, as it is significantly slower than symmetric ciphers. In this post, we will explore the encryption and decryption process of RSA and delve into the reasons behind its slower performance. We will also discuss the security of RSA, and the math that is the basis for its security.

It is highly suggested that you read the following posts to fully understand RSA:

The RSA Algorithm

Unlike symmetric cryptography algorithms like DES and AES, public key algorithms require the computation of the key. Specifically it requires the computation of a key pair which is made of a public key k_pub and a private key k_pr.

This is different than how we generate the key in symmetric cryptography which are generated randomly for security. In asymmetric cryptography we use quite heavy math to ensure keys are made securely. So lets see how we compute the key pair in RSA.

RSA Key Generation

Depending on the public key algorithm the key generation can be pretty complex. Thankfully RSA key generation is not to bad, and this only has to be done once, i.e. it doesn’t have to be done for each encryption and/ or decryption.

RSA Key Generation:

Choose two ‘large’ primes p, q. such that p, q ≥ 2 ⁵¹².
Compute n = p ⋅ q.
Compute ϕ(n) = (p – 1) ⋅ (q – 1).
Choose k_pub = e ∈ {1, 2, …, ϕ(n) – 1}, such that gcd(e, ϕ(n)) = 1.
Compute k_pr = d such that d⋅ e ≡ 1 mod ϕ(n).

From this we get the key pair k_pub = (e, n) and k_pr = d.

What do I mean when I say ‘large’ primes when picking p and q? When we are picking p and q for RSA key generation we mean we want p and q to be at least ≥ 2 ⁵¹². So that p ⋅ q = n ≥ 2 ¹⁰²⁴. In fact we usually want p and q to be twice that, i.e. p, q ≥ 2 ¹⁰²⁴ sop ⋅ q = n ≥ 2²⁰⁴⁸. Note that you may see people say they want RSA with security 2048. They are referring to how large n is, not how large p and q are.

You may also be wondering how we compute d? But it is actually quite simple, we use the Extended Euclidean Algorithm! That is why we introduced that in Introduction to Asymmetric Cryptography, so if you need a refresher or don’t recognize that algorithm I suggest you read that first because I will assume you know how the Extended Euclidean and the Euclidean algorithm work.

RSA Encryption & Decryption

RSA encryption and decryption are done in an integer ring ℤ_n which is why I suggested you read Introduction to Modular Arithmetic if you don’t know what a ring is in this use. The beauty of RSA and public key is that the algorithms are quite simple on the surface.

RSA Encryption: Given k_pub = (e, n) and x ∈ ℤ_n= {0, 1, …, n – 1}.

y = e_{k_pub}(x) ≡ x^e mod n.

That’s it, really! No multiple rounds of abstract matric multiplication and shifting with s-boxes. Just a simple exponentiation and a modular reduction.

Here is decryption in RSA:

RSA Decryption: Given k_pr = d and y ∈ ℤ_n= {0, 1, …, n – 1}.

x = d_{k_pr}(y) ≡ y^d mod n.

Not bad huh? Well the simplicity is a little deceptive. Recall these numbers can be huge! Like a few 100 digits long, so computing these x and y are not free, it takes a fair bit of computing power to do this. Since we can choose e depending on the gcd condition, we can choose a small value. But d is still typically a large number. For perspective here is an example of the size of e and d.

Example of values:

n = 8426380390767063404067292414722201545067870269163079145022138082473198563764916951495558681815854547630225357542305962567820977552695224472095364909059521322749754608506314673073110954847385458182234056932218929632428161501975641844255300279358306258453783620390066301168516989317386447813808781010303495276030292778950118500013142207550527535325934282627351616454325538354747235961930734340601618421400551531346301322107808905147785690539299064167212767752829594365243408475185696588960303179144282384534339464973722322920288775732232417027840706375875002438620275126522655234928750770235444596145999070981154150993

e = 65537

d = –2417584425402339032709420621542358601277311513665156738389783822340716733974270006850649097367647482476938636157712117035609470084430601122248640407480448898052453360754142466054193894807442952381106046546172582417238303869900178427415542535556620421711498747489119377769376458338569317763142141223076073388646792840290623286358143725859790903917537762585524886398381961254690352811567463446030863625986159646720585246523415298814345769377032964907916255151646847009160419632475607920791920496440154155451894555839906288648996235199230751898176548475729347850998845554354766801839866132851687700312301447794150589007

As you can probably guess from those example values, it could take a bit to actually compute these exponents especially in decryption since we have no way to make d smaller. Before we discuss a way to make this faster lets go over an example of RSA key generation, encryption and decryption with small numbers.

Example:

Let p = 3 and q = 11.
Compute n = 3 ⋅ 11 = 33.
Compute ϕ(n) = (3 – 1) ⋅ (11 – 1) = 2 ⋅ 10 = 20.
Choose e = 3, check gcd(3, 20) = 1.
Derive d = 7, check 7 ⋅ 3 = 21 ≡ 1 mod 20.

Let x = 4. So the encrypt we compute:

y = 4³ mod 33 = 31.

To decrypt:

x = 31⁷ mod 33 = 4.

Which is what we wanted.

I mentioned this quite a few times, but it is because it is important. The parameters we are using a really big, and as you now know computing these exponents the way we know isn’t all that fast. It is important that these algorithms are fast because imagine you are on a website, and it is using RSA to verify you. If the algorithm is slow that means they can’t display the website until the computation is done, and it is expected that things are fast. So that could mean the difference of someone staying on your website and leaving.

So we need a way to do these exponentiations faster.

Fast Exponentiation

The problem we face in RSA is that exponentiation as we know is slow when it comes to large numbers. But if we somehow reduced the size of the numbers into smaller chunks we can speed up the operation considerably.

But lets see how we do exponentiation currently:

Naïve Example: x⁴ = ?

x ⋅ x = x².
x ⋅ x²= x³.
x ⋅ x³ = x⁴.

Total of 3 Multiplications.

Better Example: x⁴ = ?

x ⋅ x = x².
x² ⋅ x²= x⁴.

Total of 2 Multiplications.

Notice the slight improvement using the better example, which is probably how you intuitively think of how to solve the example. Lets see how it works with larger exponenets.

Naïve Example: x⁸ = ?

x ⋅ x = x².
x ⋅ x²= x³.
x ⋅ x³ = x⁴.
x ⋅ x⁴ = x⁵.
x ⋅ x⁵ = x⁶.
x ⋅ x⁶ = x⁷.
x ⋅ x⁷ = x⁸.

Total of 7 Multiplications.

Better Example: x⁸ = ?

x ⋅ x = x².
x² ⋅ x²= x⁴.
x⁴ ⋅ x⁴= x⁸.

Total of 3 Multiplications.

With this example you can see how the improvements are getting better and better when the exponent gets bigger and bigger. Lets see how good of an improvement we can get with numbers that we want to work with in RSA.

Naïve Example: x^2¹⁰²⁴ = ?

x ⋅ x = x².
x ⋅ x²= x³.
…
x ⋅ x^{2¹⁰²⁴ – 1} = x^2¹⁰²⁴ .

Total of 2¹⁰²⁴ – 1 Multiplications.

Better Example: x^2¹⁰²⁴ = ?

x ⋅ x = x².
x² ⋅ x²= x⁴.
…
x^2¹⁰²³ ⋅ x^2¹⁰²³ = x^2¹⁰²⁴ .

Total of 1024 Multiplications.

Now you can really see the improvements using the better method. Compared to the naïve way which would take more multiplications than there are atoms in the universe, we can do it by hand in an afternoon if we wanted to. But you may have noticed a problem with this better way, and that is the exponent has to be a power of 2. So we need a algorithm to use this trick, but for any number. That is where the square-and-multiply algorithm comes in.

Square-and-Multiply Algorithm

So we have to change this method to work with any number. To introduce this method I will first show an example to give an idea of how the algorithm works, then we will go into detail how it works.

Example: x²⁶ = ?

SQUARE: x ⋅ x = x².
MULTIPLY: x ⋅ x²= x³.
SQUARE: x³ ⋅ x³= x⁶.
SQUARE: x⁶ ⋅ x⁶= x¹².
MULTIPLY: x ⋅ x¹²= x¹³.
SQUARE: x¹³ ⋅ x¹³= x²⁶.

Total of 6 Multiplications.

Not to bad huh? But now that we know an example, we need to know how it works. Further more we need an algorithm to do this quickly for any number.

First lets notice in the last example we are either squaring or multiplying. But how do we decide when to square and when to multiple? I could do what I usually do and show you the algorithm or the pseudo code, but I think there is an easier way to see this. There is a better way to show how we decide to square or multiply, and that is by looking at the binary representation of the exponent. The idea behind this is to use traits of binary operations to ‘rebuild’ the exponent step by step using only squares or multiples. To show this I will use the same example:

Example: x²⁶ = x^11010₂ = ?

For the first step we only have one option, and that is to square:

x^1₂ ⋅ x^1₂ = x^10₂.

Going left to right of 11010₂ we have 10₂, so we want to make that right bit into a 1. To do that we multiply:

x^1₂ ⋅ x^10₂ = x^11₂.

Now we square to get another 0 on the end:

x^11₂ ⋅ x^11₂ = x^110₂.

Notice we have the same first three bits from 11010₂so we square again:

x^110₂ ⋅ x^110₂ = x^1100₂.

We need to change that right most 0 bit into a 1 bit, so we multiply:

x^1₂ ⋅ x^1100₂ = x^1101₂.

Then we square once more to get:

x^1101₂ ⋅ x^1101₂ = x^11010₂ = x²⁶.

Total of 6 Multiplications.

*Notice if you went back to the original example above you would get the same steps.

Okay so to summarize the square-and-multiple algorithm now that we have a good idea of how it works we do:

Scan the exponent bits left-to-right, then:

In each iteration we square
If the current bit is 1 then we also multiply by x.

This gives us a much faster way to take the exponent for even very large numbers. But note that even though we speed the RSA encryption/ decryption algorithm considerably using the square-and-multiply algorithm it is still slower than symmetric ciphers like AES. For that reason RSA is not typically used to encrypt data but is used for key exchanges or digital signatures (these will be discussed in further posts).

Code Implementation

Here is my code implementation of the RSA encryption and decryption algorithm in Python this is done for educational purposes, so should not be used for documents that need verifiable security. This implementation for my blog will only have the encryption/ decryption, so the key generation was done before hand. If you want to see a more organized program with the key generation make sure to check out my GitHub here.

				
					# By: Hunter Richardson
# Date: 10/10/2023

# For the purpose of education

# This implementation is tested using NIST standards:


import math

class Key:
    e = 65537
    d = -2417584425402339032709420621542358601277311513665156738389783822340716733974270006850649097367647482476938636157712117035609470084430601122248640407480448898052453360754142466054193894807442952381106046546172582417238303869900178427415542535556620421711498747489119377769376458338569317763142141223076073388646792840290623286358143725859790903917537762585524886398381961254690352811567463446030863625986159646720585246523415298814345769377032964907916255151646847009160419632475607920791920496440154155451894555839906288648996235199230751898176548475729347850998845554354766801839866132851687700312301447794150589007
    n = 8426380390767063404067292414722201545067870269163079145022138082473198563764916951495558681815854547630225357542305962567820977552695224472095364909059521322749754608506314673073110954847385458182234056932218929632428161501975641844255300279358306258453783620390066301168516989317386447813808781010303495276030292778950118500013142207550527535325934282627351616454325538354747235961930734340601618421400551531346301322107808905147785690539299064167212767752829594365243408475185696588960303179144282384534339464973722322920288775732232417027840706375875002438620275126522655234928750770235444596145999070981154150993

def encrypt(x, e, n):
    return pow(x, e, n)

def decrypt(y, d, n):
    return pow(y, d, n)

def main():
    k = Key()
    
    plaintext_message = int(input("Enter plain text here:"))
    ciphertext_message = encrypt(plaintext_message, k.e, k.n)
    print("Encrypted ciphertext: " + str(ciphertext_message))

    plaintext_message = decrypt(ciphertext_message, k.d, k.n)
    print("Decrypted plaintext: " + str(plaintext_message))



if __name__ == '__main__':
    main()

Security of RSA

Even though a few attacks have been proposed against RSA. The only one that threatens RSA is quantum computing. There are a few other proposed attacks, but those mainly attack the implementation of RSA rather than the algorithm itself. Lets look at the attacks.

Quantum Computing: The rise of quantum computing poses a new threat to RSA’s security. It is believed that quantum computers, when they become sufficiently advanced, could efficiently factor large numbers, rendering RSA obsolete. As a result, there is ongoing debate about the recommended length of RSA moduli. To ensure long-term security, it is advisable to select RSA parameters within the range of 2048 to 4096 bits, as shorter lengths may become vulnerable to quantum attacks within a decade or so as of 2023.

Protocol Attacks: In this type of attack an attacker tries to find a weakness in how RSA is being used. One of these ways is how the original p and q are chosen. The YouTube channel Computerphile has a great video over it which I will link below. But essentially if p and q are chosen and they are very close to each other, then it is very easy for an attacker to factor n, to get its prime factorization which can be used to find the Euler Phi Function.
Video: https://www.youtube.com/watch?v=-ShwJqAalOk

There are a few other methods such as mathematical attacks which try to use math to find the prime factorization faster or side-channel attacks which exploit information about the private key which is given through physical channels like power consumption.