Cryptography Fundamentals 3: Elliptic Curve Fundamentals

Cryptography Fundamentals 3: Elliptic Curve Fundamentals

Apple podcast: [here]

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 co-ordinate value are possible. This then leads to the order, and 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 her is that the double point and point adding will have a different amount of time to compute than just the point double, and where Eve could determine if there was a 0 or a 1 in the value of n.

https://asecuritysite.com/ecc/ecc_kr2

Public key encryption

So how is this used in public key encryption? Well, first we pick a base point (G) on the elliptic curve. For our example, we could pick (2,9). Next we then pick our private key (sk). Our public key is then pk=sk.G, and where G is added to itself sk times. Our private key is thus a scalar value, and our public key is an elliptic curve point. We use this in terms of digitally signing a message, and where the private key (sk) is used to create a digital signature, and the public key validates it. The most popular methods for this are ECDSA (Elliptic Curve Digital Signature Algorithm and EdDSA (Edward Digital Signature Algorithm). I will explain these more in a future podcast.

Conclusions

And, so, for our elliptic curve, we don’t always have a valid (x,y) point, but for our Weierstrass curve, sif we do, we end up with two y values for every x co-ordinate. With our points we conduct to simple operations, a point addtion and a point doubling.