RSA step by step

1. What RSA is doing

RSA uses a pair of mathematically related keys:

• 🔓 Public key — can be shared with everyone.
• 🔐 Private key — must remain secret.

For encryption, the important idea is:

              Alice                                  Bob
       wants to send "7"                       owns the key pair

                                                    ┌─────────────┐
                                                    │ PUBLIC KEY  │
                                                    │   (n, e)    │
                                                    └──────┬──────┘
                                                           │
                         public key ◀───────────────────────┘
                              │
                              ▼
                         ┌─────────┐
                         │ message │
                         │    7    │
                         └────┬────┘
                              │
                              │ use public key
                              │
                              ▼
                    ┌───────────────────┐
                    │     ENCRYPT       │
                    │                   │
                    │   c = m^e mod n   │
                    └─────────┬─────────┘
                              │
                              ▼
                         ┌──────────┐
                         │ciphertext│
                         │    13    │
                         └────┬─────┘
                              │
                              │ send over network
                              │
              ────────────────┼──────────────────────────────▶
                              │
                                                          Bob
                                                           │
                                                           ▼
                                                    ┌─────────────┐
                                                    │ PRIVATE KEY │
                                                    │   (n, d)    │
                                                    └──────┬──────┘
                                                           │
                                                           ▼
                                                 ┌───────────────────┐
                                                 │      DECRYPT      │
                                                 │                   │
                                                 │   m = c^d mod n   │
                                                 └─────────┬─────────┘
                                                           │
                                                           ▼
                                                      ┌─────────┐
                                                      │ message │
                                                      │    7    │
                                                      └─────────┘

The interesting property is:

                    PUBLIC                         PRIVATE

message ──────▶ RSA operation ──────▶ ciphertext ──────▶ RSA operation
   7               using e                13               using d
                                                               │
                                                               ▼
                                                               7

The public key can therefore be given to anyone:

Public key
   │
   ├── n
   └── e

while the private key stays with the owner:

Private key
   │
   ├── n
   └── d

For now, we will ignore how the keys were generated.

Assume somebody has already given us:

public_key = {55, 3}
private_key = {55, 27}

That means:

Public key
(n, e)
(55, 3)


Private key
(n, d)
(55, 27)

Let's encrypt the number 7.

message = 7

{n, e} = public_key

ciphertext =
  message
  |> Integer.pow(e)
  |> rem(n)

ciphertext

Result:

13

So this happened:

        message
           7
           │
           │ public key (55, 3)
           ▼
      7³ mod 55
           │
           ▼
          13
       ciphertext

Now decrypt it with the private key:

{n, d} = private_key

decrypted_message =
  ciphertext
  |> Integer.pow(d)
  |> rem(n)

decrypted_message

Result:

7

So the complete journey was:

                    PUBLIC KEY                     PRIVATE KEY
                     (55, 3)                        (55, 27)
                        │                               │
                        ▼                               ▼

      7  ─────────▶  7³ mod 55  ─────▶  13  ─────▶ 13²⁷ mod 55 ─────▶ 7

   message                            ciphertext                       message

Or mathematically:

Encryption:

c = m^e mod n

c = 7³ mod 55
c = 13

and:

Decryption:

m = c^d mod n

m = 13²⁷ mod 55
m = 7

Why does this work?

7
│
│ raise to e
▼
7^e mod n
│
│ raise to d
▼
7 again

And where did these numbers come from?

n = 55
e = 3
d = 27

That is what we will build step by step.

The journey starts with two prime numbers:

              p = 5              q = 11
                 \                /
                  \              /
                   \            /
                    ▼          ▼

                      n = p × q

                      n = 55

From p and q, we will eventually construct:

             p                  q
              \                /
               \              /
                └──────┬─────┘
                       │
                       ▼
                       n
                       │
                ┌──────┴──────┐
                │             │
                ▼             ▼
                e             d
                │             │
                ▼             ▼
          PUBLIC KEY     PRIVATE KEY
            (n, e)         (n, d)

Important: this notebook is implementing RSA with tiny numbers to understand the mathematics. It is not an implementation that should be used for real cryptography.

