## 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 *x _{k}* =

*x*

_{k-1}

^{2}(mod

*n*). The parameter

*n*is the product of two large primes

*p*and

*q*, each congruent to 3 modulo 4. The initial value

*x*

_{0}is calculated as

*s*

^{2}(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

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

My Haskell solution (see http://bonsaicode.wordpress.com/2009/08/18/programming-praxis-blum-blum-shub/ for a version with comments):

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

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

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

Late to the party, but here we go:

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