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.
Programming Praxis 
[…] Praxis – Autokey By Remco Niemeijer In today’s Programming Praxis we have another cipher algorithm. Let’s get […]
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) msgWhat 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.
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.
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; }[…] 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 […]
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)
}
> 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!
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; }The solution I posted above is implemented in C.