Bitcoin Forum
September 26, 2023, 10:36:56 AM
 News: Latest Bitcoin Core release: 25.0 [Torrent]
 Home Help Search Login Register More
 Pages: [1]
 Author Topic: Luck when selecting Secp256k1 parameters  (Read 211 times)
OneGoLuck (OP)
Newbie

Offline

Activity: 13
Merit: 4

 July 02, 2020, 12:22:05 PM

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://bitcointalk.org/index.php?topic=289795.msg3183975#msg3183975

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
1695724616
Hero Member

Offline

Posts: 1695724616

Ignore
 1695724616

1695724616
 Report to moderator
Remember that Bitcoin is still beta software. Don't put all of your money into BTC!
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1695724616
Hero Member

Offline

Posts: 1695724616

Ignore
 1695724616

1695724616
 Report to moderator
1695724616
Hero Member

Offline

Posts: 1695724616

Ignore
 1695724616

1695724616
 Report to moderator
Jean_Luc
Sr. Member

Offline

Activity: 448
Merit: 692

 July 02, 2020, 01:26:47 PM

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...
gmaxwell
Moderator
Legendary

Offline

Activity: 4018
Merit: 7844

 July 02, 2020, 07:24:00 PMLast edit: July 02, 2020, 07:49:36 PM by gmaxwell

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).
j2002ba2
Full Member

Offline

Activity: 189
Merit: 399

 July 02, 2020, 07:26:47 PM

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.
 Pages: [1]