1

Cryptography has long history. Really long one.
Of course, there is no need to say, how important was safety of secret messages between rulers and generals.
In olden times, ciphers used were pretty simple, but they evolved to more complex ones.

Old ciphers had big flaw: they were symmetric, which allowed cracking them.

But what about asymmetric key encryption (for example RSA)? In modern times, it is most important technique of encryption. One could think, that bringing it to Middle Ages would create completely unbreakable cipher.

But mathematical calculations connected to encoding, and decoding RSA messages require a lot of work, thats why we use computers for it. In Middle Ages, there were no computers, and no possibility to create one, even with knowledge from the future.

Of course, it would still be possible - just train some scholars (and accidentally spawn some great mathematical theories, but who cares?), and use sufficiently small keys.

But, would keys small enough, that one (of course only one, because of safety) scholar at kings court, would be able to decrypt message in few hours, still be powerful? Maybe, keys so small will not provide enough protection?

Question:

Is using asymmetric key encryption in those terms really safe?

Clarification: all calculations in encryption, and decryption process are done by hand, or using techniques available in late Middle Ages, and shouldn't take more than a day to one man to handle.

RSA is only example of assymetric key encryption - if it turns out, that RSA would be useless, but some other type would be okay, I accept the answer.

By safe, I expect something similar to our time definition: nobody knows a quick method of breaking, and brute force solutions take years at the very least.

EDIT:
Not a duplicate of cryptography in world without computers, as this question is about one, special family of ciphers, while above is about cryptography as whole.

Tomasz Czarkowski
  • 27
  • 2
  • 1
    Could you please add some explanation about RSA for the less technically-savvy among us, so that we might try to think of an answer? – Galastel supports GoFundMonica Jun 05 '18 at 20:00
  • I think it would take half of question - so i will link article. – Tomasz Czarkowski Jun 05 '18 at 20:06
  • Are you willing to handwave into existence the required mathematics? I don't know when the mathematics that modern public-key encryption relies on was discovered, but I kind of doubt that it had been in the Middle Ages. – user Jun 05 '18 at 20:08
  • @Michael Kjörling Math is handwaved - "(and accidentally spawn some great mathematical theories, but who cares?)". – Tomasz Czarkowski Jun 05 '18 at 20:09
  • 8
    Keep in mind that it's not whether a cipher is symmetric or asymmetric that makes it breakable or not. AES is symmetric, yet believed quite secure; RSA, especially "textbook RSA", is trivially breakable by an adversary with the appropriate knowledge especially when used with short keys. The value of encryption is typically in keeping a message secure until its value has diminished sufficiently that spending resources on breaking it no longer makes sense; in a world where adversaries aren't particularly powerful (messenger carrying physical piece of parchment from A to B) you don't need much. – user Jun 05 '18 at 20:11
  • @Michael Kjörling Thank for note: that is the reason why i accept any public key encryption that would work in this situation, and RSA is just most known example – Tomasz Czarkowski Jun 05 '18 at 20:13
  • 2
    This might be a question for https://cryptography.stackexchange.com – Philipp Jun 05 '18 at 20:14
  • I removed the [tag:time-travel] tag because though you might possibly use time travel as a means to achieve the end, you aren't asking about time travel. And I'm inclined to agree with @Philipp, this question (possibly rewritten slightly) might be a better fit for experts in [cryptography.se]. – user Jun 05 '18 at 20:15
  • 2
    I don't think a general will want to wait a whole day to decode a message from the King. King's probably don't want to waste an hour to decipher a message from his general. time to encode/decode seems too excessive for viable use. – Michael Kutz Jun 05 '18 at 20:20
  • 1
    @TomaszCzarkowski, thank you for editing to highlight the distinction compared to the proposed duplicate. That's exactly how it should be done. – user Jun 05 '18 at 20:21
  • 2
    Symmetric ciphers are not inherently more easily crackable than asymmetric ones. In reality, usual asymmetric ciphers need much longer keys to be as secure as good symmetric ciphers. As for medieval cryptanalists, a simple cipher such as an ordinary three-rotor Enigma would be way beyond their ability to crack, due to the number of operations required. – AlexP Jun 05 '18 at 20:43

4 Answers4

4

It's totally possible, your issue comes in when you're trying to encrypt the message.

Let's go through the RSA algorithm:

  1. Choose two primes, $p$ and $q$.
  2. set $n=p*q$
  3. find $\phi (n)$ which is equal to $(p-1)(q-1)$
  4. choose a number, $1<e<\phi (n)$ such that $gcd(e,\phi (n))=1$
  5. solve for $d$ given that $d*e \equiv 1 (mod\space\space n)$

