## 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.

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

```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 …

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