Cryptography Fundamentals 3: Elliptic Curve Fundamentals ASecuritySite Podcast

In previous podcasts, I outlined the usage of discrete logarithms in the form of a=g^x (mod p). Unfortunately, we now need a relatively large prime number to make sure it is now possible to discover x from a, g and p. This slows down the creation of the discrete log value. One method which has been used to replace them in some applications is to use elliptic curve points. Later in this series, I will explain how elliptic curve cryptography actually works, but in this one, we will just look at the fundamentals of the elliptic curve points.
So what is a group in elliptic curve cryptography (ECC)? Well with this, we will map one group of points to another with a one-way function, and which should be difficult to reverse or find the method we have used to perform the mapping. As we will find, the basic operation is to either add two points in a group to create another point in the group or to double the point to get another point. With these simple operations, we should be able to perform point multiplication. The method of ECC was created independently by Neal Koblitz and Victor Miller.
So, how did I create this mapping? Well, a basic elliptic curve has the form of: 
y² = x³ + ax + b 
For y² = x³ + 7
If x=1, we get:
y² = 1+7
and where y is the square root of 8, which is 2.82. But, in cryptography, we only deal with integers, so we must modify this with a modular form of:
y² = x³ + ax + b (mod p)
For example, if a is zero, b is 7, and the prime is 11, we get:
y² = x³ + 7 (mod 11) 
The possible points are (2, 9) (2, 2) (3, 1) (3, 10) (4, 4) (4, 7) (5, 0) (6, 5) (6, 6) (7, 3) (7, 8). e can try it, and where:
9² (mod 11) = 4 and 2³+7 (mod 11) = 4
https://asecuritysite.com/ecc/ecc_pointsv?a0=0&a1=7&a2=11
As we see, not all the points for an x-coordinate value are possible. This then leads to the order, which is the number of valid x-axis points — which is 6 in this case. W
Point double and add In ECC, we then add points together (P+Q) or double them 2.P and get a new point. With this, it is difficult to reverse back the addition or doubling and find the original point. 
For y²=x³+7 (mod 11)
The valid points are (2, 9) (2, 2) (3, 1) (3, 10) (4, 4) (4, 7) (5, 0) (6, 5) (6, 6) (7, 3) (7, 8). Now let’s take a point of (2,9) and add another point. So this, we get:
https://asecuritysite.com/ecc/ecc_points_add3?a0=2&a1=0&a2=7&a3=11
P1=(2,9) P2=(2,9) P1+P2=(5,0)
P1=(2,9) P2=(3,1) P1+P2=(4,7)
P1=(2,9) P2=(4,4) P1+P2=(3,10)
P1=(2,9) P2=(6,5) P1+P2=(4,4)
P1=(2,9) P2=(7,3) P1+P2=(3,1)
and so we see when we do a point add, we always get another point on the curve, but where it is difficult to reverse back to the points which resulted in this point.
Multiplying points So, can we multiply points in an efficient way? Let’s say we have G, and want to add it to itself n times. We could represent this as n.G. For this, Peter Montgomery created a method known as the Montgomery Ladder.
The basic method is:
N ← P
Q ← 0
for i from 0 to m do
if di = 1 then
Q ← point_add(Q, N)
N ← point_double(N)
return Q For a=100 we have a binary value of 1100100:
1100100, thus we double the point (N=2G). 1100100, thus we double the point (N=4G). 1100100, thus we add the point (Q=4G), and then double the point (N=8G). 1100100, thus we double the point (N=16G). 1100100, thus we double the point (N=32G). 1100100, thus we add the point (Q=4G+32G=36G), and then double the point (N=64G). 1100100, thus we add the point (Q=36G+64G=100G), and then double the point (N=128G). The result is then Q=4G+32G+64G=100G. Overall, the great advantage of this method is that we will always take the same time to compute the answer, no matter the size of the value of n. This is useful, as some cryptographic operations leak information from the time they take to compute the result. The only problem here is that the double point and point adding will have a different amount of time to compute than just t