Programming Praxis – Blum Blum Shub

In today’s Programming Praxis problem we have to implement a stream cipher based on the Blum Blum Shub method. Let’s get started.

First our imports:

import Data.Bits
import Data.Char

This is our random number generator. I’m using the least significant 3 bits instead of just one because it scrambles the original message a bit more.

rng :: Int -> Int -> [Int]
rng m = map (.&. 7) . tail . iterate (\n -> mod (n ^ 2) m)

Encoding or decoding is a simple matter of xor’ing the message and the random number stream.

cipher :: Int -> Int -> Int -> String -> String
cipher s p q = map chr . zipWith xor (rng (p * q) s) . map ord

And that’s all there is to it. Let’s see if it works:

main :: IO ()
main = do print $ cipher 3 11 19 "Bonsai Code"
          print . cipher 3 11 19 $ cipher 3 11 19 "Bonsai Code"

Seems to work just fine. Not bad for just two lines of code.