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(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.
Programming Praxis 
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()[…] 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 […]
My Haskell solution (see http://bonsaicode.wordpress.com/2009/12/15/programming-praxis-affine-shift-cipher/ for a version with comments):
;; 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)
@ 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]…
Duh, with a = 12, my code is never going to work, since it’s got no inverse… Rather use, say, 11…
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))#!/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