Caesar's Encryption
Julius Caesar encrypted by shifting the letters of the alphabet 3
places forward: a was replaced with D, b with E, and so on. At the very end
of the alphabet, the letters wrap around and so z was replaced
with C, y with B, and x with A. For example, encryption of the message
"begin the attack now" (with spaces removed), gives:
EHJLQWKHDWWDFNQRZ
.An immediate problem with this cipher is that the encryption method
is fixed; there is no key. Anyone learning how Caesar encrypted
his messages would be able to decrypt them effortlessly.
Before reading on, try to decrypt the following ciphertext that was
generated using the shift cipher and a secret key k:
OVDTHUFWVZZPISLRLFZHYLAOLYL
.
Is it possible to recover the message without knowing k? Actually, it
is trivial. The reason is that there are only 26 possible keys k. So one
can try to decryptthe ciphertext using every possible key and
thereby obtain a list of 26 candidate plaintexts. The correct
plaintext will certainly be on this list; moreover, if the ciphertext
is "long enough" then the correct plaintext will likely be the only
candidate on the list that "makes sense." The latter is not
necessarily true, but will be true most of the time. Even when it is
not, the attack narrows down the set of potential plaintexts to at most
26 possibilities.) By scanning the list of candidates it is easy to
recover the original plainttext.
Any secure encryption scheme must have a key space that is
sufficiently large to make an exhaustive-search attack infeasible.
The key space thus consists of all bijections,
or permutations, of the alphabet. So, for example, the key that
defines the following permutation
a b c d e f g h i j k l m n o p q r s t u v w x y z
X E U A D N B K V M R O C Q F S Y H W G L Z I J P T
(in which a maps to X, etc.). There are 26! possibilities, a
large number indeed.
However. if the same permutation key is used throughout the message
(say always replacing E by D), then using a letter frequency table for
English (see below), you can often decypher the message fairly quickly.