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.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 * 23 = 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 * y = 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
}
How to crack the RSA?
# We know only
# Public key: (n, e) = (187, 7)
# Ciphertext: [179, 96]
n = 187
e = 7
cipher = [179, 96]
# find p using brute force 2..sqrt(n)
p = Enum.find(2..floor(:math.sqrt(n)), fn x -> rem(n, x) == 0 end)
q = div(n, p)
IO.inspect({p, q}, label: "secret primes {p, q}")
# calculate phi(n)
phi_n = (p - 1) * (q - 1) |> IO.inspect(label: "phi(#{n})")
# find d using Extended Euclidean Algorithm
{1, x, _y} = Euclid.extended_gcd(e, phi_n)
d = Integer.mod(x, phi_n) |> IO.inspect(label: "d")
bytes =Enum.map(cipher, fn c -> Integer.mod(Integer.pow(c, d), n) end)
|> IO.inspect(label: "decrypted bytes", charlists: :as_lists)
message = :erlang.list_to_binary(bytes)
Day 4
Key generation
ββββββββββββββββ
β KEY GENERATIONβ
ββββββββ¬ββββββββ
β
βββββββββββ΄ββββββββββ
β β
βΌ βΌ
secret p secret q
β β
βββββββββββ¬ββββββββββ
β
βΌ
n = p Γ q
β
βΌ
derive e and d
β
βββββββββββ΄ββββββββββ
β β
βΌ βΌ
ββββββββββββββββ ββββββββββββββββ
β PUBLIC KEY β β PRIVATE KEY β
β (n, e) β β (n, d) β
ββββββββββββββββ ββββββββββββββββ
Picking random numbers (prime random numbers)
# Conditions for the number
# 1. The number should be ~ 1024-bit (2^1023 <= n < 2^1024)
# 2. The number should be secure-random
# 3. The number should be prime
Picking a 1024-bit (128 bytes) number
# Lets take a look at 8-bit (1 byte) numbers
# 00000000 = 0
# 00000001 = 1
# 00000010 = 2
# 00000011 = 3
# 00000100 = 4
# 00000101 = 5
# 00000110 = 6
# ...
# 10000000 = 128 <- smallest 8-bit integer
# 11111111 = 255 <- biggest 8-bit integer
# A 1024-bit integer (128 bytes)
# 0...0 = 0 <- it will have 1024 positions (or 128 groups of 1 byte each)
# FB...LB = n <- FB - first bit and LB - last bit
# LB = 1 - means that the number is odd
# FB = 1 - means the number is 1024-bit integer
# Simple way to create 1024-bit integer
# Firstly let's create the smallest 8-bit integer
# We know that 1 in 8-bit is
# 0000 0001 = 1
# 1000 0000 = 2^7 = 128
# to get from 1 to 128 we need to do 7 shifts
import Bitwise
1 <<< 7 |> IO.inspect(label: "1 <<< 7")
smallest_1024_int = 1 <<< 1023 |> IO.inspect(label: "1 <<< 1023 is the smallest 1024-bit integer")
# 1000 0000 = 128 the shift created the smallest 8-bit integer but even number
# the LB = 0 which means even
# 0000 0001 = 1
# 1000 0000 = 128
# Bitwise OR operator - |||
# 1000 0001 = 129
(128 ||| 1) |> IO.inspect(label: "128 ||| 1")
# We want to make our 1024-bit odd
n1024_bit_int = (smallest_1024_int ||| 1) |> IO.inspect(label: "(1 <<< 1023) ||| 1 = 2^1023 + 1")
# we want to verify that our number is 1024-bit and it is odd
%{
digits: length(Integer.digits(n1024_bit_int, 2)),
bytes: byte_size(:binary.encode_unsigned(n1024_bit_int)),
odd?: rem(n1024_bit_int, 2) == 1,
smaller_than_2_to_power_1024?: (n1024_bit_int < Integer.pow(2, 1024)),
bigger_than_2_to_power_1023?: (n1024_bit_int > Integer.pow(2, 1023))
}
Picking a 1024-bit (128 bytes) number the elixir way
# 8-bit (1 byte) numbers as elixir bitstrings
# 00000000 = 0
# ...
# 10000000 = 128 <- smallest 8-bit integer
# 11111111 = 255 <- biggest 8-bit integer
# now in elixir
zero_bitstring = <<0>>
bit_size(zero_bitstring) |> IO.inspect(label: "bit_size")
byte_size(zero_bitstring) |> IO.inspect(label: "byte_size")
(zero_bitstring == 0) |> IO.inspect(label: "bitstring == integer")
(zero_bitstring == <<0>>) |> IO.inspect(label: "bitstring == bitstring")
# zero as 8-bit bitstring
z1 = <<0>>
z2 = <<0::8>>
z3 = <<0::size(8)>>
(z1 == z2 and z1 == z3) |> IO.inspect(label: "all three represent zero using 8 bits")
bit_size(<<0::1>>) |> IO.inspect(label: "zero using 1 bit")
bit_size(<<0::2>>) |> IO.inspect(label: "zero using 2 bits")
bit_size(<<0::3>>) |> IO.inspect(label: "zero using 3 bits")
# 0000 0001 = 1
<<1::1>> |> IO.inspect(label: "one using 1 bit")
# 0000 0010 = 2
<<1::1, 0::1>>
# 2-bit numbers
<<0::1, 0::1>> |> IO.inspect(label: "zero using 2 bits")
<<0::1, 1::1>> |> IO.inspect(label: "one using 2 bits")
<<1::1, 0::1>> |> IO.inspect(label: "two using 2 bits")
<<1::1, 1::1>> |> IO.inspect(label: "three using 2 bits")
# 8-bit numbers as bitstring
<<0::8>> |> IO.inspect(label: "zero using 8 bits")
# 1000 0000
<<1::1, 0::7>> |> IO.inspect(label: "128 using 8 bits")
# smallest 1024-bit that is odd
smallest_1024_bitstring = <<1::1, 0::1023>> |> IO.inspect(label: "smallest 1024-bit integer")
n1024_bitstring = <<1::1, 0::1022, 1::1>> |> IO.inspect(label: "n 1024-bit bitstring")
n1024_bit_int |> IO.inspect(label: "n 1024-bit int")
n1024_bit_int == n1024_bitstring
n1024_bit_int == :binary.decode_unsigned(n1024_bitstring)
:binary.encode_unsigned(n1024_bit_int) == n1024_bitstring
bit_size(:binary.encode_unsigned(3))
Picking a 1024-bit (128 bytes) number byte by byte
(0b1010 == 10) |> IO.inspect(label: "binary notation") # 0|1 : 2^n
(0o12 == 10) |> IO.inspect(label: "octal notation") # 0|1|2|3|4|5|6|7 : 8^n
(0xA == 10) |> IO.inspect(label: "hexadecimal notation") # 0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F : 16^n
(0xF == 15) |> IO.inspect(label: "hexadecimal notation")
# Let's have 3 bytes (24 bits total)
# 00000001 = 1
# 00000010 = 2
# 00000011 = 3
0x01 == 1 # true
0x02 == 2 # true
0x03 == 3 # true
# Construct a binary containing our 3 bytes
bytes = <<0x01, 0x02, 0x03>>
bit_size(bytes) |> IO.inspect(label: "bits") # 24
byte_size(bytes) |> IO.inspect(label: "bytes") # 3
# The complete binary representation:
#
# 00000001 00000010 00000011
#
# This is one integer using 24 bits:
#
# 0x010203 = 66051
# Each byte contributes according to its position:
#
# First byte: 1 Γ 256Β² = 65536
# Second byte: 2 Γ 256ΒΉ = 512
# Third byte: 3 Γ 256β° = 3
# -----
# 66051
a1 = 1 * 256 * 256 + 2 * 256 + 3
a1 |> IO.inspect(label: "integer") # 66051
# We can decode the binary directly
:binary.decode_unsigned(bytes) == a1
# Now lets implement the following algorithm
# acc = (acc <<< 8) ||| byte
acc = 0
byte = 0x01
acc = (acc <<< 8) ||| byteacc |> IO.inspect(label: "step 1")
byte = 0x02
acc = (acc <<< 8) ||| byte
acc |> IO.inspect(label: "step 2")
byte = 0x03
acc = (acc <<< 8) ||| byte
acc |> IO.inspect(label: "step 3")
import Bitwise
bytes = [
0x01,
0x02,
0x03
]
Enum.reduce(bytes, 0, fn b, acc -> (acc <<< 8) ||| b end)
|> IO.inspect(label: "sanity check")
(0x80 == 128) |> IO.inspect(label: "0x80 == 128")
(0x0 == 0) |> IO.inspect(label: "0x0 == 0")
(0x1 == 1) |> IO.inspect(label: "0x1 == 1")
# 1024 bits are 128 bytes
bytes =
[0x80] ++ List.duplicate(0x0, 126) ++ [0x1]
n1024_byte_by_byte = Enum.reduce(bytes, 0, fn b, acc -> (acc <<< 8) ||| b end)
(n1024_bit_int == n1024_byte_by_byte) |> IO.inspect(label: "n1024_bit_int == n1024_byte_by_byte")
%{
digits: length(Integer.digits(n1024_byte_by_byte, 2)),
bytes: byte_size(:binary.encode_unsigned(n1024_byte_by_byte)),
odd?: rem(n1024_byte_by_byte, 2) == 1,
smaller_than_2_to_power_1024?: (n1024_byte_by_byte < Integer.pow(2, 1024)),
bigger_than_2_to_power_1023?: (n1024_byte_by_byte > Integer.pow(2, 1023))
}
Randomness
# How can we generate 128 unpredictable bytes
# and what does it actually mean for a number to be cryptographically random?
# Randomness describes the unpredictable outcomes we want.
# Entropy measures uncertainty about an outcome.
# PRNG (Pseudo Random Number Generator) is an algorithm
# that produces numbers that appear random, starting from some internal state
# Example A - a completely predictable generator
next_number = fn n -> rem(n + 5, 256) end
next_number.(1) |> IO.inspect(label: "1")
next_number.(2) |> IO.inspect(label: "2")
next_number.(3) |> IO.inspect(label: "3")
next_number.(434) |> IO.inspect(label: "434 (maybe 439)")
# Example B β a seeded generator
# Example C β a cryptographically secure generator
# RSA implementations typically don't generate a prime directly.
# They generate a random number and test whether it is prime. If it isn't, they try again.
#
defmodule PrimeGenerator do
end