Unless one can deeply understand the math and cryptography for
themselves, we all have to trust the community and those
that do have the specialized knowledge.
I try to understand as best I can as a hobby, but
I simply don't have the time or energy to devote
to understanding every aspect of Bitcoin.
Topic: This message was too old and has been purged (Read 7931 times)
legendary
Activity: 1302
Merit: 1008
Core dev leaves me neg feedback #abuse #political
Yeah using secp256r1 would have been a nightmare. The NSA doesn't screw up this badly. Cryptographic constants should be "nothing up my sleeve numbers". Lets look how the NSA "randomly" came up with the parameters for secp256r1
Ok so lets work backwards.
We want p & q to be prime numbers (or probably prime).
So we use a generator to try values in sequence and use the first curve for a given security strength which meets our requirements. Why do we use the FIRST value? To provide a level of reassurance that it is legit and not chosen for a malicious reason. If there were 4872498374938247398 valid curves and the NSA picked the 4872498374938247399th one that would be suspicious right. Alright so we are using the first one we find, building some trust here. That is good.
Ok so how do we seed the generator. We take the hash of some number at random? WTF? Did some 2 bit scammer on bitcointalk come up with this method? I mean this is the fracking NSA. They know a "little" about cryptography. There is no possible way they "forgot" that this makes all the subsequent steps worthless. I mean it is like saying "You can trust me because you can trust me" See I am not asking you to trust me blindly. I gave you a specific reason why you can trust me."
Now the NSA isn't stupid. The obvious elephant in the room is how do we know the "random" seed value is random. Maybe the NSA went through quadrillions of random seed values until they found one which when hashes produces a sequence such that the first valid curve is the one which has a property that the NSA knows has a weakness. In other words all the song and dance about following this generator sequence and performing various checks is predicated on the generator seed being chosen "fairly" but they just happened to forget that the seed for the generator isn't provable or even probably fair (nothing up my sleeve) and thus the entire process is security theater.
Formally
You can stop reading at step #1. The foundation is sand. So what was the domain parameter seed picked at random over all others (you can trust us )?
c49d3608 86e70493 6a6678e1 139d26b7 819f7e90
A totally arbitrary number. Was this the first one the NSA tried? Or did they have their super computer crunching for years before they came up with this seed which when you follow the rest of their "sleight of hand" generator produced the "random" curve which is EXACTLY what they wanted it to be for some reason only they know? The rest of their security process is just feel good security. It is the wand in a magic trick so you don't look closely to the fact that the magician is just cheating with his other hand.
Now if the seed for secp256r1 was say the first 160 bits of pi well we would have at least some confidence that the curve produced was strong. It would be a rather extreme coincidence that the first 160 bits of pi happened to produce a curve which the NSA knew was weak.
Quote
Previous versions of this Standard contained a method for the generation of the domain
parameters p and q using SHA-1 and probabilistic methods. This method is no longer approved
for domain parameter generation; however, the validation process for this method is provided in
Appendix A.1.1.1 to validate previously generated domain parameters.
A method for the generation and validation of the primes p and q using probabilistic methods is
provided in Appendix A.1.1.2 and is based on the use of an approved hash function; this method
shall be used for generating probable primes. The validation process for this method is provided
in Appendix A.1.1.3.
The probabilistic methods use a hash function and an arbitrary seed (domain_parameter_seed).
Arbitrary seeds could be anything, e.g., a user’s favorite number or a random or pseudorandom
number output by a random number generator (see SP 800-90). The domain_parameter_seed
determines a sequence of candidates for p and q in the required intervals that are then tested for
primality using a probabilistic primality test (see Appendix C.3). The test determines that the
candidate is either not a prime (i.e., it is a composite integer) or is “probably a prime” (i.e., there
is a very small probability that a composite integer will be declared to be a prime). p and q shall
be the first candidate set that passes the primality tests. Note that the domain_parameter_seed
shall be unique for every unique set of domain parameters that are generated using the same
method.
parameters p and q using SHA-1 and probabilistic methods. This method is no longer approved
for domain parameter generation; however, the validation process for this method is provided in
Appendix A.1.1.1 to validate previously generated domain parameters.
A method for the generation and validation of the primes p and q using probabilistic methods is
provided in Appendix A.1.1.2 and is based on the use of an approved hash function; this method
shall be used for generating probable primes. The validation process for this method is provided
in Appendix A.1.1.3.
The probabilistic methods use a hash function and an arbitrary seed (domain_parameter_seed).
Arbitrary seeds could be anything, e.g., a user’s favorite number or a random or pseudorandom
number output by a random number generator (see SP 800-90). The domain_parameter_seed
determines a sequence of candidates for p and q in the required intervals that are then tested for
primality using a probabilistic primality test (see Appendix C.3). The test determines that the
candidate is either not a prime (i.e., it is a composite integer) or is “probably a prime” (i.e., there
is a very small probability that a composite integer will be declared to be a prime). p and q shall
be the first candidate set that passes the primality tests. Note that the domain_parameter_seed
shall be unique for every unique set of domain parameters that are generated using the same
method.
Ok so lets work backwards.
We want p & q to be prime numbers (or probably prime).
So we use a generator to try values in sequence and use the first curve for a given security strength which meets our requirements. Why do we use the FIRST value? To provide a level of reassurance that it is legit and not chosen for a malicious reason. If there were 4872498374938247398 valid curves and the NSA picked the 4872498374938247399th one that would be suspicious right. Alright so we are using the first one we find, building some trust here. That is good.
Ok so how do we seed the generator. We take the hash of some number at random? WTF? Did some 2 bit scammer on bitcointalk come up with this method? I mean this is the fracking NSA. They know a "little" about cryptography. There is no possible way they "forgot" that this makes all the subsequent steps worthless. I mean it is like saying "You can trust me because you can trust me" See I am not asking you to trust me blindly. I gave you a specific reason why you can trust me."
Now the NSA isn't stupid. The obvious elephant in the room is how do we know the "random" seed value is random. Maybe the NSA went through quadrillions of random seed values until they found one which when hashes produces a sequence such that the first valid curve is the one which has a property that the NSA knows has a weakness. In other words all the song and dance about following this generator sequence and performing various checks is predicated on the generator seed being chosen "fairly" but they just happened to forget that the seed for the generator isn't provable or even probably fair (nothing up my sleeve) and thus the entire process is security theater.
Formally
Quote
D.5 Generation of Pseudo-Random Curves (Prime Case)
Let l be the bit length of p, and define
v = ( l – 1) /160
w = l – 160v – 1.
1. Choose an arbitrary 160-bit string s as the domain parameter seed.
2. Compute h = SHA-1(s).
3. Let h0 be the bit string obtained by taking the w rightmost bits of h.
4. Let z be the integer whose binary expansion is given by the 160-bit string s.
5. For i from 1 to v do:
5.1 Define the 160-bit string si to be binary expansion of the integer
(z + i) mod (2 160).
5.2 Compute hi = SHA-1(si).
6. Let h be the bit string obtained by the concatenation of h0 , h1, … , hv as follows:
h = h0 || h1 || … || hv.
7. Let c be the integer whose binary expansion is given by the bit string h.
8. If ((c = 0 or 4c + 27 ≡ 0 (mod p))), then go to Step 1.
9. Choose integers a, b ∈GF(p) such that
c b^2 ≡ a^3 (mod p).
(The simplest choice is a = c and b = c. However, one may want to choose differently for
performance reasons.)
10. Check that the elliptic curve E over GF(p) given by y^2 = x^3 + ax + b has suitable order.
If not, go to Step 1.
Let l be the bit length of p, and define
v = ( l – 1) /160
w = l – 160v – 1.
1. Choose an arbitrary 160-bit string s as the domain parameter seed.
2. Compute h = SHA-1(s).
3. Let h0 be the bit string obtained by taking the w rightmost bits of h.
4. Let z be the integer whose binary expansion is given by the 160-bit string s.
5. For i from 1 to v do:
5.1 Define the 160-bit string si to be binary expansion of the integer
(z + i) mod (2 160).
5.2 Compute hi = SHA-1(si).
6. Let h be the bit string obtained by the concatenation of h0 , h1, … , hv as follows:
h = h0 || h1 || … || hv.
7. Let c be the integer whose binary expansion is given by the bit string h.
8. If ((c = 0 or 4c + 27 ≡ 0 (mod p))), then go to Step 1.
9. Choose integers a, b ∈GF(p) such that
c b^2 ≡ a^3 (mod p).
(The simplest choice is a = c and b = c. However, one may want to choose differently for
performance reasons.)
10. Check that the elliptic curve E over GF(p) given by y^2 = x^3 + ax + b has suitable order.
If not, go to Step 1.
You can stop reading at step #1. The foundation is sand. So what was the domain parameter seed picked at random over all others (you can trust us
c49d3608 86e70493 6a6678e1 139d26b7 819f7e90
A totally arbitrary number. Was this the first one the NSA tried? Or did they have their super computer crunching for years before they came up with this seed which when you follow the rest of their "sleight of hand" generator produced the "random" curve which is EXACTLY what they wanted it to be for some reason only they know? The rest of their security process is just feel good security. It is the wand in a magic trick so you don't look closely to the fact that the magician is just cheating with his other hand.
Now if the seed for secp256r1 was say the first 160 bits of pi well we would have at least some confidence that the curve produced was strong. It would be a rather extreme coincidence that the first 160 bits of pi happened to produce a curve which the NSA knew was weak.
so........ where does all that put us about the likelihood
that insider knowledge of elliptic curve manipulation
exists?
After researching this quite a bit and several emails with one of the guys from the group that designed secp256k1 without input from NIST or the NSA. I personally, and many others who were involved, are convinced that all the parameters used in the secp256k1 curve are reasonable and can be accounted for. In other words, as opposed to the more popular secp256r1 curve, which was designed directly by NIST/NSA and uses "magic numbers" supplied directly by them, there are no "magic numbers" used in the design of the curve we use in the Bitcoin protocol. that insider knowledge of elliptic curve manipulation
exists?
legendary
Activity: 1302
Merit: 1008
Core dev leaves me neg feedback #abuse #political
so........ where does all that put us about the likelihood
that insider knowledge of elliptic curve manipulation
exists?
that insider knowledge of elliptic curve manipulation
exists?
This message was too old and has been purged
Just wanted to throw in that *every* multiplicative group of a finite field is cyclic.
You are right. That's what I get for trying to be smart about a subject I don't understand well. The point was that you have to be careful when selecting the finite field.
It seems it can be great idea to make new curve based on open and peer reviewed standards.
There is no need to do that. There is nothing wrong with or even slightly hinky about the curve we are using as discussed in detail in the thread described in this post:https://bitcointalksearch.org/topic/m.4568250
It seems it can be great idea to make new curve based on open and peer reviewed standards.
This message was too old and has been purged
and do you want to know what is even more bizarre?
just prior to the release of ECC, there was a significant mathematical work in the realm of Elliptic Curves and Cyclic groups! Thus it very plausible to suspect that insider knowledge of elliptic curve manipulation exists.
http://math.stanford.edu/~lekheng/flt/wiles.pdf
is it a coincidence that ECC became a standard not long after pioneering work in the exact theoretical field in which they are situated?
-bm
Hey Guys,
We all know, that the security of ECDSA relies on the complexity of solving the discrete logarithm problem in cyclic groups. ECDSA works on Kolitz-Curves which have a prime number, that they use as the modulo, and a generator which is a primitive root on the curve which - when exponentiated - is able to generate all other elements of the group.
To all of you, who do not know what the discrete logarithm is, here comes a short explanation:
Let us say we work on the Group Z/29Z - that means we have a cyclic group modulo 29. Further let's say we have a generator point 3. It is impossible to solve the equation:
3^x mod 29 = 13 mod 29
The solution is by the way x=26, which can be only found out by trying all possible combinations.
However, being n the primnumber to calculate the modulus, to compute a discrete logarithm it suffices to be able to get the prime factorization of n+1. To make this as hard as possible the prime number n is usually chosen to be 2q+1 where q is another very large prime number.
NOW COMES THE DANGER:
If the creator of the curve (be it the NIST or the founder of secp256k1) chooses the primenumbers in such a way that p-1 has a small known prime factor
... then despite the prime looks purely random to the average joe, the creator knows the prime factorization and may solve any discrete logarithm in this cyclic group easily (for example using the Pohlig-Hellman algorithm)
What I want to say: If any of the creators remembered the prime factors during creation of the curve, he can calculate your private key in an instant.
All I want to say is: do not trust anyone!
We all know, that the security of ECDSA relies on the complexity of solving the discrete logarithm problem in cyclic groups. ECDSA works on Kolitz-Curves which have a prime number, that they use as the modulo, and a generator which is a primitive root on the curve which - when exponentiated - is able to generate all other elements of the group.
To all of you, who do not know what the discrete logarithm is, here comes a short explanation:
Let us say we work on the Group Z/29Z - that means we have a cyclic group modulo 29. Further let's say we have a generator point 3. It is impossible to solve the equation:
3^x mod 29 = 13 mod 29
The solution is by the way x=26, which can be only found out by trying all possible combinations.
However, being n the primnumber to calculate the modulus, to compute a discrete logarithm it suffices to be able to get the prime factorization of n+1. To make this as hard as possible the prime number n is usually chosen to be 2q+1 where q is another very large prime number.
NOW COMES THE DANGER:
If the creator of the curve (be it the NIST or the founder of secp256k1) chooses the primenumbers in such a way that p-1 has a small known prime factor
... then despite the prime looks purely random to the average joe, the creator knows the prime factorization and may solve any discrete logarithm in this cyclic group easily (for example using the Pohlig-Hellman algorithm)
What I want to say: If any of the creators remembered the prime factors during creation of the curve, he can calculate your private key in an instant.
All I want to say is: do not trust anyone!
It's well known thath you can't have an elliptic curve over any arbitrary field. If you have an EC over a cyclic group, the discrete logarithm can be easily computed. You need special groups over which you contrstruct EC for them to be usable in cryptography.
legendary
Activity: 1302
Merit: 1008
Core dev leaves me neg feedback #abuse #political
Can anyone recommend a good ECC video for beginners? I watched 1 or 2 but they were kind of dry, so please let me know if you know of some really good ones. Not looking to become an expert...I just want to learn some of the basic principles. Thanks. JF
and do you want to know what is even more bizarre?
just prior to the release of ECC, there was a significant mathematical work in the realm of Elliptic Curves and Cyclic groups! Thus it very plausible to suspect that insider knowledge of elliptic curve manipulation exists.
http://math.stanford.edu/~lekheng/flt/wiles.pdf
is it a coincidence that ECC became a standard not long after pioneering work in the exact theoretical field in which they are situated?
-bm
Hey Guys,
We all know, that the security of ECDSA relies on the complexity of solving the discrete logarithm problem in cyclic groups. ECDSA works on Kolitz-Curves which have a prime number, that they use as the modulo, and a generator which is a primitive root on the curve which - when exponentiated - is able to generate all other elements of the group.
To all of you, who do not know what the discrete logarithm is, here comes a short explanation:
Let us say we work on the Group Z/29Z - that means we have a cyclic group modulo 29. Further let's say we have a generator point 3. It is impossible to solve the equation:
3^x mod 29 = 13 mod 29
The solution is by the way x=26, which can be only found out by trying all possible combinations.
However, being n the primnumber to calculate the modulus, to compute a discrete logarithm it suffices to be able to get the prime factorization of n+1. To make this as hard as possible the prime number n is usually chosen to be 2q+1 where q is another very large prime number.
NOW COMES THE DANGER:
If the creator of the curve (be it the NIST or the founder of secp256k1) chooses the primenumbers in such a way that p-1 has a small known prime factor
... then despite the prime looks purely random to the average joe, the creator knows the prime factorization and may solve any discrete logarithm in this cyclic group easily (for example using the Pohlig-Hellman algorithm)
What I want to say: If any of the creators remembered the prime factors during creation of the curve, he can calculate your private key in an instant.
All I want to say is: do not trust anyone!
We all know, that the security of ECDSA relies on the complexity of solving the discrete logarithm problem in cyclic groups. ECDSA works on Kolitz-Curves which have a prime number, that they use as the modulo, and a generator which is a primitive root on the curve which - when exponentiated - is able to generate all other elements of the group.
To all of you, who do not know what the discrete logarithm is, here comes a short explanation:
Let us say we work on the Group Z/29Z - that means we have a cyclic group modulo 29. Further let's say we have a generator point 3. It is impossible to solve the equation:
3^x mod 29 = 13 mod 29
The solution is by the way x=26, which can be only found out by trying all possible combinations.
However, being n the primnumber to calculate the modulus, to compute a discrete logarithm it suffices to be able to get the prime factorization of n+1. To make this as hard as possible the prime number n is usually chosen to be 2q+1 where q is another very large prime number.
NOW COMES THE DANGER:
If the creator of the curve (be it the NIST or the founder of secp256k1) chooses the primenumbers in such a way that p-1 has a small known prime factor
... then despite the prime looks purely random to the average joe, the creator knows the prime factorization and may solve any discrete logarithm in this cyclic group easily (for example using the Pohlig-Hellman algorithm)
What I want to say: If any of the creators remembered the prime factors during creation of the curve, he can calculate your private key in an instant.
All I want to say is: do not trust anyone!
*listen*
Is that your final answer? 
Better check wolfram alpha, shit
...I have however not seen any statistical analysis of how high the chances are given we have x bitcoin addresses with balance right now.
perhaps https://eprint.iacr.org/2013/734.pdf
This message was too old and has been purged
Is that your final answer?
Wait a second...
...well I'm glad that's over
This message was too old and has been purged
Careful now
But
p = 2256 - 232 - 977 = 2256 - 232 + (210 - 25 - 23 - 22 - 21 - 20)
p = 2256 - 232 - 977 = 2256 - 232 - (+210 - 25 - 23 - 22 - 21 - 20)
watch that pesky distributive property
whew...
Actually the Prime is:
2256 - 232 - (210 - 25 - 23 - 22 - 21 - 20)
2256 - 232 - (210 - 25 - 23 - 22 - 21 - 20)
But
p = 2256 - 232 - 977 = 2256 - 232 - (+210 - 25 - 23 - 22 - 21 - 20)
whew...
This message was too old and has been purged
Jump to: