PQG parameter generation fails



17 years ago
17 years ago


(Reporter: Jamie Nicolson, Assigned: Ian McGreer)


Firefox Tracking Flags

(Not tracked)



(3 attachments)



17 years ago
The algorithm tries to generate a prime, Q, by generating random numbers and
then testing them for primality. It loops around until it finds a prime, or
until MAX_ITERATIONS is exceeded. MAX_ITERATIONS is set to 5, which is usually
too low to find a prime.

Comment 1

17 years ago
Ian, is this your code?
Assignee: wtc → mcgreer

Comment 2

17 years ago
This is my code.  I believe the number does need to be larger.  I seem to 
remember the frequency of primes in 1024-bit numbers being about 1/300, so I 
suggest 500 (this operation is fairly fast).

I also want to change the number of Miller-Rabin primality tests to 50, which is 
what FIPS-186 specifies.

patch forthcoming.

Comment 3

17 years ago
Created attachment 22445 [details] [diff] [review]
comments?  Nelson, is 500 reasonable?
Please don't change "the number of Miller-Rabin primality tests to 50"
until we can discuss it more.  I believe it is unnecessary.  I don't
want to elaborate here.

I'd say that the limit ought to be a function of the size of the prime,
and ought to be at least twice the frequency.  That is, if the frequency
is really 1/300 then I'd do up to 600.

Comment 5

17 years ago
I got the number 50 from FIPS 186, section 2.1.  I thought mpp_pprime was an 
implementation of Miller-Rabin, so I assumed that 50 would be the correct 
number.  Is that not the case?
The requirement is to produce a number whose probability of 
being non-prime is less than 1/(4**50).  Doing Miller-Rabin
50 times will assure that, but is overkill for very large 
values.  1/(4**n) is the upper bound for probability that 
the test will declare a composite number prime. As the 
numbers get larger, the probability of a pseudoprime
goes down.  

That is why mpp_make_prime adjusts the number of tests
according to the size of the number.

You'll find that quite a few other libraries also do this.
I'm looking for a citable reference on this (other than
third party source code).
First , I need to correct what I wrote above.
The FIPS 186-1 requirement is that a "robust primality
test" be used on q and p to determine if they're prime
(Appendix 2.2, steps 4 and 11.  A footnote in that 
appendix defines "robust primality test" as "one where
the probability of a non-prime number passing the test
is at most 2**-80."

In the Handbook of Applied Cryptography, Table 4.4, 
part of note 4.49 (page 148) shows t, the number of 
MR tests that must be run on a k-bit candidate, for 
which the probability is at most (1/2)**80.   Section
4.4.3, especially note 4.57 (pages 150-151) state that
for randomly chosen 160 bit numbers (q), 18 MR tests
is enough, and that 5 is more than enough for all 
valid values of L (bits in P).  I'm going to replace
the code in mpp_make_prime with code that implements
table 4.4.

So, 50 is way overkill.  Please use the values 18 and 5
for q and p respectively.
Created attachment 22718 [details] [diff] [review]
proposed changes to lib/freebl/mpi/mpprime.c

Comment 9

17 years ago
I verified the patch by checking the values in HAC table 4.4.

I will attach a revised patch for the PQG bug.  In it, the maximum number of 
iterations to attempt to generate a prime is fixed at 600.  Nelson, I read from 
your comments that this should be sufficient?  I don't believe it should be 
neccessary to make this number a function of the size of the prime, since it's 
really just there to prevent the library from spinning out of control.  

Comment 10

17 years ago
Created attachment 22779 [details] [diff] [review]
patch as promised
Ian, your patch looks good to me.

Comment 12

17 years ago
Please check in the fix.

Comment 13

17 years ago
I have checked in the patch to pqg.c.
My patch is also checked in.
Ian, is this bug realy to be marked resolved/fixed?

Comment 15

17 years ago
Yes, I believe so.  Marking as fixed.
Last Resolved: 17 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.