9
$\begingroup$

The popular ECC parameters secp256k1 are documented in SEC2 as using curve $y^2\equiv x^3+a\cdot x+b\pmod p$ with $a=0$, $b=7$, $p=2^{256}-2^{32}-\mathtt{3d1_h}$, base point $G$ with the apparently haphazard $(x,y)$ coordinates (hex)

79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

and order $n=2^{256}-\mathtt{14551231950b75fc4402da1732fc9bebf_h}$, cofactor $h=1$.

However, it turns out that $G$ is $G'+G'$ with $G'$ having $(x',y')$ coordinates (hex)

00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
c0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c

which is easily computable as $\displaystyle\frac{n+1}2\times G$. The 90 leading zero bits in $x'$ show beyond doubt that this is a deliberate choice. What does it allow (faster computation, attack..)?

As an aside: is it known how $x'$ was chosen? The earliest mentions of that number that I could find are in this answer (January 5, 2015) without mention of its property, and in this challenge (date unknown but it existed on June 5, 2015) where its property is meaningful.

Update: I notice that the generator of secp224k1 is also twice a $G'$ with the very same anomalously small $x'$ as above (this time with 58 leading zero bits, which is still remarkable). I found nothing similar about the generator of secp192k1 or secp160k1. I did not check other SEC curves (but secp112r1 secp112r2 secp128r1 secp128r2 secp160r1 secp160r2 secp192r1 secp224r1 secp256r1 secp384r1 secp521r1 are reportedly verifiably random, thus nothing similar should occur).


The special form of $G$ seems to allow some perceptible speedup when computing $k\times G$ for arbitrary $k$ by some elementary methods. We can rewrite $k\times G$ as $(2k\bmod n)\times G'$, and the frequent point additions of $G'$ or ($-G'$) occurring in left-to-right binary scan of the scalar multiplier can be sped up a little (at least when using affine, projective or Jacobian coordinates), because multiplication by $x'$ occurs in the point additions, and some of the word multiplications can be skipped.

However, I do not know if the fastest methods used in practice can take advantage of the special form of $G$ (or what these methods are).

$\endgroup$
  • 1
    $\begingroup$ Also, why not pick $G'$ in the first place? If its smallness means simplified attack - then that's also a concern for $G$ in half the cases ... $\endgroup$ – Hagen von Eitzen Jun 30 '18 at 13:52
  • $\begingroup$ if the intention is speedup, why then isn't this not made public in the first place? $\endgroup$ – user27950 Jun 30 '18 at 15:05
  • 1
    $\begingroup$ @Cryptostase: One theory could be that the special form of $G$ was deliberately hidden to keep a small speed edge on the competition. Another could be that $G$ what deliberately chosen of the form $2\times G'$ by analogy with the habit of choosing generator $g={g'}^2\bmod p$ in $\Bbb Z_p^*$ with $p$ a safe prime, which makes $g$ a generator of the subgroup of the quadratic residues (though I know no analog to quadratic residues on Elliptic Curve groups, thus no rational reason to do this); and $G'$ was accidentally/lazily chosen small. $\endgroup$ – fgrieu Jun 30 '18 at 15:17
  • $\begingroup$ have you also checked the other Certicom curves for "hidden relations" ? $\endgroup$ – user27950 Jun 30 '18 at 17:36
  • $\begingroup$ I think the formula must be $G' = (n+1)/2 * G$ $\endgroup$ – user27950 Jul 1 '18 at 5:34
6
$\begingroup$

One thing we know is that it doesn't allow any special attack.

Let us assume that we knew a special point $G$ that makes computing the discrete log easy, that is, given $xG$, it's easy (or at least, easier than expected) to recover $x$.

Then, given $H$ and $xH$, here's what we could do; we know that $H = yG$ for some $y$ (as $G$ is a generator), and so we can use our special purpose discrete log problem to recover $y$. Similarly, we have that $xH = zG$ for some $z$, again, we can recover $z$. So, we have $x(yG) = zG$, or $x = y{-1}z$; that immediately gives us the value $x$.

Hence, if they knew a 'weak point' $G$, that would imply that the entire curve is weak. Since we don't believe that, we can assume that their special value $G$ is no weaker than any other point (as long as $G$ generators the entire group, which is true in this case)

