Programming Praxis

Affine-Shift Cipher

December 15, 2009 9:00 AM

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(x − b) 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.

Posted by programmingpraxis

Categories: Exercises

Tags:

« Older Newer »

8 Responses to “Affine-Shift Cipher”

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()

By Jaime on December 15, 2009 at 11:55 AM

[…] 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 […]

By Programming Praxis – Affine-Shift Cipher « Bonsai Code on December 15, 2009 at 12:47 PM

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

By Remco Niemeijer on December 15, 2009 at 12:48 PM

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

By Axioplase on December 17, 2009 at 2:16 AM
@ 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]…

By Axioplase on December 17, 2009 at 2:21 AM
Duh, with a = 12, my code is never going to work, since it’s got no inverse… Rather use, say, 11…

By Axio on December 17, 2009 at 3:34 AM

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

By Remco Niemeijer on December 17, 2009 at 9:53 AM

#!/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

By Graham on May 21, 2011 at 3:29 AM

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.

Programming Praxis

Affine-Shift Cipher

Share this:

Related

8 Responses to “Affine-Shift Cipher”

Leave a Reply