For a finite field elliptic curve we can search for the first 100 points for a curve of \(y^2 = x^3 + ax +b\) and for a defined prime number (\(p\)):
First 100 Elliptic Curve Points |
Background
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.
ECC involves uses an equation such as:
\(y^2=x^3+ax + b \pmod 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^{256} −2^{32}−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^2 = 1 + 7 = 8 \pmod {97})\)
If we now try the value of \(69^2 \pmod {97}\) and \(28^2 \pmod {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]:
Compressed or uncompressed point
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:
rom 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.
Presentation
The following is an outline: