Ron’s Cipher #4

September 4, 2009

Our solution follows the pseudocode closely. Here is the code that initializes the pseudo-random byte generator; the first do initializes K[i] to i, and the second do mixes the key with the K-bytes:

(define (rc4-init key)
  (let ((kvec (make-vector 256)) (klen (string-length key)) (j 0))
    (do ((i 0 (+ i 1))) ((= i 256)) (vector-set! kvec i i))
    (do ((i 0 (+ i 1))) ((= i 256) kvec)
      (set! j (modulo (+ j (vector-ref kvec i)
                (char->integer (string-ref key (modulo i klen)))) 256))
      (let ((t (vector-ref kvec i)))
        (vector-set! kvec i (vector-ref kvec j))
        (vector-set! kvec j t)))))

Rc4-stream creates a function that returns the next pseudo-random byte in the stream each time it is called:

(define (rc4-stream key)
  (let ((i 0) (j 0) (kvec (rc4-init key)))
    (lambda ()
      (set! i (modulo (+ i 1) 256))
      (set! j (modulo (+ j (vector-ref kvec i)) 256))
      (let ((t (vector-ref kvec j)))
        (vector-set! kvec j (vector-ref kvec i))
        (vector-set! kvec i t))
      (vector-ref kvec (modulo (+ (vector-ref kvec i) (vector-ref kvec j)) 256)))))

Finally, rc4-cipher performs the encryption or decryption:

(define (rc4-cipher key text)
  (let ((rc4 (rc4-stream key)))
    (let loop ((ts (map char->integer (string->list text))) (zs '()))
      (if (null? ts) (list->string (map integer->char (reverse zs)))
        (loop (cdr ts) (cons (logxor (rc4) (car ts)) zs))))))

Logxor is provided by most Scheme systems; if it’s not in yours, it is available from the Standard Prelude. Here’s a sample run:

> (rc4-cipher "SAVVY"
    (rc4-cipher "SAVVY"
      "PROGRAMMING PRAXIS"))
"PROGRAMMING PRAXIS"
> (map char->integer
    (string->list
      (rc4-cipher "SAVVY"
        "PROGRAMMING PRAXIS")))
(244 115 158 222 204 154 68 152 118 218 148 16 167 15 3 142 36 15)

You can run the program yourself at http://programmingpraxis.codepad.org/pQc8OwsW.

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

%d bloggers like this: