1
$\begingroup$

I reviewed all the curves in http://www.secg.org/SEC2-Ver-1.0.pdf . All the secp*k* curves have the $a$ parameters as 0 and those are the only ones with the $a$ as 0.

Is this a defining requirement of a Koblitz curve - that the $a$ parameter must be 0?

http://www.secg.org/SEC2-Ver-1.0.pdf#page=10 says the following:

The name Koblitz curve is best-known when used to describe binary anomalous curves over $\mathbb{F}_{2^m}$ which have $a, b \in {0, 1}$. Here it is generalized to refer also to curves over $\mathbb{F}_{P}$ which possess an efficiently computable endomorphism

While $a, b \in {0, 1}$ appears to be true for $\mathbb{F}_{2^m}$ it does not appear to be true for $\mathbb{F}_{P}$. In particular, $b$ is not $1$ in any of these curves. In secp224k1 it's $5$. In secp256k1 it's $7$. Maybe the generalization allows for $a \in {0, 1}$ whilst requiring $b = 0$ in $\mathbb{F}_{P}$? Maybe in the generalization $a = 0$ is a requirement? Or maybe the fact that $b = 0$ in all these curves is still, despite the generalization, is none-the-less by random happenstance?

$\endgroup$
  • $\begingroup$ See line 3-4 on the page labelled 4 (PDF page 10). $\endgroup$ – dave_thompson_085 Mar 25 '18 at 6:03
  • $\begingroup$ @dave_thompson_085 - what they say doesn't make a lot of sense to me. I edited my question to explain why. $\endgroup$ – neubert Mar 25 '18 at 11:02
3
$\begingroup$

Neal Koblitz is an actual person who did more than one thing in his life. Notably, he proposed several types of curves, which are all "Koblitz curves", but not necessarily all following the same rules.

Generally speaking, the "Koblitz curves" we are talking about have a common property which is that they have an efficiently computable non-trivial endomorphism. An endomorphism $\phi$ maps a curve point to another curve point, with the property that for any two curve points $P$ and $Q$, then $\phi(P+Q) = \phi(P) + \phi(Q)$. When working over a curve of prime order $n$ (or a subgroup of the curve, of prime order $n$), then an efficient endomorphism $\phi$ is necessarily equivalent to multiplying by a given scalar $k$. The endomorphism is said to be "efficient" if it can be computed faster than usual multiplication of a point by a scalar.

On binary fields $\mathbb{F}_{2^m}$, Koblitz proposed curves that are actually defined over $\mathbb{F}_2$. In $\mathbb{F}_2$, there are only two values, $0$ and $1$. Thus, the curve equation $y^2 + xy = x^3 + ax^2 + b$ must be such that both $a$ and $b$ are in $\mathbb{F}_2$, i.e. are $0$ or $1$. Then, that curve equation is used over the field $\mathbb{F}_{2^m}$, which is an extension of degree $m$ over $\mathbb{F}_2$ (we usually use a prime $m$). Such a curve has some interesting property:

  • Its order is easy to compute. No Schoof/SEA shenanigans, just some plain additions and multiplications.

  • Since $\mathbb{F}_2 \subset \mathbb{F}_{2^m}$, the curve on $\mathbb{F}_2$ is a subgroup of the curve on $\mathbb{F}_{2^m}$. Hence, the order of the latter must be a multiple of the order of the former. This prevents the full curve from having prime order. If $m$ is prime, though, then it is possible to have the full curve order be the product of a big prime with either $2$ or $4$, which is considered good enough for cryptography. Indeed, the order of the curve over $\mathbb{F}_2$ is $2$ if $a = b$, $4$ if $a \neq b$.

  • If $b = 0$ then the curve is singular and various problems occur (and it's not good for cryptography). So we can assume that $b = 1$.

  • The efficiently computable endomorphism is $\phi(x,y) = (x^2,y^2)$. This is known as the Frobenius endomorphism. In a binary field, squaring is an automorphism (notably, $(u+v)^2 = u^2 + v^2$, for all values $u$ and $v$), which makes that operation "compatible" with the curve equation, as long as $a^2 = a$ and $b^2 = b$, which is the case since we chose both values to be $0$ or $1$.

  • Applying the Frobenius endomorphism $m$ times brings you back to the original point. This, in fact, defines $m$ endomorphisms. A consequence is that it reduces difficulty of discrete logarithm by $(\log m)/2$ bits, which is not a big deal (it means with with $m = 283$, you do not get "141-bit security" but closer to "136-bit security").

The endomorphism can be used for an efficient point multiplication in which point doubling is replaced with application of the Frobenius endomorphism.

On prime order fields $\mathbb{F}_p$, with $p = 1 \bmod 3$ a prime number, Koblitz proposed equation $y^2 = x^3 + b$ (i.e. $a = 0$ in the usual short Weierstraß equation):

  • Since $p = 1 \bmod 3$, then there are three distinct cubic roots of $1$ in the field. One of them is $1$. Let's call $u$ another cubic root of $1$; the third cubic root is then $u^2$. The roots are linked with the relation $1 + u + u^2 = 0$.

  • The efficient endomorphism is $\phi(x, y) = (ux, y)$. You can trivially verify that for any point $P$, $\phi(P)$ is indeed a curve point. Less trivially (you have to work it through the addition formulas), this is indeed an endomorphism.

  • The endomorphism can be used for speed up point multiplications, but not as much as the Frobenius endomorphism in the binary case. The reason is that applying $\phi$ only three times brings you back to the start point. In that sense, it is "less powerful" than the point doubling operation, and cannot be used to replace all doublings in a multiplication. It can still help avoiding half of the doublings; this is known as a GLV curve. This optimization is not often implemented because it has a few hidden costs and is hard to do with pure constant-time code.

  • If we use the same equation with a prime $p$ such that $p = 2 \bmod 3$ then we get a supersingular curve, with exactly $p+1$ points. Such a curve allows for efficient pairing computations with a very small embedding degree (only $2$, since $p^2-1$ is a multiple of $p+1$). In other words, you need a much larger $p$ to achieve decent security, and that kills performance; this is done only if you want a pairing for advanced things such as identity-based encryption. Even for that, there are better pairing-friendly curves (e.g. Barreto-Naehrig).


Both types of curves are "Koblitz curves", but certainly not the same kind of curve.

In practice, curves on binary fields are being abandoned, because it turned out that we don't have a good intuition about what happens on binary fields, and cryptographers got afraid and panicked. They may be back, much later on, when the current generation has died away. The other type of Koblitz curves, on prime fields, is well alive and kicking; for instance, the main curve in Bitcoin is secp256k1, with equation $y^2 = x^3 + 7$.

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