Monday, 27 March 2017


Pick a number

Remember those "pick a number" mathematical games children play on each other? Here's one.

Pick a number between 0 and 76. Now multiply it by itself 17 times. Subtract 77 from the result, and keep subtracting 77 until the number you get is less than 77. Done? Excellent.

For example, 2417 = 290,797,794,982,682,557,415,424. You'll need to subtract 77 a total of 3,776,594,740,034,838,407,992 times reaching the result of 40. (I didn't promise you could do this trick in your head.)

You've just encrypted a number. In the example, 24 has become 40.

Take the resulting number and repeat the process, but this time multiply it by itself 23 times and then subtract 77s. You should end up with the number you first selected.

Continuing with the example, 4023 = 7,036,874,417,766,400,000,000,000,000,000,000,000. Making 91,387,979,451,511,688,311,688,311,688,311,688 subtractions of 77 gives the original number, 24.

This is an example of RSA encryption: an algorithm first described publicly in the 1970s. It's at the heart of many so-called "strong encryption" systems. The pairs of numbers 17,77 and 23,77 are the encryption and decryption keys.

Whenever you browse a secure website, or send a secure message, this is pretty much the kind of thing your computer's doing. (Except that rather than encryption keys a couple of digits long, you're using keys hundreds or thousands of digits long.)

I've been able to describe the encryption algorithm in just a couple of sentences. The magic is in how to select the encryption and description keys, but even that uses only basic maths and could be implemented by anyone with a pretty basic level of programming experience.

This is why it's futile to insist that WhatsApp or Apple "assist" Governments by making their encryption breakable: if they do, those who want strong encryption will just get a teenager to re-implement strong crypto for them in about a dozen lines of code.

The maths can't be uninvented. Dissemination of the knowledge could be outlawed, but is that really feasible? If this blog post ever disappears, you'll know that's what's happened.

For the curious, RSA relies on carefully choosing three numbers — d, e and n — such that this property holds:

m, m<n: mde mod nm

Such numbers can be found like this:

  1. Think of two prime numbers; call them p and q.
  2. Multiply p and q together; call the result n.
  3. Calculate λ: the least common multiple of p-1 and q-1.
  4. Now invent a number, greater than 1 but less than λ, which has no common factors with λ other than 1; call this d.
  5. Find e, such that d multiplied by e modulo n is equal to 1.

The encryption key is e,n; the decryption key is d,n. Don't share p, q or λ — the security of the crypto system revolves around the fact that d is difficult to derive from e if you don't know p, q or λ. Of course in practice the original prime numbers will be very large, with hundreds of decimal digits.

For my example, p=7, q=11, n=77, λ=30, d=23, e=17.

Rivest, Shamir and Adleman's 1977 paper that introduced the RSA cryptosystem for the first time is surprisingly simple and well worth reading.

Posted by pab at 20:27 | Comments will be back one day. Please email me instead!