## Autokey

### December 4, 2009

We begin with functions to add and subtract a key letter from a text letter, using modulo-26 arithmetic:

```(define (plus a b)   (define (f a) (- (char->integer (char-upcase a)) 65))   (integer->char (+ (modulo (+ (f a) (f b)) 26) 65)))```

```(define (minus a b)   (define (f a) (- (char->integer (char-upcase a)) 65))   (integer->char (+ (modulo (- (f a) (f b)) 26) 65)))```

The `clean` function strips non-letters from the input text; it uses `filter` from the Standard Prelude:

```(define (clean text)   (list->string     (filter char-alphabetic?       (string->list text))))```

To encipher a plain-text, the text is appended to the key, then we iterate through the plain-text, adding key and text, until we reach the end of the text:

```(define (encipher key text)   (let ((text (clean text)))     (let loop ((ks (string->list (string-append key text)))                (ts (string->list text)) (cs '()))       (if (null? ts)           (list->string (reverse cs))           (let ((c (plus (car ts) (car ks))))             (loop (cdr ks) (cdr ts) (cons c cs)))))))```

The inverse operation is a little bit harder, because we can only add another letter to the key after the letter in the shifted-left position has been deciphered:

```(define (decipher key text)   (let loop ((ks (string->list key)) (ts (string->list text)) (cs '()))     (if (null? ts)         (list->string (reverse cs))         (let ((c (minus (car ts) (car ks))))           (loop (append (cdr ks) (list c)) (cdr ts) (cons c cs))))))```

Here’s an example, which you can run for yourself at http://programmingpraxis.codepad.org/Re3dl3Q7:

There are many variations on the standard autokey cipher. De Vigenère himself used single-letter keys. The Blum Blum Shub and RC4 ciphers that we have examined in previous exercises are types of autokey ciphers in which later elements of the key depend on earlier elements of the key rather than on earlier elements of the message. In the extreme case, the Vernam cipher uses a key that is the same length as the plain-text; this is the “one-time pad” that spies always use in movies, and is theoretically unbreakable, though the difficulty of synchronizing keys between sender and recipient makes it impractical for use by real spies.

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

```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!

```/*
* 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;
}
```