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