Let be the equation of the elliptic curve E. Any line L that intersects the curve will intersect the curve in at most 3 points. Below are examples of how these look like.
A mathematical structure can defined on E. We can “add” two points on E to get a third point. First, let’s define the negative of a point. A point is the negative of a point if the point is the mirror image of the point with respect to the x-axis that is,
From the relation above, we can define to be
The point is the “point at infinity”.
Let L be a line that intersects E at points , and . We define the sum
From this definition, we see that the the sum of any of the two points is the negative of the third point, that is, .
So how do we actually add 2 points given their coordinates? It turns out that if we are given the x and y coordinates of 2 points, we can easily compute the third point. To see this, let be the equation of the line that intersects the elliptic curve at points , and . Solving for the x-coordinates of the intersection, we get
From this we see that
Therefore, if we have and , we can get from the formula:
Once we get , we can get from the formula of the slope:
The variable is the slope of the line. If the line is tangent to the curve E at point , the slope is calculated using the derivative of E at the :
Now that we have seen how to add two points, let’s summarize the formula here:
Given points and , the third point can be computed from
Important! Take note that . The value of should be the negative of the computed value.
Let the elliptic curve be , then points and lie on the curve. The third point can be computed as follows:
If , we have:
The set of points of E together with the point at infinity, , forms a group under the addition operation defined above.
- It is associative:
- Every element has an inverse:
- It contains the identity element. From the inverse we have . Therefore, , which makes the identity element.
- It is closed: For every ,
The addition formula also works for modular arithmetic. Let be a prime number, then given two points and , the third point can be computed as
Suppose , and , then we compute the third point as follows:
N-fold Point Addition
Let be a point in E. If is an integer greater than 1, the point is defined as
Let . Let , then using the formula for and :
Elliptic Curve Cryptography
Alice and Bob want to exchange information using Elliptic Curve Cryptography. They agree on an elliptic curve equation and a base point . Alice and Bob both choose a random number between 1 and 71. Let and be the secret numbers chosen by Alice and Bob (respectively) and publishes the public keys and . Alice wants to send the message encoded in a point . She multiplies Bob’s public key and her private key and adds it to the message to get and sends the pair .
Bob receives the message multiplies his private key to Alice’s public key to get . He then subtracts this to the message to get the original message .
Assume Bob and Alice agree on the equation , the base point and the modulus p=71. Suppose Alice’s private key is 4 and Bob’s private key is 5. Alice will publish her public key as . Likewise, Bob will publish his public key as .
Alice wants to send Bob a message encoded in the point of E. First, Alice will multiply Bob’s public key with her private key to get . She will then add this to to get encrypted message . She will send to Bob.
Bob then receives the message . The first thing he will do is to multiply Alice’s public key with his private key to get . Next, he will subtract this from the encrypted message to get , which is the unencrypted message of Alice!