iglake has asked for the wisdom of the Perl Monks concerning the following question:

Any perl-monks crypto savvy ?
I'd like to have an opinion on how to choose good primes for DH agreement :
here is an except of my perl code, I have mixed feeling about it, please comment !
(link for downloading the file directly : http://gateway.ipfs.io/ipfs/QmRi8Ag9ApvgXYhHybvdY9RXRwxG1gkUTuihN6qq2MBjeq )

#!/usr/bin/perl our $dbug = 0; use YAML::Syck qw(DumpFile); # 0) initialization get (g,p) # 1) Bob to create keypair # 2) Alice to get Bob's public key # 3) Alice to compute a shared-secret with Bob's public key... # 4) Alice to send her public-key to Bob # 5) Bob to generate his side of the shared-secret # 6) compare ! my $user = 'Bob'; # --------------------------------------------------- $PKI = { anon => ['anonymous', 'pubkey' => '123', secret => undef ] }; # --------------------------------------------------- my $seed = srand(); printf "seed: %s\n",$seed; my $iv_key = rand(4125415); my ($g,$p) = &get_IV($iv_key); # keys agreement : use Crypt::DH; my $bob; # Bob's DH # --------------------------------------------------------- if ($user eq 'Bob') { my $I = uc substr($user,0,1); $bob = Crypt::DH->new( p => "$p", g => $g ); if ($dbug) { printf "g: %s\n",$bob->g(); printf "p: %s\n",$bob->p(); } my $pub = $bob->generate_keys; my $keypair = { user => $user, pubkey => $pub, seckey => $bob->priv_key() }; printf "%s:\n",$user; printf "pub(%s): %s\n",$I,substr($pub,0,32); printf "priv(%s): %s...\n",$I,substr($bob->priv_key(),0,32); DumpFile("DH_$user.key",$keypair); $PKI->{bob}{pubkey} = $bob->pub_key(); print ".\n"; } # --------------------------------------------------------- { # Alice's my $dh = Crypt::DH->new( p => "$p", g => $g ); my $pub = $dh->generate_keys; my $keypair = { user => 'Alice', pubkey => $pub, seckey => $dh->priv_key() }; printf "%s:\n",'Alice'; printf "pub(A): %s...\n",substr($pub,0,32); printf "priv(A): %s...\n",substr($dh->priv_key(),0,32); DumpFile("DH_Alice.key",$keypair); print ".\n"; my $secret = $dh->compute_secret( $PKI->{bob}{pubkey} ); printf "Alice's secret : %s\n",$secret; $PKI->{alice}{pubkey} = $dh->pub_key(); $PKI->{alice}{secret} = $secret; } # --------------------------------------------------------- { # BOB again ... my $secret = $bob->compute_secret( $PKI->{alice}{pubkey} ); printf "Bob's secret : %s\n",$secret; die if ($secret ne $PKI->{alice}{secret}); } exit $?; # -------------------------------- sub get_IV { # set initialization vector for keypair generation my $key = shift; my ($g,$p) = (2,undef); if ($dbug == 1) { ($g,$p) = (3,107); # very bad choice but simple case to verify t +he maths ! } else { $p = &get_prime($key); } return ($g,$p); } # -------------------------------- # ------------------------------------------ sub get_prime { my $key = shift; local $/ = "\n"; my $buf = ''; while (<DATA>) { # get prime from the bottom of this file ! next if /^#/o; # skip comments next if /^__\w+__/; # & markers chomp; y/ //d; $buf .= $_; } printf "buf: %s.\n",$buf if $dbug > 1; use Math::BigInt; my $bint = Math::BigInt->from_hex($buf); if (defined $key) { use Math::Primality qw(is_prime next_prime); my $digest = &digest('RIPEMD-160',$key); $digest =~ s/ //go; my $offset = Math::BigInt->from_hex($digest); my $candidate = $bint + $offset; if ($dbug > 1) { print "hash: $digest\n"; print "cand: $candidate\n"; } if (! &is_prime($candidate)) { print " p is not a prime ... will find an other one ! \n" if $ +dbug; $bint = &next_prime($candidate); if (&is_prime($bint)) { printf "%s is now a prime\n",$bint if $dbug; } } else { $bint = $candidate; printf "%s is prime!\n",$bint; } } return $bint; } # ------------------------------------------ sub digest { use Digest qw(); my $alg = shift; my $msg = Digest->new($alg) or die $!; $msg->add(join'',@_); my $digest = lc( $msg->hexdigest() ); return $digest; # hex form ! } # ------------------------------------------ 1; __DATA__ # SSH2 prime: FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381 FFFFFFFF FFFFFFFF __END__

Replies are listed 'Best First'.
Re: How to get good primes for DH agreement ?
by Anonymous Monk on Mar 20, 2018 at 19:59 UTC

    Any perl-monks crypto savvy ?
    Not really, but we can read Wikipedia, and therefore we know it all! ;)

    But Seriousely? You are limiting your pool of primes to 4125415 possibilities.

    Use RDRAND or RDSEED instruction to fill the $candidate. This way, only you and the NSA can haz the secret. Well, except if you're on Ryzen+, then it's only you and ESA1).

    #1 The European Spice Agency, or whatever it is called.

      Thanks a lot this helps, I was wondering if looking for the next prime from a random value is introducing some bias compared to building iterating on random numbers until one fall on a prime, (which is obviously more time consuming).
      Also I am curious though about your comment: how does the NSA or ESA get to know the secret,
      do they bruteforce "weak" primes ?

        Yes, using what is sometimes called the PRIMEINC algorithm does introduce a significant bias, as some values will be output much more frequently than some others. At the moment there is no known exploit for this with non-tiny bit sizes, and some software uses it because it's not too hard to make it fast. Making the TRIVIAL algorithm (randomly select integers in the range and reject until it passes your primality test) fast takes more effort.

        I think it is much more likely that something else is a bigger issue, as rolling ones own crypto is full of pitfalls. Admittedly using someone else's crypto stuff also has pitfalls, but they are usually more non-obvious.

        Math::Prime::Util has a lot of routines for efficiently generating random primes. Relevant to DH, it has a routine for generating random n-bit strong primes, but not currently safe primes. I've written one which will go in the next version. It's of course possible to do it by hand, such as something like:

        my $b = 256; # Whatever your bit length is my($p,$q); do { $q = random_nbit_prime($b-1); $p = 2*$q+1; } while ( ($q % 3) != 2 || ($q % 5) == 2 || ($p % 3) != 2 || !is_prime($p) ); return $p;
        The advantage of the call is (1) it's ~10x faster, and (2) it's more convenient.


        You can also call out to something like openssl.

        Lastly, consider Crypt::DSA::GMP which follows the FIPS 186-2 or FIPS 186-4 standards for generating keys. It will give the <p,q,g> parameters you need.