$\endgroup$
  • $\begingroup$ The discrete log problem is only one aspect. It could make ECDH or ECDSA weak without making discrete log weak. $\endgroup$ – user27950 Jun 30 '18 at 17:43
  • $\begingroup$ @Cryptostase: is there a known method for that? Do we know something precise that would go wrong if using the generator $(x=1,y=$4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee$)$? This one makes more savings.. $\endgroup$ – fgrieu Jun 30 '18 at 17:47
  • 1
    $\begingroup$ I don't know but I would also not exclude the existence of hidden weaknesses only known to few people. $\endgroup$ – user27950 Jun 30 '18 at 17:50
  • $\begingroup$ @Cryptostase: actually, similar (but somewhat more complex) logic applies to ECDH. In any case, if you assume a hidden weakness known to a few people, that means that the entire curve is weak (to those few people); hence they'd be silly to publish their special 'weak' point (as that'd give a clue to everyone else where to look) $\endgroup$ – poncho Jun 30 '18 at 19:09
  • $\begingroup$ @poncho: You are probably right. But I am not comfortable if someone choses cryptographic parameters without a rationale (e.g. giving a proof of random generation). If in addition to that also some hidden structure is detected then trust is almost completely lost. $\endgroup$ – user27950 Jun 30 '18 at 19:19
2
$\begingroup$

Information on how the specific base point was chosen is scarce. If you look at SEC1 (section 3.1.3.2), you will find a pseudo-random method in which a given seed is hashed (along with some parameters, in particular a counter value) into a bit string, which is then interpreted as the $X$ coordinate of the candidate point (if there is no valid point with that $X$ coordinate, the counter is incremented and a new candidate $X$ is obtained, and so on).

If you are doing that in the late 1990s, i.e. before the invention of the SHA-2 functions, chances are that you will use SHA-1 (or possibly RIPEMD-160), with a 160-bit output, in which case you naturally get a "short" $X$.

Now, in the case of secp256k1, we see that the $X$ coordinate is slightly longer (it has length 166 bits, not 160); moreover, the actual generator is twice the point you obtain with the $X$ above. The algorithm in SEC 1 calls for multiplying the candidate point with the cofactor $h$, but, for secp256k1, this cofactor is $1$, not $2$.

My guess is that the following happened:

  • In the mid-1990s, some people involved in defining new standard curves (which would happen under the aegis of SECG starting in 1998) tried to generate verifiably random curve elements.

  • These people were working notably on curves over binary field, in particular the famous Koblitz curves ($y^2 + xy = x^3 + ax^2 + 1$, with $a = 0$ or $1$, in $\mathbb{F}_{2^m}$). Such curves have an even cofactor, in practice $2$ or $4$. The algorithm expressed in SEC 1 will then produce (with SHA-1) a "short $X$" point, and there would be a multiplication of the point by 2.

  • Somebody, at some point, worked over the other kind of Koblitz curves, those that are over prime fields ($y^2 = x^3 + b$ over $\mathbb{F}_p$, with $p$ prime and $p = 1 \bmod 3$). Curve secp256k1 is of that kind. By analogy with the first kind of Koblitz curves, the same generating code may have been imported "as is", or with only a slight variant, and including the final multiplication by 2 of the point, which is not needed (but harmless) for a prime order curve.

  • It is probable that however the points were initially chosen, they just "stuck". This is a common phenomenon: once some test values have been disseminated, it is very very hard to correct them afterwards, because that would imply that several people must fix their code accordingly. This won't happen if there is not a good reason to do so. And, as @poncho points out, the general understanding is that the choice of the generator has no significance for security, and cannot be "backdoored", and thus does not require verifiable randomness.

We may note that SEC1 and SEC2 were not the last word on curve standardization; most of it was lifted into ANSI X9.62, and also in IEEE p1363, and also into FIPS 186-4. In FIPS 186-4, the curve parameter selection was described again, but only for the curves that NIST was interested on, and these do not include secp256k1 (they have Koblitz curves on binary fields, not on prime fields). Even for the NIST curves such as secp256r1 (P-256), the generator is not explained: section D.1.1.5 of FIPS 186-4 even says:

Any point of order n can serve as the base point. Each curve is supplied with a sample base point $G = (G_x, _y)$. Users may want to generate their own base points to ensure cryptographic separation of networks. See ANS X9.62 or IEEE Standard 1363-2000.


Summary: exactly how the base point was generated is lost in the mists of time. For the last two decades, this was considered as "not very important" and people did not bother even keeping track of the method; they just recopied the values from standard to standard, and from implementation to implementation. My guess is that, at the source, some hashing with SHA-1 was involved, explaining the "short values". These were later rediscovered and exploited to get some (very slight) performance improvement in some operations.

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