Topic: Algorithm for elliptic curve point compression (Read 6615 times)

thx, that clears it up.

Or more generally all ECC curves are over a specific finite field.  These can be broken into two groups.  They are either F2m fields which are binary fields [1, 2^m-1] or Fp fields which are prime fields [1, p-1].   The curve used by Bitcoin is in the later camp, it is a curve over an Fp field.  All the relevant details in that tutorial would be in section 3 (the corresponding math in 3.2).


Remember all ECC systems require all parties to use the domain parameters (simplistically values which define the curve and the finite field).  Secp256k1 is simply one of an infinite number of possible curves.  Since all parties must use the values, there are agreed upon standards.  Bitcoin could have used a different curve (and and altcoin could do so in the future) however two participants can't be using different domain parameters.  The domain parameters for Bitcoin are those set by Secp256k1.

https://en.bitcoin.it/wiki/Secp256k1

If you are looking for the math related to Bitcoin Secp256k1, it is a curve over a prime field (Fp).  The equivalent section would be 3.2.

For any finite field all values must be one of the finite values within the field.  For a F2m field the range of possible values are the natural numbers [1, 2^m-1].  So a negative number is never a valid number as it is outside the finite field.  While curves over real numbers can have an infinite number of points, curves over finite fields have a specific finite (but usually in cryptography very very large) number of values.

are you saying that b/c elements of the field F2m are m-bit strings, they don't apply to Bitcoin?

You're just looking in the wrong section. Bitcoin uses a prime field:

http://www.certicom.com/index.php/32-arithmetic-in-an-elliptic-curve-group-over-fp

From Certicom:  The negative of the point P = (xP, yP) is the point -P = (xP, -yP mod p)

Note to readers: because of the modulus operation, the "negative" of P is always a pair of non-negative numbers.

from Certicom:  The negative of the point P = (xP, yP) is the point -P = (xP, xP + yP)

http://www.certicom.com/index.php/42-arithmetic-in-an-elliptic-curve-group-over-f2m

is that right?  i thought it should be:  The negative of the point P = (xP, yP) is the point -P = (xP, -yP)

yeah, thanks for reminding me of that thread.  had been following superficially back then but my understanding is much better now.

I believe he is referencing this great thread:

https://bitcointalksearch.org/topic/nsa-and-ecc-289795

and specifically this post:

https://bitcointalksearch.org/topic/m.3206788

This (and the comments that followed) are also very interesting:

https://bitcointalksearch.org/topic/m.3183975

Just because people might misunderstand: K must be unknown to the attacker. Even if a K value is only used once, if an attacker has knoweldge of K and a single signature with it they can also recover the private key. It's also important that your Ks are not linearly related, or otherwise more sophisticated attacks are still possible.

The variable k is the per-message secret number used when producing the ECDSA signature.  It doesn't need to be random, but if two different messages are signed with the same value for k, then the private key can be determined algebraically.  This "repeat k-value" problem led to the hack of the Sony PS3 in 2010 and the more recent bitcoin thefts from the Android wallets (due to a bug in the SecureRandom Java class which led to the same k value being used more than once).  

There is presently a push to use deterministic k values, as specified by RFC 6979, to eliminate the need for secure RNGs when producing signatures.  

in this case, k is the random number?

Yep.

There was another thread in this subform where we showed that all of the secp256k1 parameters can be deterministically derived from reasonable first principles— even ones simpler than the ones we know where actually used (e.g. you don't have to require that the curve have the efficient endomorphism, a practical increment from zero search still finds ours first), except for the generator point— whos value is irrelevant for security assumptions except in somewhat contrived situations (basically if someone from cetricom or the NSA shows up and tries to convince you that they don't know the discrete log of to_point(H(pi)) on our curve, you might not want to believe them because G could have been selected in such a way as to make the discrete log of a chosen in advance but seemingly nothing up my sleeve point known).

Ok, that sounds reasonable enough (from what I understand). So the way it's derived is:
nextprime(2^256 - 2^32 - 2^10)
This makes me more confident that there's "nothing up my sleeve" than 2^256 - 2^32 - 977 or 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1. Thanks!

Sorry, the criteria also required that x < 1024, the performance speed-up requires x to be a small integer.

thanks for this

2^256-2^32-x is prime for the following positive x: 263, 359, 361, 487, 739, 949, 977, 1049, 1057, 1339, ...
This explanation doesn't make sense to me: there are larger x, and smaller x. Either it's outright wrong, or not explained very clearly. Can you clarify?

makes sense for me, thanks

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.

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

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).

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.