Yeah that graph doesn't make it clear but it is one of the properties having not just integer values but integer values "over" a finite field. The numbers "wrap around" when they go past the edge of the field. So in a finite field over 23 a y =-5 if reflected around the order to be y = 18 (-5 + 23).
From our patent trolls at certicom.
Note that there is two points for every x value. Even though the graph seems random, there is still symmetry about y = 11.5. Recall that elliptic curves over real numbers, there exists a negative point for each point which is reflected through the x-axis. Over the field of F23, the negative components in the y-values are taken modulo 23, resulting in a positive number as a difference from 23. Here -P = (xP, (-yP Mod 23))
Now because I have had a few, I am going to cheat and just verify the solutions rather than solve the problem. I would also point out this is a nice small (and essentially useless) finite field, real cryptography uses much much larger prime numbers.
So lets look at (1,5) & (1,18)
(y^2) % 23 = (x^3 + x) % 23
(5^2) % 23 = (1^3 +1 ) % 23
25 % 23 = 2 % 23
2 = 2 so the solution (1,5) is valid.
(y^2) % 23 = (x^3 + x) % 23
(18^2) % 23 = (1^3 +1 ) % 23
324 % 23 = 2 % 23
2 = 2 so the solution (1,18) is valid.
This also illustrates how we can use compressed keys. The y^2 means that when a point exists there will always be one reflected around the axis and having the finite field over a prime number means you will always have exactly one odd y value and exactly one even y value in that pair of points.
x=1, y = {5, 18} = one odd & one even
x=11, y = {10, 13} =one odd & one even
x=15, y = {3, 20} = one odd & one even
Bonus points if you can see where this is going. If you can compute the pair of y values* from x and they will always be an even and odd then instead of writing (15,3) or (15,20) you could write (15, O) or (15, E). Now with this tiny finite field it doesn't save much but when your values are 32 bytes you save a lot of bytes.
finally, finally, finally. now that is a brilliant explanation.
and finally a graph with the axes labeled properly and illustrating why we're dealing with positive whole numbers. isn't that what we're really dealing with here, whole numbers vs. integers (which would include negatives)? or does the fact that this is defined over a finite field exclude the negative integers?
the other thing that strikes me when eyeballing the graph is that i thought all points in a finite field would have a symmetrical reflected point and i see in this example a point at (0,0) which doesn't have a reflected point at (0,23). i'm sure this has to do with the mod 23 which wouldn't be in the field but i don't recall seeing any points on a graph like this w/o a paired point?
thx D&T. as always, very helpful.
Show Posts
