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.

About these ads

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)
    
  6. Gierad said

    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;
    }

  7. Gierad said

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: