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.

Improve this question
$\endgroup$
3
  • $\begingroup$ NIST has published a bunch of them. $\endgroup$
    – CodesInChaos
    Nov 11, 2013 at 7:09
  • 5
    $\begingroup$ Where? I can't find any. $\endgroup$
    – ithisa
    Nov 11, 2013 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, 2017 at 16:48

2 Answers 2

Reset to default
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
Improve this answer
$\endgroup$
5
  • $\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, 2017 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, 2017 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, 2017 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, 2017 at 15:25
  • 1
    $\begingroup$ I am surprised why this answer has not been marked 'accepted' yet. $\endgroup$
    – Papa Delta
    Jun 28, 2019 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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