# Would RSA make sense if we used no computers?

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?

• It's not clear if asymmetric encryption would be useful for their use cases, even if we ignore performance. Commented Oct 1, 2013 at 18:16
• Why wouldn't it be? Commented Oct 1, 2013 at 18:20
• I share this link describing what kind of cryptography they used at Medieval times: cryptography at medieval times. Sounded like asymmetric cryptography would have been giant leap. Commented Oct 1, 2013 at 18:59
• You probably would need a monastery full of monks to do the key generation - and then kill all the monks to keep the private key safe :P Commented Oct 1, 2013 at 19:44

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.

• Thanks, didn't know that generating prime numbers is that hard! First thing I thought of is that there are fast tests for primality, but actually, if there's just 8% of primes in the below-million set, it sounds a bit hard. Commented Oct 1, 2013 at 19:52
• The fast tests for probable primality were not known back then. Then again I would say that numbers between 10000 and 100000 would already be enough to get started. Why? Its already enough to illustrate the substantial amount of difference in effort adversary has to do compared to legitimate parties. Anyway, consider that in many cases adversaries did not even break basic substitution ciphers. Anyway, once algorithm like RSA is known to some parties, and its usability is acknowledged then related problems (like finding primes) could get more research. Commented Oct 1, 2013 at 19:58
• To enforce the above point I could mention Pascal. Mathematical theory of probability was studied during 1600's by Blaise Pascal because there was practical problem involved: making money in gamble. But then again. I would not expect inventing RSA without first understanding all the foundations of mathematics and probability we know. Commented Oct 1, 2013 at 19:59
• So, would fast prime tests actually make it feasible? Commented Oct 1, 2013 at 20:10
• For number of RSA interest and where computing the private RSA function is done by hand, Fermat factoring, known for about 350 years, is much more plausible than trial division, and quite so.
– fgrieu
Commented Oct 2, 2013 at 15:06

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.

• Witch trials were actually extremely rare. If someone demonstrated extreme mathematical ability, they would not be regarded as dangerous, just as very smart. Now, if they could shoot fire out of their hands and mind-controlling people, that might be grounds for assuming they are in league with the Devil... Commented May 19, 2019 at 23:51
• Strong (large and random) padding would not be necessary as Coppersmith attacks would be too complicated. Commented Jan 23, 2021 at 21:13

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.

• "With RSA, the difference grows exponentially with the key size"; actually, no, it grows superpolynomially (with the currently known algorithms) Commented Jan 23, 2021 at 14:21
• @poncho did you mean "subexponentially"? Commented Jan 23, 2021 at 20:31
• @Fractalic: either; it grows faster than any polynomial function (hence "superpolynomial" but slower than any exponential function (with positive increasing exponents), hence "subexponential". Commented Jan 24, 2021 at 3:14

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.