EC (Elliptic Curve) elliptic curve
Three types of elliptic curves
General information will use the Weierstrass Curve as an example to introduce the basic concepts and operating principles of elliptic curves. This is because any elliptic curve can be written in the form of a Weierstrass curve. In fact, elliptic curves also include many other types, such as Montgomery Curve, Twisted Edwards Curve, etc. Curve25519 is an elliptic curve defined on the Montgomery curve, while Ed25519 is an elliptic curve defined on the twisted Edward curve.
1. Weierstrass Curve
The general form of an elliptic curve can be expressed as:
$E:y^2=x^3+Ax+B$
Among them \(A,B∈\mathbb{F}_p\), \(4A^3+27B^2≠0\). The above equation is generally called the elliptic curve equation of Weierstrass form.
2. Montgomery Curve
The Montgomery form of the elliptic curve equation is defined as:
$Kt^2=s^3+Js^2+s$ where $K,J∈\mathbb{F}_p$, $K(J^2-4)≠0$.
3. Twisted Edwardian Curve
The equation of an elliptic curve in twisted Edwardian form is defined as:
$av^2+w^3=1+dv^2 w^2$ where $a,d≠0$ and $a≠d$.
Conversion between elliptic curves
The three types of elliptic curves, Weierstrass curve, Montgomery curve, and twisted Edward curve, can be converted into each other.
Montgomery Curve ⇔ Weierstrass Curve
Any elliptic curve can be written in Weierstrassian form. Conversely, a Weierstrass elliptic curve can be converted into a Montgomery elliptic curve when certain conditions are met. For specific conversion conditions, please refer to “Montgomery Curve》Equivalence with Weierstrass curves section.
The method of converting the Montgomery curve\(Kt^2=s^3+Js^2+s\) into the equivalent Weierstrass curve\(y^2=x^3+Ax+B\) is:
$\left\{ \begin{array}{l}
{A = \frac{3 – J^{2}}{3K^{2}}} \\
{B = \frac{2J^{3} – 9J}{27K^{3}}}
\end{array} \right.$
The method of converting Montgomery curve point\((s,t)\) into equivalent Weierstrass curve point\((x,y)\) is:
$\left\{ \begin{array}{l}
{x = \frac{3s + J}{3K}} \\
{y = \frac{t}{K}}
\end{array} \right.$
On the contrary, the method of converting the Weierstrass curve point\((x,y)\) into the equivalent Montgomery curve point\((s,t)\) is:
$\left\{ \begin{array}{l}
{s = \frac{3Kx – J}{3}} \\
{t = \frac{y}{K}}
\end{array} \right.$
Montgomery Curve ⇔ Weierstrass Curve
All twisted Edward curves are birationally equivalent to Montgomery curves and vice versa. The so-called two-way rational equivalence can be understood as that, except for individual points, there is a mutual mapping relationship between the points of the twisted Edward curve and the points of the Montgomery curve.
The method of converting the twisted Edward curve\(av^2+w^3=1+dv^2 w^2\) into the equivalent Montgomery curve\(Kt^2=s^3+Js^2+s\) is:
$\left\{ \begin{array}{l}
{J = \frac{2\left( {a + d} \right)}{a – d}} \\
{K = \frac{4}{a – d}}
\end{array} \right.$
The method of converting the twisted Edward curve point\((v,w)\) into the equivalent Montgomery curve point\((s,t)\) is:
$
\left\{ \begin{array}{l}
{s = \frac{1 + w}{1 – w}} \\
{t = \frac{s}{v}}
\end{array} \right.$
The method of converting Montgomery curve point\((s,t)\) into twisted Edward curve point\((v,w)\) is:
$\left\{ \begin{array}{l}
{v = \frac{s}{t}} \\
{w = \frac{s – 1}{s + 1}}
\end{array} \right.$
When \(t=0\) or \(s=-1\), the mapping method is \((v,w)=(0,-1)\).
Operations on Elliptic Curves
1. Negative elements of finite fields
The negative element of \(P(x,y)\) is\((x,-y\pmod{p})=(x,py)\)
2. Addition of finite fields
\(P(x_1,y_1 )\), \(Q(x_2,y_2 )\) and \(R(x_3,y_3 )\) three points (where \(R\) is a straight line \(PQ\ ) and the symmetry point of the intersection point of the curve about the \(x\) axis, that is, \(R=P+Q\)) have the following relationship:
$\left\{ \begin{array}{l}
{x_{3} \equiv k^{2} – x_{1} – x_{2}~\left( {\text{mod}~p} \right)} \\
{y_{3} \equiv k\left( {x_{1} – x_{3}} \right) – y_{1}~\left( {\text{mod}~p} \right)}
\end{array} \right.$
3. Slope calculation
$k = \left\{ \begin{matrix}
\frac{3x_{1}^{2} + a}{2y_{1}} & {P = Q} \\
\frac{y_{2} – y_{1}}{x_{2} – x_{1}} & {P \neq Q}
\end{matrix} \right.$
ECC-ElGamal public key encryption algorithm
- Let\(p>3\) be a large prime number, \(E\) be the elliptic curve on the finite field \(\mathbb{F}_p\), \(G∈E\) be a point on the elliptic curve , and the order of \(G\) is large enough. \(p\) and \(E\) and \(G\) are all public.
- Randomly select an integer \(x\), \(1≤x≤\mbox{ord}(G)-1\), where \(\mbox{ord}(G)\) represents the base point \(G\ ) generates the order of the group on the curve \(E\). Calculate\(Y=xG\). \(Y\) is the public encryption key (public key), and \(x\) is the confidential decryption key (private key).
- Encryption transformation: The plaintext message is mapped to a point on the elliptic curve \(M=(m_1,m_2 )\), and an integer \(k\) is randomly selected to satisfy \(1≤k≤\mbox{ord}(G) -1\), the ciphertext is \(C=(c_1,c_2 )\), where \(c_1=kG\), \(c_2=M+kY\).
- Decryption transformation: For any ciphertext\(C=(c_1,c_2)\), the plaintext is\(M=c_2-xc_1\).
prove:
According to the encryption transformation, there are \(c_1=kG\), \(c_2=M+kY=M+kxG\), so \(c_2-xc_1=M+kxG-xkG=M\).
Certification completed.
example:
Assume \(p=11\), \(E\) is the finite field \(\mathbb{F}_{ determined by \(y^2≡x^3+x+6\pmod{11}\) Elliptic curve on 11}\), base point\(G=(2,7)\). The selected private key is \(x=7\), and the plaintext maps to the point of the curve \(M=(10,9)\).
Since the selected private key is \(x=7\), then the corresponding public key is
$Y=7G=(7,2)$
Example of calculation process:
First calculate \(2G\), \(2G=G+G\),
$k \equiv \frac{3 \cdot 2^{2} + 1}{2 \cdot 7}~\left( {\text{mod}~11} \right) \equiv 13 \cdot 14^{- 1}~\left( {\text{mod}~11} \right) \equiv 2 \cdot 4~\left( {\text{mod}~11} \right) \equiv 8$
$x \equiv 8^{2} – 2 – 2~\left( {\text{mod}~11} \right) \equiv 60~\left( {\text{mod}~11} \right) \equiv 5$
$y \equiv 8\left( {2 – 5} \right) – 7~\left( {\text{mod}~11} \right) \equiv – 31~\left( {\text{mod}~11} \right) \equiv 2$
So\(2G=(5,2)\).
Then calculate\(3G\),\(3G=2G+G\),
$k \equiv \frac{2 – 7}{5 – 2}~\left( {\text{mod}~11} \right) \equiv – 5 \cdot 3^{- 1}~\left( {\text{mod}~11} \right) \equiv 6 \cdot 4~\left( {\text{mod}~11} \right) \equiv 2$
$
x \equiv 2^{2} – 5 – 2~\left( {\text{mod}~11} \right) \equiv – 3~\left( {\text{mod}~11} \right) \equiv 8$
$y \equiv 2\left( {5 – 8} \right) – 2~\left( {\text{mod}~11} \right) \equiv – 8~\left( {\text{mod}~11} \right) \equiv 3$
So\(3G=(8,3)\).
Similar calculations can be obtained\(4G=(10,2)\),\(6G=(7,9)\),\(7G=(7,2)\),\(8G=(3,5)\ ),\(14G=(2,7)\). It can be noted that there is \(14G=G⇒13G=0\), so for the base point \(G=(2,7)\) there is \(\mbox{ord}(G)=13\). From this, the public key \(Y\) is calculated as
$Y = 7G = (7,2)$
Assuming that \(k=3\) is randomly selected, we have
$c_1=kG=3G=(8,3)$
$c_2=M+kY=M+kxG=(10,9)+21(2,7)=(10,2)$
Therefore, the ciphertext corresponding to the plaintext \(M=(10,9)\) is \(C=(c_1,c_2 )=((8,3),(10,2))\).
For the decryption process, the private key \(x=3\) is known, the ciphertext \(C=(c_1,c_2)=((8,3),(10,2))\) is received, so the plaintext The recovery process is
$M = c_{2} – xc_{1} = (10,2) – 3(8,3) = (10,9)$
At this point, the encryption and decryption process of the ECC-ElGamal public key encryption algorithm is completed.
reference
ISO/IEC 18033-2:2006 Information technology – Security techniques – Encryption algorithms – Part 2: Asymmetric ciphers
RFC 7748 Elliptic Curves for Security
Cao Tianjie. Introduction to cryptography[M].
Ed25519 and Curve25519: concepts and mutual conversion – Zhihu (zhihu.com)
Elliptic curve encryption algorithm (ECC) – Zhihu (zhihu.com)
Cofactor explanation: Uncovering the unknown secrets of elliptic curves – Zhihu (zhihu.com)
Information Theory and Coding: Finite Fields – gxzzz – Blog Park (cnblogs.com)
