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?
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.
|show 2 more comments|
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.