Affine-Shift Cipher

December 15, 2009

The affine-shift cipher is simple but cryptographically weak. It works by mapping the twenty-six letters of the alphabet onto the integers 0 through 25, then applying the function (ax + b) mod 26 to each character in turn, finally mapping back from integers to letters. The key is formed by the numbers a and b. Decryption is the inverse operation, a-1(xb) mod 26, where a-1 is the modular inverse of a modulo m; this means that a and m must be coprime. For instance, the plain-text PROGRAMMINGPRAXIS is enciphered with a=5 and b=8 as FPAMPIQQWVMFPITWU, and deciphered with 21 as the modular inverse.

Your task is to write functions to encipher and decipher messages using the affine-shift cipher. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

8 Responses to “Affine-Shift Cipher”

  1. Jaime said

    A solution in Python

    LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    VALUES = dict(zip(LETTERS, range(len(LETTERS))))
    RVALUES = dict(zip(range(len(LETTERS)), LETTERS))
    
    def find_coprime(a):
        """
        >>> find_coprime( 5 )
        21
        >>> find_coprime( 21 )
        5
    
        """
        for i in range(26):
            if ((i * a) % 26) == 1:
                return i
            
        #Raise an error
        raise Exception, "The codeword %d has not a coprime, try another" % a
    
    def encode_affine(msg, a, b):
        """
        >>> encode_affine('PROGRAMMINGPRAXIS', 5, 8)
        'FPAMPIQQWVMFPITWU'
        """
        
        #Code to numbers
        encoded_message = [ RVALUES[(a * VALUES[i] + b) % 26] for i in msg ]
            
        return ''.join(encoded_message)
    
    
    def decode_affine(msg, a, b):
        """
        >>> decode_affine('FPAMPIQQWVMFPITWU', 5, 8)
        'PROGRAMMINGPRAXIS'
        """
        #Inverse of the modulo
        m = find_coprime(a)
        
        decoded_message = [ RVALUES[(m * (VALUES[i] - b)) % 26] for i in msg ]
        
        return ''.join(decoded_message)
    
    
    if __name__ == '__main__':    
        import doctest
        doctest.testmod()
    
  2. [...] Praxis – Affine-Shift Cipher By Remco Niemeijer In today’s Programming Praxis we have to implement the Affine-Shift Cipher. Let’s get going, shall [...]

  3. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2009/12/15/programming-praxis-affine-shift-cipher/ for a version with comments):

    import Data.Char
    
    convert :: (Int -> Int) -> String -> String
    convert f = map (chr . (\i -> f (i - 65) `mod` 26 + 65) . ord . toUpper)
    
    encode :: Int -> Int -> String -> String
    encode a b = convert (\i -> a*i + b)
    
    decode :: Int -> Int -> String -> String
    decode a b = convert (\i -> (26-a) * (i-b))
    
  4. Axioplase said

    ;; My CL is rusty, so design may be over suboptimal
    ;; But, the hell, it works :)

    (defun str->ints (str)
    (loop for c across str
    collect (- (char-code (char-upcase c)) 65)))

    (defun ints->str (ints)
    (concatenate ‘string
    (loop for i in ints
    collect (code-char (+ i 65)))))

    (defun inv (n m)
    (loop for i from 0 to m
    when (= 1 (mod (* n i) m))
    do (return i)))

    (defun cypher (str a b)
    (let* ((li (str->ints str))
    (li2 (mapcar
    (lambda (x) (mod (+ (* a x) b) 26))
    li)))
    (ints->str li2)))

    (defun decypher (str a b)
    (let* ((li (str->ints str))
    (li2 (mapcar
    (lambda (x) (mod (* (inv a 26) (- x b)) 26))
    li)))
    (ints->str li2)))

    (defvar a 12)
    (defvar b 23)
    (decypher (cypher “programmingpraxis” a b) a b)

  5. Axioplase said

    @ Remko: I’m afraid your notion of “inverse” is wrong.
    21 happens to be 5′s inverse mod 26 as well as 26-5, but we’re looking for a^-1 so that a*a^-1=1 [26]…

  6. Axio said

    Duh, with a = 12, my code is never going to work, since it’s got no inverse… Rather use, say, 11…

  7. Remco Niemeijer said

    Thanks to Axioplase for spotting the error in my algorithm. Here’s the correct version:

    import Data.Char
    
    convert :: (Int -> Int) -> String -> String
    convert f = map (chr . (\i -> f (i - 65) `mod` 26 + 65) . ord . toUpper)
    
    inverse :: Int -> Int -> Int
    inverse x n = f (mod x n) 1 where
        f 0 _ = error "Numbers not coprime"
        f 1 a = a
        f y a = let q = - div n y in f (n + q * y) (mod (q * a) n)
    
    encode :: Int -> Int -> String -> String
    encode a b = convert (\i -> a*i + b)
    
    decode :: Int -> Int -> String -> String
    decode a b = convert (\i -> inverse a 26 * (i-b))
    
  8. Graham said
    #!/usr/bin/env python
    
    def char_to_int(c):
        return ord(c) - 65
    
    def int_to_char(i):
        return chr(65 + i)
    
    def encipher(a, b, x):
        return (a * x + b) % 26
    
    def inv(a):
        return next(i for i in xrange(1, 26) if (i * a) % 26 == 1)
    
    def decipher(a, b, x):
        return (inv(a) * (x - b)) % 26
    
    def encrypt(p_text, a, b):
        return ''.join(int_to_char(encipher(a, b, char_to_int(p))) for p in p_text)
    
    def decrypt(c_text, a, b):
        return ''.join(int_to_char(decipher(a, b, char_to_int(c))) for c in c_text)
    
    if __name__ == "__main__":
        P_TEXT = "PROGRAMMINGPRAXIS"
        A, B = 5, 8
        C_TEXT = encrypt(P_TEXT, A, B)
        P_PRIME = decrypt(C_TEXT, A, B)
        print P_TEXT
        print C_TEXT
        print P_PRIME
    

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

%d bloggers like this: