Algorithm for elliptic curve point compression

[dogisland]

I'd be grateful if someone here could help out with curve compression for me.

http://stackoverflow.com/questions/17171542/algorithm-for-elliptic-curve-point-compression

Thanks.

[1713291477]

1713291477

[1713291477]

1713291477

[1713291477]

1713291477

[1713291477]

1713291477

[1713291477]

1713291477

[kjj]

Compression is easy.  Look at the last bit of the Y coordinate, add it to 0x02 and use that as the flag instead of 0x04.  Then discard Y.

[dogisland]

Compression is easy.  Look at the last bit of the Y coordinate, add it to 0x02 and use that as the flag instead of 0x04.  Then discard Y.

Sorry, you lost me a bit there. What is 0x02 and 0x04 ?

[jackjack]

A public key is a point (X, Y)
Its serialization is 04+X+Y as uncompressed, and (02+X as compressed if Y is even), and (03+X as compressed if Y is odd). X and Y are here the corresponding 64-character hexadecimal string

[dogisland]

A public key is a point (X, Y)
Its serialization is 04+X+Y as uncompressed, and (02+X as compressed if Y is even), and (03+X as compressed if Y is odd). X and Y are here the corresponding 64-character hexadecimal string

OK, let me give an example of what I want to do. Take the ECDH demo here http://www-cs-students.stanford.edu/~tjw/jsbn/ecdh.html

If I generate a private key for alice I can get

Code:

P = 1175846487558108474218546536054752289210804601041

Which gives the following public key point.

Code:

X = 583857549063195252150226340830731484791130788759
Y = 1195037839477751118658084226553581900533276838164

So with the compression above, Y is even so I prefix with 02 and use X as the point so the compressed point would be.

Code:

02583857549063195252150226340830731484791130788759

So how would I go from the above back to the original X,Y point assuming I don't have the private key ?

[jackjack]

A public key is a point (X, Y)
Its serialization is 04+X+Y as uncompressed, and (02+X as compressed if Y is even), and (03+X as compressed if Y is odd). X and Y are here the corresponding 64-character hexadecimal string

OK, let me give an example of what I want to do. Take the ECDH demo here http://www-cs-students.stanford.edu/~tjw/jsbn/ecdh.html

If I generate a private key for alice I can get

Code:

P = 1175846487558108474218546536054752289210804601041

Which gives the following public key point.

Code:

X = 583857549063195252150226340830731484791130788759
Y = 1195037839477751118658084226553581900533276838164

So with the compression above, Y is even so I prefix with 02 and use X as the point so the compressed point would be.

Code:

02583857549063195252150226340830731484791130788759

