It’s a concern for Europeans as it is for people elsewhere in the world: there have been suggestions among governments to either outlaw, curtail, or backdoor strong end-to-end encryption. There are many arguments against ruining encryption, but the strongest among them is that encryption can be simple enough to implement that a high-school student can understand its operation, and almost any coder can write something that does it in some form, so to ban it will have no effect on restricting its use among anyone who wants it badly enough to put in the effort to roll their own.
With that in mind, we’re going to have a look at the most basic ciphers, the kind you could put together yourself on paper if you need to.
There have no doubt been cryptologists and codebreakers at work as long as there have been humans capable of repeating messages, and the strong public-key cyphers we use today were created by mathematicians who stood on the shoulders of those before them in an unbroken line that goes back thousands of years. It’s the public-key ciphers that are in the eyes of the lawmakers, but perhaps surprisingly they are not the only strong encryption scheme that remains functionally unbreakable. A much older and simpler cypher also holds that property, and it’s this that we’re presenting as the paper-based answer to strong encryption legislation. The so-called one-time pad was a staple in tales of Cold War espionage for exactly the properties we’re looking for.
To explain a one-time pad it’s necessary to first travel back to ancient Rome, for the simple alphabetic substitution cypher. In its most basic form an alphabet from A to Z is either shifted or randomised, and the resulting list of letters is used to encrypt the message into the cyphertext by direct substitution. The cyphertext is encrypted, but its flaw comes in that it preserves the frequency distribution of the letters in the message text. Frequency analysis was a technique developed and refined by the mathematicians of the Islamic caliphates, in which the frequency of individual letters in a cyphertext could be compared with that of letters in the language as a whole. By this technique a codebreaker could identify enough of the letters in the message to reconstruct it by guessing those which remained.
Addressing this flaw in the substitution cypher leads us to 16th century Italy and the polyalphabetic cypher, which instead of using a single substitution alphabet uses a number of them, switching from one to the next in sequence. The Vigenère cipher uses a table of alphabets each shifted by one letter with respect to the previous one, and switches from one to the next with each successive letter. By the use of a keyword to determine the sequence of which shifted alphabets in the table would be used for the substitution it created a cypher which was considered unbreakable until the 19th century, when mathematicians including Charles Babbage succeeded in breaking it by spotting the repeating patterns of its keyword.
So the Vigenère cipher is compromised, but its weakness lies not with its method but in the use of a repeating keyword to implement it. If a short keyword is used, such as “hackaday”, then it becomes in effect a series of eight sequentially repeating substitution cyphers; alphabet shifts h, a, c, k, a, d, a, and y in order over and over again, and a more complex but still achievable set of calculations will reveal its secret. These calculations become more complex as the length of the keyword increases, to the point at which it is the same length as the cyphertext and the possibility for spotting its repeats no longer exists.
A One-Time Pad
A Vigenère cypher whose key is the same length as its text is unbreakable by frequency analysis in an attempt to spot the repeating keyword. But if the keyword itself contains a recognisable pattern such as a passage from a book or even a pseudo-random sequence there is still a chance that it can be compromised particularly if it is re-used, and hence we come to the idea of the one-time pad.
If every message uses a fresh encryption key composed of random characters that is the same length as its text then it contains no clues to help a code-breaker, because the entropy of the cyphertext is the same as that of the random key. Those cold-war spies achieved this in a low-tech manner using a pad whose pages contained random key text and from which each page could be torn and discarded once it had been used, hence the term “one-time pad”.
One-time pad encryption then. It’s unwieldy because both parties have to have a copy of the same pad, and even though it’s simple enough to do with a paper and pencil (or even a set of XOR gates) it’s probably not a sensible alternative to more modern forms of encryption. But it is genuinely strong end-to-end encryption, which would make it subject to any attempts to curtail encryption. So the point of this article hasn’t been to persuade you all to switch to using a Vigenère square and a notebook full of random digits, instead it’s been to write down just how simple secure end-to-end encryption can be. If a child can do it with a pen and paper then the most novice of coders can implement it in a script with nothing more than a text editor, so any proposal to censure it seems like closing the stable door after the horse has bolted.
0 Commentaires