Victorian public key cryptography

Electronic computers were invented before public key cryptography. Would public key cryptography have been possible before computers?

The security of RSA encryption depends on the ratio of the difficulty of factoring relative to the difficulty of multiplication. This ratio was high, maybe higher, before modern computers.

Suppose the idea of RSA encryption had occurred to Lewis Carroll (1832-1898). What key size would have been necessary for security in his day? Would it have been practical to manually encrypt data using keys of that size?

I imagine if you handed Victorians a pair of public and private RSA keys, they could have manually carried out public key encryption. But coming up with private keys, i.e. finding pairs of large prime numbers, would be harder than carrying out the encryption process.

The largest prime discovered without a computer was 2¹²⁷ - 1, proved prime by Edouard Lucas in 1876. Such primes would have been large enough-I doubt it was feasible to factor the product of 40-digit primes at the time-but this was a prime of a very special form, a Mersenne prime. Lucas had developed an algorithm for efficiently testing whether a Mersenne number is prime. To this day the largest known primes are Mersenne primes. More on this here.

Lucas would not have been able to produce two 40-digit primes. The largest known prime in 1851 had 12 digits:

999,999,000,001

Because of the special form of this number, it would seem that even coming up with 12-digit primes was quite an achievement. Euler (1707-1783) had found a 10-digit prime, but it was also a Mersenne prime. Large primes without special structure were unknown.

Perhaps if Lewis Carroll had found a couple moderately large primes, he might have presented them to his queen to be used in public key cryptography. Their product could be published in newspapers, but the factors would be state secrets. Anyone could send Queen Victoria encrypted messages via public communication.

Diffie-Hellman public key encryption might have been more practical. It only requires one large prime, and that prime can be made public. Everyone can share it.

The prime p that Lucas discovered would do, until people realized that p - 1 has a lot of small factors [1], which could be used to break Diffie-Hellman cryptography. I don't know that any large safe primes were known until more recently.

If someone from the future had given the Victorians a large safe prime, Diffie-Hellman cryptography would have been possible, though laborious. Someone could write a steampunk novel about a time traveler giving the pre-computerized world a big safe prime and teaching them Diffie-Hellman cryptography.

***

[1] 2¹²⁶ - 1 = 3^3 * 7^2 * 19 * 43 * 73 * 127 * 337 * 5419 * 92737 * 649657 * 77158673929

See the next post for a theorem that would allow you to find this factorization by hand.

The post Victorian public key cryptography first appeared on John D. Cook.