Ron’s Cipher #4

September 4, 2009

RC4 is a stream cipher, similar to the Blum Blum Shub cipher of an earlier exercise, invented by Ron Rivest in 1987. RC4 provides encryption for the SSL protocol that permits secure internet connections and the WEP protocol that secures wireless networks.

RC4 works by using a key to initialize a 256-byte array, which then forms the basis of a pseudo-random byte generator. The stream of random bytes is xor’ed with plaintext to produce ciphertext; decryption is performed by xor’ing the same stream of random bytes with the ciphertext to produce plaintext.

The key array K is initialized like this:

for i from 0 to 255
    K[i] := i

j := 0

for i from 0 to 255
    j := (j + K[i] + key[i mod klen]) mod 256
    swap K[i], K[j]

Once the key array is initialized, the pseudo-random byte generator uses a similar calculation to build the stream of random bytes:

i := 0
j := 0

start:
    i := (i + 1) mod 256
    j := (j + K[i]) mod 256
    swap K[i], K[j]
    output K[ (K[i] + K[j]) mod 256 ]
    goto start

Your task is to write a function that takes a key and a text and produces the corresponding output text; the same function can be used for both encryption and decryption. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

4 Responses to “Ron’s Cipher #4”

  1. [...] Praxis – Ron’s Cipher #4 By Remco Niemeijer In today’s Programming Praxis problem, we have to implement the RC4 cipher, which is often used in protocols [...]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2009/09/04/programming-praxis-ron%E2%80%99s-cipher-4/ for a version with comments):

    import Data.Bits
    import Data.Char
    import Data.IntMap ((!), fromList, insert, size, IntMap)
    
    swap :: Int -> Int -> IntMap a -> IntMap a
    swap i j a = insert j (a ! i) $ insert i (a ! j) a
    
    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]
      
    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'
    
  3. [...] in point, I’ll use the recent kata from Programming Praxis for this Python exercise, as they provide straightforward pseudocode. Here’s the encryption [...]

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

%d bloggers like this: