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

> (decipher 974153 17
    (encipher 974153 17 "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

    My Haskell solution (see for a version with comments):

    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)^ for c in text]

    def decypher (n, s, lst):
    bbs = blum_blum_shub(n, s)
    return ”.join([chr(i^ for i in lst])

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

  4. pschorf said

    a clojure solution:

    (defn bbs
    ([n s]
    (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))))
    (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
        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: [1], [2], [3], [4], [5], [6], [7], [8], [9] (I didn’t realize it was so many until I went back […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: