Topic: Algorithm for elliptic curve point compression - page 2. (Read 6611 times)

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.

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.

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.




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.

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.

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.

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

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/

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.

Ignore this :

And do whatever you want.

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.

Thanks jackjack that's great.

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

https://bitcointalksearch.org/topic/compressed-keys-y-from-x-162805

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


Which gives the following public key point.


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.


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

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

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

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.

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.