Published in:

Open Access 2022 | OriginalPaper | Chapter

6. Elliptic Curve

Author : Zhiyong Zheng

Published in: Modern Cryptography Volume 1

Publisher: Springer Singapore

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Patentsearch

Off

Abstract

In 1985, mathematician v. Miller introduced elliptic curve into cryptography for the first time. In 1987, mathematician N. Koblitz further improved and perfected Miller’s work and formed the famous elliptic curve public key cryptosystem. Elliptic curve public key cryptosystem, RSA public key cryptosystem and ElGamal public key cryptosystem based on discrete logarithm are recognized as the three major public key cryptosystems, which occupy the most prominent position in modern cryptography. Compared with RSA cryptography, elliptic curve cryptography can provide the same or higher level of security with a shorter key; compared with ElGamal cryptosystem, they are based on the same mathematical principle and are essentially based on discrete logarithm cryptosystem. ElGamal cryptosystem is based on the discrete logarithm of multiplication group over finite field, and elliptic curve cryptosystem is based on the discrete logarithm of Mordell group of elliptic curve over finite field, but choosing elliptic curve has more flexibility than choosing finite field, so elliptic curve cryptosystem has attracted more attention This paper systematically and comprehensively introduces elliptic curve cryptography from the three aspects of cryptography mechanism and factorization, in order to make readers better understand and master this public key cryptography mechanism.

6.1 Basic Theory

The working platform of this chapter is a field E, especially $E=\mathbb {R}$(real number field), $E=\mathbb {C}$(complex field), $E=\mathbb {Q}$(rational number field) or $E=\mathbb {F}_{q}$(Finite field of q elements) four common fields. The characteristic $\chi (E)$ of a field E is the order of the multiplicative unit element e of E in the additive group. That is, $\chi (E)=o(e)$ is a prime number or $\infty $, specifically,

