# Asymmetric Encryption

This is an open study of the RSA encryption scheme (source).

# Problem

`Bob` wants to send a secret message `m` to `Alice` without having to rely on a shared secret (symmetric keys)

# Background

• In 1970, James Ellis, a british engineer and mathematician was working on an idea for "non-secret encryption": lock and unlock are inverse operations.
• Alice could buy a `lock`, open it, keep the `key`, and send the `lock` to Bob.
• Bob uses the `lock` to lock a `box` with the hidden `message` inside and send the `box` back to Alice.
• With its `key`, Alice could open the `box` to get the `message`.
• Ellis never arrived at a mathematic formulation, but he had an intuitive sense of how it should work: an `encryption` key and a `decryption` key.
• The decryption key performs the inverse, or the undo operation, that was applied to the encryption key.
• In 1973, Clifford Cocks (cryptographer) looked into a special kind of reversable function a trap door function.
• A known `public` function `f(x) = y` that was easy to compute but hard to invert: given `y` it is hard to compute `x`, unless you have `private` information available.
• So, if you wanted to send you a message, you'd use `f(m) = y` and send you the `public` result `y`, which nobody but you (who have a special piece of `private` information), would be able to compute the inverse of `f` to invert `y` into the `m`.
• For this he turned into modular exponentiation.
• He knew that computing discrete logarithms was hard for computers: given `a` an `k` such that `b ^ k = a`, it is really hard to compute `b`.
• So, if Alice provided `e` and `n` publicly (the lock), Bob could send a message to Alice `m` by calculating `c = m ^ e % n` and send `c` to Alice (and no one would be able to invert `c` into `m`, because it would be involving computing a discrete logarithm)

This observation was also cleverly used on the diffie helmann key exchange protocol here.

• This would construct a confidential lock, but not a correct one: given `c`, `e` and `n` it is not possible to invert back to `m`, including for Alice
• So, he tried to build a trap door in the lock such that (a) only Alice could use it to invert `c` back into `m` and (b) `m` was inverted correctly.
• Something that makes reversing this easier for Alice but hard for everybody else.
• So, he proposed: what if unlocking could be performed by taking `c` and raising it to some other private exponent, `d`, to undo the operation and arrive at `m`?
• That is, can we construct `e`, `d` and `n` such that for every `m`:
• If `c = m ^ e % n` is the message Alice gets from Bob
• And Alice computed `c ^ d % n` = `(m ^ e % n) ^ d % n` = `m ^ e ^ d % n` = `m ^ (e * d) % n` = `m`.
• Then Bob's `m` = Alice's `m` and `c`, `e` and `n` could be made `public`.
• So, he needed to find a way to make Alice construct a `e` and `d` such that it lead (correctly) to `m` while making it hard for anyone else to find `d` (confidential).
• So, he needed a second one way function for generating `d`, and for this he looked back at Euclid, Euler and Fermat's little theorem.
• In ~300BC, Euclid devised the fundamental theorem of arithmetic: every number can be represented uniquely as a product of prime numbers
• He also knew that computing the prime factorization was known to be a hard problem
• So, imagine Alice picked two big prime numbers, say, `p` and `q` and multiplied then to construct `n = p * q`.
• That is, given `n`, it was known to be hard to compute `p` and `q`, unless you have either `p` or `q`.
• So, that was a trapdoor: something that is easy to do if you have Alice's `private` information (`p` or `q`) but hard otherwise.
• So, Cocks started to look for function that depended on knowing the factorization of `n`.
• For that he looked back to Euler.
• In the ~1700s, Euler was investigating the distribution of prime numbers.
• One important function he defined as the `phi(b)` function.

Not super important to understand it, but it measures the breakability of a number. `phi(n)` outputs how many integers less than or equal to n that do not share. A common factor with n. e.g. `phi(8)` = `4` (1, 3, 5 and 7)

• What's interesting about `phi(n)`, that `phi(n)` is hard to calculate except in one case: prime numbers.
• If `n` is prime, `phi(n) = n - 1`: `phi(n)` is easy to compute for primes.
• It was also known that `phi(n)` was multiplicative: i.e. `phi(a * b)` = `phi(a) * phi(b)`
• If `n` is the product of two primes `a` and `b` then `phi(n) = phi(a * b) = phi(a) * p(b) = (a - 1) * (b - 1)` is easy to compute
• And that was the trapdoor that Cocks was looking for: if you know the prime factorization `a` and `b` of `n`, than `phi(n)` is easy to compute as `(a - 1) * (b - 1)`, but hard to compute otherwise
• But, how could he connect this trapdoor to the previously one he devised? For that, he turned back into Fermat and Euler:
• Fermat-Euler's theorem states that for every `m`, `m ^ phi(n) % n = 1` (if `m` and `n` are coprime positive integers)
• First, we can always exponentiate `1` by `k` and we'll always get `k`, i.e. `1 ^ k = 1`:
• Therefore `(m ^ phi(n)) ^ k % n = 1 ^ k`
• i.e. `m ^ (k * phi(n)) % n = 1`
• Second, we can always multiply both sides by `m`: `1 * m = m`:
• Therefore `m * (m ^ (k * phi(n)) % n) = m * 1`
• i.e. `m ^ (k * phi(n) + 1) % n = m`
• That allowed Cocks to put things back together
• From before:
• Bob can encrypt `m` with `c = m ^ e % n`, given `e` and `n` from Alice, and know that it is going to be hard to invert `m`.
• Alice knows that
• She could take `c` and apply `c ^ d % n` to arrive at `m` which is the same as `m`.
• She knows that `m ^ (k * phi(n) + 1) % n = m` (Euler's theorem)
• So, Alice can construct `e`, `d` and `n` such that `m ^ (e * d) % n` = `m`
• Alice can pick `e`, `d` and `n` such that `(e * d) = k * phi(n) + 1`
• i.e. `d = (k * phi(n) + 1) / e`
• Corretness
• If Alice chooses `e` and `n` such that `d` as above, that would make `m ^ (e * d) % n = m` into `m ^ (k * phi(n) + 1) % n = m` which we know to be true (Euler)
• Confidentiality
• Alice would know that the value that she picked for `d`, given `e` and `n`, is only computable if you can solve `phi(n)`, which is only known if you can factorize `n`
• That is known to be hard, unless you know what `p` and `q` (which only Alice knows!)

# Try it yourself!

Use the demo below to send messages from Bob to Alice!

• Bob wants to send a message `m` = to Alice
• Alice, picks two large prime number, `p` = and `q` =
• Alice computes `n` = `p * q` = `p * q` = `b`
• Alices computes `phi(n)`, which is easy for her since knows the factorization of `n` but hard for everybody else
• Alice computes `phi(n)` = `phi(p * q)` = `phi(p) * phi(q)` = `(p - 1) * (q - 1)` = `(p - 1) * (q - 1)` = `phi`
• Alice picks some small public exponent `e` = , an odd number that does not share a factor with `phi(n)`
• Alice computes `d` = `(2 * phi(n) + 1 ) / e` = `d`
• Alice shares `n` = n and `e` = e, her public key (the open lock)
• Bob computes `c` = `m ^ e % n` = `m ^ e % n` = c and
• Bob sends `c` = c to Alice
• Alice computes `r` = `c ^ d % n` = `c ^ d % n` = `r`
• Alice knows that `r` = `r` = `m` = `m`