File Coverage

blib/lib/Crypt/DSA/Util.pm

Criterion	Covered	Total	%
statement	88	107	82.2
branch	16	30	53.3
condition	5	6	83.3
subroutine	18	21	85.7
pod	5	10	50.0
total	132	174	75.8

package Crypt::DSA::Util;

use strict;
use warnings;
use Math::BigInt 1.78 try => 'GMP, Pari';
use Crypt::SysRandom qw (random_bytes);

use Fcntl;
use Carp qw( croak );

our $VERSION = '1.24'; #VERSION

use vars qw( $VERSION @ISA @EXPORT_OK );
use Exporter;

BEGIN {
    @ISA       = qw( Exporter );
    @EXPORT_OK = qw( bitsize bin2mp mp2bin mod_inverse mod_exp makerandom randombelow isprime );
}

## Nicked from Crypt::RSA::DataFormat.
## Copyright (c) 2001, Vipul Ved Prakash.
sub bitsize {
    length(Math::BigInt->new($_[0])->as_bin) - 2;
}

sub bin2mp {
    my $s = shift;
    $s eq '' ?
        Math::BigInt->new(0) :
        Math::BigInt->new("0b" . unpack("B*", $s));
}

sub mp2bin {
    my $p = Math::BigInt->new(shift);
    my $base = Math::BigInt->new(256);
    my $res = '';
    while ($p != 0) {
        my $r = $p % $base;
        $p = ($p-$r) / $base;
        $res = chr($r) . $res;
    }
    $res;
}

sub mod_exp {
    my($a, $exp, $n) = @_;
    $a->copy->bmodpow($exp, $n);
}

sub mod_inverse {
    my($a, $n) = @_;
    $a->copy->bmodinv($n);
}

sub makerandom {
    my %param = @_;
    my $size = $param{Size};
    my $bytes = int($size / 8) + 1;
    my $r = random_bytes($bytes);
    my $down = $size - 1;
    $r = unpack 'H*', pack 'B*', '0' x ( $size % 8 ? 8 - $size % 8 : 0 ) .
        '1' . unpack "b$down", $r;
    Math::BigInt->new('0x' . $r);
}

# Uniform random integer in [0, $n-1] with no modulo bias (rejection
# sampling).  Unlike makerandom(), this does NOT force the high bit, so
# it is correct for DSA nonces and private keys, which must be uniform
# in [1, q-1].  makerandom() forces the high bit to obtain an exactly
# 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__