Hello everybody.
I'm sorry for off topic. Please, see me thread, I need help. I saw what you have deep knowledge of bitcoin.
https://bitcointalksearch.org/topic/what-is-the-bast-way-for-find-privkey-range-from-address-or-pubkey-5259592
Big thank you.
Topic: Luck when selecting Secp256k1 parameters (Read 238 times)
When a=0, for every prime p>=5 and p=2 mod 3, we get number of points n=p+1, which is always not prime.
When p=1 mod 3, there are 6 possible number of points.
There are (p-1)/6 values of b in interval (0,p) which produce the same n.
Let p=2256-s, s=232+t.
t=977 is the first prime p, which gives a curve with prime number of points (n).
The smallest positive value for b and prime n is b=7.
In the other five possibilities we have non-prime number of points, also 3 of the curves have torsion 2, 3, and 14.
Something interesting is, that the number of points of y2=x3+7 mod n = p, which might have been an additional requirement.
When p=1 mod 3, there are 6 possible number of points.
There are (p-1)/6 values of b in interval (0,p) which produce the same n.
Let p=2256-s, s=232+t.
t=977 is the first prime p, which gives a curve with prime number of points (n).
The smallest positive value for b and prime n is b=7.
In the other five possibilities we have non-prime number of points, also 3 of the curves have torsion 2, 3, and 14.
Something interesting is, that the number of points of y2=x3+7 mod n = p, which might have been an additional requirement.
However, the endormposhism (x,y)->(beta.x,y) is strange. There is well a (lamba,beta) such as lambda^2 + lamda + 1 = 0 (mod n) and beta^2 + beta + 1 = 0 (mod p) (a primitive cubic root of unity, p=1(mod 3) and n=1(mod 3)) but the value of lambda does not bring very interesting things. No speed up in doubling or adding formula.
You are mistaken because your focus has been on things like DL breaking which is a very weird and contrived usage. 
The existence of the endomorphism is a roughly 20% speedup in a plain multi-exp due to halving the number of doublings. What it does is gives many algorithms which could be batched across multiple point the efficiency they'd have at twice the number of pubkeys. It's a pretty big speedup and AFAIK at an equivalent level of optimization it makes secp256k1 the fastest to verify of any widely deployed curve. So the motivation there is pretty clear, I think.
Quote
There is a weakness in some curves that was not known when the parameters were chosen, but I guess bitcoin got lucky (yet again).
I don't believe that is currently the case, -- that's a rather tall claim and begs for concrete justification. Got a cite?b=5 wouldn't have been used because the resulting group isn't prime ordered.
a=0 is necessary to get the endomorphism (also leads to slightly faster group law).
I don't think these parameters have been chosen more or less randomly, just to ease some calculations, and that we can say that "bitcoin is lucky".
They probably make a search to get a prime near 2^256 for the field, a prime order, a large enough embedding degree, etc, ...
However, the endormposhism (x,y)->(beta.x,y) is strange. There is well a (lamba,beta) such as lambda^2 + lamda + 1 = 0 (mod n) and beta^2 + beta + 1 = 0 (mod p) (a primitive cubic root of unity, p=1(mod 3) and n=1(mod 3)) but the value of lambda does not bring very interesting things. No speed up in doubling or adding formula. This choice is strange and may be the weakness (if there is a weakness) will come from complex multiplication or something in this area...
They probably make a search to get a prime near 2^256 for the field, a prime order, a large enough embedding degree, etc, ...
However, the endormposhism (x,y)->(beta.x,y) is strange. There is well a (lamba,beta) such as lambda^2 + lamda + 1 = 0 (mod n) and beta^2 + beta + 1 = 0 (mod p) (a primitive cubic root of unity, p=1(mod 3) and n=1(mod 3)) but the value of lambda does not bring very interesting things. No speed up in doubling or adding formula. This choice is strange and may be the weakness (if there is a weakness) will come from complex multiplication or something in this area...
Bitcoin curve is secure. The values [0,7] are extremely well chosen. There is a weakness in some curves that was not known when the parameters were chosen, but I guess bitcoin got lucky (yet again).
While researching how can it be possible that they succeeded in choosing so good parameters, (when they could not have known) I was reading how the parameters for bitcoin curve were selected from this old thread:
https://bitcointalksearch.org/topic/m.3183975
And it seems that the curve equation y2=x3+ax+b (a=0 and b=7) was selected, by first selecting an "easy" value for P, which will make some calculations faster.
P=2256-232-29-28-27-26-24-1 or
P=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
And then searching for the smallest value for b, (while keeping a=0), that would make the resulting curve have a prime order.
So the value b=7 was not even consciously chosen, as it was a result of just choosing an "easy" value for P. They could have selected another "easy" value for P and then b could have been something else.
And that is where bitcoin got lucky, because if b would have been 5 or 9 (or one of several possibilities) there would have been a weakness in the curve that would have made it a lot easier to break the encryption. I do not know if it would be possible to actually break it even then, but it would be 1/1000 times easier nevertheless.
This just shows that we always need a bit of luck, whatever we do.
PS: can you guess what is the weakness if b=5 or 9 or one of several other values? My lips are sealed
While researching how can it be possible that they succeeded in choosing so good parameters, (when they could not have known) I was reading how the parameters for bitcoin curve were selected from this old thread:
https://bitcointalksearch.org/topic/m.3183975
And it seems that the curve equation y2=x3+ax+b (a=0 and b=7) was selected, by first selecting an "easy" value for P, which will make some calculations faster.
P=2256-232-29-28-27-26-24-1 or
P=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
And then searching for the smallest value for b, (while keeping a=0), that would make the resulting curve have a prime order.
So the value b=7 was not even consciously chosen, as it was a result of just choosing an "easy" value for P. They could have selected another "easy" value for P and then b could have been something else.
And that is where bitcoin got lucky, because if b would have been 5 or 9 (or one of several possibilities) there would have been a weakness in the curve that would have made it a lot easier to break the encryption. I do not know if it would be possible to actually break it even then, but it would be 1/1000 times easier nevertheless.
This just shows that we always need a bit of luck, whatever we do.
PS: can you guess what is the weakness if b=5 or 9 or one of several other values? My lips are sealed
Jump to: