3
$\begingroup$

I have seen the NIST, SEC and Brainpool standards. They have used same prime for a particular bit curve (128,192,256,521). Is the prime value fixed for a particular security (field size)?

$\endgroup$
  • 1
    $\begingroup$ The question in the title isn't repeated in the body of your post. Actually, it seems to me that you ask two (strongly related) questions. Could you adjust and make sure that the body and the title match? $\endgroup$ – Maarten - reinstate Monica Feb 8 '17 at 9:57
  • $\begingroup$ (i) Of these three standards, only SEC publishes a 128-bit curve. (ii) All the Brainpool primes are different from all the NIST primes. (SEC and NIST use the same curve parameters, not just the same primes.) $\endgroup$ – TonyK Feb 8 '17 at 11:05
6
$\begingroup$

In general you start by fixing the field, which translates into fixing the prime, and then you start to look to a suitable (i.e. secure/safe) elliptic curve defined over that field.

Note that, once you've fixed $p$, there are $\sim2p$ isomorphism class of elliptic curves defined over $\mathbb{F}_p$, which grants you a big set where you are supposed to find a curve with all the desired security properties, unless you are looking for very specific properties such as low CM discriminant.

There are two good reasons for it.

First: the field is linked to the curve's cardinality by Hasse's Theorem. which means that by choosing the size of the prime you also strictly bound the size of the cardinality (within a bit).

And second, and most important, a particular choice of the prime provides faster-than-generic modular reductions, which provides performance benefits of elliptic curve computations.

For example, all NIST P curves are defined over Solinas primes (also called generalized Mersenne), except P-521 which is over a Mersenne prime. The idea is that using Solinas reduction is faster than a generic modular reduction and can be used to speed up the computation.

Similar arguments are used in more modern elliptic curves such as curve25519 which uses a pseudo Mersenne prime ($2^{255}-19$) or FourQ which uses is defined over a field $\mathbb{F_{p^2}}$ with $p=2^{127}-1$.

Note that the Brainpool standard uses random primes, however its deterministic algorithm for curve generation selects first a random prime, and then look for a suitable curve. See appendix A of RFC 5639.

$\endgroup$
  • $\begingroup$ What do you mean by isomorphism class ? $\endgroup$ – Venkatesh Feb 8 '17 at 9:44
  • 2
    $\begingroup$ @Venkatesh you in fact have multiple (~p) elliptic curves, defined over the same field, with the same j-invariant and same number of points. Those are in fact isomorphic to each other. These belong to the same isomorphic class. $\endgroup$ – Ruggero Feb 8 '17 at 10:23
1
$\begingroup$

The NIST curves as published in FIPS-PUB 186-3 and SEC curves are identical. The P-xxx curves are the same as the secpxxxr1 curves (where xxx is the bit size). NIST just standardized most of the curves and gave them separate names from the SEC curves by the Certicom corporation.

I'll show you the Bouncy Castle code for the NIST curves:

defineCurve("B-571", SECObjectIdentifiers.sect571r1);
defineCurve("B-409", SECObjectIdentifiers.sect409r1);
defineCurve("B-283", SECObjectIdentifiers.sect283r1);
defineCurve("B-233", SECObjectIdentifiers.sect233r1);
defineCurve("B-163", SECObjectIdentifiers.sect163r2);
defineCurve("K-571", SECObjectIdentifiers.sect571k1);
defineCurve("K-409", SECObjectIdentifiers.sect409k1);
defineCurve("K-283", SECObjectIdentifiers.sect283k1);
defineCurve("K-233", SECObjectIdentifiers.sect233k1);
defineCurve("K-163", SECObjectIdentifiers.sect163k1);
defineCurve("P-521", SECObjectIdentifiers.secp521r1);
defineCurve("P-384", SECObjectIdentifiers.secp384r1);
defineCurve("P-256", SECObjectIdentifiers.secp256r1);
defineCurve("P-224", SECObjectIdentifiers.secp224r1);
defineCurve("P-192", SECObjectIdentifiers.secp192r1);

The prime fields of the Brainpool curves and SEC curves certainly differ, for instance the prime field over 256 bit curve is:

FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF 

for the SEC curve and

A9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377

for Brainpool.

Here the SEC / NIST specified curve uses a specific prime while the Brainpool curve was (semi-) randomly generated. More information in the answer of Ruggero


So no, the prime value isn't fixed for a particular field size. There is no specific way to calculate the prime for a particular field, but you may at least want to make the generation of curve parameters opaque. Most cryptographers will probably agree with D.J. Bernstein that the domain parameter generation must be verifiable. I'll gladly point out the SaveCurves website for more information.

Brainpool scores better in this regard although the choice of prime is probably not the biggest issue here; the SEC primes are well known primes and it seems unlikely that they are part of some specific plot. You may want to make sure that you choose the right prime for speedy calculations (lots of 0 bits or 1 bits set generally helps, to simplify the requirements to the extreme).

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