I am implementing a security protocol based on discrete log. I came across the equation $p = kq + 1$. Understand that based on number theories that both $p$ and $q$ should be large enough to be "safe". However, how does it justifies safe? Say I chose $p = 7$, $k = 2$ and $q = 3$, will my implementation be screwed up?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ You have chosen the tag "dsa", but there is no mention of digital signatures in your question. Do you need primes for Diffie-Hellman or for a signature scheme? $\endgroup$– Henrick HellströmDec 26, 2014 at 19:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
There already exist standard primes that might be used for Finite Field Discrete Logarithm based schemes. One set is found in RFC 3526. Another set is currently in the process of being standardized as part of TLS and can be found in the current Negotiated FF DHE draft (this link will expire no later than June 15 2015).
The smallest prime in the former set is 1536 bits, which means that it is greater than $2^{1535}$. It is recommended to be used with a 180 bit exponent, which corresponds to an integer greater than $2^{179}$.
The smallest prime in the latter set (TLS) is currently fixed at 2048 bits, although an even greater number was originally proposed.
By comparison, 7 is only 3 bits and 3 is only 2 bits, so, yes, your implementation would be kind of inadequate, should you try to use these primes.
answered Dec 26, 2014 at 18:54
-
$\begingroup$ Hi @Henrick Hellström, Thanks for giving such detailed explanation and also providing relevant resource for my learning. Yes, what i am implementing is Chameleon Hashing, which is based on discrete log, like DSA, which I will be using to generate the prime numbers, hence the tag. $\endgroup$– kenAu89Dec 26, 2014 at 19:09