Rotating Ciphers

So, last time, we looked at simple substitution ciphers. In a substitution
cipher, you take each letter, and pick a replacement for it. To encrypt a
message, you just substitute the replacement for each instance of each letter.
As I explained, it's typically pretty each to break that encryption - the basic
secret of the encryption is the substitution system, and it's pretty easy to
figure that out, because the underlying information being encrypted still has a
lot of structure.

There are a couple of easy improvements on a simple substitution cipher, some of which came up in the comments. For example, two
good easy improvements are:

1. Instead of defining substitutions for single characters, define
   substitutions for groups (pairs, triplets) of characters. This improves things,
   because it allows you to work with groups that will reduce the visibility of
   patterns. Still, because there's so much structure in human language, given
   enough data, an encrypted message is still likely to be easy to decode. So this
   is great for short messages, but not for anything bigger.
2. Multiple substitutions: instead of always substituting, say, "x" for "a",
   substitute each letter with a two-digit number. Then for common letters, allow
   multiple possible substitutions. By assigning many codes to common letters, and
   few codes to uncommon letters, you can make the coded symbols appear with
   roughly equal frequency. This can seriously hamper frequency based analyses.

Both of those changes help. They work particularly well when combined. To do
a two-character version of that, you create a list of all possible two-character
sequences. Then you generate a frequency table for how often each two-character
sequence occurs in a large sample of the kind of text you're going to encode.
Then, finally, you assign a number of substitutions for each pair so that they
occur with approximately equal frequency. That gives you a pretty good
system.

Still, it's not great. Given enough encoded text, it can be cracked with a
relatively small amount of computational power. If I know the basic idea of the
cipher, and I've got a decent amount of encoded text, I can write a program that
will figure it out pretty quickly. Plus, it's really a lot of work to generate
the cipher - you need to generate frequency tables, and work out the number of
substitions, etc. It's definitely not trivial to set up, and it's still pretty
easy to crack.

For that reason, those kinds of solutions aren't used much - there's a lot
of prep work, and the secret that you need to share with your partner is large
and complicated. You can get better quality with less effort and a
simple secret using a different scheme called a rotating cipher.

A rotating cipher is one of the simplest examples of a form of encryption
that CS geeks like me call stateful encryption. The idea is that you
start with a simple substitution. But then each time you encrypt a character,
you change the substitution. This covers an incredibly wide range of
encryption techniques - you can understand most digital encryption schemes as
being some kind of stateful cipher.

So let's look at the simplest kind of stateful cipher: a simple rotating
cipher. In a rotating cipher, you have an alphabet, consisting of the set of
characters that you can use in messages. You have a basic cipher, which consists
of the set of characters arranged in some order. You take the alphabet in order,
and line it up with the cipher. Each time you encode a character, you shift the
way that the cipher and the basic alphabet line up. The reason it's called a
rotating cipher is that the physical version of this consists of two wheels: the
inner wheel has the un-encrypted alphabet; the outer wheel has the cipher. To
encrypt a character, you look it up on the inner ring, and write down the
corresponding character on the outer ring. After that, you rotate the outer
ring.

The precise way that you rotate that outer ring varies depending on the
exact encryption technique being used. There are a variety of techniques that
you can use for rotating the cipher. Two simple examples:

1. Rotate by a fixed number of steps each character. For example,
   rotate the cipher wheel three steps after each character is encrypted.
2. Rotate by a function of the unencrypted character. For example,
   if you encrypt the character at position five in the alphabet, rotate
   the cipher by five steps.

For example, here's some Python code which implements rotating ciphers. It's
implemented as an abstract superclass with two subclasses using two different
rotation methods. The first is a fixed rotator - it rotates by three characters
each time. The second is a variable rotation: it rotates by 3 times the position
of the encoded character in the alphabet.

