# Could public-key crypto be performed long ago if the idea had been discovered?

Public-key cryptography was not invented until the 1970's. Apart from the idea not existing earlier (as talked about here), is there any reason it could not have been used earlier? For example, are there forms that are easy enough to perform by hand but complicated enough to not be solved (easily) by hand?

• How are you are going to distribute the public key? Even at the beginning, the public key systems have higher protocol steps so some people dismiss it. Commented Aug 7, 2019 at 17:21
• @kelalaka Not sure what you mean. Two people could meet and exchange their public keys. I'm not asking about why this didn't catch on or why it wasn't discovered, I'm asking if there's forms that could be done in a timely manner by hand. Commented Aug 7, 2019 at 17:48
• people could meet and change keys, too, and that was common before. Also, you have to write many messages to distribute with public key. Commented Aug 7, 2019 at 17:50
• What do you mean by "have to write many messages to distribute with public key"? What messages? Commented Aug 7, 2019 at 18:19

What an interesting question! Yes, it certainly could. The math required to carry out RSA encryption, for example, have been known for millennia. The most complex algorithms are:

• Primality testing for key generation. I think that the first efficient algorithm was Fermat's, from ~1600
• Euclid's, which is from 300 BC
• Binary exponentiation, which I couldn't find when it was discovered, but I'd guess it's pretty old too
• Even the Chinese Remainder Theorem, which can speed up the RSA computation, is from 300 AD.

So, if someone discovered RSA and also Fermat's primality testing, then it would be possible to use RSA millenia ago.

People wouldn't need to use keys as large as in use today since any attacker would also need to do calculations by hand. The first efficient (sub-exponential) factorization algorithm, the continued fraction algorithm appeared in 1931. So an attacker would need to brute force the key with trial division, in $$O(\sqrt{n})$$ steps. In 1903, a 67-bit Mersenne number was factored. Leaving 2 bits of breathing room (the calculation took half a year, 3 additional bits would make it take four years), then $$(67+3) = 70$$-bit (21-digit) keys would be more or less safe against brute-forcing by hand. This seems to be an overestimation, though, since calculators existed at that time, see this discussion.

20-digit calculations seem a lot, but considering it may be overestimated, it seems using RSA millenia ago would be possible.

These are all approximations though, someone with deeper knowledge of math history should be able to shed more light in this question. (Maybe this question would even fit the Math.SE better)

• The first efficient (sub-exponential) factorization algorithm, the continued fraction algorithm appeared in 1931 - of course, had RSA been in use since the 1600s, the history of progress of integer factorization may have been different. Commented Aug 7, 2019 at 21:10
• Would it really be practical to generate an RSA key by hand? With a computer, it's the slowest part. You need to test a lot of candidates before finidng a suitable prime. Also I'm not sure if Fermat primality testing would be good enough for RSA. Commented Aug 8, 2019 at 6:54
• @Gilles Yes, that would be the hardest part... on the other hand, keys would be much smaller. We'd need a more thorough analysis on how fast people can compute by hand. But RSA is just an example, maybe ElGamal would be more suitable. Commented Aug 8, 2019 at 11:31
• @Gilles Even if key generation took a long amount of time it's only a one-time thing. You can use the key over and over. It's a valid point though. Commented Aug 8, 2019 at 12:57
• For the curious: I have cross-posted to Math SE as suggested. Here is the question. Commented Aug 14, 2019 at 14:27