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.
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.