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.

About these ads

Pages: 1 2

6 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 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. 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)
    

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: