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.