4
$\begingroup$

Reductions modulo Mersenne primes are extremely fast, and there are several of a suitable size for modp-based Diffie-Hellman (such as $2^{2281}-1$). Is there any reason such primes are not commonly used for this purpose? Same question also applies to pseudo-Mersenne primes, of the form $2^{n}-c$ for small $c$, which also have fast reductions.

I'm assuming the reason they are not used is that something about the special form allows fast discrete logarithm computations, but I haven't been able to find any references to such an attack.

|improve this question
$\endgroup$
  • 4
    $\begingroup$ en.wikipedia.org/wiki/Special_number_field_sieve $\endgroup$ – SEJPM♦ Sep 19 '17 at 19:21
  • $\begingroup$ Thanks! If you want to post that as an answer I will accept $\endgroup$ – Jack Lloyd Sep 19 '17 at 19:29
  • $\begingroup$ In addition to the SNFS issue, Diffie-Hellman primes generally need to have other properties, for example a lack of any (exhaustably) small multiplicative subgroups. I don't think in general that Mersenne primes have this property (although I would love for someone to give a more solid demonstration one way or the other). $\endgroup$ – Liam Sep 19 '17 at 23:03
  • 1
    $\begingroup$ @Liam Except for 7, no Mersenne prime is a safe prime, since every safe prime except 7 is congruent to 1 mod 6. Same goes for Fermat primes, with the exception of 5. However, there are tempting options like $2^{2048} - 1942289$ which, while not Mersenne primes, still admit fast arithmetic…and still easily fall to the SNFS. $\endgroup$ – Squeamish Ossifrage Mar 23 '19 at 8:54
4
$\begingroup$

I'm assuming the reason they are not used is that something about the special form allows fast discrete logarithm computations

Yes, the Special Number Field Sieve (SNFS) which is a faster version of the General Number Field Sieve (GNFS). More specifically the best known discrete logarithm computation with the GNFS was with a 768-bit safe prime. The best known result with SNFS is 1039-bit for factoring (which should have comparable work-load as discrete log) and 1024-bit for discrete log (using a specifically crafted prime).

As you can see, while 2048-bit or larger primes aren't feasible with the SNFS either, these primes have a structural weakness, which cryptographers like to avoid. Actually the cost of picking larger primes to defend against SNFS probably would probably far outweigh the gains from the special form and the faster reduction.

Reductions modulo Mersenne primes are extremely fast

Which is why the "256-bit security" NIST elliptic curve P-521 uses $2^{521}-1$ as the underlying field-prime.

Same question also applies to pseudo-Mersenne primes, of the form $2^n−c$ for small $c$, which also have fast reductions.

Which was done with Curve25519 which uses $2^{255}-19$ as the underlying field-prime.

|improve this answer
$\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.