Blum Blum Shub
August 18, 2009
Function make-blum-blum-shub takes a parameter n and a seed s and returns a function that, when called, returns the next number in the requested pseudo-random sequence, using the eight least-significant bits:
(define (make-blum-blum-shub n s)
(let ((s s))
(lambda ()
(set! s (modulo (* s s) n))
(modulo s 256))))
For instance, given p = 983 and q = 991 and a seed s = 17, the pseudo-random sequence is 33, 65, 201, 32, 30, 107, 36, 248, 246, 64, 26, 49, 21, 167, 126, 145, ….
Enciphering a string involves converting each character to an integer, performing the xor operation, then converting back to a character; deciphering is exactly the same as enciphering:
(define (encipher n s plain-text)
(let ((bbs (make-blum-blum-shub n s)))
(let loop ((ps (string->list plain-text)) (cs '()))
(if (null? ps)
(list->string (reverse cs))
(loop (cdr ps) (cons (integer->char
(logxor (bbs) (char->integer (car ps)))) cs))))))
(define decipher encipher)
Logxor is part of the R6RS Scheme standard, under the name bitwise-xor, but not of any earlier RnRS standards. If your Scheme system doesn’t provide it, you can use SRFI-60 or build a simple logxor yourself, using digits and undigits from the Standard Prelude:
(define (logxor x y)
(let loop ((x (reverse (digits x 2))) (y (reverse (digits y 2))) (z '()))
(cond ((and (null? x) (null? y)) (undigits z 2))
((and (null? x) (zero? (car y))) (loop x (cdr y) (cons 0 z)))
((null? x) (loop x (cdr y) (cons 1 z)))
((and (null? y) (zero? (car x))) (loop (cdr x) y (cons 0 z)))
((null? y) (loop (cdr x) y (cons 1 z)))
((= (car x) (car y)) (loop (cdr x) (cdr y) (cons 0 z)))
(else (loop (cdr x) (cdr y) (cons 1 z))))))
Enciphering and deciphering work as expected, but the ciphertext is unprintable; you can see the program run at http://programmingpraxis.codepad.org/CXQsxZ1f:
> (decipher 974153 17
(encipher 974153 17 "PROGRAMMING PRAXIS"))
"PROGRAMMING PRAXIS"
> (map (char->integer (string->list
(encipher 974153 17 "PROGRAMMING PRAXIS"))))
(113 19 134 103 76 42 105 181 191 14
93 17 69 245 63 201 240 71)
The security of Blum Blum Shub relies on the difficulty of factoring n. If p and q are known, there is a known technique of number theory that can recover the pseudo-random sequence, making a known-plaintext attack simple. If you are interested in the math, search the internet for “blum blum shub cryptanalysis.” In practice, p and q are much larger than we have shown here, at least a hundred digits each.
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