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;

[download]
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.

In reply to Re^3: How to get good primes for DH agreement ? by danaj
in thread How to get good primes for DH agreement ? by iglake

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.