1
$\begingroup$

In NIST FIPS 186-4 (page 90), it is said that $c$ is the output of SHA-1 on a seed that was chosen randomly. Then the parameter $b$ of the EC is chosen, according to the formula: $$b^2 \times c \equiv -27 \pmod p$$ Why choose $b$ this way? Why, as an example, couldn't $b = c$?

$\endgroup$
3
$\begingroup$

The algorithm for generating EC curve is in appendix D.5 of NIST FIPS 186-4, and the verification algorithm is in D.6. They are taken from ANSI X9.62, which justified the rationale as the following:

In order to verify that a given elliptic curve was indeed generated at random, the defining parameters of the elliptic curve are defined to be outputs of the hash function SHA-1 (as specified in ANSI X9.30 Part 2 [4]). The input (SEED) to SHA-1 then serves as proof (under the assumption that SHA-1 cannot be inverted) that the parameters were indeed generated at random.

The curve generation algorithm requires $a,b$ to satisfy $b^2\cdot c \equiv a^3 \bmod p$, and it is not necessary that $a$ and $b$ be chosen at random. In the case of NIST Prime curves, they all use fixed $a=-3$, so $b^2\cdot c \equiv -27 \bmod p$.

As to the question why $b$ cannot equal to $c$, note if $a$ is not fixed then it is actually valid to choose $a=b=c$. But $a=-3$ is chosen by NIST, so this is not possible because the seed does not hash to $-3$.

$\endgroup$
  • $\begingroup$ Thank you! Can you kindly elaborate where the condition came from? Its not identical to the requirement for the discriminant #0, that is, for a certain values of random c (maybe not this one specifically), the discriminant could be zero, isn't it? $\endgroup$ – Evgeni Vaknin Jul 17 '18 at 7:17
  • 1
    $\begingroup$ No this is not the same. That requires $4a^3+27b^2\ne 0$. In fact in NIST FIPS 186-4 D.5, step 8, it checks $4c+27\ne 0 \bmod p$, to ensure the discriminant is not 0 if $(a,b)$ is chosen by the formula $b^2\cdot c \equiv a^3$. As to where this $b^2\cdot c \equiv a^3$ formula comes from, I am not sure because it is not documented anywhere. $\endgroup$ – Changyu Dong Jul 17 '18 at 13:56

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.