knightcoin
Full Member
Offline
Activity: 238
Merit: 100
Stand on the shoulders of giants
|
|
June 28, 2014, 05:48:52 AM |
|
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
|
|
June 28, 2014, 03:11:50 PM |
|
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
Legendary
Offline
Activity: 1764
Merit: 1002
|
|
June 28, 2014, 04:59:27 PM |
|
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
Moderator
Legendary
Offline
Activity: 4200
Merit: 8439
|
|
June 28, 2014, 05:46:43 PM |
|
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
|
|
June 28, 2014, 08:53:41 PM |
|
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
Moderator
Legendary
Offline
Activity: 4200
Merit: 8439
|
|
June 28, 2014, 10:54:27 PM |
|
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
Legendary
Offline
Activity: 1764
Merit: 1002
|
|
July 01, 2014, 10:52:31 PM |
|
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
Legendary
Offline
Activity: 1162
Merit: 1007
|
|
July 02, 2014, 12:15:06 AM |
|
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
Moderator
Legendary
Offline
Activity: 4200
Merit: 8439
|
|
July 02, 2014, 12:38:24 AM Last edit: July 02, 2014, 01:39:53 AM by 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
Legendary
Offline
Activity: 2646
Merit: 1136
All paid signature campaigns should be banned.
|
|
July 02, 2014, 01:01:36 AM |
|
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.0and specifically this post: https://bitcointalk.org/index.php?topic=289795.msg3206788#msg3206788This (and the comments that followed) are also very interesting: https://bitcointalk.org/index.php?topic=289795.msg3183975#msg3183975
|
Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
|
|
|
cypherdoc
Legendary
Offline
Activity: 1764
Merit: 1002
|
|
July 02, 2014, 07:12:23 PM |
|
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.0and specifically this post: https://bitcointalk.org/index.php?topic=289795.msg3206788#msg3206788This (and the comments that followed) are also very interesting: https://bitcointalk.org/index.php?topic=289795.msg3183975#msg3183975yeah, thanks for reminding me of that thread. had been following superficially back then but my understanding is much better now.
|
|
|
|
|
|
cypherdoc
Legendary
Offline
Activity: 1764
Merit: 1002
|
|
July 08, 2014, 06:20:35 PM |
|
are you saying that b/c elements of the field F2m are m-bit strings, they don't apply to Bitcoin?
|
|
|
|
DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Merit: 1079
Gerald Davis
|
|
July 08, 2014, 06:21:40 PM |
|
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
Donator
Legendary
Offline
Activity: 1218
Merit: 1079
Gerald Davis
|
|
July 08, 2014, 06:24:21 PM |
|
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
Legendary
Offline
Activity: 1764
Merit: 1002
|
|
July 08, 2014, 06:27:09 PM |
|
thx, that clears it up.
|
|
|
|
|