This article is an excellent article from the KX forum.
KX forum author ID: Gu He
I encountered an ECC-related problem while solving questions, and I studied several articles from experts on ECC. After learning, I recorded my thoughts to reinforce my understanding.
This article should strictly be considered as study notes. During the summarization process, I observed many predecessors’ posts and literature, writing down every word, and in the end, I barely understood ECC. Therefore, there might be inaccuracies or errors in my thoughts. I hope the experts will be lenient, and I also hope that fellow learners like myself can gain a bit more understanding of ECC.
Elliptic Curve Cryptography (ECC) is a public key encryption algorithm similar to RSA and ElGamal algorithms, which is asymmetric encryption. ECC is recognized as the most secure encryption algorithm given a specific key length.
0x02 Mathematical Introduction
1. Starting with Parallel Lines
Since middle school math, we have known that two parallel lines never intersect. However, this conclusion has been questioned in modern times. So far, what we have seen are parallel lines at a finite distance, which indeed do not intersect. But what about at an infinite distance that we cannot see? Do parallel lines eventually intersect? This becomes a question.
Thus, the assumption that parallel lines a // b never intersect is questionable.
We can also assume that a and b eventually intersect at an infinite point P∞.
Based on this assumption, we can draw the following diagram:
Assuming that parallel lines a and b intersect at an infinite point P∞.
Therefore, P∞ is the intersection point of parallel lines. To differentiate, we will refer to the points on the plane as ordinary points.
From the simple analysis above, we can derive the following characteristics:
(1) There is only one infinite point P∞ on the line L.
(2) A group of mutually parallel lines in the plane has a common infinite point, such as lines a and b in the figure. Thus, all parallel lines should intersect at the same infinite point P∞.
(3) Any two intersecting lines L1 and L2 in the plane have different infinite points. (Since the infinite point is the intersection of parallel lines, if L1 and L2 intersect in the plane, then their infinite points must be different.)
(4) All infinite points in the plane form an infinite line.
(5) All infinite points in the plane and all ordinary points form a projective plane.
The concept of a projective plane is introduced from the ordinary Cartesian coordinate system, which is the Cartesian product coordinate system we learned in middle school.
We know that the Cartesian coordinate system does not set infinite points, so to represent infinite points, a new concept called the projective plane coordinate system was created. This projective plane coordinate system can represent both infinite points and ordinary points.
Next, let’s see how to establish the projective plane coordinate system.
This is the ordinary Cartesian coordinate system:
On the coordinate system, there is a point A with coordinates A(4,3) where x=4 and y=3.
Now let x = x/z, y = y/z (z!=0), then point A can be represented as A(x,y,z).
Now we have established a new coordinate system based on the plane Cartesian coordinate system.
Here, x/z = 4, y/z=3 (z!=0).
Thus, the coordinates of point A in the new coordinate system can be represented as A(4z,3z,z).
All representations of points in the form of (4z,3z,z) are the coordinate representations of point A in the new coordinate system.
In middle school, we learned that the line equation is: Ax + By + C = 0 (AB cannot both be 0).
Based on the above analysis, we can express the line in the new coordinate system as: A(x/z) + B(y/z) + C = 0.
Multiplying both sides by z gives us the new line equation: Ax + By + Cz = 0.
Now, let’s assume there are two parallel lines:L1: Ax + By + C1z = 0L2: Ax + By + C2z = 0
C1 != C2, based on the definition of parallel lines (same slope), we can conclude that L1 is parallel to L2.By solving the two line equations, we can find:
L1 : C1z = -(Ax + By)L2 : C2 z = -(Ax + By)
Thus, C1z = C2z = -(Ax + By).
Since C1 !=C2, we have z = 0, therefore -(Ax + By) = 0, which means (Ax + By = 0).Thus, the expression is: Ax + By + C*0 = 0.
So the expression for the infinite line corresponds to z= 0.
Let’s assume we have two parallel lines:L1 : x + 2y +3z =0L2: x + 2y + z = 0
To find the intersection point at infinity, since L1 // L2, we can conclude that z=0, thus x+2y=0.So x = -2y.
In coordinate point representation, this means:(Note that at the infinite point, z=0)(-2y:y:0)
All representations in the form of (-2y:y:0) where y !=0 can represent infinite points.
Thus, the new coordinate system can represent ordinary points and infinite points. This coordinate system that can represent all points on the plane is called the projective plane coordinate system.
Finally, we are getting to the main topic. The previous lengthy explanation of the projective plane coordinate system was necessary because the equation of the elliptic curve is established in the projective plane coordinate system.
Let’s see how Wikipedia defines an elliptic curve:
Thus, an elliptic curve that satisfies the Weierstrass equation in the projective plane is represented as:
For ordinary points (x,y) on the plane, letting x=X/Z, y=Y/Z, Z≠0, we get the following equation:
Finally, we arrive at a simplified version of the equation:
There are three points to note:
(1) The equation of the elliptic curve is a homogeneous equation.
(2) Every point on the curve must be non-singular (smooth). Non-singular means that the partial derivatives Fx(x,y,z), Fy(x,y,z), Fz(x,z,y) cannot all be zero at the same time. In simple terms, it means that there exists a tangent line at any point that satisfies the equation.
(3) The elliptic curve has no relation to ellipses.
Based on the above equation, let’s take an example of an elliptic curve equation:
When z=1, we derive the following equation:
Here is the image of the derived elliptic curve:
Or a more classic elliptic curve:
5. Elliptic Curve Abelian Groups
In mathematics, a group is an algebraic structure consisting of a set and a binary operation. Given a set and operation (G,), if it is a group, it must satisfy the following requirements:
a. Closure: ∀a,b∈G, ab ∈ G
b. Associativity: ∀a,b,c∈G, (ab)c = a(bc)
c. Identity element: ∃e∈G, ∀a ∈G, ea = ae = a
d. ∀a ∈G, ∃b∈G such that ab = ba = e
If it is an Abelian group, it must also satisfy the commutative property: ab = ba.
For example, the addition operation within integers is an Abelian group (Z,+).
a. Closure is satisfied: if a and b ∈ Z, then a+b ∈ Z.
b. Associativity is satisfied: (a+b) + c = a + (b+c).
c. Identity element is satisfied: 0 is the identity element because for all integers, a+0=0+a=a.
d. Inverse element is satisfied: the inverse of a is -a because a+(-a) = 0 which is the identity element.
Thus, the addition operation of integers (Z,+) is an Abelian group.
Similarly, elliptic curves can also define addition and Abelian groups.
Using the previously drawn elliptic curve as an example:y^2 = x^3 -x
Find points P and Q on the curve, draw a line passing through P and Q, and intersect the elliptic curve at point R’. Then, draw a vertical line from R’ to the x-axis, intersecting the curve at another point R. We define P+Q = R as shown in the figure:
When P=Q, the tangent line at point P intersects the elliptic curve at R’, and a vertical line to the x-axis intersects at R (the upper figure shows this, and the right figure shows P=Q).
According to the definition, in the left figure, R=P+Q, and in the right figure: R=P+P.
Thus, R can be referred to as 2P, written as R= 2P, and similarly, we can conclude that 3P= P + P + P =R+P.
The addition definition of the elliptic curve is as follows:As shown in the figure, we take points P and Q on the elliptic curve, draw a line that intersects the elliptic curve at R’, and then through R’ draw a vertical line to get R, thus yielding R=P+Q.
This means P, Q, and R’ are all on the same line.
Now connect R with P or R with Q to continue drawing a line, which will intersect the elliptic curve at a new intersection point R2′, and then through R2′ draw a line of symmetry to get R2. Thus, R2=R+P or R2=R+Q.
In the right figure, when P=Q, we have already obtained R=P+P.
Now, connect R and P to draw a new line which intersects the curve at R2.
Then R2 = R+P, which means R2 = P+P+P.
This can repeat, leading to R3 = P+P+P+P.
From the above definition, we can see that when a point P is given, the operation “finding point xG given x” is not difficult because of the properties of addition, allowing for relatively fast calculations.
However, conversely, “finding x given point xG” is very difficult because it requires iterating through each x to perform the operation. This is the discrete logarithm problem utilized in elliptic curve cryptography.
Here, xG represents x times G, where G is the base point. In other words, if we know a point G on the elliptic curve and we know x, we can directly obtain xG by adding G x times. However, if we only know G and xG, it is almost impossible to determine x.
However, this operation alone does not satisfy the properties of an Abelian group. To satisfy this, we need to introduce an infinite point O∞.
Now assume that the infinite point O∞ of the elliptic curve intersects with a point P on the elliptic curve at point P’. Drawing a parallel line from P’ to the y-axis intersects at P. Thus, we have O∞ + P = P, making the role of the infinite point O∞ similar to that of 0 in ordinary addition, for example, 0+5=5. Hence, the infinite point O∞ is also referred to as the zero element, while P’ becomes the inverse of P, denoted as -P.
From the above description, we can conclude that if three points P1, P2, and P3 on the elliptic curve lie on the same line, then their sum equals the zero element. That is, P1 + P2 + P3 = O∞.
Now the elliptic curve satisfies the properties of an Abelian group.
Elliptic Curves over Finite Fields
However, all the content introduced above is based on real numbers and cannot be used for encryption. To apply elliptic curves to cryptography, we need to define them in discrete points.
The reason elliptic curves are continuous is that the coordinates on the elliptic curve are real numbers, which are continuous. Therefore, to use elliptic curves for encryption, we must define them over finite fields.
Now let’s define a finite field Fp:
a. Fp has p (where p is a prime number) elements 0, 1, 2, …, p-2, p-1.
b. The addition in Fp is a+b≡c(mod p).
c. The multiplication in Fp is a×b≡c(mod p).
d. The division in Fp is a÷b≡c(mod p), i.e., a×b^(-1)≡c(mod p), where b^(-1) is an integer between 0 and p-1 that satisfies b×b^(-1)≡1 (mod p).
e. The identity element in Fp is 1, and the zero element is 0.
f. The operations in Fp satisfy the commutative, associative, and distributive laws.
Elliptic curve Ep(a,b), where p is a prime, x,y∈[0,p-1], is defined as:
y^2 = x^3 + ax + b(mod p).
When this curve is defined over the finite field F23, it can be written as:
This means that the values on the left and right sides of the equation are congruent modulo 23, as shown in the graph:
If we take point P = (3,10) on the elliptic curve as the base point, we can calculate 2P, 3P, 4P… with results as shown in the following figure.
We can see that the generated points appear to be random. For example, point P = (3,10) and point 23P = (9,7). Here, solving the discrete logarithm problem translates to finding 23 given points (3,10) and (9,7). In this case, p=23, the problem is still relatively easy to solve. However, when the value of p is extremely large, finding this solution becomes very difficult.
There’s also a concept: the order of a point on the elliptic curve over a finite field refers to the smallest positive integer n such that nP = O∞, where n is called the order of P. If no such n exists, P is said to be of infinite order.
0x03 Practical Applications
In elliptic curve cryptography, given an elliptic curve E, a base point G, and a point xG, we refer to xG as the public key, and x as the private key. As previously analyzed, it is easy to derive the public key from the private key, while it is almost impossible to derive the private key from the public key.
Thus, by analyzing elliptic curves, we obtain the key pair, which allows us to perform encrypted communication.
Let’s take the classic example of Alice communicating with Bob.
Now let’s analyze the process of elliptic curve encryption:
First, Alice selects an elliptic curve Ep(a,b) and chooses a base point G on the curve.
Alice chooses a private key k (k
Alice now transmits E (the elliptic curve), K (the public key), and G (the base point) to Bob.
Bob receives Alice’s message, encodes the plaintext to a point M on Ep(a,b), and generates a random number r (r<n).</n).
Bob calculates the points C1 = M + rK and C2 = rG.
Bob sends the calculated C1 and C2 to Alice.
Upon receiving Bob’s information, Alice computes C1-kC2 to obtain M.
Thus, C1 – C2 = M+rK – krG.
Using the distributive property, krG = r(kG).
From the second equation, we know K = kG.
So, C1 – C2 actually equals M + rK – rK = M.
Therefore, Alice only needs to subtract C1 and C2 to obtain M, and then decode M to retrieve the plaintext.
Let’s analyze what was transmitted during the process:
First, Alice: Alice selected the curve Ep, transmitted her public key K, and the selected base point G.Then Bob: Bob selected a random number r and transmitted C1 and C2 calculated from r.
Why is this transmission secure? Let’s look further (a rough diagram is provided):
It can be intuitively seen that the transmitted information includes Ep, K, G, C1, and C2.
Based on several expressions, we can see that it is nearly impossible to derive the critical r or k from the publicly transmitted information.
Thus, in cryptography, a commonly used six parameters to describe an elliptic curve over Fp are: T = (p,a,b,G,n,h).
Here, p, a, and b are used to determine an elliptic curve, G is the base point acquired by user A, n is the order of point G, and h is the integer part of the ratio of the number of points on the elliptic curve to n.
These parameters directly determine the strength and security of the encryption, so generally, the requirements are:
1. The larger the value of p, the safer it is, but increasing strength leads to performance losses. Generally, it is around 200 bits.
2. n should be a prime number.
5. pt !=1 (mod n) (1<=t<=20).
6. 4a^3 + 27b^2 !=0 (mod p).
Let’s test first, then we will complete it, using Python 2.7 environment.
Based on previous analysis, the points p and q connected by a line will intersect the elliptic curve at point R.The logic is:
c = (3px^2+a)/2py, rx = c^2-2px, ry=c(px-rx)-py.
Thus, we write the following function to calculate r:
def get_r(p, q,mod=MOD, a=A):
p = map(lambda x: x % mod, p)
q = map(lambda x: x % mod, q)
if p[0] == q[0] and (p[1]+q[1])%mod==0:
return [np.infty,np.infty]
if p != q:
c = (p[1]-q[1])*invert(p[0]-q[0], mod)%mod
else:
c = (3*p[0]**2+a)*invert(2*p[1],mod)%mod
rx = (c**2-p[0]-q[0])%mod
ry = (c*(p[0]-rx)-p[1])%mod
return [rx,ry]
def invert(element, mod):
if element >= mod:
element = element%mod
if element == 0:
return None
for index in xrange(1, mod):
if element*index%mod == 1:
return index
def get_add(G, multiple):
lr = G
for index in xrange(1, multiple):
lr = get_r(lr, G)
return lr
Now we take a base point G(1,18).
Thus, the public key K = kG.
Let’s take an encryption point M(34,24).
C1 = get_r(M,get_add(pubkey, r)).
We will try to calculate the value of M from C1 and C2.
# -*- coding: utf-8 -*-
A = 0
B = 7
MOD = 79
def get_r(p, q,mod=MOD, a=A):
p = map(lambda x: x % mod, p)
q = map(lambda x: x % mod, q)
if p[0] == q[0] and (p[1]+q[1])%mod==0:
#互为逆元点和为无穷远点，方便处理 记为[np.infty,np.infty]
return [np.infty,np.infty]
if p != q:
c = (p[1]-q[1])*invert(p[0]-q[0], mod)%mod
else:
c = (3*p[0]**2+a)*invert(2*p[1],mod)%mod
rx = (c**2-p[0]-q[0])%mod
ry = (c*(p[0]-rx)-p[1])%mod
return [rx,ry]
def invert(element, mod):
if element >= mod:
element = element%mod
if element == 0:
return None
for index in xrange(1, mod):
if element*index%mod == 1:
return index
def get_add(G, multiple):
lr = G
for index in xrange(1, multiple):
lr = get_r(lr, G)
return lr
G = (1,18)
prikey = 40
pubkey = get_add(G, prikey)
r = 16
M = (34,24)
C1 = get_r(M,get_add(pubkey, r))
C2 = get_add(G, r)
temp = get_add(C2,prikey)
print get_r(C1,(temp[0], MOD-temp[1]))
KX ID:Gu He
https://bbs.pediy.com/user-757351.htm
* This article is original by KX forum Gu He, please indicate the source when reprinting from the KX community.
* Dynamic DSE code and principles
* ollvm source code analysis – Pass of SplitBasicBlocks
* Some pitfalls and solutions encountered in Linux kernel driver debugging (a must-read guide for beginners)
* Analysis of the kthroltlds mining worm variant
* Metasploit backdoor and cross-platform backdoor generation
Advanced Security Circle, a must-read book
