Programming Praxis – Affine-Shift Cipher

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.

About these ads

Tags: , , , , , , , ,

2 Responses to “Programming Praxis – Affine-Shift Cipher”

  1. Axioplase Says:

    I’m afraid your code doesn’t work as exected.
    Your inverse function is wrong… (see comment@programmingpraxis)

    Try with a=7 and see…

    Cheers.

  2. Remco Niemeijer Says:

    Whoops. Fixed it, thanks.

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 35 other followers

%d bloggers like this: