## Blum Blum Shub

### August 18, 2009

Function `make-blum-blum-shub`

takes a parameter *n* and a seed *s* and returns a function that, when called, returns the next number in the requested pseudo-random sequence, using the eight least-significant bits:

`(define (make-blum-blum-shub n s)`

(let ((s s))

(lambda ()

(set! s (modulo (* s s) n))

(modulo s 256))))

For instance, given *p* = 983 and *q* = 991 and a seed *s* = 17, the pseudo-random sequence is 33, 65, 201, 32, 30, 107, 36, 248, 246, 64, 26, 49, 21, 167, 126, 145, ….

Enciphering a string involves converting each character to an integer, performing the xor operation, then converting back to a character; deciphering is exactly the same as enciphering:

`(define (encipher n s plain-text)`

(let ((bbs (make-blum-blum-shub n s)))

(let loop ((ps (string->list plain-text)) (cs '()))

(if (null? ps)

(list->string (reverse cs))

(loop (cdr ps) (cons (integer->char

(logxor (bbs) (char->integer (car ps)))) cs))))))

`(define decipher encipher)`

`Logxor`

is part of the R6RS Scheme standard, under the name bitwise-xor, but not of any earlier RnRS standards. If your Scheme system doesn’t provide it, you can use SRFI-60 or build a simple `logxor`

yourself, using digits and undigits from the Standard Prelude:

`(define (logxor x y)`

(let loop ((x (reverse (digits x 2))) (y (reverse (digits y 2))) (z '()))

(cond ((and (null? x) (null? y)) (undigits z 2))

((and (null? x) (zero? (car y))) (loop x (cdr y) (cons 0 z)))

((null? x) (loop x (cdr y) (cons 1 z)))

((and (null? y) (zero? (car x))) (loop (cdr x) y (cons 0 z)))

((null? y) (loop (cdr x) y (cons 1 z)))

((= (car x) (car y)) (loop (cdr x) (cdr y) (cons 0 z)))

(else (loop (cdr x) (cdr y) (cons 1 z))))))

Enciphering and deciphering work as expected, but the ciphertext is unprintable; you can see the program run at http://programmingpraxis.codepad.org/CXQsxZ1f:

`> (decipher 974153 17`

(encipher 974153 17 "PROGRAMMING PRAXIS"))

"PROGRAMMING PRAXIS"

> (map (char->integer (string->list

(encipher 974153 17 "PROGRAMMING PRAXIS"))))

(113 19 134 103 76 42 105 181 191 14

93 17 69 245 63 201 240 71)

The security of Blum Blum Shub relies on the difficulty of factoring *n*. If *p* and *q* are known, there is a known technique of number theory that can recover the pseudo-random sequence, making a known-plaintext attack simple. If you are interested in the math, search the internet for “blum blum shub cryptanalysis.” In practice, *p* and *q* are much larger than we have shown here, at least a hundred digits each.

Pages: 1 2

[…] Praxis – Blum Blum Shub By Remco Niemeijer In today’s Programming Praxis problem we have to implement a stream cipher based on the Blum Blum Shub method. […]

My Haskell solution (see http://bonsaicode.wordpress.com/2009/08/18/programming-praxis-blum-blum-shub/ for a version with comments):

def blum_blum_shub(n, s):

while True:

s = s**2 % n

yield int(s % 256)

def encypher(n, s, text):

bbs = blum_blum_shub(n, s)

return [ord(c)^bbs.next() for c in text]

def decypher (n, s, lst):

bbs = blum_blum_shub(n, s)

return ”.join([chr(i^bbs.next()) for i in lst])

decypher(974153, 17, encypher (974153, 17, “PROGRAMMING PRAXIS”))

a clojure solution:

(defn bbs

([n s]

(iterate

(fn [x] (rem (rem n (* x x)) 256))

(rem (rem n (* s s)) 256))))

(defn stream-cipher

([text n s]

(let [sequence (if (= (class text) java.lang.String) (seq text) text)]

(map (fn [x y] (char (bit-xor (int x) (int y)))) sequence (bbs n s))))

([text]

(stream-cipher text (* 199967 199999) (- (* 199967 199999) 1)))))

[…] that I would get into clojure for some time, and i finally got around to doing a programming praxis exercise in clojure. Basically, it consists of creating a sequence of pseudo-random numbers, and […]

Late to the party, but here we go:

[…] a hardware guy I suggest the Blum-Blum-Shub cryptographically-secure random number generator of a previous exercise. The second is a way to convert bits to letters. The method we choose is to take 26 consecutive […]