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

Activity: 13
Merit: 4


View Profile
July 02, 2020, 12:22:05 PM
 #1

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 Lips sealed
1695720240
Hero Member
*
Offline Offline

Posts: 1695720240

View Profile Personal Message (Offline)

Ignore
1695720240
Reply with quote  #2

1695720240
Report to moderator
1695720240
Hero Member
*
Offline Offline

Posts: 1695720240

View Profile Personal Message (Offline)

Ignore
1695720240
Reply with quote  #2

1695720240
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1695720240
Hero Member
*
Offline Offline

Posts: 1695720240

View Profile Personal Message (Offline)

Ignore
1695720240
Reply with quote  #2

1695720240
Report to moderator
1695720240
Hero Member
*
Offline Offline

Posts: 1695720240

View Profile Personal Message (Offline)

Ignore
1695720240
Reply with quote  #2

1695720240
Report to moderator
1695720240
Hero Member
*
Offline Offline

Posts: 1695720240

View Profile Personal Message (Offline)

Ignore
1695720240
Reply with quote  #2

1695720240
Report to moderator
Jean_Luc
Sr. Member
****
Offline Offline

Activity: 448
Merit: 692


View Profile
July 02, 2020, 01:26:47 PM
 #2

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
*
expert
Offline Offline

Activity: 4018
Merit: 7844



View Profile WWW
July 02, 2020, 07:24:00 PM
Last edit: July 02, 2020, 07:49:36 PM by gmaxwell
 #3

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

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 Offline

Activity: 189
Merit: 399


View Profile
July 02, 2020, 07:26:47 PM
 #4

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]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!