sgo.to

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