## 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

### 10 Responses to “Blum Blum Shub”

1. […] 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. […]

2. Remco Niemeijer said

```import Data.Bits
import Data.Char

rng :: Int -> Int -> [Int]
rng m = map (.&. 7) . tail . iterate (\n -> mod (n ^ 2) m)

cipher :: Int -> Int -> Int -> String -> String
cipher s p q = map chr . zipWith xor (rng (p * q) s) . map ord

main :: IO ()
main = do print \$ cipher 3 11 19 "Bonsai Code"
print . cipher 3 11 19 \$ cipher 3 11 19 "Bonsai Code"
```
3. Lautaro Pecile said

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”))

4. pschorf said

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))))) ```

5. […] 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 […]

6. Graham said

Late to the party, but here we go:

```#!/usr/bin/env python

def bbs_gen(n, seed):
"""Blum Blum Shub PRNG"""
x = pow(seed, 2, n)
while True:
yield x % 256
x = pow(x, 2, n)

def xor_cipher(text, n, seed):
"""Uses Blum Blum Shub generator to en/decipher text via XOR"""
bbs = bbs_gen(n, seed)
return ''.join(chr(x) for x in (ord(t) ^ next(bbs) for t in text))

if __name__ == "__main__":
P, Q, S = 983, 991, 17
PLAIN = "PROGRAMMING PRAXIS"
CIPHER = xor_cipher(PLAIN, P * Q, S)
print CIPHER
print xor_cipher(CIPHER, P * Q, S)
```
7. […] 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 […]

8. […] built several random number generators: , , , , , , , ,  (I didn’t realize it was so many until I went back […]