$$ \chi (E)= {\left\{ \begin{array}{ll}\infty , &{} \text {if}~E=\mathbb {C}, \mathbb {R}, \mathbb {Q},\\ p, &{} \text {if}~E=\mathbb {F}_{q}, q=p^{r}. \end{array}\right. } $$

Definition 6.1

(i) Suppose E is a field, the character of E $\chi (E)\ne 2, 3, f(x)=x^{3}+ax+b\in E[x]$ is a cubic polynomial and has no multiple roots in the split field. An elliptic curve in field E refers to the set of finite points $(x,y)\in E^{2}$ plus infinity on the “plane,” where the finite point (x, y) satisfies

$$y^{2}=x^{3}+ax+b, \text {where}~a\in E, ~b\in E~\text {given}.$$

$C_{E}$ represents the elliptic curve, and “O” represents the infinity point, i.e.,

$$\begin{aligned} C_{E}=\{(x,y)\in E^{2}|y^{2}=x^{3}+ax+b\}\cup \{O\}. \end{aligned}$$

(6.1)

(ii) If $\chi (E)=2$, then an elliptic curve $C_{E}$ on the field E with the characteristic of 2 is defined as

$$\begin{aligned} C_{E}=\{(x,y)\in E^{2}|y^{2}+y=x^{3}+ax+b\}\cup \{O\}. \end{aligned}$$

(6.2)

(iii) If $\chi (E)=3$, $x^{3}+ax^{2}+bx+c\in E[x]$ has no multiple roots in the split field, then an elliptic curve $C_{E}$ on E is defined as

$$\begin{aligned} C_{E}=\{(x,y)\in E^{2}|y^{2}=x^{3}+ax^{2}+bx+c\}\cup \{O\}. \end{aligned}$$

(6.3)

Let $F(x,y)\in E[x,y]$ be a bivariate polynomial, then $F(x,y)=0$ defines an algebraic curve C on E. $(x_{0},y_{0})\in C$ is called a nonsingular point on C, if at least one of the partial derivatives $\frac{\partial F}{\partial x}$ and $\frac{\partial F}{\partial y}$ at $(x_{0},y_{0})$ is not 0. If $\chi (E)\ne 2,3$, let $f(x)=x^{3}+bx+c$, then the finite points of an elliptic curve $F(x,y)=y^{2}-f(x)=0$ on E are nonsingular points, which is the same as that in $\chi (E)=2$, $\chi (E)=3$. Therefore, an elliptic curve is also called a nonsingular cubic curve.

Among many profound arithmetic properties of elliptic curves, Mordell group on elliptic curves is the most beautiful and important basic property. Firstly, we introduce Mordell group when $E=\mathbb {R}$ is familiar with real number field and then extend it to finite field.

Elliptic curve over real number field

Definition 6.2

Let $E=\mathbb {R}$ be real number field, $C_{E}$ is an elliptic curve, P and Q are two points on $C_{E}$, that is $P\in C_{E}$, $Q\in C_{E}$, we define addition according to the following rules:

(1) If $P=O$ is infinity, define that $P+P=O$ is still infinity; that is, infinity is the unit element of addition, and the negative element of P is $-P=P=O$.

(2) If $P=(x,y)\in C_{E}$ is a finite point. Define $-P=(x,-y)$, obviously, $-P\in C_{E}$, is the specular reflection point of point P on the $xy-$plane.

(3) If $P,Q\in C_{E}$ are two finite points, they have different x-coordinates $(\text {i.e.,}P=(x_{1}, y_{1}), Q=(x_{2}, y_{2}), x_{1}\ne x_{2})$, then there is exactly a point R on the connecting line between P and Q on the $xy-$plane, which is the intersection of the connecting line and the elliptic curve, define $P+Q=-R$, is the specular reflection point of R. If Q is infinity. Then define $P+O=P$.

(4) If $Q=-P$, that is, P and Q have the same x-coordinate, and $P+Q=O$ is defined as infinity.

(5) If $P=Q$ is a finite point on $C_{E}$. Then the tangent of $C_{E}$ at P has exactly an intersection R with $C_{E}$, define $P+P=-R$.

We use the geometric construction method to define the addition on elliptic curve $C_{E}$, for the connection of finite points with different x-coordinates and why the tangent at the finite point has only a unique intersection with $C_{E}$, it needs strict mathematical proof. We attribute it to the following lemma.

Lemma 6.1

Let $P=(x_{1},y_{1}), Q=(x_{2},y_{2})$ be two finite points on elliptic curve $C_{E}$, and $x_{1}\ne x_{2}$, then

(i) The line between P and Q has only a unique intersection $R=(x_{3},y_{3})$ with $C_{E}$, satisfies $R\ne P, R\ne Q$, where

$$\begin{aligned} {\left\{ \begin{array}{ll} \ x_{3}=(\frac{y_{2}-y_{1}}{x_{2}-x_{1}})^{2}-x_{1}-x_{2}, \\ \ y_{3}=-y_{1}+(\frac{y_{2}-y_{1}}{x_{2}-x_{1}})(x_{1}-x_{3}). \end{array}\right. } \end{aligned}$$

(6.4)

(ii) Let $\alpha $ be the value of derivative $\frac{dy}{dx}$ at point P, then the tangent of point P and $C_{E}$ only have a unique intersection $R=(x_{3},y_{3})$, $R\ne P$, where

$$\begin{aligned} {\left\{ \begin{array}{ll} \ x_{3}=(\frac{3x_{1}^{2}+a}{2y_{1}})^{2}-2x_{1}, \\ \ y_{3}=-y_{1}+(\frac{3x_{1}^{2}+a}{2y_{1}})(x_{1}-x_{3}). \end{array}\right. } \end{aligned}$$

(6.5)

Proof

Let the functional equation of the connecting line between P and Q be $y=\alpha x+\beta $ on the $xy-$plane, where

$$\alpha =\frac{y_{2}-y_{1}}{x_{2}-x_{1}}, ~\beta =y_{1}-\alpha x_{1}.$$

A point $(x,\alpha x+\beta )$ on line $y=\alpha x+\beta $ is on elliptic curve $C_{E}$ if and only if

$$\begin{aligned} (\alpha x+\beta )^{2}=x^{3}+ax+b. \end{aligned}$$

(6.6)

Therefore, the three solutions of $x^{3}-(\alpha x+\beta )^{2}+ax+b=0$ are x, and each solution will produce an intersection. But we assume that P and Q are at the intersection, so there is only the third intersection $R=(x,\alpha x+\beta )=(x_{3},\alpha x_{3}+\beta )$. Because the three solutions $x_{1},x_{2},x_{3}$ of equation (6.6) satisfy the following relationship

$$x_{1}+x_{2}+x_{3}=\alpha ^{2}.$$

There is

$$ {\left\{ \begin{array}{ll} \ x_{3}=(\frac{y_{2}-y_{1}}{x_{2}-x_{1}})^{2}-x_{1}-x_{2}, \\ \ y_{3}=\alpha x_{3}+\beta =-y_{1}+(\frac{y_{2}-y_{1}}{x_{2}-x_{1}})(x_{1}-x_{3}). \end{array}\right. } $$

Thus, (6.4) holds. If point Q is infinitely close to point P, the connecting line becomes the tangent of curve $C_{E}$ at point P, now

$$\alpha =\frac{dy}{dx}|_{(x_{1},y_{1})}=\frac{3x_{1}^{2}+a}{2y_{1}}.$$

So the tangent has a unique intersection with $C_{E}$, $R\ne P$, $R=(x_{3},\alpha x_{3}+\beta )$, where

$$ {\left\{ \begin{array}{ll} \ x_{3}=\alpha ^{2}-2x_{1}=(\frac{3x_{1}^{2}+a}{2y_{1}})^{2}-2x_{1},\\ \ y_{3}=-y_{1}+(\frac{3x_{1}^{2}+a}{2y_{1}})(x_{1}-x_{3}). \end{array}\right. } $$

(6.5) holds, So as to complete the proof of Lemma (Fig. 6.1).

Example 6.1

On the real plane, we give a specific example $y^{2}=x^{3}-x$ to illustrate the addition rule on this elliptic curve:

The point of $C_{E}$ in the left half plane is called the torsion point of $C_{E}$, and the point of C in the right half plane is called the free point of $C_{E}$.

Remark 6.1

In Lemma 6.1, if $P=(x_{1},0)$, that is $y_{1}=0$, then the only intersection of the tangent of point P and $C_{E}$ is defined as the infinity point $`` O''$ .

From Definition 6.1 and Lemma 6.1, we have the following important corollaries.

Corollary 6.1

(i) All points of elliptic curve $C_{E}$ form an Abel group under addition, in which the infinity point “O” is the zero element of the group. This group is called Mordell group.

(ii) If $P=(x_{1},y_{1}),Q=(x_{2},y_{2})$ is a rational point, that is, $x_{1},y_{1},x_{2},y_{2}$ is a rational number, then another unique intersection R between the line between P and Q and $C_{E}$ is also a rational point.

Proof

(i) is directly given by Definition 6.1. Conclusion (ii) is directly derived from Formula (6.4) and Formula (6.5) of Lemma 6.1.

Elliptic curves over rational fields

Let $E=\mathbb {Q}$, then a, b, c in Definition 6.1 are rational numbers. Elliptic curves over rational number fields are one of the most important research topics in modern number theory. There are many important conclusions and famous number theory problems related to them, such as the famous “BSD” conjecture, the ancient congruence problem and so on. Mordell theorem is the most basic conclusion of elliptic curves over rational fields. Since cryptography only cares about elliptic curves over finite fields, here we briefly introduce some important results without proof.

Let $C_{E}$ be an elliptic curve in the field of rational numbers. From Corollary 6.1, all points of $C_{E}$ form an Abel group G. In algebra, an Abel group is equivalent to a module over an integer ring, so an Abel group is also called $\mathbb {Z}-$module. The Mordell group on elliptic curve $C_{E}$ is regarded as a $\mathbb {Z}-$module G, according to the decomposition theorem of modules on the principal ideal ring, a $\mathbb {Z}-$module can be decomposed into the direct sum of a twisted module and a free module. Therefore, the Mordell group G on $C_{E}$ has

$$G=Tor(G)\oplus Free(G).$$

Mordell first proved the following important conclusions. Mordell Theorem: The Abel group G on elliptic curve $C_{E}$ ($E=\mathbb {Q}$ is a rational number field) is finitely generated; in other words, G is a finitely generated $\mathbb {Z}$-module. Therefore, Mordell group G can be decomposed into

$$G=Tor(G)\oplus \mathbb {Z}(\alpha _{1},\alpha _{2},\ldots ,\alpha _{r}).$$

where $\alpha _{1},\alpha _{2},\ldots ,\alpha _{r}$ is a set of bases of free module Free(G) and r is the rank of free module. The rank r is only known to be finite, but how to calculate it is a famous number theory problem. The so-called BSD conjecture holds that r can be given by the function value of L-function on elliptic curve, but it has not been fully proved at present.

Another problem related to elliptic curves is the ancient congruence problem, which can be traced back to Plato’s time in ancient Greece.

The congruent number problem: if $n>1$ is a positive integer, is there a right triangle with rational side length, and its area is exactly n?

This problem is equivalent to the rank $r>0$ of elliptic curve $y^{2}=x^{3}-n^{2}x$, at present, this problem has not been completely solved. Chinese mathematicians prof. Tian Ye have made substantial progress in this problem.

Elliptic curves over finite fields

Let $E=\mathbb {F}_{q}$ be a q-element finite field, $q=p^{r}$, and p be a prime number. Let

$$\begin{aligned} F(x,y)= {\left\{ \begin{array}{ll}y^{2}-f(x),\quad \ \ &{} \text {if}~p\ne 2,\\ y^{2}+y-f(x),\quad \ \ &{} \text {if}~p=2. \end{array}\right. } \end{aligned}$$

(6.7)

where

$$\begin{aligned} f(x)= {\left\{ \begin{array}{ll}x^{3}+ax+b,\quad \ \ &{} \text {if}~p\ne 2,\\ x^{3}+ax^{2}+bx+c,\quad \ \ &{} \text {if}~p=2. \end{array}\right. } a,b,c\in \mathbb {F}_{q}. \end{aligned}$$

(6.8)

Then an elliptic curve $C_{E}$ on $\mathbb {F}_{q}$ is defined as

$$\begin{aligned} C_{E}=\{(x,y)\in \mathbb {F}_{q}^{2}|F(x,y)=0\}\cup \{O\}. \end{aligned}$$

(6.9)

where $``O''$ is the infinity point.

Obviously, the number of points in $C_{E}$ is limited, let $N_{q}=|C_{E}|$, be called the number of points of elliptic curve in $\mathbb {F}_{q}$. $N_{q}\le 2q+1$ is a trivial estimate, because each $x\in \mathbb {F}_{q}$ has at most two y values, together with the infinity point. The more accurate estimation of $N_{q}$ depends on the Riemann hypothesis on the field of univariate algebraic functions proved by A. Weil, which is a very profound result in mathematics. A. Hasse proved the following results when F(x, y) is an elliptic curve.

Theorem 6.1

(Hasse Theorem) Let $N_{q}$ be the number of elliptic curve $F(x,y)=0$ at the midpoint of $\mathbb {F}_{q}$, then we have

$$|N_{q}-(q+1)|\le 2\sqrt{q}.$$

Proof

Let $\chi $ be a quadratic real feature in $\mathbb {F}_{q}$, that is

$$ \chi (a)= {\left\{ \begin{array}{ll}0,\quad \ \ &{} \text {if}~a=0, \\ 1,\quad \ \ &{} \text {if}~a=b^{2},b\in \mathbb {F}_{q}, \\ -1,\quad \ \ &{} \text {otherwise}. \end{array}\right. } $$

By definition, it is obvious that the number of solutions of $u^{2}=a$ in $\mathbb {F}_{q}$ is $1+\chi (a)$, so suppose $N_{q}$ is the number of solutions of elliptic curve $F(x,y)=0$ in $\mathbb {F}_{q}$, where F(x, y) is given by Eq. (6.7), then

$$\begin{aligned} {\begin{matrix} N_{q}&{}=1+\sum _{x\in \mathbb {F}_{q}}(1+\chi (x^{3}+ax+b))\\ &{}=q+1+\sum _{x\in \mathbb {F}_{q}}\chi (x^{3}+ax+b). \end{matrix}} \end{aligned}$$

(6.10)

We use $\mathbb {F}_{q}(x)$ to represent the rational function field on $\mathbb {F}_{q}$, then the univariate algebraic function field defined by $y^{2}=f(x)$ can be regarded as a quadratic finite extension field on $\mathbb {F}_{q}(x)$. The genus d of this function field is $d=3$. Hasse can prove that the Riemann hypothesis on this special algebraic function field is true; that is, all zeros of the corresponding Riemann $\xi -$function lie on the straight line of $s=\frac{1}{2}+it$. A special case of this conclusion is

$$\begin{aligned} |\sum _{x\in \mathbb {F}_{q}}\chi (x^{3}+ax+b)|\le (d-1)\sqrt{q}=2\sqrt{q}. \end{aligned}$$

(6.11)

By (6.10),

$$|N_{q}-(q+1)|\le 2\sqrt{q}.$$

We have completed the proof.

Remark 6.2

(6.11) is called the characteristic sum over a finite field, so that $g(x)\in \mathbb {F}_{q}[x]$ is any polynomial and $\chi $ is any nontrivial multiplication characteristic over $\mathbb {F}_{q}$, according to A. Weil’s famous theorem, we have the following general characteristics and estimates,

$$|\sum _{x\in \mathbb {F}_{q}}\chi (g(x))|\le (\deg g-1)\sqrt{q}.$$

Let’s briefly introduce A. Weil’s theorem. Let $\mathbb {F}_{q^{n}}$ be an n-th extension on $\mathbb {F}_{q}$, that is $n=[\mathbb {F}_{q^{n}}:\mathbb {F}_{q}]$. $N_{q^{n}}$ is the number of solutions of elliptic curve $F(x,y)=0$ in extended field $\mathbb {F}_{q^{n}}$. Zeta function $Z(T, C_{E})$ on elliptic curve $C_{E}$ is defined as the formal power series of T:

$$\begin{aligned} Z(T)=Z(T, C_{E})=\exp (\sum _{n=1}^{+\infty }\frac{1}{n}N_{q^{n}}T^{n}). \end{aligned}$$

(6.12)

where $\exp (a)=e^{a}$ is an exponential function. A. Weil proves that Z(T) is a rational function, i.e.,

$$\begin{aligned} Z(T)=\frac{qT^{2}-\alpha T+1}{(1-T)(1-qT)}. \end{aligned}$$

(6.13)

where $\alpha $ is an integer depends on elliptic curve $C_{E}$. In fact, the above formula is valid for general algebraic curves. Because of $N_{q}=q+1-\alpha $, and $\alpha ^{2}-4q<0$ (Hasse theorem). Therefore, zeta function Z(T) has two complex roots, that is, the two solutions $\alpha _{1}$ and $\alpha _{2}$ of $q T^{2}-\alpha T+1=0$, and $|\frac{1}{\alpha _{1}}|=|\frac{1}{\alpha _{2}}|=\sqrt{q}$. This is the Riemann hypothesis on elliptic curves. A. Weil proved it on general algebraic curves for the first time. See Chap. 5 of Silverman (1986 of reference 6) for the specific proof process.

From the above a. Weil theorem, take logarithms on both sides of Eq. (6.12) and compare the coefficients on both sides of the formal power series. Let $N_{q^{n}}$ be the number of points of the elliptic curve in $\mathbb {F}_{q^{n}}$, then

$$\begin{aligned} |N_{q^{n}}-(q^{n}+1)|\le 2q^{\frac{n}{2}}(n\ge 1). \end{aligned}$$

(6.14)

The above formula can also be derived directly from Hasse theorem.

Now let’s look at a specific elliptic curve in $\mathbb {F}_{2}$, $y^{2}+y=x^{3}$; thus, we have a better understanding of A. Weil’s theorem. Because $F(x,y)=y^{2}+y-x^{3}=0$ has three points in $\mathbb {F}_{2}$, the zeta function on the elliptic curve,

$$\begin{aligned} {\begin{matrix} Z(T)&{}=\exp (\sum _{n=1}^{+\infty }\frac{N_{n}}{n}T^{n})\\ &{}=\frac{2T^{2}+1}{(1- T)(1-2T)}. \end{matrix}} \end{aligned}$$

Write $2T^{2}+1=(1-\alpha _{1}T)(1-\alpha _{2}T)$, where $\alpha _{1}=i\sqrt{2}$, $\alpha _{2}=-i\sqrt{2}$. Take logarithms on both sides of the above formula and compare the coefficients of $T^{n}$ on both sides,

$$ N_{n}= {\left\{ \begin{array}{ll}2^{n}+1,\quad \ \ &{} \text {if}~n\text {~is odd}, \\ 2^{n}+1-2(-2)^{\frac{n}{2}},\quad \ \ &{} \text {if~}n\text {~is even}. \end{array}\right. } $$

Where $N_{n}$ represents the number of points of elliptic curve $y^{2}+y=x^{3}$ in $\mathbb {F}_{2^{n}}$.

Finally, the Mordell group of elliptic curve on $\mathbb {F}_{q}$ is a finite Abel group of order $N_{q}$; according to the classification theorem of finite Abel groups, this group can be expressed as the direct sum of two cyclic groups, which will be further explained when necessary.

6.2 Elliptic Curve Public Key Cryptosystem

An elliptic curve over a finite field $\mathbb {F}_{q}$ forms a finite Abel group G, which is similar to $\mathbb {F}_{q}^{*}$; therefore, the elliptic curve public key cryptosystem can be constructed by using discrete logarithm. Compared with other public key cryptosystems based on discrete logarithm (such as ElGamal cryptosystem), elliptic curve cryptosystem has greater flexibility, because when a huge q is selected, the working platform of ElGamal cryptosystem has only one multiplication group $\mathbb {F}_{q}^{*}$, but multiple elliptic curves can be defined on $\mathbb {F}_{q}$, so there will be multiple Mordell groups to choose, and elliptic curve cryptosystem has greater concealment and security.

Before introducing elliptic curve cryptography, we first discuss the computational complexity on two species group. The computational complexity of multiplication over finite field $\mathbb {F}_{q}$ has been discussed in Chap. 4 Lemma 4.12, specially, $\alpha \in \mathbb {F}_{q}$, k is an integer, then $Time(\alpha ^{k})=O(\log k\log ^{3} q)$. In the case of elliptic curves, the Mordell group G is an addition operation, so that $P\in G$ is a point. kP means that the points P are added k times continuously.

Lemma 6.2

Let $E=\mathbb {F}_{q}$ be a q-element finite field, $C_{E}$ be an elliptic curve on $\mathbb {F}_{q}$ defined by Weierstrass equations (6.7), (6.8) and (6.9), $P\in G$, G be a Mordell group on $C_{E}$, then for any integer k,

$$ {\left\{ \begin{array}{ll} \ Time(k P)=O(\log k\log ^{3} q), &{} \text {if~}k\le N_{q}; \\ \ Time(k P)=O(\log ^{4} q), &{} \text {if~}k>N_{q}. \end{array}\right. } $$

where $N_{q}$ is the number of points of curve $C_{E}$ and the order of Mordell group G.

Proof

Let $P=(x,y),y\ne 0$, then $P+P=(x',y')$, where $x'$ and $y'$ are determined by Equation (6.5), (6.5) (addition, subtraction, multiplication, division, etc.) involved in the formula shall not exceed 20 calculations, and the bit operation times of each calculation is $O(\log ^{3} q)$. By the “repeated square method,” kP can be transformed into $\log k$ steps, thus

$$Time(k P)=O(\log k\log ^{3} q).$$

If $y=0$, defined by $P+P=O$ and “repeated square method,” there is $Time(kP)=O(\log k)$.

If $k>N_{q}$, because $N_{q}\cdot P=0$, let $k=s\cdot N_{q}+r$, $1\le r\le N_{q}$, thus $kP=rP$. We can calculate rP. Thus

$$Time(kP)=O(\log N_{q}+\log N_{q}\log ^{3} q)=O(\log ^{4} q).$$

We use Hasse’s theorem: $N_{q}=q+1+O(\sqrt{q})$, there is $N_{q}=O(q)$, thus

$$ \log N_{q}=O(\log q).$$

Lemma 6.2 holds.

Secondly, we consider how to correspond a plaintext unit m to a point on a given elliptic curve $C_{E}$, which is a necessary premise for encryption using elliptic curve. Unfortunately, there is no definite algorithm for polynomial bit operation, which can correspond any huge integer m to a point on any elliptic curve. Instead, we can only choose the probability algorithm with sufficiently low error probability to realize the correspondence from number to point. The so-called probability algorithm does not guarantee $100\%$ success rate $( \text {therefore, each operation depends on your luck})$, but the success probability should be large enough, that is

$$P\{\text {number to point correspondence}\}>1-\varepsilon , ~\varepsilon >0~\text {sufficient small}.$$

Next, we introduce a probabilistic algorithm to realize the correspondence from number to point, which makes theoretical preparation for the construction of elliptic curve cryptosystem.

Probabilistic algorithm

Treat each plaintext unit as an integer m, $0\le m<M$, k is an integer. Select a finite field $\mathbb {F}_{q}$, $q=p^{r}$ satisfies $q>kM$. We write the positive integer n from 1 to kM as follows,

$$\begin{aligned} 1\le n\le kM, n=mk+j, 0\le m<M, 1\le j\le k. \end{aligned}$$

(6.15)

Lemma 6.3

There is a 1-1 correspondence $\tau $ between the set of integers $A=\{1,2,\ldots , kM\}$ and a subset of finite field $\mathbb {F}_{q}(q>kM)$.

Proof

Because $q=p^{r}$, let $g(x)\in \mathbb {F}_{q}[x]$ be a monic irreducible polynomial, and $\deg g(x)=r-1$, from the finite extension theory of fields, $\mathbb {F}_{q}$ is isomorphic to a quotient ring of polynomial ring $\mathbb {F}_{p}[x]$ over subfield $\mathbb {F}_{p}$, that is

$$\mathbb {F}_{q}\cong \mathbb {F}_{p}[x]/_{<g(x)>}=\{a_{0}+a_{1}x+\cdots +a_{r-1}x^{r-1}|a_{i}\in \mathbb {F}_{p}\}.$$

Each element $\alpha \in \mathbb {F}_{q}$ uniquely corresponds to a polynomial $a_{0}+a_{1}x+\cdots +a_{r-1}x^{r-1}$, we write

$$\alpha =(a_{r-1}a_{r-2}\cdots a_{1}a_{0})_{p},$$

is called the p-ary representation of $\alpha $.

For every m, $0\le m<M$, each j, $1\le j\le k$, then it uniquely corresponds to $n=mk+j$, express n as a p-ary number, if the p-ary of n is expressed as $(a_{r-1}a_{r-2}\cdots a_{1}a_{0})_{p}$, then let $\tau (n)=\alpha \in \mathbb {F}_{q}$. The uniqueness represented by p-ary, then $\tau $ is an injection.

$$A'=\{\tau (n)|1\le n\le kM\}\subset \mathbb {F}_{q}.$$

Therefore, we establish a 1-1 correspondence $\tau $ of $A\rightarrow A'$. The Lemma holds.

Next, for each $m(0\le m<M)$, we establish a 1-1 correspondence $\sigma $ between m and the point on elliptic curve $C_{E}$. Arbitrary choice $1\le j\le k$, then $n=mk+j$ corresponds to an element in $\mathbb {F}_{q}$, that is $\tau (n)=x_{j}\in \mathbb {F}_{q}$. For each $x_{j}$, consider the solution of the following equation.

$$\begin{aligned} y^{2}=f(x_{j})=x_{j}^{3}+ax_{j}+b. \end{aligned}$$

(6.16)

If the above equation has a solution, let $y_{1}$ be one of the solutions, then $P_{m}=(x_{j},y_{1})\in C_{E}$, we let $\sigma (m)=P_{m}$, the inverse mapping $\sigma ^{-1}(P_{m})$ of $\sigma $ is

$$\begin{aligned} \sigma ^{-1}(P_{m})=[\frac{\tau ^{-1}(x_{j})-1}{k}]. \end{aligned}$$

(6.17)

where $\tau $ is the 1-1 correspondence in lemma 6.3. Because $\tau ^{-1} (x_{j})=mk+j$, so

$$[\frac{\tau ^{-1}(x_{j})-1}{2}]=[m+\frac{j-1}{k}]=m.$$

So $\sigma ^{-1}$ is exactly the inverse mapping of $\sigma $. From $\sigma $, a 1-1 correspondence between each m and the point on the elliptic curve is established. $\sigma $ is called a probabilistic algorithm.

Lemma 6.4

Probability algorithm $\sigma $ can successfully achieve probability $\ge 1-\frac{1}{2^{k}}$, that is

$$P\{\text {is generated by~}\sigma \text {~and the number~} m\text {~corresponds to 1-1 of the point}\}\ge 1-\frac{1}{2^{k}}.$$

Proof

When m, $0\le m<M$ given, $n=mk+j$, where k is any given positive integer, $1\le j\le k$. By Lemma 6.3, $\tau (n)=x_{j}\in \mathbb {F}_{q}$, then the probability that $f(x_{j})=x_{j}^{3}+ax_{j}+b$ is a square number is $\frac{1}{2}$, in other words, the probability that equation (6.16) has a solution in $\mathbb {F}_{q}$ is $\frac{1}{2}$; therefore, the probability of no solution is also $\frac{1}{2}$. We randomly and independently select j, $1\le j\le k$, the error probability of each j (no solution in Eq. (6.16)) is $\frac{1}{2}$; therefore, the error probability of k j is $\frac{1}{2^{k}}$. Once Equation (6.16) has a solution, then $P_{m}= (x_{j},y)\in C_{E}$, we can establish the 1-1 correspondence $\sigma $ between m and points on $C_{E}$, $\sigma (m)=P_{m}$. Thus

$$P\{\sigma \text {~Successfully implemented}\}\ge 1-\frac{1}{2^{k}}.$$

We complete the proof of lemma.

Remark 6.3

$f(x_{j})=x_{j}^{3}+ax_{j}+b$ is a square number, that is, the probability that Equation (6.16) has a solution is exactly $N_{q}/2q$, where $N_{q}$ is the number of points of $C_{E}$. By Hasse’s theorem, $N_{q}/2q$ is very close to $\frac{1}{2}$.

Definition 6.3

Let $C_{E}$ be an elliptic curve over a finite field $\mathbb {F}_{q}$ and $B\in C_{E}$ be a point. For any point P on $C_{E}$, if there is an integer x, such that $xB=P$, x is called the discrete logarithm of P to base B.

With the above preparation, we can establish elliptic curve public key cryptosystem.

Diffie–Hellman key conversion principle

Symmetric cryptosystem, also known as classical cryptosystem or traditional cryptosystem, is the mainstream cryptosystem before the advent of public key cryptosystem. It has high efficiency because its encryption and decryption share the same algorithm (such as DES, the data encryption standard algorithm launched by the American Bureau of standards in 1977). When Diffie and Hellman proposed asymmetric cryptosystem, they pointed out that symmetric cryptosystem and asymmetric cryptosystem are not completely separated. The two cryptosystems are interrelated and can even be used together. Diffie–Hellman key conversion principle is based on the following mathematical principles.

Lemma 6.5

Let p be a prime number, $q=p^{r}$, $\mathbb {F}_{q}$ is a q-element finite field, $\mathbb {Z}_{p^{r}}$ is the residual class ring ${{\,\mathrm{mod}\,}}p^{r}$, $\mathbb {Z}_{p}^{r}$ is an n-dimensional vector space on $\mathbb {F}_{p}$, then $\mathbb {F}_{q}$, $\mathbb {Z}_{p^{r}}$, $\mathbb {Z}_{p}^{r}$ have 1-1 correspondence with each other.

Proof

$\mathbb {F}_{q}$ is an r-th finite extension on $\mathbb {F}_{p}$, so the additive group $\mathbb {F}_{q}^{+}$ of $\mathbb {F}_{q}$ is isomorphic with $\mathbb {F}_{p}^{r}$, that is $\mathbb {F}_{q}^{+}\cong \mathbb {F}_{p}^{r}$, therefore, there is a 1-1 correspondence between $\mathbb {F}_{q}$ and $\mathbb {F}_{p}^{r}$. Each $a=(a_{0},a_{1},\ldots ,a_{r-1})\in \mathbb {F}_{p}^{r}$, define

$$\sigma (a)=a_{0}+a_{1}p+\cdots +a_{r-1}p^{r-1}\in \mathbb {Z}_{p}^{r}.$$

Then $\sigma $ is a surjection and a injection of $\mathbb {F}_{p}^{r}\rightarrow \mathbb {Z}_{p^{r}}$, so $\sigma $ is a 1-1 correspondence of $\mathbb {F}_{p}^{r}\rightarrow \mathbb {Z}_{p^{r}}$. Since there is a 1-1 correspondence between $\mathbb {F}_{q}$ and $\mathbb {F}_{p}^{r}$ and a 1-1 correspondence between $\mathbb {F}_{p}^{r}$ and $\mathbb {Z}_{p^{r}}$, there is also a 1-1 correspondence between $\mathbb {F}_{q}$ and $\mathbb {Z}_{p^{r}}$, the Lemma holds.

From the above lemma, we have the following conclusions.

Lemma 6.6

Let N be a positive integer. $\mathbb {Z}_{N}$ is a residue class ring ${{\,\mathrm{mod}\,}}N$. Then for any prime p, there is a finite field $\mathbb {F}_{p^{r}}$ such that there is an injection $\sigma $ of $\mathbb {Z}_{N}\rightarrow \mathbb {F}_{p^{r}}$, this injection is also called embedded mapping.

Proof

When N given, for any prime p, express N as a p-ary number, then exists a positive integer $r\ge 1$, such that $p^{r-1}\le N<p^{r}$. We write

$$\mathbb {Z}_{N}=\{0,1,2,\ldots , N-1\}\subset \{0,1,2,\ldots , N-1,N,\ldots , p^{r}-1\}=\mathbb {Z}_{p^{r}}.$$

That is, $\mathbb {Z}_{N}$ is regarded as a subset of $\mathbb {Z}_{p^{r}}$. Let $\mathbb {Z}_{p^{r}}{\mathop {\longrightarrow }\limits ^{\sigma }}\mathbb {F}_{p^{r}}$ be 1-1 correspond, so $\sigma $ gives that $\mathbb {Z}_{N}\rightarrow \mathbb {F}_{p^{r}}$ is an injection. The Lemma holds.

From the above conclusions, we can establish Diffie–Hellman’s key conversion principle. Because symmetric cryptographic keys are related to the numbers of $\mathbb {Z}_{N}$, each number in $\mathbb {Z}_{N}$ can be embedded into a finite field $\mathbb {F}_{q}$ by Lemma 6.6. Therefore, the discrete logarithm on $\mathbb {F}_{q}$ can encrypt each embedded number asymmetrically, so that the two cryptosystems can be combined with each other.

Taking the affine cryptosystem introduced in Chap. 4 as an example, A is a $k\times k$-order reversible square matrix in $\mathbb {Z}_{N}$, $b=(b_{1},b_{2},\ldots ,b_{k})\in \mathbb {Z}_{N}^{k}$ is a given vector, affine transformation $f=(A,b)$ gives the encryption algorithm of each plaintext unit $m=m_{1}m_{2}\cdots m_{k}\in \mathbb {Z}_{N}^{k}$.

$$ f(m)=c=A\begin{pmatrix} m_{1} \\ \vdots \\ m_{k} \end{pmatrix} +\begin{pmatrix} b_{1} \\ \vdots \\ b_{k} \end{pmatrix}. $$

Let $A=(a_{ij})_{k\times k}$, each $a_{ij}\in \mathbb {Z}_{N}$. By Lemma 6.6, we can embed $a_{ij}$ into a finite field $\mathbb {F}_{q}$. $a_{ij}$ is encrypted again by using the discrete logarithm algorithm on $\mathbb {F}_{q}$, so that the two cryptosystems can be effectively combined.

In the case of elliptic curve, we introduce the workflow of Diffie–Hellman elliptic curve cryptography. First, the user selects a public finite field $\mathbb {F}_{q}$, and an elliptic curve $C_{E}$ on $\mathbb {F}_{q}$, randomly select a point $P\in C_{E}$, let $P=(x,y)$, then $x\in \mathbb {F}_{q}$. By Lemma 6.5, x corresponds to an r-dimensional vector $(a_{0},a_{1},\ldots , a_{r-1})$ in $\mathbb {F}_{p}^{r}$ space (where $q=p^{r}$), consider $(a_{0}, a_{1},\ldots , a_{r-1})$ as a p-ary number, that is

$$(a_{0}, a_{1}, \ldots , a_{r-1})\rightarrow a_{0}+a_{1}p+\cdots +a_{r-1}p^{r-1}.$$

Then $(a_{0}, a_{1}, \ldots , a_{r-1})$ can be used as the key of other cryptosystems, especially symmetric cryptosystems.

Secondly, the user selects a common point $B\in C_{E}$, like a finite field, as the basis of the discrete logarithm on the Mordell group. The difference from finite field is that the Mordell group on elliptic curve is not a cyclic group, so point B is not the generator of Mordell group. However, we require order o(B) of B to be as large as possible ($o(B)|N_{q}$). When point B is selected, the working platform of elliptic curve cryptography is actually the subgroup $<B>$ generated by B.

In order to generate the key, each user can randomly select an integer a, whose order is roughly the same as $N_{q}$, as their own user’s private key, a should be strictly confidential. Calculate $aB=A\in C_{E}$. Point A is the public key of each user. Now each user has its own public key (A, B) and private key (a, B).

Massey–Omura elliptic curve cryptography.

In order to encrypt and send a plaintext unit $m(0\le m<M)$, m is corresponding to the only point $P_{m}\in C_{E}$ on elliptic curve $C_{E}$ by using the probability algorithm introduced earlier. Let $N=N_{q}=|C_{E}|$; that is, the order of Mordell group is known. Each user randomly selects an integer e to satisfy

$$1\le e\le N, \text {and}~(e,N)=1.$$

$d=e^{-1}{{\,\mathrm{mod}\,}}N$ is calculated by Euclidean rolling division method, that is

$$de\equiv 1({{\,\mathrm{mod}\,}}N), \text {and}~1\le d\le N.$$

Suppose user A wants to encrypt and send plaintext message $P_{m}$ to user B, so that $(e_{A},d_{A})$ and $(e_{B},d_{B})$ are the respective private keys of A and B. First, A sends a message $e_{A}P_{m}$ to B, and then B returns the message $e_{B}e_{A}P_{m}$ to A, A can calculate the message by using the private key $d_{A}$. Because $NP_{m}=0$, $d_{A}e_{A}\equiv 1({{\,\mathrm{mod}\,}}N)$, so

$$d_{A}e_{B}e_{A}P_{m}=e_{B}P_{m}.$$

Finally, user A sends the calculation result $e_{B}P_{m}$ to B, and user B can read the original real message $P_{m}$ of user A by using the private key $d_{B}$, because $d_{B}e_{B}\equiv 1({{\,\mathrm{mod}\,}}N)$, so

$$d_{B}e_{B}P_{m}=P_{m}.$$

It should be noted that even if user B receives the message $e_{A}P_{m}$ sent by A for the first time, $e_{A}P_{m}$ is given to user B as a point $Q=e_{A}P_{m}$ on the elliptic curve. If B does not calculate the discrete logarithm, $e_{A}$ and $d_{A}$ are not known. Although the last user B already knows the plaintext $P_{m}$, the calculation of the discrete logarithm of Q under base $P_{m}$ is very complex. Similarly, when user A receives a reply from user B and calculates $e_{B}P_{m}$, he cannot know B’s private key $(e_{B},d_{B})$.

ElGamal elliptic curve cryptography

ElGamal cryptosystem is another elliptic curve cryptosystem completely different from Massey–Omura cryptosystem. In this system, the order N of Mordell group of elliptic curve does not need to be known. All users jointly select a fixed finite field $\mathbb {F}_{q}$, an elliptic curve $C_{E}$ on $\mathbb {F}_{q}$ and a fixed point $B\in C_{E}$ on $C_{E}$ as the basis of discrete logarithm. Each user randomly selects an integer $a(0\le a< N_{q})$ as the private key, calculates $Q=aB\in C_{E}$ and discloses it. Its workflow is as follows:

If user A wants to encrypt and send a plaintext unit $P_{m}$ to user B, the public key of A is $Q_{A}=a_{A}\cdot B$, the private key is $a_{A}$, the public key of B is $Q_{B}=a_{B}\cdot B$ and the private key is $a_{B}$. The encryption algorithm of $A{\mathop {\longrightarrow }\limits ^{f}}B$ is

$$\begin{aligned} f(m)=f(P_{m})=(kB,P_{m}+kQ_{B})=c. \end{aligned}$$

(6.18)

The decryption algorithm is that user B multiplies the first number with private key $a_{B}$ and then subtracts the second number. That is,

$$\begin{aligned} f^{-1}(c)=P_{m}+kQ_{B}-a_{B}(kB). \end{aligned}$$

(6.19)

Because $Q_{B}=a_{B}\cdot B$, there is

$$f^{-1}(c)=P_{m}+ka_{B}\cdot B-ka_{B}\cdot B=P_{m}.$$

Where k is an integer randomly selected by user A. This integer k does not appear in cryptosystemtext c and is called a layer of “ mask” added by user A to protect plaintext $P_{m}$. In fact, the cryptosystemtext $c=(A_{1},A_{2})$ received by user B is two points on elliptic curve $C_{E}$, where

$$A_{1}=kB,A_{2}=P_{m}+kQ_{B}=P_{m}+k(a_{B}\cdot B).$$

Even if the third user knows the private key $a_{B}$ of user B (assuming that the private key of user B is not secure), decryption with $A_{2}-a_{B}\cdot B$ cannot obtain plaintext $P_{m}$, because

$$A_{2}-a_{B}\cdot B=P_{m}+kQ_{B}-a_{B}B =P_{m}+k(a_{B}\cdot B)-a_{B}\cdot B\ne P_{m},$$

if $k\ne 1$.

The two elliptic curve cryptosystems introduced above are based on the selected elliptic curve $C_{E}$ and a point B on $C_{E}$ as the basis of discrete logarithm. How to randomly select $C_{E}$ and B needs further research.

Lemma 6.7

Let $x^{3}+ax+b\in \mathbb {F}_{q}[x]$ be a cubic polynomial, then $x^{3}+ax+b=0$ have no multiple roots in the split domain if and only if the discriminant $4a^{3}+27b^{2}\ne 0$.

Proof

This conclusion can be deduced directly from the root formula of cubic algebraic equation.

In order to randomly select an elliptic curve on $\mathbb {F}_{q}$, $C_{E}$ is determined by equation $y^{2}=x^{3}+ax+b$ at $\chi (\mathbb {F}_{q})\ne 2,3$. Randomly select three elements $(x_{0},y_{0},a)$ in $\mathbb {F}_{q}$, let

$$b=y_{0}^{2}-(x_{0}^{3}+ax_{0}).$$

Check whether $f(x)=x^{3}+ax+b$ has multiple roots. From Lemma 6.7, just check whether discriminant $4a^{3}+27b^{2}$ is 0. If f(x) has no multiple roots, then select the elliptic curve $y^{2}=x^{3}+ax+b$. Where $(x_{0},y_{0})\in C_{E}$ is a point on an elliptic curve. So let $B=(x_{0},y_{0})$ is the base of discrete logarithm. Similarly, for $q=2^{r}$ or $q=3^{r}$, we can also randomly draw an elliptic curve $C_{E}$ and determine the basis $B\in C_{E}$ of the discrete logarithm at the same time.

It should be noted that at present, no algorithm can calculate the number of points $N_{q}$ of any elliptic curve. Some special algorithms, such as schoof algorithm, are quite complex and lengthy in practical application, although the computational complexity is polynomial.

Now we introduce the second method of selecting elliptic curves, called ${{\,\mathrm{mod}\,}}p$ method. An elliptic curve $C_{E}$, if E is a number field, such as $E=\mathbb {R},\mathbb {Q},\mathbb {C}$, $C_{E}$ is called a global curve. We use the ${{\,\mathrm{mod}\,}}p$ method to convert a global curve into a “local” curve. Firstly, a point $B\in C_{E}$ on a global curve $C_{E}$ and $C_{E}$ is selected, where B is the group element of Mordell group, its addition order is $\infty $, where $E=\mathbb {Q}$ is the rational number field.

$$C_{E}: y^{2}=x^{3}+ax+b, ~a,b\in \mathbb {Q}.$$

Let p be a prime number and coprime with the integers in the denominators of a and b, then we obtain an elliptic curve on $\mathbb {F}_{p}$,

$$C_{E} {{\,\mathrm{mod}\,}}p: y^{2}\equiv x^{3}+ax+b({{\,\mathrm{mod}\,}}p),a,b\in \mathbb {F}_{p}.$$

and a point $B {{\,\mathrm{mod}\,}}p$ on $C_{E}{{\,\mathrm{mod}\,}}p$, when localizing an elliptic curve, the choice of prime p only needs to satisfy

$$p \not \mid a \text {and~}b\text {~'s denominator, ~and~}4a^{3}+27b^{2}\not \equiv 0({{\,\mathrm{mod}\,}}p).$$

In fact, we can ask further

$$\begin{aligned} N_{p}=|C_{E} {{\,\mathrm{mod}\,}}p|=\text {prime}. \end{aligned}$$

(6.20)

In this way, the Mordell group of $C_{E} {{\,\mathrm{mod}\,}}p$ is a cyclic group, and any finite point of $C_{E} {{\,\mathrm{mod}\,}}p$ will be the generator of the group. At present, there is no deterministic algorithm for selecting the prime number p satisfying Formula (6.20), and it is generally speculated that a probabilistic algorithm with success probability $\ge O(\frac{1}{\log p})$ exists.

6.3 Elliptic Curve Factorization

In 1986, mathematician H.W. Lenstra used elliptic curve to find a new method of factor decomposition. Lenstra’s method has greater advantages than the known old algorithms in many aspects, which is also one of the main reasons why elliptic curve has attracted more and more attention in the field of cryptography, We first introduce a classical factorization method called Pollard $(p-1)$ algorithm.

$(p-1)$ algorithm

Suppose n is a compound number, and p is a prime factor of n; of course, p is unknown and needs to be further determined. If $p-1$ happens to have some small prime factors, or all prime factors of $p-1$ are not too large, the essence of $(p-1)$ method is to find the prime factor p with this property of n. $(p-1)$ method can be completed in the following steps:

Let B be a positive integer. Select a positive integer k so that k is a multiple of most positive integers smaller than B, for example, $k=B!$, or k can be the least common multiple of all positive integers smaller than B.

Select a positive integer a to satisfy $2\le a\le n-2$, $(a,n)=1$, such as $a=2$, or $a=3$, and any randomly selected positive integer.

Using the “repeated square method” to calculate the minimum nonnegative residual $a^{k} {{\,\mathrm{mod}\,}}n$ of $a^{k}$ under ${{\,\mathrm{mod}\,}}n$.

The maximum common divisor $d=(a^{k}-1,n)$ of $a^{k}-1$ and n is calculated by Euclidean rolling division method.

If $d=1$ or $d=n$, that is, if d is the trivial factor of n, re select a, and then repeat steps 1–4 above.

In order to explain the working principle of $(p-1)$ algorithm, we further assume that k is a multiple of all positive integers less than B, and p|n,

$$\begin{aligned} p-1=\prod p_{i}^{\alpha _{i}},\text {where}~ \forall ~ p_{i}^{\alpha _{i}}\le B. \end{aligned}$$

(6.21)

There is $p-1|k$. By Fermat congruence theorem,

$$a^{p-1}\equiv 1({{\,\mathrm{mod}\,}}p), \Longrightarrow a^{k}\equiv 1({{\,\mathrm{mod}\,}}p).$$

So p|d, where $d=(a^{k}-1,n)$.

Definition 6.4

Suppose n is a compound number, p|n. B is a sufficiently large positive integer arbitrarily selected, and p is called $B-$smooth prime, if Eq. (6.21) holds. That is, $p-1$ can be decomposed into the product of prime powers less than B.

Lemma 6.8

Suppose n is a compound number and B is a positive integer. If n has a $B-$smoothing prime factor p, select k and a according to the algorithm steps $1-4 $, then we have $d=(a^{k}-1,n)>1$, so we have factor decomposition $n=d\cdot \frac{n}{d}$.

Proof

If p is a smoothing prime factor of n, then we have $p|(a^{k}-1,n)$, thus $d>1$. The Lemma holds.

In the above algorithm, if $d=(a^{k}-1,n)=n$. That is $n|a^{k}-1$, if the algorithm fails, we must reselect a and carry out a new round of testing.

Example 6.2

Factorization of $n=540143$, if $(p-1)$ method is used, then choose $B=8$, $k=840$, is the least common multiple of $1,2,\ldots ,8$, let $a=2$, calculate the minimum nonnegative residue of $2^{840}$ under ${{\,\mathrm{mod}\,}}n$,

$$2^{840}\equiv 53047({{\,\mathrm{mod}\,}}540143).$$

Calculate $(2^{840}-1,n)$,

$$d=(2^{840}-1,n)=(53046,540143)=421.$$

So we have factorization $540143=421\times 1283$.

Pollard’s $(p-1)$ method is essentially the multiplication group of $\mathbb {Z}_{p}$, the order of $\mathbb {Z}_{p}^{*}$ cannot be divided by a huge prime number; otherwise, this method will not work. Lenstra can overcome this disadvantage by using elliptic curves for factor decomposition, because there are many elliptic curves to choose from, we can always hope that the order of Mordell group on an elliptic curve is not divided by a huge prime number. Next, we introduce Lenstra’s method in detail. First, we discuss the elliptic curve ${{\,\mathrm{mod}\,}}n$.

The following general assumption is that n is an odd number and a compound number, p|n (p is unknown) and $p>3$. Let m be a positive integer, $x_{1},x_{2}$ be two rational numbers, and the denominators of $x_{1}$ and $x_{2}$ are mutually prime with m, so that $x_{1}-x_{2}=\frac{c}{d}$ is a reduced fraction, then define

$$\begin{aligned} x_{1}\equiv x_{2}({{\,\mathrm{mod}\,}}m), ~\text {if~}m|c. \end{aligned}$$

(6.22)

Lemma 6.9

Suppose $x_{1}\in \mathbb {Q}$ is a rational number, if its denominator and m are mutually prime, there is a unique nonnegative integer r, such that $x_{1}\equiv r({{\,\mathrm{mod}\,}}m)$. r is called the nonnegative residue of $x_{1}$ under ${{\,\mathrm{mod}\,}}m$, denote as $r=x_{1} {{\,\mathrm{mod}\,}}m$.

Proof

Write $x_{1}=\frac{b}{a}$, where $(a,m)=1$, $x_{1}-x=\frac{-ax+b}{a}$, because the congruence equation $-ax+b\equiv 0({{\,\mathrm{mod}\,}}m)$ has a unique solution r, $0\le r<m$. So there is a unique r such that $x_{1}\equiv r({{\,\mathrm{mod}\,}}m)$. The Lemma holds.

In order to randomly generate an elliptic curve $C_{E}$ over the rational number field $\mathbb {Q}$, we randomly select three integers $a, x_{0}, y_{0}\in \mathbb {Z}$, let $b=y_{0}^{2}-x_{0}^{3}-ax_{0}$ to satisfy

$$\begin{aligned} \Delta =4a^{2}+27b^{2}\ne 0, \text {and}~(\Delta ,n)=1. \end{aligned}$$

(6.23)

We get an elliptic curve $C_{E}:y^{2}=x^{3}+ax+b$, where $(x_{0},y_{0})\in C_{E}$. Because $a,b\in \mathbb {Z}$, $\Delta =4a^{2}+27b^{2}$ and n are coprime, then for all prime p, $p|n, \Longrightarrow \Delta \not \equiv 0({{\,\mathrm{mod}\,}}p)$. Therefore, as a cubic algebraic equation over a finite field $\mathbb {F}_{p}$, $x^{3}+ax+b$ has no multiple roots, so we obtain a “local” elliptic curve $C_{E} {{\,\mathrm{mod}\,}}p$, where

$$\begin{aligned} C_{E} {{\,\mathrm{mod}\,}}p: y^{2}\equiv x^{3}+ax+b({{\,\mathrm{mod}\,}}p). \end{aligned}$$

(6.24)

And a point $(x_{0} {{\,\mathrm{mod}\,}}p,y_{0} {{\,\mathrm{mod}\,}}p)\in C_{E} {{\,\mathrm{mod}\,}}p$ on $C_{E} {{\,\mathrm{mod}\,}}p$, let’s write this point on $C_{E} {{\,\mathrm{mod}\,}}p$ with P, that is

$$P=(x_{0} {{\,\mathrm{mod}\,}}p,y_{0} {{\,\mathrm{mod}\,}}p)\in C_{E} {{\,\mathrm{mod}\,}}p.$$

Next, we want to calculate kP, like the “continuous square method” of multiplication, and there is a similar continuous doubling method for addition.

Lemma 6.10

When k is a huge integer, the computational complexity of kP is

$$Time(kP)=\log k\cdot Time(P).$$

Proof

k is expressed as a binary integer, i.e.,

$$k=a_{0}+a_{1}2+a_{2}2^{2}+\cdots +a_{m-1}2^{m-1},\forall ~ a_{i}=0 ~\text {or~}1.$$

We can double continuously, that is, $2^{j}P+2^{j}P=2\cdot 2^{j}P(0\le j\le m-2)$, thus obtain kP, m is the binary digit of k, $m=O(\log k)$, there is

$$Time(kP)=\log k\cdot Time(P).$$

The Lemma holds.

Theorem 6.2

Let $C_{E}$ be an elliptic curve over the rational field $\mathbb {Q}$, define the equation as $y^{2}=x^{3}+ax+b$, where $a,b\in \mathbb {Z}$, and $(4a^{3}+27b^{2},n)=1$. Let $P_{1}$ and $P_{2}$ be two points on $C_{E}$, and their denominators are coprime with n, and $P_{1}\ne -P_{2}$, $P_{1}+P_{2}\in C_{E}$. Let $P_{1}+P_{2}=(x,y)$, then the necessary and sufficient condition for the denominator of x and y to be mutually prime with n is that there is no prime factor p|n of n, $P_{1} {{\,\mathrm{mod}\,}}p$ and $P_{2} {{\,\mathrm{mod}\,}}p$ are two points on the local curve $C_{E} {{\,\mathrm{mod}\,}}p$,

$$P_{1} {{\,\mathrm{mod}\,}}p+P_{2} {{\,\mathrm{mod}\,}}p=0.$$

Proof

Let $P_{1}=(x_{1},y_{1})$, $P_{2}=(x_{2},y_{2})$ is the two points on $C_{E}$. $P_{1}+P_{2}=(x,y)$. If the denominators of x and y are coprime with n, we have to prove

$$\begin{aligned} P_{1} {{\,\mathrm{mod}\,}}p+P_{2} {{\,\mathrm{mod}\,}}p\ne 0,\forall ~p|n. \end{aligned}$$

(6.25)

If $x_{1}\not \equiv x_{2}({{\,\mathrm{mod}\,}}p)$, it is obvious that Formula (6.4) is true from Formula (6.25). Might as well make $x_{1}\equiv x_{2}({{\,\mathrm{mod}\,}}p)$. If $P_{1}=P_{2}$, now $x_{1}=x_{2},y_{1}=y_{2}$, we only need $ p \not \mid 2y_{1}$. If $p|2y_{1}$, because the coordinates of $2P_{1}=(x,y)$ are determined by equation (6.5),

$$ {\left\{ \begin{array}{ll} \ x=(\frac{3x_{1}^{2}+\alpha }{2y_{1}})^{2}-2x_{1}; \\ \ y=y_{1}-(\frac{3x_{1}^{2}+\alpha }{2y_{1}})(x_{1}-x). \end{array}\right. } $$

Where $\alpha =\frac{3x_{1}^{2}+a}{2y_{1}}$. By $p|2y_{1}, \Longrightarrow 3x_{1}^{2}+\alpha \equiv 0({{\,\mathrm{mod}\,}}p)$. Because n is an odd number, so $p|y_{1}$, we have

$$ {\left\{ \begin{array}{ll} \ x_{1}^{3}+ax_{1}+b\equiv 0({{\,\mathrm{mod}\,}}p); \\ \ 3x_{1}^{2}+a\equiv 0({{\,\mathrm{mod}\,}}p). \end{array}\right. } $$

That is, $x_{1}$ is the root of $f(x)=x^{3}+ax+b$ and derivative $f'(x)=3x^{2}+a({{\,\mathrm{mod}\,}}p)$. This is contradictory to $(4a^{3}+27b^{2},n)=1$. So you might as well let $P_{1}\ne P_{2}$, now $x_{1}\equiv x_{2}({{\,\mathrm{mod}\,}}p)$, $x_{1}\ne x_{2}$(because $P_{1}\ne -P_{2}$), we can write

$$x_{2}=x_{1}+tp^{r},r\ge 1.$$

The numerator and denominator of t and p are mutually prime, which can be deduced from Formula (6.4),

$$y_{2}=y_{1}+sp^{r}.$$

On the other hand, by $y_{2}^{2}=x_{2}^{3}+ax_{2}+b$, there is

$$\begin{aligned} {\begin{matrix} y_{2}^{2}&{}=(x_{1}+tp^{r})^{3}+a(x_{1}+tp^{r})+b\\ &{}\equiv x_{1}^{3}+ax_{1}+b+tp^{r}(3x_{1}^{2}+a)({{\,\mathrm{mod}\,}}p)\\ &{}\equiv y_{1}^{2}+tp^{r}(3x_{1}^{2}+a)({{\,\mathrm{mod}\,}}p). \end{matrix}} \end{aligned}$$

(6.26)

But $x_{1}\equiv x_{2}({{\,\mathrm{mod}\,}}p)$, $y_{1}\equiv y_{2}({{\,\mathrm{mod}\,}}p)$, there is

$$P_{1}{{\,\mathrm{mod}\,}}p+P_{2}{{\,\mathrm{mod}\,}}p=2P_{1}.$$

The above formula is infinite if and only if $y_{1}\equiv y_{2}\equiv 0({{\,\mathrm{mod}\,}}p)$. If $y_{1}\equiv y_{2}\equiv 0({{\,\mathrm{mod}\,}}p)$, then $y_{2}^{2}-y_{1}^{2}=(y_{2}-y_{1})(y_{2}+y_{1})$ will be divided by $p^{r+1}$. Therefore, Equation (6.26) contains $3x_{1}^{2}+a\equiv 0({{\,\mathrm{mod}\,}}p)$. It’s impossible. Because $x^{3}+ax+b({{\,\mathrm{mod}\,}}p)$ has no multiple roots, $x_{1}$ cannot be the roots of $x^{3}+ax+b$ and derivative $3x^{2}$ under ${{\,\mathrm{mod}\,}}p$. This proves that Formula (6.25) holds under the assumption.

Conversely, if Eq. (6.25) holds, we prove that the denominator of $P_{1}+P_{2}$ and n are coprime. Fixed p|n, if $x_{1}\not \equiv x_{2}({{\,\mathrm{mod}\,}}p)$, from equation (6.4), the denominator of $P_{1}+P_{2}$ and p are coprime. Might as well make $x_{1}\equiv x_{2}({{\,\mathrm{mod}\,}}p)$, then $y_{2}\equiv \pm y_{1}({{\,\mathrm{mod}\,}}p)$. Because $P_{1}{{\,\mathrm{mod}\,}}p+P_{2}{{\,\mathrm{mod}\,}}p\ne 0$, we have $y_{2}\equiv y_{1}\not \equiv 0({{\,\mathrm{mod}\,}}p)$. First assume $P_{2}=P_{1}$, then Equation (6.5) and the fact of $y_{1}\not \equiv 0({{\,\mathrm{mod}\,}}p)$ prove that the denominator of $P_{1}+P_{2}=2P_{1}$ and p is coprime. Finally, let $P_{2}\ne P_{1}$, we write $x_{2}=x_{1}+tp^{r},(t,p)=1$, using the congruence of Formula (6.26), there are

$$\frac{y_{2}^{2}-y_{1}^{2}}{x_{2}-x_{1}}\equiv 3x_{1}^{2}+a({{\,\mathrm{mod}\,}}p).$$

Because $p\not \mid y_{2}+y_{1}\equiv 2y_{1}({{\,\mathrm{mod}\,}}p)$, so the denominator of

$$\frac{y_{2}^{2}-y_{1}^{2}}{(y_{2}+y_{1})(x_{2}-x_{1})}=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}$$

cannot be divided by p, by (6.4), the denominator of $P_{1}+P_{2}$ cannot be divided by p. Since p|n is arbitrary, we complete the proof of the whole theorem.

Lenstra algorithm.

Let n be an odd compound number, we hope to find a nontrivial factor d of n, d|n, $1<d<n$, so there is factorization $n=d\cdot \frac{n}{d}$. Previously, we have introduced the random selection of an elliptic curve $C_{E}$ on rational number field $\mathbb {Q}$ and a point P on $C_{E}$. Lenstra’s algorithm hopes to factorize n by $(C_{E},P)$. There is no doubt that the Lenstra algorithm to be explained below is also a probability algorithm. If $(C_{E},P)$ cannot be factorized successfully, as long as the probability of failure is $p<1$, select another elliptic curve and a point above. If this continues, after randomly and independently selecting n elliptic curves, the probability of successful factorization of n,

$$P\{n=d\cdot \frac{n}{d}\}\ge 1-p^{n}(p<1).$$

When n is sufficiently large, the success probability of Lenstra algorithm can be infinitely close to 1. Therefore, the so-called Lenstra algorithm can be simply summarized as an algorithm that factorizes n by using any rational elliptic curve $(C_{E},P)$, and its failure probability is $p<1$.

Let $(C_{E},P)$ be a given rational elliptic curve, and B and C be the positive upper bound of selection. Let k be divided by some small prime powers, to be exact,

$$\begin{aligned} k=\prod _{1<l\le B}l^{\alpha _{l}}, \end{aligned}$$

(6.27)

where $\alpha _{l}$ is the largest index satisfying $l^{\alpha _{l}}\le C$. Thus $\alpha _{l}=[\frac{\log C}{\log l}]$.

Next, we calculate $kP({{\,\mathrm{mod}\,}}n)$, by (6.4) and (6.5), if $x_{2}-x_{1}$ and $2y_{1}$ have a rational number whose denominator and n are not prime, for example $d=(x_{2}-x_{1},n),1<d<n$; Then we have factorization $n=d\cdot \frac{n}{d}$. If $d=n$, then re select point P on rational elliptic curves $C_{E}$ and $C_{E}$. By Theorem 6.2, $d>1$ appears in these rational numbers $x_{2}-x_{1}$ and $y_{1}$ if and only if there is a $k_{1}$, such that

$$k_{1}\cdot (P{{\,\mathrm{mod}\,}}p)=0,\forall ~ p|n.$$

From the selection of equation k in (6.27), there is a maximum probability $k_{1}|k$, thus

$$k\cdot (P{{\,\mathrm{mod}\,}}p)=0,\forall ~p|n.$$

Therefore, in Lenstra algorithm, by calculating the rational point kP, there is a great probability that there is a certain p, p|n such that

$$\begin{aligned} k(P{{\,\mathrm{mod}\,}}p)=0, p|n, \text {~is a prime number}. \end{aligned}$$

(6.28)

By Theorem 6.2, let $P=(x_{1},y_{1}), (k-1)P=(x_{2},y_{2})$, thus $d=(x_{2}-x_{1},n)>1$ or $(2y_{1},n)=d'>1$, we obtain the nontrivial factorization of n.

From the above Lenstra algorithm, the key problem is to calculate $k\cdot P$. Using the continuous doubling method given in Lemma 6.10, we only need to calculate $2P, 2(2P),2(4P), \ldots , 2^{\alpha _{2}}P$, $3(2^{\alpha _{2}}P), 3(3\cdot 2^{\alpha _{2}}P)\cdots 3^{\alpha _{3}}2^{\alpha _{2}}P$, this continues until $(\prod _{1< l\le B}l^{\alpha _{l}})P$, i.e., kP.

For the probability estimation and computational complexity of Lenstra algorithm, see 1986 of reference 6.

Exercise 6

Let $C_{E}=\{(x,y)\in \mathbb {C}\mid y^{2}=x^{3}+ax+b,a,b\in \mathbb {R}\}$ is a complex elliptic curve, then $C_{E}\bigcap \mathbb {R}^{2}$ is a subgroup of $C_{E}$, determine all subgroups of $C_{E}$ whose coordinates are real numbers.

The points of order n on complex elliptic curve and real elliptic curve are determined.

Take an example of a rational elliptic curve $C_{E}$, there are exactly two points on $C_{E}$ with order 2. Another example is that there are exactly four points on $C_{E}$ with order 2.

Let $C_{E}$ is a real elliptic curve, $P\in C_{E}$ is a finite point, determine the geometric equivalence condition of $o(P)=2,o(P)=3,o(P)=4$.

Calculate the order of points on the following rational elliptic curves:

(i) $P=(0,16),C_{E}:y^{2}=x^{3}+256;$

(ii) $P=(\frac{1}{2},\frac{1}{2}),C_{E}:y^{2}=x^{3}+\frac{x}{4};$

(iii) $P=(3,8),C_{E}:y^{2}=x^{3}-43x+16;$

(iv) $P=(0,0),C_{E}:y^{2}+y=x^{3}-x^{2}.$

Proved that the following elliptic curve has exactly $q+1$ points in $\mathbb {F}_{q}$:

(a) $y^{2}=x^{3}-x$, when $q\equiv 3({{\,\mathrm{mod}\,}}4);$

(b) $y^{2}=x^{3}-1$, when $q\equiv 2({{\,\mathrm{mod}\,}}3), ~q$ is odd;

Let $q=2^{r}$, the elliptic curve $C_{E}$ on $\mathbb {F}_{q}$ be: $y^{2}+y=x^{3};P=(x,y)\in C_{E}$, calculate 2P and $-P$. If $q=16$, prove that every point on $C_{E}$ has order 3.

Please give a probabilistic algorithm to find a nonsquare number in the finite field $\mathbb {F}_{q}$.

The deterministic algorithm can map the embedding of plaintext units to any $\mathbb {F}_{q}-$ elliptic curve. Please give the specific algorithm process for the following elliptic curves:

(1) $C_{E}:y^{2}=x^{3}-x$, when $q\equiv 3({{\,\mathrm{mod}\,}}4)$,

(2) $C_{E}:y^{2}+y=x^{3}$, when $q\equiv 2({{\,\mathrm{mod}\,}}3)$.

10.

Let $C_{E}$ be an elliptic curve on the finite field $\mathbb {F}_{p}$, and $N_{r}$ represents the number of midpoint of $C_{E}$ in the finite field $\mathbb {F}_{p^{r}}$, then

(i) If $p>3$, when $r>1$, $N_{r}$ is not prime.

(ii) When $p=2, 3$, a counterexample is given to show that $N_{r}$ is a prime number.

11.

Take an example of an elliptic curve $C_{E}$, which has only one point on $\mathbb {F}_{4}$, the infinity point. Take $N_{r}$ as the number of points of $C_{E}$ on $\mathbb {F}_{4^{r}}$, then $N_{r}$ is the square of Mersenne prime $2^{r}-1$.

12.

Decompose $n=53467$ at $k=840,a=2$ using Pollard’s $(p-1)$ method.

13.

Let $n_{k}=2^{2^{k}}+1$ be Fermat number, the following is Pepin’s method to detect whether $n_{k}$ is a prime number:

(i) $n_{k}$ is a prime, if and only if there is an integer a, $a^{2^{2^{k-1}}}\equiv -1({{\,\mathrm{mod}\,}}n_{k})$.

(ii) If $n_{k}$ is a prime, then $a\in \mathbb {Z}_{n_{k}}^{*}$ over $50\%$ has the congruence property of (i).

(iii) When $k>1$, we can always choose $a=3, 5$, or $a=7$.

Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

Springer Professional

Abstract

6.1 Basic Theory

6.2 Elliptic Curve Public Key Cryptosystem

6.3 Elliptic Curve Factorization