# 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. – CodesInChaos Oct 1 '13 at 18:16
Why wouldn't it be? – d33tah Oct 1 '13 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. – user4982 Oct 1 '13 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 – Maarten Bodewes Oct 1 '13 at 19:44

## 2 Answers

I thought about this and 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 and that was due 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 or 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 is a one off effort they need to attack any modulus which is the product of two six digit primes.

Finally, to factor a particular spy's modulus they simply give it to a pool of people who 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'd 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. – d33tah Oct 1 '13 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. – user4982 Oct 1 '13 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. – user4982 Oct 1 '13 at 19:59
So, would fast prime tests actually make it feasible? – d33tah Oct 1 '13 at 20:10
No they would not. My answer took the approach that I assumed that in addition to RSA they have had more mathematical knowhow than they do. If they just had RSAEP and RSADP there would be little they could do with it. It would be like receiving a electric car from future via a time machine. In medieval times you'd do almost nothing with an electric car as you cannot charge it at all. Modern inventions have dependencies on other previously existing technologies, this is true even for innovations that are mostly documentation and know-how instead of tangible property. – user4982 Oct 2 '13 at 13:59

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.

-