“Yes” is the answer. An understandable reaction to any proposal for an unbreakable cipher is to assert that it is logically impossible to achieve, the argument being that no matter how clever the design, someone will eventually come up with a way of breaking it. This, however, is not the case, and it is possible to demonstrate this quite simply:
The following is a message encrypted by adding a random key stream in the range 0 – 25 from a “one-time pad” to the 26-letter alphabet, also numbered 0 to 25. Under this system A+2 = C, but more significantly, Z+2 = B
W L O C M K O R L
The goal of the attacker is to find which random stream to subtract in order to restore the plain text, bearing in mind that pure randomness implies that all streams are equally probable:
Subtracting 3 7 23 11 24 19 6 25 18 produces TERRORIST
Subtracting 11 3 19 24 21 21 0 3 0 produces LIVERPOOL
Subtracting 20 23 2 13 18 17 10 0 19 produces COMPUTERS
Since all streams are equally probable, then all plain texts including TERRORIST, LIVERPOOL and COMPUTERS are equally probable, which means that key-crashing is a futile exercise.
The fundamental dilemma, which distinguishes the unconditionally unbreakable cipher from those that rely on a very strong session key, is that all decrypted texts obtained by an exhaustive key search are equally probable, making it impossible to determine which message was the original.
It may be argued that this is a special case because the radix (R) is limited to 26. The proof, however, holds for any value of R. Using the whole keyboard means R = 93 and perhaps there is a case for a byte cipher where R = 256.
In order to prove that the principle of the one-time pad applies to all values of R, we draw on “Modular Arithmetic”, popularly known as “Clock Arithmetic”. If we apply this Arithmetic to the hands of a normal clock, the Arithmetic is classed as “Modulo 12” and the numbering on the dial starts with “0” at the top, followed by 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11. The Arithmetic is 8 + 3 = 11, 8 + 4 = 0, 7 + 8 = 3, 3 – 5 = 10.
Applying this idea to a cipher, we imagine that R characters are arranged clockwise in order in a circle so that character number “R-1” is followed by character number “0”. Encrypting is then a matter of adding the key and counting clockwise round the circle. Decryption is a matter of counting anti-clockwise.
If we take any one character from the circle, and try to decrypt it without knowledge of the key, the only course open to us, bearing in mind that all values of the key from 0 to R-1 are equally probable, is to count back anti-clockwise. In so doing we find ourselves up against the fundamental dilemma. All characters selected by counting backwards are equally probable, so it is impossible to determine which character was the original. The cipher is unconditionally unbreakable. Quod Erat Demonstrandum.
Author: Bill Hawthorne
