Notesclub

created by hec & contributors

terms privacy

RSA step by step

notebooks/rsa_step_by_step.livemd

Aleksandar

@isavita

rsa_lab

Share to X

Share to Bluesky

More notebooks

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:

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:

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.mod(e * d, phi_n) |> IO.inspect(label: "mod(#{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

Day 3

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  │
       └─────────────┘

How do we calculate the private exponent d?

p = 11 # private prime number
q = 17 # private prime number
n = 11 * 17 # 187 public number
phi_n = 160 # phi(187) = (p - 1) * (q - 1) = 10 * 16 =  160
e = 7 # public encryption exponent

# We need to find d satisfying:
# e * d = 1 (mod phi(n)) = 1 + k * phi(n)
# 7 * d = 1 + k * 160

# 7 * 1 = 7 mod 160 -> 7
# 7 * 2 = 14 mod 160 -> 14
# 7 * 3 = 21 mod 160 -> 21
# ...
# 7 * 22 = 154 mod 160 -> 154
# 7 * 23 = 161 mod 160 -> 1 <- Bingo!
# d = 23
# Does it need to be first one? Nope
# 7 * 183 = 1281 mod 160 -> 1
# Integer.mod(7 * 183, 160)

# d = Enum.find(1..(phi_n - 1), fn x -> Integer.mod(e * x, phi_n) == 1 end)

How the Extended Euclidean Algorithm finds d

# 160 = 22 * 7 + 6
# 7 = 1 * 6 + 1

# 1 = 7 - (160 - 22 * 7)
# 1 = 7 - 6

# 1 = 23 * 7 - 160

How the Extended Euclidean Algorithm works

# The ordinary Euclidean Algorithm finds the greatest common divisor gcd 
# of two numbers using repeated division.

# The Extended Euclidean Algorithm goes further
# it also finds two integers x and y satisfying:
# a * x + b * x = gcd(a, b) - This is called Bezout's identity.

# For RSA, we already know:

e = 7
phi_n = 160 # phi(187) = (p - 1) * (q - 1) = 10 * 16 = 160
# gcd(a = e, b = phi_n) = 1

# 7 * x + 160 * y = 1

# Step 1: Euclidean Algorithm (find GCD)
# We know that gcd(7, 160) = 1.

# Step 2: Work backwards (find x and y)
# 1 = 7 - 6
# 1 = 7 - (160 - 22 * 7)
# 1 = 23 * 7 - 160
# gcd(e, phi_n) = d * e + y * phi_n

x = 23
y = -1

# Verify Bezout's identity
e * x + phi_n * y |> IO.inspect(label: "Bezout's identity")

# Step 3: x is the modular inverse of e
# 7 * 23 = 1 (mod 160)
d = Integer.mod(x, phi_n) |> IO.inspect(label: "d")

# Verify our private exponent
Integer.mod(e * d, phi_n) |> IO.inspect(label: "e * d mod phi(n) = #{e} * #{d} mod (#{phi_n})")

Implementation in elixir

defmodule Euclid do
  # a * x + b * y == gcd(a, b)
  # we get {gcd, x, y}
  def extended_gcd(a, 0), do: {a, 1, 0}
  def extended_gcd(a, b) do
    {gcd, x, y} = extended_gcd(b, rem(a, b))
    {gcd, y, x - div(a, b) * y}
  end
end

Euclid.extended_gcd(e, phi_n) |> IO.inspect(label: "{gcd(#{e}, #{phi_n}), x, y}")

What do we have so far?

# Private primes: (p, q) = (11, 17)
# Public key: (n, e) = (187, 7)
# Private key: (n, d) = (187, 23)

Simple example

Encrypting and decrypting "hi"

Our keys:

Public key:   (n, e) = (187, 7)
Private key:  (n, d) = (187, 23)

Encryption — Alice sends "hi" to Bob

              ┌──────────────────┐
              │   MESSAGE "hi"   │
              └────────┬─────────┘
                       │
                       ▼
              Convert to UTF-8
                       │
               ┌───────┴───────┐
               ▼               ▼
           'h' = 104       'i' = 105
               │               │
               ▼               ▼
          ENCRYPT USING PUBLIC KEY
                 (187, 7)

              c = m^7 mod 187
               │               │
               ▼               ▼
          104^7 mod 187   105^7 mod 187
               │               │
               ▼               ▼
              179             96
               │               │
               └───────┬───────┘
                       ▼
              ┌──────────────────┐
              │ CIPHERTEXT       │
              │ [179, 96]        │
              └────────┬─────────┘
                       │
                       ▼
                  Send to Bob

Decryption — Bob recovers "hi"

              ┌──────────────────┐
              │ CIPHERTEXT       │
              │ [179, 96]        │
              └────────┬─────────┘
                       │
                 PRIVATE KEY
                  (187, 23)
                       │
                       ▼
             m = c^23 mod 187
                       │
               ┌───────┴───────┐
               ▼               ▼
         179^23 mod 187   96^23 mod 187
               │               │
               ▼               ▼
              104             105
               │               │
               ▼               ▼
              'h'             'i'
               │               │
               └───────┬───────┘
                       ▼
              ┌──────────────────┐
              │ ORIGINAL MESSAGE │
              │       "hi"       │
              └──────────────────┘

message = "hi" # [104, 105]
p = 11
q = 17
n = 187
e = 7
d = 23

# convert the UTF-8 string "hi" to bytes 
bytes = :binary.bin_to_list(message) |> IO.inspect(label: "'hi' to bytes", charlists: :as_list)

# c = m^e mod n = m^7 mod 187 (m - message, e = 7, n = 187, c - cipher)
# 'h'
# 104^7 mod 187 = 131593177923584 mod 187 = 179
# 'i'
# 105^7 mod 187 = 140710042265625 mod 187 = 96
encrypted = 
  Enum.map(bytes, fn byte -> Integer.mod(Integer.pow(byte, e), n) end)
  |> IO.inspect(label: "#{inspect(bytes, charlists: :as_lists)}^#{e} mod #{n} encrypted")

# m = c^d mod n (c - cipher, d = 23, n = 187, m - message)
# 179
# 179^23 mod 187 = 6540631965696128420322916230417828079450389770678939 mod 187 = 104
# 96
# 96^23 mod 187 = 3910554653407316789122934745158676505360859136 mod 187 = 105
decrypted =
  Enum.map(encrypted, fn cipher -> Integer.mod(Integer.pow(cipher, d), n) end)
  |> IO.inspect(label: "#{inspect(encrypted, charlists: :as_lists)}^#{e} mod #{n} encrypted")

Serious example

# Two 1024-bit prime numbers (~309 decimal digits each)

p =
  String.to_integer(
    "151358458404882542685732211677319830351213488860896531644579" <>
    "075457500219154876823247411581136926936718031953440481635148" <>
    "012196037971793918798683886387950999125896066957052878222964" <>
    "895309427033243208347998796452526892684390310971242722404939" <>
    "575901879020274216522966690729875361359526001338200876696979" <>
    "536492391"
  ) |> IO.inspect(label: "p")

q =
  String.to_integer(
    "142464930204668045593976644912335191032909932762062678945968" <>
    "319332913538422727221973619083536679979710152514769936039467" <>
    "778291629154009245550154347302413902674170192021744061569489" <>
    "322478517311383097008587818146109027705064430667059018916808" <>
    "650838864703759844701937515107272200150979264530022496772800" <>
    "805797557"
  )  |> IO.inspect(label: "q")

# RSA key generation
n = p * q |> IO.inspect(label: "p * q")
phi_n = (p - 1) * (q - 1) |> IO.inspect(label: "phi(n)")

e = 65_537 |> IO.inspect(label: "e")

# Calculate d using your existing Extended Euclidean Algorithm
{1, x, _y} = Euclid.extended_gcd(e, phi_n)
d = Integer.mod(x, phi_n) |> IO.inspect(label: "d")

# Verify
%{
  p_digits: byte_size(Integer.to_string(p)),
  q_digits: byte_size(Integer.to_string(q)),
  n_digits: byte_size(Integer.to_string(n)),
  d_digits: byte_size(Integer.to_string(d)),
  modulus_bits: bit_size(:binary.encode_unsigned(n)),
  inverse_check: Integer.mod(e * d, phi_n)
}

Encrypt

message = "Bel: I'm coming for you RSA!"
m = :binary.decode_unsigned(message)

# Encryption: c = m^e mod n
ciphertext =
  :crypto.mod_pow(m, e, n)
  |> :binary.decode_unsigned()

# Decryption: m = c^d mod n
decrypted =
  :crypto.mod_pow(ciphertext, d, n)

%{
  message_number: m,
  encrypted: ciphertext,
  decrypted: decrypted
}

Other notebooks:

Meng Zhang
@wsxiaoys

ds-bench

Encrypt Attributes

encrypt-attributes.livemd

tutorial advanced security ash ash_cloak cloak

2026-8-12
@DockYard-Academy

curriculum

Classified

deprecated_classified.livemd

tutorial intermediate jason kino youtube hidden_cell

2026-7-12
Cocoa
@cocoa-xu

tflite_elixir

Audio classification with TensorFlow Lite

audio_classification.livemd

tutorial advanced data-science nx_signal tflite_elixir nx kino req

2026-7-6
Ammar Massoud
@ammar-mohamed-massoud

Dockyard-Academy

Guards

guards.livemd

tutorial advanced intermediate jason kino youtube hidden_cell

2026-7-25
Bill Allen
@bwanab

Music_Build

Connect sapf to elixir with Midiex

sapf_test.livemd

tutorial advanced music_build music_prims midifile better_weighted_random midiex kino

2026-7-7
piacerex
@piacerex

livebook_trial

Iris classification

iris_knn.livemd

tutorial advanced data-science nx scholar explorer kino_explorer kino_vega_lite scidata exla

2023-8-31
Ammar Massoud
@ammar-mohamed-massoud

Dockyard-Academy

Booleans

booleans.livemd

tutorial beginner jason kino youtube hidden_cell visual

2026-7-25

Back