Status
People
(Reporter: Jamie Nicolson, Assigned: Ian McGreer)
Tracking
Firefox Tracking Flags
(Not tracked)
Details
Attachments
(3 attachments)
874 bytes,
patch

Details  Diff  Splinter Review  
1.52 KB,
patch

Details  Diff  Splinter Review  
3.27 KB,
patch

Details  Diff  Splinter Review 
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.
(Assignee)  
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 1024bit numbers being about 1/300, so I suggest 500 (this operation is fairly fast). I also want to change the number of MillerRabin primality tests to 50, which is what FIPS186 specifies. patch forthcoming.
(Assignee)  
Comment 3•17 years ago


Created attachment 22445 [details] [diff] [review] comments? Nelson, is 500 reasonable?
Comment 4•17 years ago


Please don't change "the number of MillerRabin 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.
(Assignee)  
Comment 5•17 years ago


I got the number 50 from FIPS 186, section 2.1. I thought mpp_pprime was an implementation of MillerRabin, so I assumed that 50 would be the correct number. Is that not the case?
Comment 6•17 years ago


The requirement is to produce a number whose probability of being nonprime is less than 1/(4**50). Doing MillerRabin 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).
Comment 7•17 years ago


First , I need to correct what I wrote above. The FIPS 1861 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 nonprime 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 kbit candidate, for which the probability is at most (1/2)**80. Section 4.4.3, especially note 4.57 (pages 150151) 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.
Comment 8•17 years ago


Created attachment 22718 [details] [diff] [review] proposed changes to lib/freebl/mpi/mpprime.c
(Assignee)  
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.
(Assignee)  
Comment 10•17 years ago


Created attachment 22779 [details] [diff] [review] patch as promised
Comment 11•17 years ago


Ian, your patch looks good to me.
Comment 12•17 years ago


Please check in the fix.
(Assignee)  
Comment 13•17 years ago


I have checked in the patch to pqg.c.
Comment 14•17 years ago


My patch is also checked in. Ian, is this bug realy to be marked resolved/fixed?
(Assignee)  
Comment 15•17 years ago


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