# Asymmetric Encryption

Sam Goto

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.

- Alice could buy a
- 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`

.

- If
- 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.

- A known
- 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:

- One important function he defined as the
- 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`

- Therefore
- Second, we can always multiply both sides by
`m`

:`1 * m = m`

:- Therefore
`m * (m ^ (k * phi(n)) % n) = m * 1`

- Therefore
- i.e.
`m ^ (k * phi(n) + 1) % n = m`

- First, we can always exponentiate
- 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`

- She knows that

- Bob can encrypt
- Alice can pick
`e`

,`d`

and`n`

such that`(e * d) = k * phi(n) + 1`

- i.e.
`d = (k * phi(n) + 1) / e`

- i.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)

- If Alice chooses
- 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!)

- Alice would know that the value that she picked for

- From before:

# 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`