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.

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 632 other followers

%d bloggers like this: