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.

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 635 other followers

%d bloggers like this: