5
$\begingroup$

Is there the way to generate new Koblitz curves, over $\mathbb F_{2^n}$ and $\mathbb F_p$?

The Certicom SEC 2 standard says:

The recommended parameters associated with a Koblitz curve were chosen by repeatedly selecting parameters admitting an efficiently computable endomorphism until a prime order curve was found.

What does "efficiently computable endomorphism" mean? Maybe it means that trace of the Frobenius map should be equal 1? I am confused about all the Frobenius maps, endomorphisms, traces, etc.

So, is there the way to generate Koblitz curves, or find efficiently computable endomorphisms?

$\endgroup$
6
$\begingroup$

The paper introducing the application of endomorphisms in arbitrary curves to cryptography was Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone, ‘Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms’, in Joe Kilian, ed., Proceedings of Advances in Cryptology—CRYPTO 2001, Springer LNCS 2139, pp. 190–200, after the initial idea of Neil Koblitz, ‘CM-Curves with Good Cryptographic Properties’, in Joan Feigenbaum, ed., Proceedings of Advances in Cryptology—CRYPTO 1991, Springer LNCS 576, 1991, pp. 279–287 (after whom the class of curves with efficient endomorphisms is named) to exploit the Frobenius endomorphism when it has trace 1 in binary curves.

The basic idea is that sometimes there is a scalar $\lambda$ such that computing $[\lambda]P$ given the $(x, y)$ coordinates of a point $P$ on the curve can be computed much more efficiently than by the standard double-and-add algorithm on the binary expansion of $\lambda$.

Here's a class of examples. Let $p \equiv 1 \pmod 3$ be a prime, and let $$E/\mathbb F_p\colon y^2 = x^3 + b$$ be an elliptic curve over the finite field $\mathbb F_p$ of $p$ elements. Suppose $\beta \in \mathbb F_p$ is an element of order 3, so that $\beta^3 \equiv 1 \pmod p$. The map $f\colon (x, y) \mapsto (\beta x, y)$ (and $f\colon \mathcal O \mapsto \mathcal O)$ is an endomorphism—if $(x, y)$ is on the curve so that $y^2 = x^3 + b$, then $$y^2 = x^3 + b = 1\cdot x^3 + b = \beta^3 x^3 + b = (\beta x)^3 + b$$ so that $(\beta x, y)$ is also on the curve. (Verifying $f(A + B) = f(A) + f(B)$ is left as an exercise for the reader.) Of course, $\beta = 1$ satisfies $\beta^3 \equiv 1 \pmod p$, but the map is interesting only if $\beta$ is a nontrivial cube root of unity, a root of $\beta^2 + \beta + 1$, which exists iff $3 \mid \phi(p) = p - 1$ so that $p \equiv 1 \pmod 3$. It turns out that if $B \in E(\mathbb F_p)$ is an element of prime order $n$, and $\lambda$ is a root of $\lambda^2 + \lambda + 1$ modulo $n$, then for any scalar $k$, $f([k]B) = [\lambda \cdot k]B$. (Obviously, this requires that $n \equiv 1 \pmod 3$ too.)

In brief, in the subgroup generated by $B$, computing $(x, y) \mapsto (\beta x, y)$, which costs only a single multiplication in the coordinate field $\mathbb F_p$, is a much cheaper way to compute $P \mapsto [\lambda]P$ than the standard double-and-add algorithm on the binary expansion of $\lambda$, which costs $H(\lambda)$ additions and $\lceil\log_2 \lambda\rceil$ doublings, where $H(\lambda)$ is the Hamming weight of $\lambda$.

To take advantage of this, for any scalar $k$, write $k \equiv k_1 + k_2 \lambda \pmod n$; then to compute $[k]P$, you can reduce it to

\begin{align*} [k]P &= [k_1 + k_2 \lambda]P \\ &= [k_1]P + [k_2]([\lambda]P) \\ &= [k_1]P + [k_2]f(P). \end{align*}

The GLV paper goes into a little more detail about how to turn this into a complete scalar multiplication algorithm. Unfortunately, the recursive decomposition of $k$ itself has costs, so the net improvement is only a modest 50% or so.

To generate a new prime Koblitz curve, or GLV curve, exploiting this particular endomorphism, lay out candidate primes $p_0, p_1, p_2 \ldots$ and curve parameters $b_0, b_1, b_2, \dots$ in some order of preference (say, primes nearest a power of two below it, and smaller parameters), and pick the first $p_i$ and $b_i$ such that

  1. $p_i$ is prime,
  2. $p_i \equiv 1 \pmod 3$,
  3. the number $\ell_i$ of $\mathbb F_{p_i}$-rational points on the curve $E/\mathbb F_{p_i}\colon y^2 = x^3 + b_i$ is prime,
  4. $\ell_i \equiv 1 \pmod 3$, and
  5. all other security criteria of interest are satisfied.

Next, pick a generator $g$ of $\mathbb F_{p_i}$, and let $\beta = g^{(p_i - 1)/3} \bmod{p_i}$; and pick a generator $h$ of $\mathbb Z/\ell_i\mathbb Z$, and let $\lambda = h^{(\ell_i - 1)/3} \bmod{\ell_i}$. These are by construction cube roots of unity, since, e.g., $\beta^3 \equiv (g^{(p_i - 1)/3})^3 \equiv g^{p_i - 1} \equiv 1 \pmod{p_i}$, and they are nontrivial because if $g$ generates $\mathbb F_{p_i}$ then it must have order $\phi(p_i) = p_i - 1$ and so $g^{(p_i - 1)/3} \not\equiv 1 \pmod{p_i}$. Since there are two nontrivial cube roots of unity in each group, they may be mismatched like socks: you may have to use $\ell_i - \lambda - 1$ instead, or $p_i - \beta - 1$ instead, to make them match.

For binary Koblitz curves, see Koblitz's original paper. The endomorphism in this case, on the $\mathbb F_{2^m}$-rational points, is the Frobenius map $f\colon (x, y) \mapsto (x^{2^m}, y^{2^m})$, with which $[2^m]P$ can be computed by $f(P) - f^2(P)$. The trick is to find an appropriate extension field $\mathbb F_{2^m}$ over one of the four curve shapes $y^2 + x y = x^3 + a x^2 + b$ where $a, b \in \{0,1\}$.

$\endgroup$
  • $\begingroup$ one additional note: There must be $n = 1 (mod 3) $ in order that $\lambda^2 +\lambda +1 = 0$ has a solution. $\endgroup$ – user27950 Jul 9 '18 at 4:58
  • $\begingroup$ Hi, I am very grateful for your exhausting asnwer! Now I want to try to make generator of these types of curves. Honestly, this mathematics isnt perfectly clear to me but still, thanks! $\endgroup$ – Daniel Herbrych Jul 11 '18 at 15:43
  • $\begingroup$ @DanielHerbrych Perhaps you could elaborate on what you hope to achieve with a custom Koblitz curve or an efficiently computable endomorphism? What application do you have in mind that is not served by, say, secp256k1? Or, if you're not clear on computing endomorphisms, why are you concerned with it at all instead of just using, say, X25519 for DH or Ed25519 for signatures? $\endgroup$ – Squeamish Ossifrage Jul 11 '18 at 16:38
  • $\begingroup$ @SqueamishOssifrage I wanted efficiently computable endomorphism to get Koblitz curves, but by my own. I'm interested in searching new curves generally. I tried curves with CM method and random approach. Now I just want to next kind - Koblitz... $\endgroup$ – Daniel Herbrych Jul 12 '18 at 11:16

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.