1
$\begingroup$

Based upon choosing a prime $p$ of recommended length and $N=2p+1$, where $N$ is also prime, and $a^2$ is not congruent to $1 \pmod N$, and $a^p ≡ 1 \pmod N$, I believe you can rely upon $a$ as having order equal to $p$.

My question is, what is a good size for $a$? And the reason I ask is because I've heard that you want the base large enough so that most of the power possibilities exceed $N$. What I'm looking for is more formal requirements or an example that provides $p, N, a$ using current recommendations.

$\endgroup$
3
$\begingroup$

The standard approach is to use $N \equiv 7 \pmod 8$ so that $a = 2$ has order $p$ by virtue of being a quadratic residue, e.g. in the RFC 3526 groups, chosen by the deterministic procedure described in RFC 2412, Appendix E. Using any other groups for finite-field Diffie–Hellman raises a lot of eyebrows.

Uniform random exponents of the usual size have negligible probability of being small enough to admit their recovery by real number logarithm computations: even for $a = 2$ and $N \sim 2^{2048}$, the probability of a 256-bit exponent admitting this attack is about $2^{11}/2^{256} = 2^{-245}$ which is a technical word for ‘not gonna happen’.

Of course, you should just use a modern system like X25519 instead of finite-field DH anyway! Faster, safer, simpler.

$\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.