# Julius Caesar with a one-time pad

Julius Caesar used a substitution cipher (now called a Caesar cipher) for sensitive private and military correspondence. The cipher involves shifting all of the letters in a message in one direction a secret number of times, wrapping around if necessary. This appears to have done well for Caesar, but could he have done better? The cipher itself is quite trivially breakable.

What if Julius Caesar had been given access to a one-time pad, or OTP? An OTP is an encryption technique that is unbreakable when used correctly. The key must be the same size as the message and completely random, but if it is, it provides information-theoretic security. The way it works is simple. The pad is the same size as the message to be encrypted. You add the position of each letter in the pad (1 for A, 2 for B, etc) to the position of each letter in the message, modulo the size of the alphabet. An example encryption of "HELLO" using pad "XMCKL" from Wikipedia:

       H       E       L       L       O   message
7 (H)   4 (E)  11 (L)  11 (L)  14 (O)  message
+  23 (X)  12 (M)   2 (C)  10 (K)  11 (L)  key
=  30      16      13      21      25      message + key
=   4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) (message + key) mod 26
E       Q       N       V       Z → ciphertext

E       Q       N       V       Z   ciphertext
4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z)  ciphertext
-  23 (X)  12 (M)   2 (C)  10 (K)  11 (L)  key
= -19       4      11      11      14      ciphertext – key
=   7 (H)   4 (E)  11 (L)  11 (L)  14 (O)  ciphertext – key (mod 26)
H       E       L       L       O → message


A random pad can be trivially generated by flipping a coin to determine which letter is present. The pad is delivered securely to the correspondents. It is one of the few concepts in cryptography that are completely and provably unbreakable. How would the Roman Empire's role in history change if:

• Julius Caesar and his private correspondents knew of the technique?
• the concept of the OTP itself was widely known throughout the empire?

In practice, the OTP would allow the Roman Empire to communicate with perfect secrecy. I could very well be overestimating how important this was for them, but it seems to me like it would lead to a rather large change given that more secret messages could be sent between two parties without needing to trust the messenger. It could have major ramifications.

• The answer to this question relies on the previous cipher technique failing, and someone cracking Caesar's communications. If that never happened, then the change that would occur from Caesar having better cryptography techniques is exactly zero. That said, if you're saying that more messages would have been sent if the system was trusted more, I'm not convinced of that because critical information for troop movements et al HAD to be sent anyway, leaving us back with an example of a message ever being breached. Did Caesar ever in history express any concern about this cipher technique? – Tim B II Mar 20 '18 at 3:52
• @TimBII and there would have been the extra overhead (and hassle) of having to send copies of the OTPs to the various generals and governors. – RonJohn Mar 20 '18 at 3:54
• @TimBII The question is not only about whether or not he himself had it. The secondary question is what would happen if everyone knew of this technique. – forest Mar 20 '18 at 3:59
• I'd ask History.SE when the Cesar encryption scheme (now known as ROT) was broken, and then come back and ask us what would the world be like if those events turned out differently. – RonJohn Mar 20 '18 at 4:20
• The wikipedia page Caesar Cipher writes that Caesar actually used more elaborate ciphers. – castor Mar 20 '18 at 10:13

The same problems that a normal one time pad face would be faced by our hypothetical Caesar.

Namely, if you want to send me a message, I need to have:

1. A one time pad at least as long as your message (or, if we're willing to settle for a shorter cipher, as many ciphers as you have messages)
2. Received every message you've sent me up until your current one (and both of us destroying pads once they've been used)
3. Successfully hidden my one time pad from the enemy

This creates a tricky situation. If I run out of pad, you can't send me more messages without somehow getting me a new pad.

If a message gets intercepted, you need to somehow figure that out and tell me how much I need to increment by. We can get around this by, say, discarding a page every day or numbering the pads, but this means a lot more pad and leads into the third problem:

I need to hide at least twice as many documents as you're sending. To decode a letter I need the letter and its key. That's two documents I could be caught with and executed for, and two documents that might be intercepted, either of which would ruin the message.

With all that said, it probably wouldn't see a great deal of use outside of very special circumstances where it's better to lose the information outright rather than risk discovery- internal affairs rather than wars. A regional governor has perverse tastes, and if discovered the province could revolt. Still the agent needs to inform their superior so it can be handled discreetly, so the one time pad is used.

In crisis situations they probably wouldn't be used - if the byzantine generals are trying to coordinate, losing the critical message to a messenger being intercepted is worse than the defenders getting hold of the plan.

Of note, the message loss problem can be solved if I retain used pads to decode corrupted messages and cope with messages arriving out of order, but this then becomes more of a codebook than a one time pad. For the circumstances we would want to use a one time pad (ie. where we would prefer for nobody to know the message over the proverbial Eve knowing it) it represents something of an unwelcome risk.

• Actually you do not need a OTP at least as long as the message. Having a finite length OTP that is cycled will suffice just fine. The security will still be far better than with a Ceasar Cipher since you have to do a far more sophisticated analysis of the cipher text to suss the contents, – MichaelK Mar 20 '18 at 9:53
• @MichaelK A "finite length OTP that is cycled" isn't an OTP. It's a Vigenère cypher. Yes, it's way better than Caesar but it's not OTP any more. – David Richerby Mar 20 '18 at 10:50
• The message loss effect is trivially mitigated by starting each message with the offset into the pad at which it was encrypted. – David Richerby Mar 20 '18 at 10:52
• @ChrisH This whole "OTP is a special case of Vigenère" line of discussion just isn't constructive. There are significant and extremely important implementation differences. If you use a book as your OTP, then both the key and cyphertext are highly structured, which gives you a huge opening for cryptanalysis. OK, probably not cryptanalysis that could have been done in Roman times (even simple analysis of Caesar doesn't seem to have been discovered until hundreds of years later, and this would be much more computationally expensive) but "some variant of OTP" isn't OTP and is much weaker. – David Richerby Mar 20 '18 at 13:50
• @DavidRicherby you're right of course. I was imagining generating a random list of letters and using them as the initials of individuals in something like a list of troops, i.e. the key is unstructured but hidden in structured text. This would be a little heavy on stone or even wax tablets, though the latter would be ideal for OTPs! I may have implied that an OTP was a special case of a V-cipher by a sloppy use of "limit" but meant that in practice you couldn't tell the difference. Of course the practical strength of Vigenère is the use of a memorable key phrase, which my list breaks. – Chris H Mar 20 '18 at 14:18

I'll go with "No effect".

The value of modern encryption lies with our use of telecommunications. Our messages can generally be intercepted by hostile agents without any real method to prevent or detect that. This creates a need for a method to secure the actual communications independent of the medium being insecure.

The Romans did not have that. Their messages were carried by human couriers, who would guard the messages. The messages themselves would be physical objects secured against tampering with seals. Provisions would be made to destroy the messages, if capture seemed imminent.

A system like that is as secure as the people involved. No system for communicating between people can improve on that. The best you can do is to minimize the number of people with access to the messages. Securing the physical messages against tampering and using guards actually works here. You do not need to be able to read the message or have any knowledge of codes used to guard or deliver it.

In fact, a more complex encryption such as OTP would be less secure. Somebody needs to write those pads, they need to be transported to correct location and then stored and secured there. And the actual encryption and decryption would be labor intensive enough to probably require additional people to deal with it.

People who can be bribed or just captured and tortured. And without the pads, messages are useless, so bribing any of the people involved with the pads to sabotage them will be quite devastating. And if people start to believe the system is secure, the security will suffer. Enigma taught us that.

By contrast a very simple cipher such as the one Caesar actually used can be memorized and decoded directly by the recipient. While the added security is fairly small, it comes without added complexity or vulnerability. And with the constant presence of servants, slaves, and guards a cipher that simply stops people reading over your shoulder does have real value.

And OTP cannot do that. It cannot be read directly by most people. You have to decode it and then read it. Which means a physical copy of the decoded plain text needs to exist during both encoding and decoding.

The bottom line is that for the needs the Romans actually had the Caesar cipher is actually superior to one time pad. Which kind of makes sense, the ancient world had some extremely smart people and Caesar was fairly well educated. If he had wanted a code that is harder to break, he would have been able to get one.

• *By contrast a very simple cipher such as the one Caesar actually used can be memorized and decoded directly by the recipient. * is demonstrated simply enough by reading lots of ROT13 text used as spoiler masks etc. I never got enough practice for it to be as fast as reading, but as a process ROT13 was more like reading than deciphering. – Chris H Mar 20 '18 at 12:05

As mentioned by others, a full-blown OTP is unpractical.

However, there’s a middle way, invented by Blaise de Vigenère in the XVIth century in France.

The Vigenère cypher is crackable using modern cryptanalysis but for a very long time it proved formidable. If it had been invented — and used — a few centuries earlier, this could have changed the course of history. I shan’t enumerate all historical events that relied on broken private communication (for a fun account, I recommend The Code Book by Simon Singh), and I can’t speculate about the influence that better cypher would have had.

