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.
[…] 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 […]
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'[…] […]
[…] in point, I’ll use the recent kata from Programming Praxis for this Python exercise, as they provide straightforward pseudocode. Here’s the encryption […]
[…] 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 […]