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.

Posted by programmingpraxis

Filed in Exercises

8 Comments »

8 Responses to “Affine-Shift Cipher”

Jaime said

December 15, 2009 at 11:55 AM

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

Programming Praxis – Affine-Shift Cipher « Bonsai Code said
December 15, 2009 at 12:47 PM
[…] 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 […]

Remco Niemeijer said

December 15, 2009 at 12:48 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))

Axioplase said
December 17, 2009 at 2:16 AM
;; 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)
Axioplase said
December 17, 2009 at 2:21 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]…
Axio said
December 17, 2009 at 3:34 AM
Duh, with a = 12, my code is never going to work, since it’s got no inverse… Rather use, say, 11…

Remco Niemeijer said

December 17, 2009 at 9:53 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))

Graham said

May 21, 2011 at 3:29 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

Programming Praxis