class RotatingCipher(object):
  def __init__(self, alphabet, cipher):
    self._alphabet = alphabet
    self._cipher = cipher

  # to be overridden by subclasses for different rotation
  # schemes.
  def _RotateCipher(self, c):
     pass

  def CryptNextChar(self, c):
    """Encrypt a single character and rotate the cipher."""
    # find position of "c" in the alphabet.
    index = self._alphabet.find(c)
    # encrypted character is that position plus the rotation,
    # modulo the size of the alphabet.    
    crypt = self._cipher[(index + self._rot) % len(self._alphabet)]
    self._RotateCipher(c)
    return crypt

  def Encrypt(self, s):
    """Encrypt a message string."""
    self._rot = 0
    result = ""
    for c in s:
      result += self.CryptNextChar(c)
    return result

  def DecryptNextChar(self, c):
    """Decrypt a single character and rotate the cipher."""
    # to decrypt of character, find index of the crypted character in
    # the cipher, and subtract the rotation from it, giving the
    # index of the decrypted character in the alphabet.
    index = self._cipher.find(c)
    index -= self._rot
    if index < 0: index = len(self._alphabet) + index
    self._RotateCipher(self._alphabet[index])
    return self._alphabet[index]

  def Decrypt(self, s):
    """Decrypt a string encrypted by this cipher."""
    self._rot = 0
    result = ""
    for c in s:
      result += self.DecryptNextChar(c)
    return result


class FixedRotatingCipher(RotatingCipher):
  """An implementation of a cipher using a rotation strategy 
     that shifts the cipher by a fixed increment after each
     character."""
  def __init__(self, alphabet, cipher, increment):
    super(FixedRotatingCipher, self).__init__(alphabet, cipher)
    self._rot = 0
    self._increment = increment

  def _RotateCipher(self, c):
    self._rot = (self._rot + self._increment) % len(self._alphabet)



class VariableRotatingCipher(RotatingCipher):
    """An implementation of a cipher using a function of the
       last character as the rotator. Each rotation shifts by
       the character index times three."""
    def __init__(self, alphabet, cipher):
        super(VariableRotatingCipher, self).__init__(alphabet, cipher)

    def _RotateCipher(self, c):
        index = self._alphabet.find(c)
        self._rot = (self._rot + (3*index)) % len(self._alphabet)


fcipher = FixedRotatingCipher(
     "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.,- ", 
     "KLMNijklSTUVabcduvwxyzABCDEFefghGHIJ.,- mnopOPQRqrstWXYZ", 3)

en = fcipher.Encrypt("Mark has a big nose.")
de = fcipher.Decrypt(en)

print "Encrypted = %s" % en
print "Decrypted = %s" % de

vcipher = VariableRotatingCipher(
     "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.,- ", 
     "KLMNijklSTUVabcduvwxyzABCDEFefghGHIJ.,- mnopOPQRqrstWXYZ")

ven = vcipher.Encrypt("Mark has a big nose.")
vde = vcipher.Decrypt(ven)

print "Variable encrypted = %s" % ven
print "Variable decrypted = %s" % vde

The quality of a rotating cipher depends largely on quality of the
the rotation strategy. A fixed offset rotator frankly stinks - it's only marginally better than a simple substitution cipher. But with a really good, sophisticated rotator, you can make an amazingly good cipher. Up to the advent of modern computers, rotating ciphers were pretty much top of the heap of encryption - but with much, much more sophisticated rotators.

For example, the infamous German Enigma machines had three or four physical rotors. Each time a character was encrypted, one of the rotors moved, and its motion could trigger motions of the other two rotors, depending on the setting of an encryption key. The positions of the rotor wheels would create an electrical circuit which actually generated the encrypted character. In the most sophisticated version of Enigma, the rotors were replaceable - which allowed you to reconfigure the relationships between the rotors; you also could set an initial position on the rotor wheels (the passcode), and the more advanced machines included an electrical plugboard that could reconfigure the electrical
part of the machine. So the "rotation" corresponded to a rewiring of the machine by switching the positions of the rotors, which interacted in a complicated way which was dependent partly on the physical markings on the rotor disks, partly on the encryption key, and partly on the last encrypted character.