Algorithm for elliptic curve point compression

[knightcoin]

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.

makes sense for me, thanks

[TimS]

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.

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?

[cypherdoc]

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.

thanks for this

[gmaxwell]

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?

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

[TimS]

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?

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

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!

[gmaxwell]

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!

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

[cypherdoc]

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.

in this case, k is the random number?

[Peter R]

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.

in this case, k is the random number?

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.  

[gmaxwell]

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.

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.

[BurtW]

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!

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

I believe he is referencing this great thread:

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

and specifically this post:

https://bitcointalk.org/index.php?topic=289795.msg3206788#msg3206788

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

https://bitcointalk.org/index.php?topic=289795.msg3183975#msg3183975

[cypherdoc]

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!

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

I believe he is referencing this great thread:

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

and specifically this post:

https://bitcointalk.org/index.php?topic=289795.msg3206788#msg3206788

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

https://bitcointalk.org/index.php?topic=289795.msg3183975#msg3183975

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

[cypherdoc]

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)

[Peter R]

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)

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.

[cypherdoc]

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)

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.

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

[DeathAndTaxes]

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.

[DeathAndTaxes]

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

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.

The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1 are specified by the sextuple T = (p,a,b,G,n,h) where the finite field Fp is defined by:

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

a = 0
b = 7

The base point G in compressed and uncompressed form
G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Finally the order n of G and the cofactor are:
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
h = 01

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

[cypherdoc]

thx, that clears it up.