Re: special DH prime

According to Pubkeybreaker <pubkeybreaker@xxxxxxx>:
Yes, such moduli can be substantially easier. The reason is that one
might be able to use the special form of the number field sieve to
represent the modulus as a polynomial with *much smaller* coefficients
than for "general primes".

The number you give results in a polynomial whose degree is too high
to be useful.

Primes with low Hamming weight are, on average, easier than general
primes.

Is there a reliable test ? I.e., is it possible to know _a priori_
whether a given modulus will be easier than a random big prime for
discrete logarithm ?

I understand that one cannot speculate on how as yet undiscovered
algorithms will react on special form moduli, but maybe it is possible
to know what a given modulus will yield for currently known attacks. For
instance, computing a low-degree polynomial with small enough
coefficients, for Special NFS. But I do not have clear ideas on what
"low degree" and "small enough" really mean in that context.


My current problem is the implementation of a transport protocol with an
ephemeral Diffie-Hellman for forward secrecy. Both parties use low power
32-bit CPU. Reglementary issues prevent me from using something else
than modular integers (otherwise I would have gone for elliptic curves)
and the required security level implies the use of a 2048 bits modulus,
which implies a really long key exchange time (maybe a dozen seconds).
Fortunately, I get the choice of the group, and I am looking for a group
where things are faster. A special form modulus should speed up things,
but I will do it only if I can give strong reasons why the DH is not
thereby weakened. Those reasons should include adequate references to
published papers.

I ran a few search programs and I have come accross the following modulus:

p = 2^2048 - 2^2016 + 2^1984 - 2^1856 - 2^1824 + 2^1792 - 2^1760
+ 2^1696 + 2^1664 + 1

p is prime, and p = 2^1664*q+1 for a 384-bit prime q. This makes this
modulus suitable for my problem, provided that discrete logarithm modulo
p is not easy. Beyond the context of my present implementation task,
this modulus should be fine for DSS-like signatures since q is
relatively small.

Moduli with this special form have been used to define the base fields
for elliptic curves; FIPS 186-2 contains some standard curves which
benefit from the fast computations allowed by moduli with this format. I
am wondering whether such fields have already been investigated for
plain Diffie-Hellman or DSS; any reference would be greatly appreciated.


--Thomas Pornin
.

Relevant Pages

  • Re: [Newbie] Prime factorization question
    ... Should I interpret this to mean that the decision to develop the modulus ... that is the product of something other than exactly two primes) ... and with far greater susceptibility to cracking through factorization. ... RSA is not completely sound, because it can still fail if one of the ...
    (sci.crypt)
  • Re: RSA moduli sizes
    ... bit RSA modulus be 1 we are effectively turning it into an -bit ... Since the best known factoring ... The sentence about "forcing the complexity as high ... two primes, uniformly at random, from a specified interval. ...
    (sci.crypt)
  • Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
    ... the product is indeed, say, 512 bits, for a 512-bit modulus. ... an N bits long product of two primes doesn't really contain N ... slightly more than 502.5 bits of entropy, so a 1024 bits long RSA ... the sieve of Eratosthenes or the sieve of Atkin. ...
    (sci.crypt)
  • Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
    ... the product is indeed, say, 512 bits, for a 512-bit modulus. ... an N bits long product of two primes doesn't really contain N ... slightly more than 502.5 bits of entropy, so a 1024 bits long RSA ... Yes, to generate an N bits prime, first you create a prime sieve using ...
    (sci.crypt)
  • special DH prime
    ... Diffie-Hellman (with modular integers, not elliptic curves) important ... for security? ... There are some modulus which may yield much better performance. ...
    (sci.crypt)