Main Parts

Key generation

                 ┌──────────────┐
                 │ KEY GENERATION│
                 └──────┬───────┘
                        │
              ┌─────────┴─────────┐
              │                   │
              ▼                   ▼
         secret p             secret q
              │                   │
              └─────────┬─────────┘
                        │
                        ▼
                   n = p × q
                        │
                        ▼
                 derive e and d
                        │
              ┌─────────┴─────────┐
              │                   │
              ▼                   ▼
       ┌──────────────┐     ┌──────────────┐
       │  PUBLIC KEY  │     │ PRIVATE KEY  │
       │    (n, e)    │     │    (n, d)    │
       └──────────────┘     └──────────────┘

Encryption and decryption

       ┌─────────────┐
       │   MESSAGE   │
       └──────┬──────┘
              │
              ▼
     convert / pad message
              │
              ▼
       ┌─────────────┐
       │ PUBLIC KEY  │
       │    (n, e)   │
       └──────┬──────┘
              │
              │  c = m^e mod n
              ▼
       ┌─────────────┐
       │ CIPHERTEXT  │
       └──────┬──────┘
              │
              ▼
       ┌─────────────┐
       │ PRIVATE KEY │
       │    (n, d)   │
       └──────┬──────┘
              │
              │  m = c^d mod n
              ▼
       ┌─────────────┐
       │   MESSAGE   │
       │  recovered  │
       └─────────────┘

What is a prime number?

# A prime number has exactly two positive divisors: 1 and itself
prime_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23]
# 11 = 1x11 -> prime, because it is only divisible by 1 and itself
# 12 = 2 × 6 = 3 × 4 -> not a prime, because it is divisible by 1, 2, 3, 4, 6, itself

RSA chooses two primes

# Requirements for the prime numbers:
# 1. They must be different p != q
# 2. They must be big (e.g. ~1024 bits each or ~300 decimal digits). NOTE: 2^1024 ~ 10^308
# 3. They must be secret
p = 11 # secret
q = 17 # secret

RSA multiplies them

# The product of these two primes is ~2048 bits number or ~600 decimal digits
# RSA reveals the product while hiding its factors.
n = p * q # public
# NOTE: If the numbers are not big you can easily find them 
# Is n divisible by 2? -> no.
# Is n divisible by 3? -> no.
# Is n divisible by 5? -> no.
# Is n divisible by 7? -> no.
# Is n divisible by 11? -> yes. Thus p = 11 and q = n / p = 187 / 11 = 17.

# Why different p and q?
# Let's pick p and q to be equal to 4957
# p1 = 4957
# n1 = p1 * p1
# :math.sqrt(n1)
# Then only thing we need to do is to take the square root of n and we will find p.

# What is the role of n?
# 1. It is the modulus used by RSA arithmetic.
# 2. It hides p and q behind the difficult integer-factorisation problem.

Why primes rather than arbitrary numbers?

# This is partly because prime numbers give RSA very clean mathematical structure.
# Prime numbers allows us to use #Euler's totient function — φ(n). https://en.wikipedia.org/wiki/Euler%27s_totient_function
# φ(n) tells us: How many positive integers smaller than n are coprime with n?

What does coprime mean?

# Two numbers are coprime if their greatest common divisor is 1.
a = 8 # divisors 1, 2, 4, 8
b = 15 # divisors 1, 3, 5, 15
# a and b are coprime because the only factor they share is 1.
Integer.gcd(8, 15) # greatest common divisor
# Integer.gcd(6, 15) # 6 -> 1, 2, 3, 6
# NOTE: the coprimes don't need to be prime themselves

What does φ(n) actually count?

# take n = 10
# φ(n) looks at
# 1 2 3 4 5 6 7 8 9
# Checks if they are coprime
# 1 → gcd(1,10) = 1    ✓
# 2 → 2                ✗
# 3 → 1                ✓
# 4 → 2                ✗
# 5 → 5                ✗
# 6 → 2                ✗
# 7 → 1                ✓
# 8 → 2                ✗
# 9 → 1                ✓
# Integer.gcd(5, 10)
# So the coprimes are 1, 3, 7, 9. There are four.
# Therefore φ(10) = 4

