Programming Praxis - Ron’s Cipher #4

In today’s Programming Praxis problem, we have to implement the RC4 cipher, which is often used in protocols such as SSL and WEP. Let’s have a go, shall we?

First, some imports:

import Data.Bits
import Data.Char
import Data.IntMap ((!), fromList, insert, size, IntMap)

In this algorithm we’re going to have to swap two elements of a list twice, so let’s make a function for it. In order to speed this operation up, we’re going to use IntMaps instead of plain lists.

swap :: Int -> Int -> IntMap a -> IntMap a
swap i j a = insert j (a ! i) $ insert i (a ! j) a

The algorithm consists of two steps. The first step is to create a list of 256 integers based on the key.

rc4init :: IntMap Char -> IntMap Int
rc4init key = snd $ foldl (\(j, a) i ->
    let j' = mod (j + a ! i + ord (key ! mod i (size key))) 256
    in (j', swap i j' a)) (0, s) [0..255] where
    s = fromList $ zip [0..] [0..255]

In the second step, we create a stream of characters based on the result of step 1, which is xor’ed with the input string.

rc4 :: String -> String -> String
rc4 key = map chr . zipWith xor (stream key) . map ord where
    stream = s 0 0 . rc4init . fromList . zip [0..]
    s i' j' k' = k ! (mod (k ! i + k ! j) 256) : s i j k where
                 i = mod (i' + 1) 256
                 j = mod (j' + k' ! i) 256
                 k = swap i j k'

Let’s see if that works correctly:

main :: IO ()
main = do print $ rc4 "Kata" "Bonsai Code"
          print . rc4 "Kata" $ rc4 "Kata" "Bonsai Code"

Yup. 11 lines, not too shabby.

About these ads

Tags: bonsai, cipher, code, Haskell, kata, praxis, programming, rc4, ron's, ssl, wep