## Affine-Shift Cipher

### December 15, 2009

We begin with the function that map characters to integers, and its inverse:

```(define (c->int c)   (- (char->integer c) 65))```

```(define (int->c i)   (integer->char (+ i 65)))```

The functions that perform the affine shift are curried:

```(define (cipher a b)   (lambda (x)     (modulo (+ (* a x) b) 26)))```

```(define (plain a b)   (lambda (x)     (modulo (* (inverse a 26) (- x b)) 26)))```

The `mapping` function provides both encryption and decryption, depending on the function passed to it:

```(define (mapping func text)   (list->string     (map int->c       (map func         (map c->int           (string->list text))))))```

Then encryption and decryption are easy:

```(define (encipher a b text)   (mapping (cipher a b) text))```

```(define (decipher a b text)   (mapping (plain a b) text))```

We defined the modular inverse in previous exercises on modular arithmetic and elliptic curves:

```(define (inverse x n)   (let loop ((x (modulo x n)) (a 1))     (cond ((zero? x) (return #f))           ((= x 1) a)           (else (let ((q (- (quotient n x))))                   (loop (+ n (* q x)) (modulo (* q a) n)))))))```

The affine-shift cipher is cryptographically weak because the key space is very small. With an alphabet of twenty-six letters, there are 12 possibilities for the a parameter that are coprime to 26 (the odd numbers from 1 to 26, excluding 13), giving only 12 × 26 = 312 possible keys.

You can run the functions at http://programmingpraxis.codepad.org/uBwJCcEk.

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