φ(p) is especially simple when p is prime

# Suppose p = 7; a prime number
# Every positive number smaller than 7 is coprime with 7:
# 1, 2, 3, 4, 5, 6
# This is because the prime number has as a divisor only 1 and itself.
# So none of the numbers 1..6 can share a divisor with it other than 1.
# φ(7) = 6
# More generally when p is prime φ(p) = p - 1. 
# This fact is one reason primes are so convenient in RSA.

Now return to our RSA example

p = 11
q = 17
n = p * q # 187 = 11x17

# What is φ(187)?
# 187 = 11x17
# A number fails to be coprime with 187 only if it is divisible by:
# 11 or 17
# Let's look at multiples of 11
# The only numbers in the range 1..186 that are divisible by 11 are
# 11
# 22
# 33
# 4x11
# ...
# 15x11 = 165
# 16x11 = 176
# 17x11 = 187 this is bigger than 186 thus we stop at 16.
# So we eliminate 16 numbers.

# Let's now look at multiples of 17
# 17
# 34
# 3x17
# ...
# 10x17 = 170
# 11x17 = 187 this is bigger than 186 thus we stop at 10.
# So we eliminate 10 numbers.

# We count what remains 186 - 16 - 10 = 160
# Therefore φ(187) = 160

Where does the famous RSA formula come from?

# Let's start with n = p * q
# Among the numbers 1...p*q, there are:
# q multiples of p:
#    p, 2p, 3p, …, q*p
# and p multiples of q:
#    q, 2q, 3q, …, p*q
# But p * q appears in both lists, so we've counted it twice.
# Therefore the number divisible by p or q is:
#    p + q − 1
# There are p*q numbers total, so the number coprime to p*q is:
#    p * q − (p + q − 1)
# Expand: 
#    p * q - p - q + 1
# Factor:
#    (p - 1) * (q - 1)
#
# φ(n) = φ(p*q) = (p - 1) * (q - 1) 
# φ(187) = φ(11*17) = (11 - 1) * (17 - 1) = 10 * 16 = 160
# NOTE: This works only if the p and q are prime

But why does RSA care about this count?

# When working modulo n, the numbers coprime with n have a special property:
# They have multiplicative inverses modulo n.

What does a modulo n mean?

# Modulo n means we only care about the remainder after division by n.
# For example, modulo 10:
# 27 / 10 = 2 remainder 7
# 27 mod 10 = 7
# 7 mod 10 = 7
# This means 27 and 7 are equivalent when working modulo 10.
Integer.mod(27, 10) == Integer.mod(7, 10)

# The numbers therefore "wrap around" every 10:
# 7
# 17
# 27
# 37
# 47
# ...
# all are 7 modulo 10
Enum.map([7, 17, 27, 37, 47, 57], &Integer.mod(&1, 10)) 
|> IO.inspect(charlists: :as_lists)

# You can think of modular arithmetic a little like a clock:

# modulo 10
# 0 → 1 → 2 → 3 → ... → 9
# ↑                       │
# └───────────────────────┘

# After reaching 9, adding 1 takes us back to 0.

# For RSA, this "wrapping around" is important 
# because almost all of the core calculations happen modulo some number.

What does a multiplicative inverse modulo n mean?

# Normally, a multiplicative inverse is a number that gets us back to 1.
# For example the inverse of 5 is 1/5.
# 5 * 1/5 = 1.

# In modular arithmetic we ask a slightly different question:

# For a number a, can we find another integer x such that their product becomes 1
# after taking modulo n?

# Mathematically:
#    a × x ≡ 1 (mod n)
#    a × x = 1 + k × n; k = 0, 1, 2, ...

# For example let's work modulo 10.
# Let's take a = 3
# The multiplicative inverse of 3 modulo 10 is 7:
# 3 × 1 = 3 mod 10 = 3
# 3 × 2 = 6 mod 10 = 6
# 3 × 3 = 9 mod 10 = 9
# 3 × 4 = 12 mod 10 = 2
# 3 × 5 = 15 mod 10 = 5
# 3 × 6 = 18 mod 10 = 8
# 3 × 7 = 21 mod 10 = 1 <- BINGO
# 21 mod 10 = 1
Integer.mod(3 * 7, 10)

