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

Posted by programmingpraxis
Filed in Exercises
10 Comments »

10 Responses to “Blum Blum Shub”

  1. Programming Praxis – Blum Blum Shub « Bonsai Code said
    August 18, 2009 at 1:23 PM

    […] 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
    August 18, 2009 at 1:24 PM

    My Haskell solution (see http://bonsaicode.wordpress.com/2009/08/18/programming-praxis-blum-blum-shub/ 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
    August 18, 2009 at 5:12 PM

    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
    August 22, 2009 at 10:37 PM

    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. » First clojure code Elements of the Life Programmatic said
    August 23, 2009 at 12:24 AM

    […] 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
    June 1, 2011 at 8:44 PM

    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. One-Time Pad | Programming Praxis said
    January 9, 2015 at 9:00 AM

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

  9. Random Number Test | Programming Praxis said
    July 7, 2017 at 9:01 AM

    […] 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 comment