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.

About these ads

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

    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))
    
  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 [26]…

  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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: