
kjj
Legendary
Offline
Activity: 1302
Merit: 1025


June 18, 2013, 02:45:58 PM 

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.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.



dogisland (OP)


June 18, 2013, 02:51:52 PM 

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
Legendary
Offline
Activity: 1176
Merit: 1255
May Bitcoin be touched by his Noodly Appendage


June 18, 2013, 02:56:31 PM 

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 64character hexadecimal string

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3  Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5  Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2 Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.



dogisland (OP)


June 28, 2013, 09:22:58 AM 

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 64character hexadecimal string
OK, let me give an example of what I want to do. Take the ECDH demo here http://wwwcsstudents.stanford.edu/~tjw/jsbn/ecdh.htmlIf I generate a private key for alice I can get P = 1175846487558108474218546536054752289210804601041 Which gives the following public key point. 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. 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
Legendary
Offline
Activity: 1176
Merit: 1255
May Bitcoin be touched by his Noodly Appendage


June 28, 2013, 09:40:11 AM 

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 64character hexadecimal string
OK, let me give an example of what I want to do. Take the ECDH demo here http://wwwcsstudents.stanford.edu/~tjw/jsbn/ecdh.htmlIf I generate a private key for alice I can get P = 1175846487558108474218546536054752289210804601041 Which gives the following public key point. 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. 02583857549063195252150226340830731484791130788759 First you need to make it hexadecimalDoing 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

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3  Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5  Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2 Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.



dogisland (OP)


June 28, 2013, 01:02:03 PM 

Thanks jackjack that's great.




cypherdoc
Legendary
Offline
Activity: 1764
Merit: 1002


June 27, 2014, 06:37:37 PM 

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
Legendary
Offline
Activity: 1862
Merit: 1011
Reverse engineer from time to time


June 27, 2014, 06:53:25 PM 

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.

BTC:1AiCRMxgf1ptVQwx6hDuKMu4f7F27QmJC2



gmaxwell
Moderator
Legendary
Offline
Activity: 4186
Merit: 8435


June 27, 2014, 07:14:09 PM 

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 oneway functions), the only the xcoordinate 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
Donator
Legendary
Offline
Activity: 1218
Merit: 1079
Gerald Davis


June 27, 2014, 08:09:32 PM 

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^2562^32977). 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/arelativelyeasytounderstandprimeronellipticcurvecryptography/




DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Merit: 1079
Gerald Davis


June 27, 2014, 08:14:27 PM Last edit: June 27, 2014, 11:39:55 PM by 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_patentsOne 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
Moderator
Legendary
Offline
Activity: 4186
Merit: 8435


June 27, 2014, 10:42:17 PM 

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
Legendary
Offline
Activity: 1764
Merit: 1002


June 27, 2014, 10:42:19 PM 

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^2562^32977). 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/arelativelyeasytounderstandprimeronellipticcurvecryptography/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 xaxis implied to me that negative y coordinates were still possible in this finite field.




DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Merit: 1079
Gerald Davis


June 28, 2014, 12:14:55 AM 

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 xaxis. Over the field of F23, the negative components in the yvalues 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
Legendary
Offline
Activity: 1764
Merit: 1002


June 28, 2014, 01:03:57 AM 

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 xaxis. Over the field of F23, the negative components in the yvalues 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
Donator
Legendary
Offline
Activity: 1218
Merit: 1079
Gerald Davis


June 28, 2014, 02:20:15 AM Last edit: June 28, 2014, 02:47:31 AM by 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, n1] 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


June 28, 2014, 03:08:12 AM 

In the field F_{23}, 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
Legendary
Offline
Activity: 1764
Merit: 1002


June 28, 2014, 03:26:58 AM 

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




gmaxwell
Moderator
Legendary
Offline
Activity: 4186
Merit: 8435


June 28, 2014, 05:30:16 AM 

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.




