## Autokey

### December 4, 2009

An autokey cipher uses the plain-text of the message being sent to form part of the key. There are many kinds of autokey ciphers. The one we will examine is classic, invented by Blaise de Vigenère in 1586, over four hundred years ago.

De Vigenère’s autokey begins with a keyword, then appends to the keyword the plain-text of the message being sent. Each letter of the plain-text is then enciphered by indexing through the alphabet according to the corresponding letter of the key:

```plain-text  A C O L L E C T I O N O F E T U D E S key         P R A X I S A C O L L E C T I O N O F cipher-text P T O I T W C V W Z Y S H X B I Q S X```

Decryption is the inverse operation.

Your task is to write functions that encipher and decipher a message as shown above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 13 Responses to “Autokey”

1. [...] Praxis – Autokey By Remco Niemeijer In today’s Programming Praxis we have another cipher algorithm. Let’s get [...]

2. Remco Niemeijer said

My Haskell solution (see http://bonsaicode.wordpress.com/2009/12/04/programming-praxis-autokey/ for a version with comments):

```combine :: (Int -> Int -> Int) -> Char -> Char -> Char
combine f a b = chr \$ mod (f (ord a) (ord b) - 2 * 65) 26 + 65

cipher :: (Int -> Int -> Int) -> String -> String -> String
cipher f key msg = zipWith (combine f) (clean msg) (clean key)
where clean = map toUpper . filter isLetter

encrypt :: String -> String -> String
encrypt key msg = cipher (+) (key ++ msg) msg

decrypt :: String -> String -> String
decrypt key msg = cipher (-) (key ++ decrypt key msg) msg
```
3. John Cowan said

What do you mean, “impractical for use by real spies”? Real spies certainly did use them: we have some of the Russian one-time pads from the 50s and 60s. There’s a picture of one at http://www.ranum.com/security/computer_security/papers/otp-faq/otp.jpg .

In practice OTPs work best in fairly low-traffic situations between specific endpoints, which is exactly the situation of an embedded spy. As Isaac Asimov pointed out, a Nazi spy successfully able to send the message ATOM BOMB OAK RIDGE TENN would have told German intelligence almost all it needed to know.

4. programmingpraxis said

Of course it is possible. But one-time pads are generally more useful for diplomats than spies. A spy would rather memorize a keyword, or a system of generating a keyword from the daily newspaper, or carry an innocent book for a book cipher, than carry an incriminating one-time pad. I know Kahn says that in his book, though I can’t cite a specific reference.

5. Skrud said

Here’s a quick Python solution.

```def encrypt(cleartext,key):
ciphertext = ""
key = key + cleartext
i = 0
while i < len(cleartext):
ciphertext += __vig( cleartext[i], key[i] )
i += 1
return ciphertext

def decrypt(ciphertext,key):
cleartext = ""
i = 0
while i < len(ciphertext):
cleartext += __vig( ciphertext[i], key[i % len(key)], True )
key += cleartext[-1]
i += 1
return cleartext

def __rot(l,d):
# Rotate the letter l by the specified number of degrees (assume uppercase)
return chr((((ord(l) - ord('A')) + d) % 26) + ord('A'))

def __vig(l,k,inverse=False):
# Determine the index of key-letter 'k' relative to 'A' and use that
# as the number of degrees to rotate by.
degree = ord(k) - ord('A')
if inverse:
degree = -degree
return __rot(l, degree)
```

Here’s a quick PHP Solution

``` function encrypt(\$str, \$key) { \$out = ""; for (\$i=0; \$i<strlen(\$str); \$i++) { \$base = ord(\$str[\$i]) - 65; // take index of base string \$offset = ord(\$key[\$i]) - 65; // take index of key \$ascii = (\$base + \$offset) % 26; // add indices and wrap around 26 \$out .= chr(65 + \$ascii); // add 65 to indices to display ASCII } return \$out; }```

``` function decrypt(\$str,\$key) { \$out = ""; for (\$i=0; \$i<strlen(\$str); \$i++) { \$base = ord(\$str[\$i]) - 65; // take index of base string \$offset = ord(\$key[\$i]) - 65; // take index of key // Perform reverse "wrapping" \$ascii = (\$base - \$offset); if (\$ascii < 0) \$ascii = 26 + \$ascii; ```

``` \$out .= chr(65 + \$ascii); // add 65 to indices to display ASCII } return \$out; } ```

Here’s a quick PHP Solution:

```function encrypt(\$str, \$key)
{
\$out = "";
for (\$i=0; \$i<strlen(\$str); \$i++)
{
\$base = ord(\$str[\$i]) - 65;	  // take index of base string
\$offset = ord(\$key[\$i]) - 65;	  // take index of key
\$ascii = (\$base + \$offset) % 26;  // add indices and wrap around 26
\$out .= chr(65 + \$ascii);	  // add 65 to indices to display ASCII
}
return \$out;
}

function decrypt(\$str,\$key)
{
\$out = "";
for (\$i=0; \$i<strlen(\$str); \$i++)
{
\$base = ord(\$str[\$i]) - 65;	// take index of base string
\$offset = ord(\$key[\$i]) - 65;   // take index of key

// Perform reverse "wrapping"
\$ascii = (\$base - \$offset);
if (\$ascii < 0) \$ascii = 26 + \$ascii;

\$out .= chr(65 + \$ascii);	// add 65 to indices to display ASCII
}
return \$out;
}
```
8. [...] programming puzzles from time to time. I’m also going to try work these problems using Perl. Today’s assignment is to make a simple Autokey Cipher, which I accomplished over my lunch [...]

9. agilefall said

Here is a scala version:

class Crypt(key: String) {
private def convert(s: String, converter: (Char, Char)=>Int) = {
new String(
(0 until plain.length).map(
ix => (converter(s(ix),key(ix % key.length)) % 26 + ‘A’).toChar
).toArray)
}

def encrypt(plain: String) = convert(plain, (a: Char, b: Char)=> a + b)
def decrypt(encrypted: String) = convert(encrypted, (a: Char, b: Char) => a - b + 26)
}

10. gramie said

> invented by Blaise de VigenĂ¨re in 1586, over five hundred years ago

Wow, I really must have overslept this morning! I could have sworn it was only 2009!

11. programmingpraxis said

Fixed!

12. Adam Thomas said
```/*
* Obtaining the encrypted character from the dictionary:
* a - plain text character
* b - cipher key character
* x - first character in dictionary ('A')
* z - size of dictionary (26)
*
* y = x + (a + b - 2 * x) % z
*/
char* encrypt(const char *txt, const char* key, char *enc)
{
unsigned i, len;
for (i = 0, len = strlen(txt); i < len; i++) {
enc[i] = 'A' + (txt[i] + key[i] - 2 * 'A') % 26;
}
return enc;
}

/*
* Obtaining the decrypted character from the dictionary:
* a - encrypted character
* b - cipher key character
* x - first character in dictionary ('A')
* z - size of dictionary (26)
*
* y = x + (a - b + z) % z
*/
char* decrypt(const char *enc, const char *key, char *dec)
{
unsigned i, len;
for (i = 0, len = strlen(enc); i < len; i++) {
dec[i] = 'A' + (enc[i] - key[i] + 26) % 26;
}
return dec;
}
```
13. Adam Thomas said

The solution I posted above is implemented in C.