First you need to make it hexadecimal
Doing this you see that it has 40 digits which is "too low", it should be 64 (or 63 or sometimes less). I think you clicked on a curve with too small parameters, try secp256r1. (but be aware it's not the curve Bitcoin uses!)

Then do it again.
For example: private key = 85028609766675152251934575542315533189276559485968373120473797427005522772778
That makes
X=74025470963109022618637889099135097200712436357290103177754999741983793503008
Y=50024355523753322356558351156744867670202798471897393499007716154220308517913

So:
X(hex)=a3a8ee8a09fa012934eb0eee2150d4bcb6268f2b4430abf31f4a58c95b365b20
Y(hex)=6e98c827edc5e80829c71e1fa9a83043379344316ba641d7c9c0850f687ed419

So the two corresponding public keys are
pbk1='04a3a8ee8a09fa012934eb0eee2150d4bcb6268f2b4430abf31f4a58c95b365b206e98c827edc5e 80829c71e1fa9a83043379344316ba641d7c9c0850f687ed419'
pbk2='03a3a8ee8a09fa012934eb0eee2150d4bcb6268f2b4430abf31f4a58c95b365b20' because Y is odd

So how would I go from the above back to the original X,Y point assuming I don't have the private key ?

https://bitcointalk.org/index.php?topic=162805.0

[dogisland]

Thanks jackjack that's great.

[cypherdoc]

shouldn't it be possible for Y to be a negative number?  assuming so, i guess it wouldn't change whether it's odd or even.

[Remember remember the 5th of November]

I'd be grateful if someone here could help out with curve compression for me.

http://stackoverflow.com/questions/17171542/algorithm-for-elliptic-curve-point-compression

Thanks.

Ignore this :

Compression of elliptic curve points is patented by Certicom, so you should not use it without the license, generally.

And do whatever you want.

[gmaxwell]

Compression of elliptic curve points is patented by Certicom, so you should not use it without the license, generally.

Thats also outrageously incorrect, it's the kind of misinformation repeated by idiots who have no idea how patents works, usually thinking the title of the patent or abstract text specifies what the patent covers (when really the scope is established by the independent claims).

All "compression" means is sending only the X corrd plus one bit of the Y it should hardly be called "compression" as much has omitting redundant data.

The observation that only the X coordinate was needed was made in the earliest of ECC papers— including, Miller, V., "Use of elliptic curves in cryptography" from 1985: "Finally, it should be remarked, that even though we have phrased everything in terms of points on en elliptic curve, that, for the key exchange protocol (and other uses as one-way functions), the only the x-coordinate needs to be transmitted."

If anyone were to have obtained a patent as broad as that it would be invalid, trivially so due to the Miller cite above and many other prior descriptions of the techniques.

[DeathAndTaxes]

shouldn't it be possible for Y to be a negative number?  assuming so, i guess it wouldn't change whether it's odd or even.

No it isn't possible. When most people hear elliptic curve they think of real numbers (-3.387232, 4.478221).  The elliptical curves used in cryptography are over finite fields.  All the values are positive integers modulo a realllllly big prime number (for secp256k1 it is 2^256-2^32-977).

Finite fields make working with curves a completely different concept.  The "curves" when graphed over a finite field don't even resemble what most people visualize when they hear eliptical curve cryptography.

Here is a pretty good article on ECC in general (if short on time page 2 is the part that is most relevant)
http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

[DeathAndTaxes]

If anyone were to have obtained a patent as broad as that it would be invalid, trivially so due to the Miller cite above and many other prior descriptions of the techniques.

This is a pet peve of mine as well.  That being said anyone looking to develop some novel applications using ECC should take a close look at Certicom's patent arsenal.
http://en.wikipedia.org/wiki/ECC_patents

One bright point is their patent on actual ECC compression should expire next month, and it involves a lot more than dropping the y value because it can be recomputed.
http://www.google.com/patents/US6141420

[gmaxwell]

Its unfortunate— more than anything else patents slayed ecash the first time around... they substantially hamper the deployment of cryptographic tech on the internet, — even when they're not actually applicable getting people to deploy cryptographic technology is uphill enough that the small amount of uncertainty from patents completely tips the balance.

Before getting too worried by DeathAndTaxes reasonable suggestion,— you really shouldn't attempt it without first taking some time to learn about how to read patents, any of that reading should also be read along side RFC 6090 which firmly establishes the unpatentable prior art basis for elliptic curve technology.

[cypherdoc]

shouldn't it be possible for Y to be a negative number?  assuming so, i guess it wouldn't change whether it's odd or even.

No it isn't possible. When most people hear elliptic curve they think of real numbers (-3.387232, 4.478221).  The elliptical curves used in cryptography are over finite fields.  All the values are positive integers modulo a realllllly big prime number (for secp256k1 it is 2^256-2^32-977).

Finite fields make working with curves a completely different concept.  The "curves" when graphed over a finite field don't even resemble what most people visualize when they hear eliptical curve cryptography.

Here is a pretty good article on ECC in general (if short on time page 2 is the part that is most relevant)
http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

thanks for referring me back to this article.  even though i've read it a couple of times i never understood the fact that the finite curve below only represented whole numbers.  it's tricky (to me) b/c of the horizontal symmetry around what looks like an x-axis implied to me that negative y coordinates were still possible in this finite field.

[DeathAndTaxes]

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.

[cypherdoc]

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.

[DeathAndTaxes]

Correct for ECC we are always working with a finite set of positive whole numbers excluding zero (sometimes called natural numbers) that are less than p, a designated prime.   For the example above p would be 23 and in secp256k1 p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1.   The example graph while clearer would be even better if it covered an interval of 1 through 22 for both x and y.  

Zero is an exception and because of its unique properties is unsuitable for cryptography.  In ECDSA private keys must be in the interval of [1, n-1] and in signatures the k value must also be in the same interval.  If the computed signature has a value of zero for r or s then it is invalid and a new k value used.

[TimS]

In the field F₂₃, -1 = 22, -2 = 21, etc. For simplicity, the canonical way we refer to them is usually as natural numbers, but it wouldn't be incorrect to think of 22 as -1. The symmetry of DeathAndTaxes's graph is more apparent if you do this: imagine the labels going from -1, -2, .. -11, 11, .. 2, 1. This makes it clear why the symmetry is around 11.5, and e.g. why the reflection of 10, -10, is equal to 13 (-10 = 13 mod 23).

[cypherdoc]

how is this derived?:  p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1

[gmaxwell]

how is this derived?:  p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1

It's a system parameter, it must be a finite field which has size near 2^256 to achieve ~128 bit security, but less than 2^256 to avoid needing more space, to make the modular reductions faster the number selected is a generalized mersenne number. In the case of secp256k1 was selected by picking the largest x such that 2^256 - 2^32 - x is prime. You can search for "generalized mersenne number" to find the Solinas paper about how fields of sizes with special form yield more efficient computation.