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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
5 Comments »

5 Responses to “Ron’s Cipher #4”

  1. Programming Praxis – Ron’s Cipher #4 « Bonsai Code said
    September 4, 2009 at 7:32 PM

    […] 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
    September 4, 2009 at 7:32 PM

    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'
  4. VaporWarning» Blog Archive » Learning Python by example: RC4 said
    September 21, 2009 at 5:54 AM

    […] in point, I’ll use the recent kata from Programming Praxis for this Python exercise, as they provide straightforward pseudocode. Here’s the encryption […]

  5. RC40 | Programming Praxis said
    March 7, 2017 at 9:01 AM

    […] consecutive shift characters enter or leave caps-lock mode. Otherwise, RC40 is exactly the same as RC4, except that all references to 256 are changed to […]

Leave a comment