## Blum Blum Shub

### August 18, 2009

A stream cipher takes its input one plaintext character at a time, producing the corresponding ciphertext character before it moves on to the next plaintext character. An easy way to do this is to seed a pseudo-random number generator and xor its output with the stream of plaintext characters; because of the xor, decryption is the exact same operation as encryption. The pseudo-random number generator must be crypographically secure; such common pseudo-random number generators as linear congruential, lagged fibonacci, and mersenne twister all fail due to serial correlation between successive values.

A simple pseudo-random number generator that is cryptographically secure is known as Blum Blum Shub, after its three inventors. Successive values are computed as the least-significant bit (or bits) of the number xk = xk-12 (mod n). The parameter n is the product of two large primes p and q, each congruent to 3 modulo 4. The initial value x0 is calculated as s2 (mod n), where s is the seed, which must be coprime to n.

Your task is to write a function that enciphers and deciphers a stream of characters as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

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