view release on metacpan or  search on metacpan

lib/Crypt/DSA/Util.pm  view on Meta::CPAN

# N-bit value for prime search, which biases a nonce/key: folding its
# output with "v -= q if v >= q" leaves the band [2^N-q, 2^(N-1)-1]
# unreachable (CWE-330, biased-nonce -> lattice key recovery).
sub randombelow {
    my $n = shift;
    $n = Math::BigInt->new("$n") unless ref($n) eq 'Math::BigInt';
    croak "randombelow: argument must be > 0" unless $n > 0;
    my $bits  = length($n->as_bin) - 2;
    my $bytes = int(($bits + 7) / 8) + 1;          # one byte of headroom
    my $rmax  = Math::BigInt->new(2) ** (8 * $bytes);
    my $limit = $rmax - ($rmax % $n);              # largest multiple of $n <= rmax
    my $r;
    do {
        $r = Math::BigInt->new('0x' . unpack('H*', random_bytes($bytes)));
    } while $r >= $limit;
    $r % $n;
}

# For testing, let us choose our isprime function:
*isprime = \&isprime_algorithms_with_perl;

# CSPRNG-drawn Miller-Rabin base, uniform enough in [2, n-2].  A witness
# only has to be a random base in range for the strong-pseudoprime test
# to be sound, so (unlike a secret nonce) a plain draw with a few extra
# bytes of headroom is fine -- the modulo bias is immaterial here.
sub _random_base {
    my ($n) = @_;
    my $range = $n - 3;                     # 0 .. n-4
    my $bytes = int(bitsize($n) / 8) + 8;   # headroom keeps bias negligible
    my $r = Math::BigInt->new('0x' . unpack 'H*', random_bytes($bytes));
    ($r % $range) + 2;                      # 2 .. n-2
}

# from the book "Mastering Algorithms with Perl" by Jon Orwant,
# Jarkko Hietaniemi, and John Macdonald
sub isprime_algorithms_with_perl {
    use integer;
    my $n = shift;
    return 0 if $n < 2;
    return 1 if $n < 4;         # 2 and 3 are prime
    return 0 unless $n % 2;     # even n > 2 (also keeps _random_base's
                                # [2, n-2] range non-degenerate)
    my $n1 = $n - 1;
    my $one = $n - $n1;  # not just 1, but a bigint

    # find the power of two for the top bit of $n1
    my $p2 = $one;
    my $p2index = -1;
    ++$p2index, $p2 *= 2
	while $p2 <= $n1;
    $p2 /= 2;

    # number of iterations:  5 for 260-bit numbers, go up to 25 for smaller
    my $last_witness = 5;
    $last_witness += (260 - $p2index) / 13 if $p2index < 260;

    for my $witness_count (1..$last_witness) {
	# Fresh, independent CSPRNG witness every round.  The old code
	# accumulated witnesses from int(rand(1024)) -- Perl's predictable
	# Mersenne-Twister PRNG, and correlated round-to-round -- which
	# both weakens each round and breaks the independence the
	# Miller-Rabin error bound assumes.
	my $witness = _random_base($n);

	my $prod = $one;
	my $n1bits = $n1;
	my $p2next = $p2;

	# compute $witness ** ($n - 1)
	while (1) {
	    my $rootone = $prod == 1 || $prod == $n1;
	    $prod = ($prod * $prod) % $n;
	    return 0 if $prod == 1 && ! $rootone;
	    if ($n1bits >= $p2next) {
		$prod = ($prod * $witness) % $n;
		$n1bits -= $p2next;
	    }
	    last if $p2next == 1;
	    $p2next /= 2;
	}
	return 0 unless $prod == 1;
    }
    return 1;
}

sub isprime_gp_pari {
    my $n = shift;

    my $sn = "$n";
    die if $sn =~ /\D/;

    my $is_prime = `echo "isprime($sn)" | gp -f -q`;
    die "No gp installed?" if $?;

    chomp $is_prime;
    return $is_prime;
}

sub isprime_paranoid {
    my $n = shift;

    my $perl = isprime_algorithms_with_perl($n);
    my $pari = isprime_gp_pari($n);

    die "Perl vs. PARI don't match on '$n'\n" unless $perl == $pari;
    return $perl;
}

1;
__END__

=head1 NAME

Crypt::DSA::Util - DSA Utility functions

=head1 SYNOPSIS

    use Crypt::DSA::Util qw( func1 func2 ... );

=head1 DESCRIPTION