The Caeser cipher uses only the 26 rotations out of the 26!
permutations on the alphabet. The monoalphabetic cipher uses
them all. A key k is an arbitrary permutation of the alphabet.
Ek(m) replaces each letter a of m by k(a) to yield c.
To decrypt, Dk(c) replaces each letter b of c by k−1(b).
The size of the key space is |K| = 26! > 274, which is too
large for a successful brute force attack. However, monoalphabetic
ciphers can be readily broken using letter frequency analysis, given a
long enough message. Because each occurrence of a letter a in the
message is replaced by the same letter k(a), the most
frequently-occurring letter of m will correspond to the most
frequently-occurring letter of c. While Eve might not know what the
most frequently-occurring letter of m is, if the message is long
enough and she knows that it is English, then it is quite likely that
the most frequently-occurring letter in m is one of the most
frequently-occurring letters in English, i.e., `e' or maybe `t'. She
can then assume that the most frequent letter b1 in c is `e', the
next most frequent letter b2 is `t', and so forth. Of course, not
all of these guesses will be correct, but the number of likely
candidates for each ciphertext letter is greatly reduced. Moreover,
many wrong guesses can be quickly discarded even without constructing
the entire trial key because they lead to unlikely letter
combinations.
A cipher that encrypts two letters at a time is much harder to break
than a monoalphabetic cipher since it tends to mask the letter
frequencies. The Playfair cipher, popularized by L. Playfair
in England circa 1854, is one such example.1 Here, the key is a 5×5 matrix of letters. Pairs of
plaintext letters are located in the matrix and used to produce a
corresponding pair of ciphertext letters.
For example, consider the key matrix that might result from the
passphrase, "CRYPTOGRAPHY REQUIRES STRONG KEYS":
C
R
Y
P
T
O
G
A
H
E
Q
U
I/J
S
N
K
B
D
F
L
M
V
W
X
Z
The matrix is constructed by writing the passphrase into the matrix
cells from left to right and top to bottom, omitting any letters that
have previously been used. It is filled out with the letters of the
alphabet that do not occur in the passphrase, in alphabetical order.
(In carrying out this process, "I" and "J" are identified, so we
are effectively working over a 25-character alphabet.) Note that each
letter of the alphabet occurs exactly once in the resulting matrix.
A message to be encrypted is first broken up into pairs of letters.
For example, the message "MEET ME AT THE SUBWAY" would be broken
into the pairs "ME" "ET" "ME" "AT" "TH" "ES" "UB" "WA"
"YX". Note that we have padded the message with a trailing "X" in
order to make its length even, and spaces have been suppressed. Now,
each pair of plaintext letters is encrypted. For example, the pair
"AT" would be encrypted by taking the rectangle with "A" and "T"
as its corners and then using the letters from the other two corners
as the cipher text. In this example, the encryption of "AT" is
"EY". Decryption is by a similar procedure. The cipher also
contains rules for handling various special cases such as when both
plaintext letters occur in the same row or the same column or both.
In decrypting, one also must resolve the I/J ambiguity and figure out
when to remove the padding character.
The Hill cipher is another example of a cipher that encrypts
groups of letters at once, thereby tending to mask letter frequencies.
It is based on linear algebra. The key is, say, a non-singular
3×3 matrix K. The message m is divided into vectors mi
of 3 letters each. Encryption is just the matrix-vector product Kv.
Decryption is the same using K−1.
Unfortunately, the Hill cipher succumbs to a known plaintext attack.
Given three linearly independent vectors m1, m2, and m3 and
the corresponding ciphertexts ci = Kmi, i=1, 2, 3, it is
straightforward to solve for K.
Another way to strengthen monoalphabetic ciphers is to use different
substitutions for different letter positions. For example, one might
choose 10 different alphabet permutations k1, …, k10, use
k1 for the first letter of m, k2 for the second letter, and so
forth, repeating this sequence after every 10 letters. While this is
much harder to break than monoalphabetic ciphers, it turns out that
letter frequency analysis can still be used. Every 10th letter is
encrypted using the same permutation, so the submessage consisting of
just those letters still exhibits normal English language letter
frequencies.
All of the methods discussed so far are based on letter substitution.
Another technique is to rearrange the letters of the plaintext. For
example, one might write a plaintext message into a matrix by rows and
then read it out by columns. While transposition does not seem like a
very powerful technique by itself, when used in combination with
substitution techniques it can be quite effective. Most practical
symmetric cryptosystems are built by composing together many stages of
substitutions and transpositions.
Rotor machines had an important history during the Second World War.
The Germans believed their Enigma machine was unbreakable, but the
Allies, with great effort, succeeded in breaking it and in reading
many of the top-secret military communications. This is said to have
changed the course of the war.
The basic idea of a rotor machine is to use electrical switches to
create a permutation of 26 input wires to 26 output wires. Each input
wire is attached to a key on a keyboard. Each output wire is attached
to a lamp. The keys are associated with letters just like on a
computer keyboard. Each lamp is also labeled by a letter from the
alphabet. Pressing a key on the keyboard causes one of the lamps to
light, which indicates the ciphertext character corresponding to the
key pressed. The operator types the message one character at a time
and writes down for each letter the corresponding lamp. To decrypt,
one could switch inputs and outputs to obtain the inverse permutation,
type in the ciphertext, and read out the plaintext.
What I have described so far is just an electro-mechanical device for
implementing a monoalphabetic cipher. However, rotor machine gain
their power by changing the permutation after each letter. Each rotor
is individually wired to produce some random-looking fixed
permutation π. Several rotors stacked together produce the composition
of the permutations implemented by the individual rotors. In addition,
the rotors can rotate relative to each other, implementing in effect a
rotation permutation (like the Caeser cipher uses). Let ρk(x) = x+k mod 26.
Then rotor in position k implements permutation ρk πρk−1.
Several rotors could be stacked together to implement the composition
of the permutations computed by each. For example,
three rotors implementing permutations π1, π2, and π3,
placed in positions r1, r2, and r3, respectively, would produce the permutation
ρr1·π1·ρ−r1·ρr2·π2·ρ−r2· ρr3·π3·ρ−r3
=
ρr1·π1·ρr2−r1·π2· ρr3−r2·π3·ρ−r3
(1)
After each letter is typed, some of the rotors change position, much
like the mechanical odometer used in older cars. The period before
the rotor positions repeat is quite long, allowing long messages to be
sent without ever repeating the same permutation. Thus, a rotor
machine is much like a polyalphabetic substitution cipher, but with a
very long period. However, unlike a pure polyalphabetic cipher, the
successive permutations until the cycle repeats are not independent of
each other but are related to each other by (1). This
gives the first toehold into methods for breaking the cipher (which
are far beyond the scope of this course).
Several different kinds of rotor machines were built and used, both by
the Germans and by others, some of which work somewhat differently
from what I described above. However, the basic principles are the
same. The interested reader can find much detailed material on the
web by searching for "enigma cipher machine" and "rotor cipher
machine". Nice description may be found at
http://en.wikipedia.org/wiki/Enigma_machine and
http://www.quadibloc.com/crypto/intro.htm.
Steganography, hiding one message inside another, is an old technique
that is still in use. For example, a message can be hidden inside a
graphics image file by using the low-order bit of each pixel to encode
the message. The visual effect of these tiny changes is probably too
small to be noticed by the user. The message can be hidden further by
compressing it or by encrypting it with a conventional cryptosystem.
Unlike conventional cryptosystems, where we assume the attacker knows
everything about the cryptosystem except for the secret key,
steganography relies on the secrecy of the method of hiding for its
security. If Eve does not even recognize the message as ciphertext,
then she is not likely to attempt to decrypt it.
Footnotes:
1See Memezes
et. al., "Handbook of Applied Cryptography", p. 239-240, for
details.
File translated from
TEX
by
TTH,
version 3.66. On 18 Sep 2005, 17:46.