Now, lets look at each step individually.

Choose two primes, $p$ and $q$.

Pretty easy to do; I learned about the sieve of eratosthenes in middle school.

set $n=p*q$ and find $\phi (n)$ which is equal to $(p-1)(q-1)$

Again, easy. Multiplication by hand is totally feasible.

choose a number, $1<e<\phi (n)$ such that $gcd(e,\phi (n))=1$

This is a little harder. If you choose $e$ to be prime, then you simply have to check if $\phi (n)$ is a multiple of $e$. Fairly easy.

solve for $d$ given that $d*e \equiv 1 \pmod{n}$

This is a little harder, but still doable by hand.

now, encryption. This gets hard. Basically, if we encode a-z, A-Z, and 0-9 as 6 bit values, then find the integer value of the message, we have our plaintext. Unfortunately, this is probably pretty large. Ergo, this method would only be used for short messages.

The format for encryption is: $c(m) \equiv m^e \pmod{n}$, and decryption is $(c)^d \equiv (m^e)^d \pmod{n}$

Basically, modular exponentiation. Unfortunately, this is hard. The most memory efficient method basically runs the algorithm for every multiplication within the exponent, which is infeasible with any $e$ or $d$ bigger than fifty or so.

Compounding on the fact that the plaintext's value quickly gets too large for mortal minds to comprehend, the inevitable conclusion is that no, RSA needs computers.

Community
  • 1
Jakob Lovern
  • 1,229
  • 6
  • 19
  • Good answer! If you can conveniently do it, I'd be interested to see an estimate of two things (1) the number of operations needed to encrypt each character of the message and (2) the likelihood that it could be done successfully by hand without error. – Mark Olson Jun 06 '18 at 21:11
  • I'd recommend trying to build a system similar to the German enigma machines, which were basically layered ceasarian ciphers, but were still pretty much unbreakable. (well, there's actually more to it than that, but you should watch the movie about Alan Turing, because Turing.) – Jakob Lovern Jun 13 '18 at 21:25
2

Of course, yes. Only without computers you can and should use short keys.

An attempt of decoding for a key will take 1-10 minutes, according to the length of text and ability of the specialist. 10-bit keys make the task 1000 more complex. Up to a day. 20-bit keys - up to 3 years. For 30-bit keys it is better to wait for the first computers.

The act of coding can take much more time than an attempt of decoding, for the last one stops when you see if you have sensible output or not. Several symbols is enough. And if you are coding, you have to put in the whole message. About an hour for a page. And this complexity is independent on the length of the key.

As for getting the full key from the partial ones, even for 30-bit keys it will take less than an hour.

There is another problem - you should have for that the medieval math with Arabian digits and theory of coding... Don't forget, that in our late-medieval times the mastering of division meant doctorate in maths.

Gangnus
  • 1,894
  • 8
  • 10
1

It's certainly possible and a suitable choice of keys would make it safe. However, the likelihood of it being done successfully or reliably is far from clear.

During the late middle ages, the recovery of ancient Greek knowledge (mathematics and philosophy) was in its infancy. Scholars and scribes spent their time translating mostly Arabic and Persian translations of the original Greek texts (in addition to original works by the Arabs and Persians). This new knowledge was still poorly understood.

Also, the Hindu-Arabic number system has just been introduced into Europe and it was still not in widespread use. Most Europeans, including scholars, would not know how to express a large number.

Scholars would be members of the clergy and would therefore be far more concerned with reconciling Greek philosophy with Christian theology. Interest in mathematics would be limited to a small number of scholars.

I guess the point I am trying to make here is that while it may be theoretically possible to train a sufficient number of scholars to do the number crunching, the practical problems appear insurmountable. Certainly the process would be unreliable at best and being prone to error makes its adaption unlikely.

abcdefg
  • 1,182
  • 9
  • 11
0

Although first discovered in 1882 and not seeing wide use until the early 1900s, you might want to look at One-Time Pads which are usable without computers (you need a pencil and paper for math), and if done properly, are totally unbreakable to anyone without a key.

hszmv
  • 10,858
  • 14
  • 29
  • One time pads are really great, but they are not "public key", as they are "one time secret key". Thanks for idea, I completely forgot about their existence, but it does not answer my question. – Tomasz Czarkowski Jun 05 '18 at 20:44