2
$\begingroup$

Recently I've been studying the ECC with the Chinese SM2 standard. One question is on standard part 5, parameters definition, it only defines $p, a, b, n, XG,$ and $YG$, but not cofactor $h$.

I found some useful discussion introducing all the parameters mathematics behind: What is the relationship between p, n, and h.It doesn't answer my question: Why SM2 does not specify h, while Key Exchange Agreement Protocol introduce in SM2 part 3 has used it.

On the standard part 1, section 5.2.2, it provides a method to verify Elliptic Curve Parameters. One option process uses to verify $h$ is:

(optional) Calculate $h'=\lfloor((p^{1/2} + 1) ^ 2)/n\rfloor$, and verify $h=h'$

This also means h can be calculated by the equation above. I calculate with an online big number calculator, the result is slightly greater than 1 (not fully equal).

Or have I misunderstood this cofactor? It is calculated instead. Elliptic curve can be perfectly defined only with $p, a, b, n, XG$, and $YG$.

$\endgroup$
2
$\begingroup$

Elliptic curve can be perfectly defined only with $p, a, b, n, XG$, and $YG$.

Yes, indeed even though it's not the nicest / most convenient set of parameters, this is sufficient to recover the curve order (using Schoof's algorithm) and with that the co-factor.

Of course Schoof's algorithm, while efficient, isn't exactly fast nor widely implemented and therefore usually the curve order and co-factor are supplied.

Why SM2 does not specify h, while Key Exchange Agreement Protocol introduce in SM2 part 3 has used it.

Well, the quality of the linked IETF draft isn't the best, so maybe it was just an oversight.

To answer your question: $h=1$.
This can be verified using the following sage-math instructions:

F=GF(0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF)
a=0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
b=0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
n=0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
E=EllipticCurve(F,[a,b])
h=E.cardinality_pari()/n;h

where the last one should return the co-factor $h$ as being $1$.

I calculate with an online big number calculator, the result is slightly greater than 1 (not fully equal).

This formula comes from the Hasse-bound (with $q$ being the curve and $p$ being the field order) $$\left|q-(p+1)\right|\leq 2\sqrt p$$ which assuming $q\geq p+1$ is \begin{align} &&q-(p+1)&\leq 2\sqrt p\\ \iff&& q&\leq p+2\sqrt p +1=(\sqrt p +1)^2\\ \iff&& h=q/n&\leq (\sqrt p +1)^2/n \end{align} If the last value is barely over $1$, this means that $h$ can only be $1$.

$\endgroup$
  • $\begingroup$ Appreciate for your reply SEJPM. According to the definition, E.cardinality_pari() will gives the result of $#E(Fq)$, how long will that calculation takes? What is the link between this function and the equation used to obtain $h'$ described in standard, $h′=[((p1/2+1)2)/n] $? Is the last one return 1? $\endgroup$ – Tian Dec 29 '18 at 11:25
  • $\begingroup$ @Tian E.cardinality_pari() is quite optimized, so it took a few seconds on my laptop. This answer used the more standard definition of co-factor from the answer by Squeamish Ossifrage you linked. Can you please locate the formula with $h'$ in the linked IETF draft or link the containing document? I failed to do so and thus didn't follow through on it, as I wasn't sure on a specific piece of notation. $\endgroup$ – SEJPM Dec 29 '18 at 11:30
  • $\begingroup$ sorry the notation is on the standard itself, not IETF draft. You may access here at SM2 Standard Part 1. Equation is at section 5.2.2, process (h). And from here the SM2 English Version you may access all other parts. $\endgroup$ – Tian Dec 29 '18 at 11:39
  • $\begingroup$ @Tian thanks, this clarified that $\lfloor \cdot \rfloor$ instead of normal parenthesis / brackets were meant. I have clarified on how this works in a new paragraph anyways. $\endgroup$ – SEJPM Dec 29 '18 at 11:45
  • $\begingroup$ Awesome! Now things come all together. You really save my day. Thanks a lot. $\endgroup$ – Tian Dec 29 '18 at 11:54

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.