Lightweight primality certificates for untrusted DH parameters Are there any light-weight techniques to generate primality certificates for custom Diffie-Hellman parameters that could be sent to the client to allow it to verify primality without needing to run its own expensive rounds of primality testing? By lightweight, I mean not significantly harder than the recommended number of Miller-Rabin rounds on the generation side, and significantly less intensive during verification (after all, there's no point if it doesn't make life easier for the client).
Well, one possibility to generate a moderately lightweight certificate would be to use this theorem:

If we have values $p, q, g$ such that:


$1 &lt; g &lt; p$
$q &gt; \sqrt{p}$
$q \mid p-1$
$g^q \equiv 1 \pmod p$
$q$ is prime


Then $p$ is prime.

So, for a certificate, we would have a list of $(p_i, g_i)$ values such that $p_{i-1}, p_i, g_i$ meet the above conditions (as $p, q, g$), with $p_0$ is the value $p$ we're actually interested in proving, and the final $p_n$ value is a prime small enough to make primality proving trivial (e.g. it may less than 16 bits long).  Each line in the certificate (almost) halves the value of $p_i$, and so the total number of lines is managable.

As for verifying the certificate, it should be fairly obvious, for each line in the certificate, we would check the first four conditions directly, and then step to the next line to verify the last condition; as the last step, you'd do a quick check that $p_n$ is prime.  The expensive part is the $g^q \equiv 1$ condition; if you total it, it's a bit less than a single Miller-Rabin computation (but has the advantage that it is deterministic; if it validates, there is no need to do a second iteration).  Whether this counts as 'significantly less' is something you'll need to decide.

As for generating the certificate, you can't select a random $p$ and try to generate the certificate.  Instead, you would create the certificate (and the prime) from the bottom-up; select a $p_n$, and then at each step, given $p_i$, you would search for a prime value $p_{i-1}$ (and $g_i$, but that's easy), eventually ending up with a $p_0$ value of the desired size.  The FIPS 186-4 Shawe-Taylor algorithm does exactly this (you'll just need to record the intermediate $p_i, g_i$ values).

As a side effect, $g_1$ is an appropriate generator for the DH group (as it generates a large prime-sized subgroup).

On the other hand, I would second Future Security's suggestion to the ECDH instead; that uses less resources, and doesn't have any known 'solve this problem and break the entire group' attacks