Would RSA make sense if we used no computers?

Question

I was recently wondering - would RSA be useful if we brought it to, say, medieval times? Could you choose the keys so that you could encrypt/decrypt messages quite easily, but factoring the private key would, say, take over 1000 days for 1000 people, provided that they used paper and pencil only and wouldn't make any mistakes?

Answer 1

I thought about this and have done a bit of research, and the answer is no.

The problem is the gap between the difficulty of factorisation versus prime generation isn't really large enough at the scale of primes/moduli we can work with.

By 1588 the largest prime discovered was 524287, thanks to Pietro Cataldi. This was a prime generated by a single person's work. I don't know how much effort this took, but given that it was a world record at the time, I think we can assume it was a fair amount of effort.

In order to have a secure instance of RSA, we'd probably want to generate a modulus using two six-digit primes. That's already quite a bit of work.

However, a nation-state can draw on more resources. They could hire a team of people to try and break the message. One observation is that there aren't actually that many primes below 1,000,000: there are only 78,498! If we consider only the primes between 100,000 and 1,000,000, this number comes down to 68,906.

A nation-state could use the sieve of Eratosthenes to find all the primes below 1,000,000. This would be a one-off effort. They would then need to attack any modulus which is the product of two six-digit primes.

Finally, to factor a particular spy's modulus they simply could give it to a pool of people who would work down through the list.

Let's say one person can try one division every five minutes. That seems like quite a long time given the size of the numbers. Nonetheless, in one eight-hour working day, they could try 96 divisions per day. Across a pool of 20 people it would take 35 days to run through the entire list.

In practice, most moduli would be solved much sooner than this because both primes will appear somewhere in the list.

This attack is entirely practical and thus makes RSA pretty useless for encryption in that historical period.

Answer 2

I'm answering to this a bit with "tongue in cheek" attitude because I like the question. Thanks d33tah. I try to make a few useful points. Maybe somebody contributes more via comments.

The term RSA in itself is ambiguous. I've assumed that entire RSA as defined in PKCS#1 + key generation stuff from FIPS 186-4 was known back then (maybe they also knew DSA and ECDSA and made wise decision to only use RSA as it is the most convenient).

Thus, I'm assuming that RSA means RSA sign/verify, padding, RSA encrypt, verify, key generation mechanisms, ... The other answer about primes is indeed completely true. There is no reason to expect that very large prime numbers were known back then. But if these things have been known...

---

There is are three laws from Clarke regarding technology. One of them is: "Any sufficiently advanced technology is indistinguishable from magic."

The medieval methodology to rubber-hose cryptoanalysis XKCD: Security was harsher that it is now (nobody expects The Spanish Inquisition). Back then somebody having skills indistinguishability from magic would have been most probably reasonable basis for witch trial.

Early forms of steganography and cryptography (think e.g. Caesar cipher) date much further back than medieval times. Therefore, it can be easily thought that some more asymmetric cryptography back then would have been possibly beneficial for faster progress in mathematics and natural sciences. Maybe renaissance would have been earlier. And, quite probably, modern computers would be something totally different.

Cryptography made certainly sense before computers, and problems related to confidentiality, integrity and authenticity existed back then.

BTW, alone RSA had been next to useless. It is too slow. For fast execution hybrid encryption is needed. Authenticity/integrity on the other hand likely needs strong hash functions.

Answer 3

Security is based on the difference in effort for encryption/decryption and for cracking. With RSA, the difference grows exponentially with the key size. So for small key sizes, the difference isn’t too bad.

To crack RSA, we need to factor the product of two large primes. There is an algorithm that should be accessible to a very talented mathematician in medieval times which solves this in O(n^(1/3)). So for two primes up to a million it takes about 10,000 steps.

So for a normal person to keep their secrets safe from a nation state, RSA won’t work.

Answer 4

I think you could implement the Enigma encryption with pen and paper. And that was barely breakable in the 1940’s. It wouldn’t be efficient enough for thousands of messages, but for one 100 character message a day it would be fine. Replacing the wheels with two strips of paper should work.