Diminished Radix parameters for DSA

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 12/23/04 

Date: 22 Dec 2004 19:17:05 -0800

I needed to generate a set of Digital Signature
Algorithm Standard parameters the other day. So I
now have code that generates p, q, and g from a
text seed according to FIPS-186-2... if there's
sufficient interest I might put it up on our web
page.

But that's not the point of this posting. While I
was doing that, I thought to myself, wouldn't it
be nice to have p and q be of a form suitable for
doing Diminished Radix modular reduction on them?
Thus the modexp operation could be made much more
efficient. Note that the greatest gain comes from
getting a good p.

The algorithm, by the way, was quite simple. I
started with 2^qbits - 1, and counted down until
I found a prime q. Then I found the greatest p
less than 2^pbits such that p = 1 (mod 2q), and
checked that for primality too. Iterate until a
valid pair (q,p) is found. Then I switch tack,
and start looking for possibly-prime q's (there's
a very quick check for divisibility by the first
5 primes, which speeds the algorithm by a factor
of about three) such that the corresponding p is
greater than the best one currently found
(hopefully having more high-order bits set). Only
after determining that it would be better do I
bother checking p or q for primality. This let me
rip through all the possible 160/1024-bit combos
with the high order 128 bits of q all set in just
under 4 hours while keeping our machine amused.
It's still going...

So, I calculated the following pairs, if anyone is
interested:

160/1024 (three pairs found so far)
--------
q = 2^160 - 0x2F67
p = 2^1024 - 0x2A434 B9FDEC95 D8F9D550 FFFFFFFF FFFFFFFF

q = 2^160 - 0x7A9954DF
p = 2^1024 - 0x17691 944D7902 BB62683A 6CEDBE8D 5D97A263

q = 2^160 - 0x1 F0C9E6BF
p = 2^1024 - 0x140E1 1F0A3EB4 D9B07336 9D4B7390 D5070DDB

Observations:
1. I appear to have been lucky with that first
one, it came up quickly and set the bar quite
high.

2. The trailing F's seem to be coincidence, as
you will see below. This means that p-1 has 2^64
as a factor. Hmm.

3. The first pair would be quite suitable on a
16-bit machine. Neat. The later pairs are not
compellingly better.

256/2048 (four pairs, three shown)
--------
q = 2^256 - 0xDAF1
p = 2^2048 -
0x1 00000000 00000000 00000000 00000000 4945DDBF 8EA2A91D 5776399B B83E188F

Observations:

1. This, too, is a pretty lucky start, which I
guess explains why there were not more showing
up. It had gone past 2^32 more candidates
without even finding a q worth testing for
primality.

2. However, it would be better if we could find a
p without that pesky leading '1'; it's because
256 divides 2048, so the nearest multiple of q
near 2^2048 is always odd, leading to an even
candidate for p that can't be prime. Once I
realised what was happening here, I nobbled the
code to put a "2^64" into q, which avoids this
behaviour. (Note again that the performance of
DSA depends more on p than q.) Here are some more
generated that way:

q = 2^256 - 0x80000000 0000D509
p = 2^2048 -
   0x22A5575 757F3CDD DB977FC8 4022D6F6 0A87EBC4 986C05F0 B5177D1F 6297569B

q = 2^256 - 0x80000000 0050130F
p = 2^2048 -
     0xD38FA D9A12F33 B87DA111 373EC8BF 3E2EEB11 59208013 6DAF0AA8 01D6BF8B

Observations:

3. could probably do better, but it takes a long time.

160/2048 (13 pairs found so far, only first and last two shown)
--------
q = 2^160 - 0x19DA5
p = 2^2048 - 0xED475126 5623CCF2 22AB3DBA 57E80367 0E00AF93

...

q = 2^160 - 0xE4AF4A5
p = 2^2048 - 0x4B4A7D 17FD1222 F0500EDF 73702868 8890225D

q = 2^160 - 0x117D0F17
p = 2^2048 - 0x21524F 45C592B1 1264665A 9AE1374F 8FE85981

Observations:

1. No funky strings of 0s here.

--------------------------------------

The mp arithmetic and prime checking was done
with libtommath. Very neat stuff, that. Yes, this
is a plug.

It would be interesting to have some performance
comparisons against "normal" DSA parameter sets...
Tom?

Greg. 

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au

Relevant Pages

  • Re: [Newbie] Prime factorization question
    ... >]The primality of the selected random numbers is not conclusively ... There is a recent algorithm which can prove ... algorithms that proved primality. ... Greg Rose ...
    (sci.crypt)
  • Re: EFFICIENCY: PRIME TEST vs PRIME GENERATOR
    ... > Let's suppose we have an algorithm that will take a positive ... > For example, the USUAL test runs on odd numbers, checking for primality. ... > The time it takes to prove one such number is either composite or prime is ... > you DON'T use every partition, you might require very large exponents. ...
    (sci.math)
  • Re: Prime Candidates
    ... >it would be nice to have a way to avoid generation of as ... an algorithm to find all primes in a given range from prime ... The least integers needed in that range to test for their primality! ... to start the initial summing process. ...
    (sci.math)
  • Re: performance for testing n prime
    ... If you have a correct algorithm for testing the primality of an n-digit ... or sqrt) if n is the number of digit? ...
    (comp.theory)
  • Re: A RSA2048 semi-prime composite challenge.
    ... Sounds like an interesting algorithm. ... Could it be implimented in Python? ... though I'm not sure whether Python has primality testing in its ... remainder against the best found so far before doing primality ...
    (sci.math)