What’s interesting is that even after the invention of the Vigenère cypher, strictly inferior systems remained in widespread use, even for communications of the utmost importance and secrecy. Of course these were soon broken.

Throughout history, there’s been an arms race between cryptographer and cryptanalyst. Whenever a stronger cryptography was developed (and used), the onus was on the attacker to break it. And when a cypher was broken, there was need to develop better cryptography.

I therefore think that the biggest influence, if Caesar had known about the Vigenère cypher, would have been on the development of modern mathematics and statistics: attackers would have spent more time thinking about how to analyse text to break the cypher. And, in doing so, they would by necessity have to invent methods of working with discrete distributions of events.

Modern statistics was almost exclusively developed in the last 200 years. Recently its use has become ubiquitous and powerful (data science? statistics. AI? statistics. … the list goes on).

Now imagine modern statistical tools had been invented 1000 years earlier.

There’s a big caveat in my speculation: even without “big data”, modern statistics relies heavily on computers for tabulation and computation. Their use is severely curtailed lacking these mechanical aids. Nevertheless, statistical thinking would have had a drastic effect on the development of science and technology.

• +1 but note that Vigenère was apparently cracked in the 1840s and certainly by the 1860s so it doesn't require any particular computational ability. – David Richerby Mar 20 '18 at 13:54
• @DavidRicherby Correct (although cracking a Vigenère cypher without a computer is a lot of manual work). I’m just wondering how generally useful modern statistics would be if it had to be performed manually. We don’t know, because modern statistics and computation developed marvellously in lockstep. – Konrad Rudolph Mar 20 '18 at 13:57

I think OTP would be perfectly useless.

Gauls were barely literate. The odds of them deploying sophisticated techniques were exactly zero.

It's quite possible that any pad would have make the message less secure by introducing an extra point of failure.

I would go with no effect -- unless you tweak the scenario. There is no intrinsic reason why the Roman Empire couldn't have had a functioning optical telegraph system connecting Rome with points several hundred miles away. Such optical communication would be vulnerable to interception so would require some form of encryption to function effectively. In an alternative history, the security of such optical communication could play a role (e.g. Roman troops ambushed because an attacker knew their route before hand). A one time pad seems to be overkill, but as others have pointed out it something like a Vigenère cipher would have given reasonable security at the time.

1. No effect. This technique has very limited use given that all communication in that age was via courier. The message and the key would both have to be sent to the same recipient by separate runners, either spaced apart or taking different runners. At best, it would take more time. At worst, if only the message or only the key was delivered, either is useless without the either, resulting in breakdown of command communication. Information security at the age when information travels at the speed of a horse is a very minute factor - especially given the literacy rate at that time period.

2. Even less of an effect. A one-time pad is "unbreakable" when used with bits. When used with words and sentences, it is literally as complex as any other substitution cipher - sentences and words have a determinable structure. Not to mention the message and the pad have to have the same number of characters, meaning it can only be used once in an age of limited communication resources - and once again, an age when most people cannot read, much less encrypt and decrypt messages. The method would far, far out-pace the means.

• Regarding #2, the pad is still unbreakable if used with words and sentences, as long as the pad is the same size as the message and uses the same character set. – forest Mar 20 '18 at 4:20
• Welcome to WorldBuilding! If you have a moment please take the tour and visit the help center to learn more about the site. Have fun! – Secespitus Mar 20 '18 at 8:51
• Your claim in 2 is completely wrong. OTP doesn't care what base is used for the arithmetic. The cyphertext gives away literally nothing about the plaintext except for its length, so there's no cryptanalysis to be done. Any given cyphertext can be generated from literally any possible plaintext of the right length by using the correct key. If you intercept a 12-character OTP-coded message and you don't have the key, it could be attackatdawn or surrendernow or ilikekittens or anything else. – David Richerby Mar 20 '18 at 10:55
• Downvoting because the first two sentences of your second paragraph are completely wrong. (The bit starting "Not to mention ..." is right) – Martin Bonner supports Monica Mar 20 '18 at 13:25
• About 1) Typically one time pads are pre-distributed over some trusted channel to make an untrusted channel safe. Here say by meeting face to face in Rome to exchange pads and then sending messages by runners while away. Sending a message in N pieces which is recoverable by having any M of them is a different kind of system from OTPs. – user25818 Mar 20 '18 at 17:51