``````#!/usr/bin/env perl
use strict;
use warnings;
use Math::GMP;
use Math::Prime::Util qw/:all/;
use Bytes::Random::Secure;
\$|=1;

# Example of Blum-Micali, Blum-Blum-Shub, and Micali-Schnorr CSPRNGs.
# Not very practical, but works as an example.

if (!@ARGV) {
die <<EOU;
Usage: \$0 <nbits> [<type>] [<bits>]

An example showing two classic CSPRNGs (cryptographically secure pseudorandom
number generators).  These are generally not used in practice for performance
reasons, with things like AES-CTR, ISAAC, Yarrow/Fortuna, or stream ciphers

<nbits>: how many bits should be generated.

<type>: one of:
"MS"  (Micali-Schnorr)       <- default
"BM"  (Blum-Micali)
"BBS" (Blum-Blum-Shub)

<bits>: How large of primes are used for P (BM) or P,Q (BBS,MS).  Default 512.
EOU
}

my \$nbits = shift || 10;
my \$type = shift || 'MS';  # BM or BBS or MS
my \$bits = shift;

die "Type must be BM, BBS, or MS" unless \$type =~ /^(BBS|BM|MS)\$/;
if (!defined \$bits) { \$bits = (\$type eq 'BBS') ? 4096 : 512; }
die "Bits must be > 64" unless \$bits > 64;

my \$rng = Bytes::Random::Secure->new(NonBlocking => 1);
my \$rbytes = int((\$bits+7)/8);

if (\$type eq 'BM') {
my(\$p, \$xn);
# Select P
do { \$p = 2 * Math::GMP->new(random_nbit_prime(\$bits-1))+1 } while !is_prime(\$p);
# Get generator
my \$g = Math::GMP->new(znprimroot(\$p));
do {  # Select the seed x0
\$xn = Math::GMP->new(\$rng->bytes_hex(\$rbytes), 16) % \$p;
} while \$xn <= 1;
# Generate bits
my \$thresh = Math::GMP::div_2exp_gmp(\$p-1, 1);
while (\$nbits-- > 0) {
\$xn = Math::GMP::powm_gmp(\$g, \$xn, \$p);
print 0 + (\$xn < \$thresh);
}
print "\n";
} elsif (\$type eq 'BBS') {
die "Blum-Blum-Shub must have bits >= 3500\n" unless \$bits >= 3500;
my(\$M,\$xn);
# Select M = p*q
while (1) {
my(\$p,\$q);
do { \$p = Math::GMP->new(random_nbit_prime(\$bits)); } while (\$p % 4) != 3;
do { \$q = Math::GMP->new(random_nbit_prime(\$bits)); } while (\$q % 4) != 3;
if (\$bits < 200) {
my \$gcd = gcd(euler_phi(\$p-1),euler_phi(\$q-1));
next if \$gcd > 10000;
}
\$M = \$p * \$q;
last;
}
do {  # Select the seed x0
\$xn = Math::GMP->new(\$rng->bytes_hex(\$rbytes), 16) % \$M;
} while \$xn <= 1 || gcd(\$xn,\$M) != 1;
# Generate bits
my \$two = Math::GMP->new(2);
while (\$nbits-- > 0) {
\$xn = Math::GMP::powm_gmp(\$xn, \$two, \$M);
print Math::GMP::gmp_tstbit(\$xn,0) ? "1" : "0";
}
print "\n";
} else {  # Micali-Schnorr
die "Micali-Schnorr must have bits >= 120\n" unless \$bits >= 120;
my \$tries = 1;
my (\$n, \$e, \$N);
while (1) {
my \$p = Math::GMP->new(random_nbit_prime(\$bits));
my \$q = Math::GMP->new(random_nbit_prime(\$bits));
\$n = \$p * \$q;
my \$phi = (\$p-1) * (\$q-1);
\$N = Math::GMP::sizeinbase_gmp(\$n, 2);
# For efficiency, choose largest e possible.  e will always be odd.
\$e = int(\$N/80);
\$e-- while \$e > 1 && gcd(\$e,\$phi) != 1;
last if \$e > 1 && \$e < \$phi && 80*\$e <= \$N && gcd(\$e,\$phi) == 1;
die "Unable to find a proper e for MS\n" if \$tries++ > 100;
}
my \$k = int(\$N * (1-2/\$e));
my \$r = \$N - \$k;
my \$xn = Math::GMP->new(\$rng->bytes_hex(int((\$r+7)/8)),16) % (Math::GMP->new(2) ** \$r);
my \$twok = Math::GMP->new(2) ** \$k;

while (\$nbits > 0) {
# y_i = x_{i-1} ^ e mod n
my \$yi = Math::GMP::powm_gmp(\$xn, \$e, \$n);

# x_i = r most significant bits of y_i
\$xn = Math::GMP::div_2exp_gmp(\$yi, \$k);   # \$xn = \$yi >> \$k;

# z_i = k least significant bits of y_i
# output is the sequence of z_i
\$twok = Math::GMP->new(2) ** \$nbits if \$nbits < \$k;
print Math::GMP::get_str_gmp( \$yi % \$twok, 2);
\$nbits -= \$k;
}
print "\n";
}
``````