ECC Trivia: There Are Two Elliptic Curve Points For Every x-Axis Point

ECC Trivia: There Are Two Elliptic Curve Points For Every x-Axis Point

So, what’s the square root of 9? You, might say it is 3, but that not the right answer … as the right answer is 3 and -3. What has that go to do with cybersecurity, well, I’ll explain.

So, let me do a bit of trivia here. In ECC (Elliptic Curve Cryptography), we have a point on a curve and we operate on it. If we call that point P. Then we might add P to itself to get 2P (a point doubling). And so with 2P, I can’t reverse the operation to find P. That’s the core of the security of ECC, in that we can’t reverse an adding (or multiplying operation). We can then have a random value of n — known as a scalar value, and then compute: Q =nP. In this case, we should not be able to compute n, even though we know the points P and Q. For this, we can then define n as our secret (or private key), and Q as our public key. If we then standardize P as a generator point (G), we know have a public key system.

But, did you know we actually end up with two possible points?

Going back to my roots

ECC involves uses an equation such as:

y²=x³+ax + b (mod p)

and where p is a prime number. One example is the Bitcoin curve (secp256k1) of:

y²=x³+ 7(mod p)

and where p=2²⁵⁶ −2³²−977. So let’s do a simple example, and with the values of x from 0 to 20, and with a=0, b=7 and p=97:

from libnum import sqrtmod, has_sqrtmod

a=0
b=7
p=97
for x in range(0,20):
   ySq=x**3+a*x+b
   if (has_sqrtmod(ySq,{p:1})): 
     res=sqrtmod(ySq,{p:1})
     y=next(res)
     print(f"({x},{y}) ")
     y=next(res)
     print(f"({x},{y}) ")

In this case we determine if there’s a possible modular square for y, given a value of x:

if (has_sqrtmod(ySq,{p:1})):

If it has then it will determine it with:

res=sqrtmod(ySq,{p:1})

This returns two values for y. If we run it, we get:

(1,69) 
(1,28) 
(5,61) 
(5,36) 
(12,38) 
(12,59) 
(13,78) 
(13,19) 
(14,61) 
(14,36) 
(17,19) 
(17,78)

Let’s see how we got these points, for x=1, we have:

y² = 1 + 7 = 8 (mod 97)

If we now try the value of 69² (mod 97) and 28² (mod 97), we get:

>>> 69**2 % 97
8
>>> 28**2 % 97
8

and can see the solution the correct. We can then plot the points up to x=100 [here]:

To compress or uncompress; that is the question

So, if we have a 256-bit prime number (such as with secp256k1), our points will have 512 bits. This is know as an uncompressed point. Obviously we could compute the y co-ordinate point easily, but we will end up with two values. Actually, we always have an odd value or an even value for the two points, and so we just have to store a value that identifies if the point is even or odd. In a compressed form we store 02 in front of the x co-ordinate point if it is even, and a 03 if it is odd. This now allows us to store our point in a compressed form of 32 bytes (256 bits) and an another byte. Our compressed points thus have 33 bytes, while uncompressed points have 64 bytes.

This can be seen when we compress our public key here [here]:

Private key: f91d8f3a49805fff9289769247e984b355939679f3080156fe295229e00f25af

Public key: 52972572d465d016d4c501887b8df303eee3ed602c056b1eb09260dfa0da0ab288742f4dc97d9edb6fd946babc002fdfb06f26caf117b9405ed79275763fdb1c

Compressed public key:
0252972572d465d016d4c501887b8df303eee3ed602c056b1eb09260dfa0da0ab2

In this case, we can see that we have a 02 at the start of the compressed public key point, and followed by the x-coordinate. This means that our y-coordinate value is even. Now let’s look at another one [here]:

Private key: ac609e0cc9681f8cb63e968be20e0f19721751561944f5b4e52d54d5f27ec57b

Public key: 18ed2e1ec629e2d3dae7be1103d4f911c24e0c80e70038f5eb5548245c475f504c220d01e1ca419cb1ba4b3393b615e99dd20aa6bf071078f70fd949008e7411

Compressed public key: 0318ed2e1ec629e2d3dae7be1103d4f911c24e0c80e70038f5eb5548245c475f50

We can see that we now have a 03 at the start, followed by the x-coordinate value from the point. But how do we get the 02 or 03? Well in the first case the y-axis co-ordinate ends with a hex value of ‘c’ (1100), and which is even. In this case, we append a 02. In the second case, the y-coordinate ends with a hex value of ‘1’ (0001), and is then odd. In this case, we add a 03. The compressed key is then:

02 (x-co-ordinate) // if y is even
03 (x-co-ordinate) // if y is odd

When we need to uncompress, we can easily compute the y-coordinate value again from the x-coordinate value, and examine whether y is odd or even. This will recover the uncompressed point. Typically, an uncompressed point will start with a 04.

Finding the inverse of a point: (x,-y)

For the inverse of (x,y) we get (x,-y). This is quite easy to find as we just need to make y negative, and then take the mod of p:

y=-y %p

Our program is then:

from libnum import sqrtmod, has_sqrtmod
a=0
b=7
p=97

for x in range(0,20):
  ySq=x**3+a*x+b
  if (has_sqrtmod(ySq,{p:1})):
     res=sqrtmod(ySq,{p:1})
     y=next(res)
     print(f"({x},{y}) ")
     y=-y %p
     print(f"({x},{y}) ")

And this will give us the same run as the last time.

Conclusions

Elliptic Curve Cryptography is used in so many places, and is the core of security on the Internet. If you want to experiment, here’s the demo here:

https://asecuritysite.com/ecc/ecc_pointsv2