-1

I once asked a question "Would RSA make sense if we used no computers?". The answer was negative, because finding primes that would make secure keys would prove too hard. Assuming that we had found another way of finding primes without computers, would RSA be usable in, for example, medieval times?

Community
  • 1
d33tah
  • 353
  • 1
  • 13
  • As mentioned in the other thread, you would also need a good (hand-computable) hash function, since RSA is very malleable and you'd need a MAC. I think a more interesting version of your question is "Suppose SE.crypto is dropped into medieval times, and we need to communicate safely without the aid of any computers. What do we do? How does this change if we've brought plenty of massive primes with us?" – Andrew Poelstra Dec 08 '13 at 17:46
  • Exponentiation without computers is still pretty annoying – CodesInChaos Dec 08 '13 at 17:52
  • 1
    Something like Merkle Puzzles could be adapted to medieval tools. – Dmitry Khovratovich Dec 08 '13 at 17:53
  • Why RSA? Using DH over a pregenerated elliptic curve or a pregenerated finite field should be faster and doesn't require per-key primes. – CodesInChaos Dec 08 '13 at 17:55
  • It's far more easy to do some key agreement without a computer than to try to break it with current methods. So if your opponent does neither have a computer something can be done, and with computer architecture known you can build something with water or mechanic wheels to do the thing. – daniel Dec 08 '13 at 18:57
  • 2
    It wouldn't. Having an alternate way of finding strong primes implies an oracle which reports on weak primes. And if you started talking about oracles in medieval times, encrypting data would be the least of your concerns. Joking aside, RSA would get increasingly hard to use as rivals factor bigger and bigger numbers. Clever substitutions were simple and effective, and you could have a dumb servant perform the task, instead of a mathematician. [Here's more](http://sarahgoslee.com/as/cryptography/index.html). – rath Dec 09 '13 at 00:45
  • While the question is about RSA, there are lots of interesting methods for modern hand encryption. [Solitaire](http://en.wikipedia.org/wiki/Solitaire_%28cipher%29) being one. – Nathan Cooper Mar 13 '14 at 12:33

1 Answers1

2

Many of the beginner explanations use very simple examples: like this

It is still hard to factorize a small number by hand, compared to other operations. There is definitely a size of prime numbers where hand computation is still feasible, but hand factorizing isn't. Would you, for instance, even armed with a list of primes, be able to quickly tell me what the prime decomposition of 1043 is?

It's 149 and 7. Slow to decompose, but easy to multiple by hand. You can go a lot bigger by hand or with an abacus etc.

Nathan Cooper
  • 396
  • 2
  • 9