1
$\begingroup$

I've been reading about safe primes and their use in: Cryptography Engineering by Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno.

Having a safe prime $q$ with $q=2p+1$ where $p$ is a Sophie Germain prime

They claim that the elements of the subgroup $p$ are the elements that are preferred to be used. Why?

Why not the elements in $2p$?

Improve this question
$\endgroup$
  • $\begingroup$ Yes, I consider to use them in Diffie-Hellman. What is so bad about large group orders? $\endgroup$ – mark23 Aug 24 '20 at 12:37
  • $\begingroup$ No, not really. But the answer given by Occams_Trimmer does $\endgroup$ – mark23 Aug 26 '20 at 14:03
  • $\begingroup$ Yes, That is another reason that I've forgotten. I'll update my answer later... $\endgroup$ – kelalaka Aug 26 '20 at 14:13
1
$\begingroup$

The Decisional Diffie-Hellman assumption, on which the key-exchange would be based on does not hold in $\mathbb{Z}_q^*$. The reason is that the Jacobi symbol "leaks" information about the shared key. Therefore one, instead, works with the subgroup of $\mathbb{Z}_q^*$ of order $p$, which is intuitively obtained by "quotienting out" this information. (This group is sometimes called the Schnorr group.) You can read the details on why DDH doesn't hold here (Exercise 2).

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you! This was exactly what I was looking for $\endgroup$ – mark23 Aug 26 '20 at 14:03

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.