Because my Common Lisp environment (CMUCL) doesn't come with a cryptographic pseudo-random number generator (PRNG), I have implemented Bob Jenkins's excellent ISAAC algorithm in ANSI standard Common Lisp.
Download it here: isaac.lisp.
;; isaac.lisp (C) May 2008 Doug Hoyte, HCSW
;; BSD license: you can do anything you want with it (but no warranty).
;;
;; Optimised Common Lisp implementation of Bob Jenkins' ISAAC-32 Algorithm:
;; Indirection, Shift, Accumulate, Add, and Count. More details and
;; the C reference implementations can be found here:
;;
;; ISAAC: a fast cryptographic random number generator
;; http://burtleburtle.net/bob/rand/isaacafa.html
;;
;; This lisp implementation is roughly as fast as Jenkins' optimised rand.c
;; when compiled with a good native-code lisp compiler. It also performs
;; well when byte-code compiled.
;;
;;
;; USAGE:
;;
;; First, create an isaac context. There are three functions that do this:
;;
;; isaac:init-kernel-seed =>
;; *RECOMMENDED* Seeds with values from /dev/arandom on BSD
;; or /dev/urandom on Linux. Reads 1024 bytes from the device.
;;
;; isaac:init-common-lisp-random-seed =>
;; Seeds with values from your Common Lisp implementation's
;; random function. Consumes 256 32-bit values from #'random.
;;
;; isaac:init-null-seed =>
;; Seeds with all 0s. Always results in the same stream.
;; For comparing with Jenkins' reference implementations.
;;
;; These are functions you can pass an isaac context to. They will modify
;; the isaac context and return a random value:
;;
;; isaac:rand32 =>
;; Uses the ISAAC-32 algorithm to generate a new random value.
;;
;; isaac:rand-bits =>
;; Uses the ISAAC-32 algorithm to generate random values between
;; 0 and (1- (expt 2 N)). This function always consumes one or more
;; ISAAC-32 words. Note that the N parameter is different from
;; the CL random function parameter. Examples:
;; (isaac:rand-bits ctx 1) => [0,1] (consumes 1 ISAAC-32 word)
;; (isaac:rand-bits ctx 2) => [0,1,2,3] (ditto)
;; (isaac:rand-bits ctx 3) => [0,1,2,3,4,5,6,7] (ditto)
;; (isaac:rand-bits ctx 32) => [0,1,...,(1- (expt 2 32))] (ditto)
;; (isaac:rand-bits ctx 33) => [0,1,...,(1- (expt 2 33))] (consumes 2 words)
;; (isaac:rand-bits ctx 512) => [0,1,...,(1- (expt 2 512))] (consumes 16 words)
;;
;;
;; QUICK RECIPE:
;;
;; Generate a 128-bit session ID as a 0-padded hexadecimal string:
;; (compile-file "isaac.lisp")
;; (load "isaac")
;; (defvar my-isaac-ctx (isaac:init-kernel-seed))
;; (format nil "~32,'0x" (isaac:rand-bits my-isaac-ctx 128))
;; => "078585213B0EF01B1B9BECB291EF38F0"
;;
;;
;; FAQ:
;; Q) My Common Lisp implementation already uses the Mersenne Twister,
;; what are the advantages of ISAAC?
;;
;; A1) The Mersenne Twister is not a cryptographic PRNG. This means that it
;; is possible for someone to predict future values based on previously
;; observed values (just over 600 of them). As such, MT is particularly
;; undesirable for things like web session IDs. You can still use MT for
;; crypto, but you must use a cryptographic hash function on the MT output.
;; A2) isaac.lisp appears to be roughly as fast as the Mersenne Twister #'random
;; of CMUCL 19d on x86 before even considering the above-mentioned hash
;; function overhead requirement of MT.
;; A3) isaac.lisp is not implemented as an x86 VOP like CMUCL's Mersenne
;; Twister, but instead in 100% standard ANSI Common Lisp (except for the
;; kernel seed interface). This should mean comparable performance on all
;; architectures targetted by your lisp compiler. The non-x86 MT
;; implementation is apparently an order-of-magnitude slower.
;;
;; Q) How "random" can I expect these values to be?
;;
;; A) Very. From Bob Jenkins' website: "Cycles are guaranteed to be at least
;; (expt 2 40) values long, and they are (expt 2 8295) values long on
;; average. The results are uniformly distributed, unbiased, and unpredictable
;; unless you know the seed. [...] Why not use RC4? RC4 is three times slower,
;; more biased, has a shorter minimum and average cycle length, and is
;; proprietary. No way is known to break either RC4 or ISAAC; both are immune
;; to Gaussian elimination."
;;
;; Note that there is a $1000 prize you can win from Jenkins if you find
;; a flaw in ISAAC (but all flaws in isaac.lisp are of course mine).
Once again, here's the link: isaac.lisp.
|