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):
[…] […]
[…] 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 […]