# But not every number has an inverse.

# For example, 2 has no multiplicative inverse modulo 10.

# The reason is:
# gcd(2, 10) = 2 
Integer.gcd(2, 10)

# They are not coprime!
# A modular inverse exists exactly when:
# gcd(a, n) = 1 
# a and n need to be coprime

Why does RSA care?

# Earlier we calculated:
# n = 187 
# φ(187) = 160
# RSA needs to choose a public exponent `e` that is coprime with 160.

# For example:
# e = 7
# gcd(7, 160) = 1
Integer.gcd(7, 160)
# Therefore 7 has a multiplicative inverse modulo 160.
# That inverse is:
# d = 23
# because:
# 7 × 23 = 161
# 161 mod 160 = 1
Integer.gcd(23, 160)

defmodule RsaLab.Math do
  # Euler's totient (phi) for n = p * q, where p and q are distinct primes.
  def phi_from_primes(p, q) do
    (p - 1) * (q - 1)
  end
end

p = 11
q = 17

n = p * q
phi = RsaLab.Math.phi_from_primes(p, q)

%{
  p: p,
  q: q,
  n: n,
  phi: phi
}

1 and itself

Day 2

Key generation

                 ┌──────────────┐
                 │ KEY GENERATION│
                 └──────┬───────┘
                        │
              ┌─────────┴─────────┐
              │                   │
              ▼                   ▼
         secret p             secret q
              │                   │
              └─────────┬─────────┘
                        │
                        ▼
                   n = p × q
                        │
                        ▼
                 derive e and d
                        │
              ┌─────────┴─────────┐
              │                   │
              ▼                   ▼
       ┌──────────────┐     ┌──────────────┐
       │  PUBLIC KEY  │     │ PRIVATE KEY  │
       │    (n, e)    │     │    (n, d)    │
       └──────────────┘     └──────────────┘

Encryption and decryption

       ┌─────────────┐
       │   MESSAGE   │
       └──────┬──────┘
              │
              ▼
     convert / pad message
              │
              ▼
       ┌─────────────┐
       │ PUBLIC KEY  │
       │    (n, e)   │
       └──────┬──────┘
              │
              │  c = m^e mod n
              ▼
       ┌─────────────┐
       │ CIPHERTEXT  │
       └──────┬──────┘
              │
              ▼
       ┌─────────────┐
       │ PRIVATE KEY │
       │    (n, d)   │
       └──────┬──────┘
              │
              │  m = c^d mod n
              ▼
       ┌─────────────┐
       │   MESSAGE   │
       │  recovered  │
       └─────────────┘

Euler discovered a crucial property

# Euler's theorem gives us an important property of numbers that are coprime with n.
# If gcd(a, n) = 1, then a ^ phi(n) = 1 mod n.
# Here `^` means a ^ b - 'a raised to the power b' (e.g. 2 ^ 3 = 2 * 2 * 2).
# If a and n are coprime, raising a to the power phi(n) brings us back to 1 modulo n.
# The Euler's theorem is a bridge between phi(n) and RSA.

# What did we have in our example
p = 11
q = 17
n = 187 # p * q = 187
phi_n = 160 # phi(187) = (p - 1) * (q - 1) = 10 * 16 = 160

# Example:
a = 2
Integer.gcd(a, n) |> IO.inspect(label: "gcd(#{a},#{n}) =")
# Euler's theorem tells us:
# a ^ phi(n) ≡ 1 (mod n)
# 2^160 = 1 mod 187 
# 2^160 = 1461501637330902918203684832716283019655932542976 mod 187 = 1 + k*187

How do we will choose e and d?

# Soon we will choose e and d so that:
# e * d = 1 mod phi(n) = 1 + k * phi(n); where k = 1, 2, ...

# That lets RSA turn:
# m ^ (e * d)
# into:
# m ^ (1 + k * phi(n)) = m * (m ^ k * phi (n)) = m * (1) = m
# and Euler's theorem is what eventually makes this collapse back to: m

# Euler: a ^ phi(n) ≡ 1
# Choose e and d: e * d ≡ 1 mod phi(n)
# RSA: m ^ (e * d) ≡ m mod n

Roughly RSA modular arithmetic

# φ(n)
#   ↓
# creates a repeating cycle in modular arithmetic
#   ↓
# choose e and d to line up with that cycle
#   ↓
# raising to e and then d returns to the original value

Choosing the public exponent e

# We pick e such that it has the property:
# gcd(e, phi(n)) = 1
# phi(n) = phi(187) = 160
# gcd(e, 160) = 1

# Why?
# Because e must have a multiplicative inverse modulo phi(n).  
# That inverse becomes the private exponent d.
# e * d = 1 (mod phi(n))
phi_n = 160
# Choose public e:
e = 7
Integer.gcd(e, phi) |> IO.inspect(label: "gcd(#{e},#{phi_n}) =")
# Choose private d:
d = 23
# e * d = 1 (mod phi(n))
Integer.gcd(e*d, phi) |> IO.inspect(label: "gcd(#{e}*#{d}=#{e*d},#{phi_n}) =")

So we have

# public exponent   e = 7
# private exponent  d = 23

#  e = 7
#    │ modular inverse mod phi(n)
#    ▼
#  d = 23

# we choose e coprime with phi(n) so that its modular inverse exists; that inverse is d
# e × d ≡ 1 (mod phi(n))

# NOTE: Not every number has a modular inverse
# If we pick for example:
# e = 8
# we need 8 * d = 1 (mod phi(n))
# 8 * 1 = 8 (mod 160)
# 8 * 2 = 16 (mod 160)
# 8 * 3 = 24 (mod 160)
# ...
# 8 * 19 = 152 (mod 160)
# 8 * 20 = 0 (mod 160)

# 8 * d = 1 + k * 160
# d = 1/8 + k * 20 <- this will always have reminder 
Integer.gcd(8, 160) |> IO.inspect(label: "gcd(8,160) =")

RSA needs

# gcd(e, phi(n)) = 1
#         ↓
# ed = 1 + k*phi(n)
#         ↓
# ed ≡ 1 mod phi(n)
#         ↓
# d exists

Which values of e could we choose?

# p = 11; q = 17, n = 187; phi(n) = 160
# This gcd(e, phi(n)) = 1 must be true
# 160 = 32 * 5 = 2^5 * 5
# e  | gcd(e,160) | Valid?
# 2	 |      2     | No
# 3	 |      1     |	Yes
# 4	 |      4     |	No
# 5	 |      5     |	No
# 6	 |      2     |	No
# 7	 |      1     |	Yes
# 8	 |      8     |	No
# 9	 |      1     |	Yes
# 10 |      10    |	No
# 11 |      1     |	Yes
# 13 |      1     |	Yes
# 15 |      5     |	No

# RSA doesn't require one unique e.
Integer.gcd(117, 160)

How could we choose e mathematically?

# 1. Calculate phi(n).
# 2. Pick an integer e where:
#        1 < e < phi(n)
# 3. Check:
#        gcd(e, phi(n)) = 1
# 4. If not, choose another e.

# For example:
# phi(n) = 160
# choose
e = 7
# gcd(7,160) = 1 <- valid
# We calculate d
# d = 7^−1 (mod 160)
# which gives us
d = 23

Real RSA usually doesn't randomly choose e

# Very frequently the e is
e = 65537
# 65537 = 2^16 + 1

# So you'll frequently see an RSA public key containing something conceptually like:

# n = enormous ~ 2048-bit number
# e = 65537

# The modulus changes for every key (the phi(n) part).
# But:
# e = 65537
# is very commonly reused.

# That's completely fine because e is public anyway.

Why 65537?

# 1. 65537 is a prime - which make the check gcd(65537, phi(n)) = 1 simpler  
# 2. It has a very convenient binary representation 65537 = 10000000000000001
#    only two bits are not zero
# small enough → fast public-key operations
# large enough → avoids problems associated with extremely tiny exponents