Posts Tagged ‘shift’

Programming Praxis – Affine-Shift Cipher

December 15, 2009

In today’s Programming Praxis we have to implement the Affine-Shift Cipher. Let’s get going, shall we?

A quick import:

import Data.Char

Since both encoding an decoding have roughly the same structure, we’re going to abstract that out into a function.

convert :: (Int -> Int) -> String -> String
convert f = map (chr . (\i -> f (i - 65) `mod` 26 + 65) . ord . toUpper)

For decoding, we need to calculate the modular inverse of a number.

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)

Encoding and decoding is then simply a case of calling the convert function with the correct argument.

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

All that’s left to do is test if everything works correctly.

main :: IO ()
main = do print $ encode 5 8 "BONSAICODE" == "NAVUIWSAXC"
          print $ decode 5 8 "NAVUIWSAXC" == "BONSAICODE"

All clear.