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 2127 − 1, proved prime by Edouard Lucas in 1876. Such primes would have been large enough—I seriously 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. But maybe two 10-digit primes would have been adequate, as long as they had no special structure, i.e. they were found by generating random numbers and testing them for primality.
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] 2126 − 1 = 3³ × 7² × 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.
Seems like the relevant question is, how fast are the *attacks* in Victorian times? If they struggle to use large primes, then attackers presumably ought to struggle to attack large composites.
Anyway, probably a better alternative here would be a sponge. It uses only hash functions and can construct public-key cryptography. Hash functions like Keccak/SHA-3 use mostly operations like pad/truncate/XOR, so nothing exorbitant like multiplying 12-digit numbers. I don’t know what the full cost of sponge public-key crypto is, but a component like Keccak is cheap on a modern CPU (~12 instructions per hashed byte) so it might be quite feasible to do by hand or by Victorian-era calculating machinery like the Difference Engine.