extra/random/blum-blum-shub/blum-blum-shub.factor

   1 USING: kernel math sequences namespaces
   2 math.miller-rabin combinators.lib
   3 math.functions accessors random ;
   4 IN: random.blum-blum-shub
   5
   6 ! TODO: take (log log M) bits instead of 1 bit
   7 ! Blum Blum Shub, M = pq
   8 TUPLE: blum-blum-shub x n ;
   9
  10 C: <blum-blum-shub> blum-blum-shub
  11
  12 : generate-bbs-primes ( numbits -- p q )
  13     #! two primes congruent to 3 (mod 4)
  14     [ [ random-prime ] curry [ 4 mod 3 = ] generate ] dup bi ;
  15
  16 IN: crypto
  17 : <blum-blum-shub> ( numbits -- blum-blum-shub )
  18     #! returns a Blum-Blum-Shub tuple
  19     generate-bbs-primes *
  20     [ find-relative-prime ] keep
  21     blum-blum-shub construct-boa ;
  22
  23 ! 256 make-bbs blum-blum-shub set-global
  24
  25 : next-bbs-bit ( bbs -- bit )
  26     #! x = x^2 mod n, return low bit of calculated x
  27     [ [ x>> 2 ] [ n>> ] bi ^mod ]
  28     [ [ >>x ] keep x>> 1 bitand ] bi ;
  29
  30 IN: crypto
  31 ! : random ( n -- n )
  32     ! ! #! Cryptographically secure random number using Blum-Blum-Shub 256
  33     ! [ log2 1+ random-bits ] keep dupd >= [ -1 shift ] when ;
  34
  35 M: blum-blum-shub random-32* ( bbs -- r )
  36     ;