5
$\begingroup$

There are many RFC documents giving large primes to use in Diffie-Hellman. However, I couldn't find standards on the $p$ and $q$ large primes used in the DSA signature scheme. This is proving to be a major obstacle in my own toy implementation of DSA, as generating these primes uses much messier math and code than the rest of the algorithm, and more places where I could make stupid mistakes that trash the security of the whole scheme.

Where can I find suitbale $p$ and $q$? They don't seem to need to be private, and frankly I'm kind of shocked that there aren't standard numbers for them to save people from needing to do the expensive calculations themselves.

$\endgroup$
  • $\begingroup$ NIST has published a bunch of them. $\endgroup$ – CodesInChaos Nov 11 '13 at 7:09
  • 5
    $\begingroup$ Where? I can't find any. $\endgroup$ – ithisa Nov 11 '13 at 13:10
  • $\begingroup$ I just asked the bear about this and he said he doesn't know of any and you're supposed use your own or those of your CA. $\endgroup$ – SEJPM Jan 21 '17 at 16:48
2
$\begingroup$

There is a very detailed algorithm on how to construct $p,q$ in FIPS 186-3, appendix A.1.2.1.2. The algorithm provided takes as input, the lengths $L,N$, of $p,q$ (resp.) (for instance L=1024,N=160) and output, the primes $p,q$ such that $p\equiv 1\pmod{q}.$
Also,there is an implementations in python (for $(L,N)=(1024,160)$). For instance

from Crypto.PublicKey import DSA
import random
def randfunc(n):
    return ''.join(str(random.random())[4] for _ in xrange(n))
DSAkey=DSA.generate(int(1024),randfunc)
p=DSAkey.p;q=DSAkey.q; 

Running the previous I got

p=898846567431157967424297114057633644601771516927834298008846524493109792\
637522535293491954598238817151457964980464592383454281215613866269456797\
539564000773528820716639254597505008070182540287714904340213156913571237\
346370468948761234961687162517352526627424620993348024330584723776744085\
98573487858308054417L
q= 1193447034984784682329306571139467195163334221569L
$\endgroup$
  • $\begingroup$ I think the OP is asking for stanardized (NIST, RFCs, ANSI, ANSSI, BSI, ...), specific numbers rather than "I just generated these". $\endgroup$ – SEJPM Jan 21 '17 at 15:13
  • $\begingroup$ If you run the standardized methods to produce them, then, will you get some "standardized" pairs $(p,q)?$ $\endgroup$ – 111 Jan 21 '17 at 15:16
  • $\begingroup$ This method will generate different parameters on each run (run it again and see how the results differ) and AFAICT the OP asks for static, fixed, written-down parameters in some standards document. $\endgroup$ – SEJPM Jan 21 '17 at 15:19
  • $\begingroup$ of course you will get different primes, but the whole point (if I understood right) is to avoid (as the OP wrote) the "expensive calculations" (i.e. to avoid writing the algorithm). $\endgroup$ – 111 Jan 21 '17 at 15:25
  • 1
    $\begingroup$ I am surprised why this answer has not been marked 'accepted' yet. $\endgroup$ – Rudra Jun 28 at 3:37
0
$\begingroup$

Using parameters for DSA generated by a third party might not be a good idea, as the recent paper "A kilobit hidden SNFS discrete logarithm computation" shows. But even if the parameters are not backdoored, commonly used 1024-bit parameters could be already broken.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.