Programming Praxis

There has been much ado recently about a law-enforcement backdoor to encryption that would enable authorized access to private encrypted communications: FBI director James Comey and British Prime Minister David Cameron have both come out strongly in favor of an encryption backdoor as a tool in the fight against terrorists, while the EFF and cryptography experts are uniformly against the proposal. Today’s exercise looks at a way that an encryption backdoor can be added to the RSA cryptosystem.

Let’s start by reviewing how RSA works, as we have studied it in a previous exercise. Two large primes p and q are chosen at random; their product n is the modulus of the cryptosystem, and the totient φ(pq) of n is (p−1) × (q−1). Then two keys are chosen, the encryption key e and the decryption key d such that de ≡ 1 (mod φ(pq)) and gcd(e, φ(pq)) = 1. Then a message m, encoded as an integer on the range 0 < m < n, is encrypted as m^e (mod n) and the resulting ciphertext c is decrypted as c^d (mod n). In practice, e is usually 2¹⁶+1 = 65537 (that choice simplifies the arithmetic involved in encryption and decryption), p and q are t-bit integers with t ∈ {512, 1024} bits, and there are algorithms that allow the message to be any length (not limited to n), though we won’t look at them here because they are arcane and not germane to the RSA backdoor.

The encryption backdoor is inserted in the key generation process. The backdoor key a is chosen as a random prime of length 3t/4 bits; also chosen are two random primes p‘ and q‘ of length t/4 bits. Then p is computed based on p‘ by the following algorithm:

1 [Initialize]: Set k ← p‘.
2 [Compute p]: Set p ← a × k + p’.
3 [Check primality]: If p is prime, return p.
4 [Try again]: Set k ← k + 1 and go to Step 2.

And likewise for q, which is computed based on q‘. This process must terminate by Dirichlet’s Theorem, which says that for integers a, b and x with a and b coprime, the arithmetic progression ax + b contains infinitely many prime numbers. Once you’ve computed p and q, the key generation and ciphering processes of the normal RSA algorithm are unchanged.

An attacker who doesn’t know the backdoor key a can read an encrypted message m only by factoring n, which is difficult; that’s the basis of the secrecy provided by the RSA system. But an attacker who knows the backdoor key a can factor n (mod a) as p‘ × q‘, recover p and q and thus the decryption key d, and thus read the message m. Factoring n (mod a) is very much easier than factoring n; for instance, if n is a 2048-bit semiprime, n (mod a) is only 512 bits, which can be factored by a single personal computer in a few months, or by an AWS cluster in a few days, or by the supercomputers in the basement of the NSA one morning before you finish your first donut.

In practice, the RSA backdoor would work like this: Each device that performs encryption, say an iPhone or Android tablet, has a unique MAC address or KEK key or serial number that is somehow converted to a backdoor key a that is also unique to the device. (If a single backdoor key a was used for all devices, it could be recovered by a method similar to this exercise.) The device generates backdoored keys on request, then sends encrypted messages in the normal way. When some police agency wants to read an encrypted message, they request warrants from a judge, seize the device, determine the backdoor key a, and perform the procedure described above.

Your task is to write programs that demonstrate the RSA backdoor. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2