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.
Programming Praxis 
[…] 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):
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"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:
#!/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)[…] 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 […]
Reinhardt http://2525.net/navi/rank.cgi?mode=link&id=1303&url=http%3A//2525.net/navi/rank.cgi%3Fmode%3Dlink%26id%3D1303%26url%3Dhttp%253A//22film.com/22home/link.php%253Furl%253Dhttp%253A//studentessay.info exams state at
[…] built several random number generators: [1], [2], [3], [4], [5], [6], [7], [8], [9] (I didn’t realize it was so many until I went back […]
https://socialkeko.com/ymadlihoff keylkassa garban 4b1f4b8a67