Elliptic Curves in 5 minutes.
2024 October 6
See all posts
Similarly to the previous article, special thanks to Vitalik Buterin and his articles. They inspired me to delve into crypto space and cryptography. Although Elliptic Curves are not quantum-resistant, they are still a leading cryptographic algorithm that is used in Solana and Ethereum, for example. This article serves mainly as a notebook for me studying elliptic curves, and for other readers to be acknowledged of them.
Set your timer up
An elliptic curve is a curve with general equation of \(y^2 = x^3 + ax + b\). The graph looks like this:
All the computations in eleptic curve are done in a field, let's define it. The base of a field is a number prime \(p\) or \(2^m\). Let \(n\) to be the number of all points on the curve. Then we need to take point \(G\) such that every point on the curve could be resulted from some integer \(k \in [0, 1, ..., n-1]\) multiplied by \(G\).(It's better to use well-known \(G\), otherwise you may fail.]}
Private key is a random integer in \([0, 1, ..., n-1]\). Public key = private key * \(G\). But how do multiply point by an integer?
Surprisingly, every non-vertical line intersects with the curve at most 3 times. Thus, if we have two points A and B, let line \(AB\) intersects the curve at (c, d), then A + B = (c, -d). If A=B, we take the line tangent to B, which intersects with the curve only twice.
But what is the formula? Lets take two points, \(A(x_a, y_a)\) and \(B(x_b, y_b)\) and equation of the curve \(y^2=x^3+px+q\).
Coefficient of the line \(AB\) is \(k=\frac{y_b-y_a}{x_b-x_a}\). Then, since \(y_a = k * x_a + b_0 => b_0 = y_a - k*x_a => y = kx + y_a - k*x_a => y = k(x-x_a) + y_a\),
Now let the line intersects with the curve at point \(C(x_c, y_c)\).
Let's substitue the formula of the line into equation of the curve: \(y_c^2 = (k(x_c-x_a) + y_a)^2 = (x_c)^3+px+q\)
Therefore \(x_c^3+px_c+q-k^2*x_c^2-k^2*x_a^2+2*k^2*x_c*x_a - y_a^2 - 2*k(x_c-x_a)*y_a=0\)
\(x_c^3 - x_c^2*k^2 + x_c(p + k^2*x_a - 2*k*y_a) + q - k^2*x_a^2 - y_a^2 + 2*k*x_a*y_a=0\)
There are at most 3 solutions, but let's recall what are we looking for: 3 common points between a line, and a curve, and 2 of these points we know alread.
Thus, we already know 2 solutions for this equation, so let's use Viet's theorem:
\(x_a+x_b+x_c = \frac{-(-k^2)}{1} = k^2\)
\(x_c = k^2 - x_a - x_b\). And \(y_c\) can be easily derived from the line's formula.
So that \(n*G\) is simply adding \(G\) over and over again \(n\) times. \(n*G = G + G + G + ...\)
Now we have public and private keys, what do we do with them?
(1) If we have a message \(m\) and we want to sign it, we first use a hash function, for example, SHA-256. Then we hash \(m\), so \(h = hash(m)\).
(2) Then take a random number \(k \in [1..n-1]\)
(3) Calculate random point \(R = k*G\), and take its x-coordinate, \(r = R_x\)
(4) Calculate signature proof \(s = k^{-1}*(h+r*privatekey), mod(n)\)
(5) Return the signature (r, s). Now you have signed the message
How do somebody else can verify the message?
(1) Find \(s^{-1}\)
(2) Retrieve the random point used during the signing \(R'\). Since \(s*s^{-1}=1=s^{-1}*k^{-1}*h+s^{-1}*r*privatekey\), then \(R'=k*G=k*G*1=k*G*s^{-1}*s=k*G*(s^{-1}*k^{-1}*h+s^{-1}*r*privatekey)=\)
\(k*k^{-1}*G*s^{-1}*h+k^{-1}*k*G*r*privatekey=G*s^{-1}*h+G*r*privatekey*s^{-1}\)
Remember that public key = private_key * G? then \(R'=G*s^{-1}*h+r*s^{-1}*publickey\)
(3) Calculate R' and check than its x-coordinate equals r.
If \(R'_x=R_x\), then you have successfully verified the signature.
That was a brief introduction to elliptic curves, thanks for reading!
If you have found any mistakes, please contact me at vladimir@osipov.cc
Elliptic Curves in 5 minutes.
2024 October 6 See all posts
Similarly to the previous article, special thanks to Vitalik Buterin and his articles. They inspired me to delve into crypto space and cryptography. Although Elliptic Curves are not quantum-resistant, they are still a leading cryptographic algorithm that is used in Solana and Ethereum, for example. This article serves mainly as a notebook for me studying elliptic curves, and for other readers to be acknowledged of them.
Set your timer up
An elliptic curve is a curve with general equation of \(y^2 = x^3 + ax + b\). The graph looks like this:
All the computations in eleptic curve are done in a field, let's define it. The base of a field is a number prime \(p\) or \(2^m\). Let \(n\) to be the number of all points on the curve. Then we need to take point \(G\) such that every point on the curve could be resulted from some integer \(k \in [0, 1, ..., n-1]\) multiplied by \(G\).(It's better to use well-known \(G\), otherwise you may fail.]}
Private key is a random integer in \([0, 1, ..., n-1]\). Public key = private key * \(G\). But how do multiply point by an integer?
Surprisingly, every non-vertical line intersects with the curve at most 3 times. Thus, if we have two points A and B, let line \(AB\) intersects the curve at (c, d), then A + B = (c, -d). If A=B, we take the line tangent to B, which intersects with the curve only twice.
But what is the formula? Lets take two points, \(A(x_a, y_a)\) and \(B(x_b, y_b)\) and equation of the curve \(y^2=x^3+px+q\).
Coefficient of the line \(AB\) is \(k=\frac{y_b-y_a}{x_b-x_a}\). Then, since \(y_a = k * x_a + b_0 => b_0 = y_a - k*x_a => y = kx + y_a - k*x_a => y = k(x-x_a) + y_a\),
Now let the line intersects with the curve at point \(C(x_c, y_c)\).
Let's substitue the formula of the line into equation of the curve: \(y_c^2 = (k(x_c-x_a) + y_a)^2 = (x_c)^3+px+q\)
Therefore \(x_c^3+px_c+q-k^2*x_c^2-k^2*x_a^2+2*k^2*x_c*x_a - y_a^2 - 2*k(x_c-x_a)*y_a=0\)
\(x_c^3 - x_c^2*k^2 + x_c(p + k^2*x_a - 2*k*y_a) + q - k^2*x_a^2 - y_a^2 + 2*k*x_a*y_a=0\)
There are at most 3 solutions, but let's recall what are we looking for: 3 common points between a line, and a curve, and 2 of these points we know alread.
Thus, we already know 2 solutions for this equation, so let's use Viet's theorem:
\(x_a+x_b+x_c = \frac{-(-k^2)}{1} = k^2\)
\(x_c = k^2 - x_a - x_b\). And \(y_c\) can be easily derived from the line's formula.
So that \(n*G\) is simply adding \(G\) over and over again \(n\) times. \(n*G = G + G + G + ...\)
Now we have public and private keys, what do we do with them?
(1) If we have a message \(m\) and we want to sign it, we first use a hash function, for example, SHA-256. Then we hash \(m\), so \(h = hash(m)\).
(2) Then take a random number \(k \in [1..n-1]\)
(3) Calculate random point \(R = k*G\), and take its x-coordinate, \(r = R_x\)
(4) Calculate signature proof \(s = k^{-1}*(h+r*privatekey), mod(n)\)
(5) Return the signature (r, s). Now you have signed the message
How do somebody else can verify the message?
(1) Find \(s^{-1}\)
(2) Retrieve the random point used during the signing \(R'\). Since \(s*s^{-1}=1=s^{-1}*k^{-1}*h+s^{-1}*r*privatekey\), then \(R'=k*G=k*G*1=k*G*s^{-1}*s=k*G*(s^{-1}*k^{-1}*h+s^{-1}*r*privatekey)=\)
\(k*k^{-1}*G*s^{-1}*h+k^{-1}*k*G*r*privatekey=G*s^{-1}*h+G*r*privatekey*s^{-1}\)
Remember that public key = private_key * G? then \(R'=G*s^{-1}*h+r*s^{-1}*publickey\)
(3) Calculate R' and check than its x-coordinate equals r.
If \(R'_x=R_x\), then you have successfully verified the signature.
That was a brief introduction to elliptic curves, thanks for reading!
If you have found any mistakes, please contact me at vladimir@osipov.cc