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

A solution in Python

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