The Wonderful World of Elliptic Curves: A Sharp Dive into Mathematical Curves and Cryptography
EC (Elliptic Curve) elliptic curve—sounds like a line from a particularly nerdy poem, doesn’t it? But hold onto your calculators, because it’s about to get mathematically saucy! We’re diving deep into something that can make your head spin faster than a poorly handled algebra equation: elliptic curves. And don’t worry—none of this will require you to wear a pocket protector (not that there’s anything wrong with that).
Three Types of Elliptic Curves
Now folks, let’s kick off with the three types of elliptic curves that will be your honourable guides on this mathematical journey. Think of them as the Three Musketeers of the crypto world: the Weierstrass, Montgomery, and Twisted Edward curves, gallantly galloping through the realm of abstract algebra. Sounds like a party, doesn’t it?
1. Weierstrass Curve
The Weierstrass curve is the prime time player here—the Beyoncé of elliptic curves, if you will. Its general form is:
E: y² = x³ + Ax + B
with (A,B ∈ mathbb{F}_p) and (4A³ + 27B² ≠ 0). Remember: a party without proper conditions is just a bunch of people standing awkwardly in a room!
2. Montgomery Curve
Next up, we have the Montgomery curve, defined as:
Kt² = s³ + Js² + s
where (K,J ∈ mathbb{F}_p) and (K(J²−4) ≠ 0). A little more curve-y, this one! You might say it’s like the hipster cousin of the Weierstrass curve, always opting for a more obscure form of expression.
3. Twisted Edward Curve
Finally, we have the Twisted Edward curve. This one is a bit of a wildcard in our ensemble:
av² + w³ = 1 + dv²w²
defined by (a,d ≠ 0) and (a ≠ d). It may not have the catchy name or the mainstream appeal but, boy, does it perform effectively!
Conversion Between Elliptic Curves
Now, let’s talk conversions. You know, like swapping your regular coffee for that fancy, overpriced cold brew! The cool thing is, these curves can transform into one another like a magician pulling a rabbit out of a hat. The relationships are quintessential—who doesn’t love a little Möbius transformation at a party?
For example, converting a Montgomery curve into a Weierstrass curve goes as follows:
A = (3 - J²) / (3K²)
B = (2J³ - 9J) / (27K³)
And if you need to convert points, simply grab this:
x = (3s + J) / (3K)
y = t / K
It’s as simple as swapping out your sneakers for boots—it’s all good until you realize one pair doesn’t match!
Operations on Elliptic Curves
When it comes to operations on these curves, it gets quite interesting. Think of adding points like making a friendship bracelet at summer camp: it’s all about knotted connections!
P(x₁, y₁), Q(x₂, y₂) and their sum R(x₃, y₃) follow this tantalizing relationship:
x₃ ≡ k² - x₁ - x₂ (mod p)
y₃ ≡ k(x₁ - x₃) - y₁ (mod p)
And to find the slope? Oh, it’s straightforward:
k = { (3x₁² + a) / (2y₁), P = Q
(y₂ - y₁) / (x₂ - x₁), P ≠ Q }
ECC-ElGamal Public Key Encryption Algorithm
Ah, the crown jewel of our mathematical soirée: the ECC-ElGamal public key encryption algorithm. It’s like sending love letters via cryptographic magic!
- First, select a large prime (p > 3) and choose an elliptic curve (E) on the finite field (mathbb{F}_p). This is the groundwork—fairly standard fare!
- Next, select an integer (x) for the decryption key like picking a partner for a dance-off—make it count! Calculate (Y = xG) for your public encryption key.
- Then, it’s time for the encryption transformation! Declare your plaintext message M = (m₁,m₂) to be mapped to a point on the elliptic curve. Don’t forget to throw in a random integer (k) for that added twist!
- Finally, the decryption transformation is where the magic happens! Your ciphertext allows you to beautifully retrieve your plaintext, and voilà, your partners are reunited.
Now, assuming you’re still awake after all that math, let’s recap the genius of elliptic curves and see how a little straightforward geometry becomes the backbone of modern encryption. All this while having a laugh or two—cryptographers surely aren’t as dreary as they sound!
So, there you have it! The sparkling world of elliptic curves laid bare like an unfiltered meme! Remember, even in the realm of abstract mathematics, a little jest goes a long way! Who knew that curves could be this exciting? Until next time, keep your numbers close and your curves closer!
References:
ISO/IEC 18033-2:2006, RFC 7748, and a bunch of other highly educated-looking texts that make you sound really smart when you drop their names!
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{2left( {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,-ypmod{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 kleft( {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+6pmod{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 8left( {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 2left( {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)
