How secp160k1 computations can beat lambda and beta due to gcd(p-1,n-1)

2 replies 168 views
coin777Senior Member
Posts: 143 · Reputation: 970
#1Jul 31, 2022, 11:10 PM
So, with secp256k1, we find that the gcd of "p-1" and "n-1" is 6. This basically means we're stuck with using lambda and beta because other factors don't match up, making it tough to link private and public keys. But with secp160k1, it looks like things change: The output shows that if the gcd is 30 instead of 6, we could potentially achieve a better speedup than just relying on lambda and beta. So, how does this "efficiently computable endomorphism" for secp160k1 actually work? Sure, we can take lambda and beta from secp256k1 and adjust the constants for secp160k1 to get some results, but if the gcd is 30, I suspect those equations must differ, and that means there's a chance for a faster implementation. Am I on the right track? Can anyone shed some light on how to derive those equations when the gcd is greater than 6?
7 Reply Quote Share
ninj42016Full Member
Posts: 45 · Reputation: 251
#2Aug 1, 2022, 12:33 AM
That's a great find.  How does working with secp160k1 help secp256k1? Is there a way to map one to the other? Below are the endomorphism values for P and N; I am trying to figure out how to get the equations. p=0xfffffffffffffffffffffffffffffffeffffac73 [1, 116413238536967823204912062004448726737640720821, 1192671444047713143517039375510234845319976240753, 320568492332623811159581411922637138849485810267, 170033768725603827466154123598115574507330393474, 888563150828732192317477979643480826024658399499, 459808123412383666504375194171595673260619233000, 506013106973151716048837162345055484894245883380, 756739066376840291689464290814729327749587999038, 914082931336101346080276401800062193637040619652, 888563150828732192317477979643480826024658399498, 343394884875415843299463132167146946522978512179, 774843300256341490735482619551103659225907196918, 436170574044216480529882878892092188900102188771, 744049162610497518614122278201946619129710226178, 1461501637330902918203684832716283019651637554290, 1345088398793935094998772770711834292913996833470, 268830193283189774686645457206048174331661313538, 1140933144998279107044103420793645880802151744024, 1291467868605299090737530709118167445144307160817, 572938486502170725886206853072802193626979154792, 1001693513918519251699309638544687346391018321291, 955488530357751202154847670371227534757391670911, 704762570954062626514220541901553691902049555253, 547418705994801572123408430916220826014596934639, 572938486502170725886206853072802193626979154793, 1118106752455487074904221700549136073128659042112, 686658337074561427468202213165179360425730357373, 1025331063286686437673801953824190830751535365520, 717452474720405399589562554514336400521927328113] 0x0100000000000000000001b8fa16dfab9aca16b6b3 [1, 1408470634914903571732066888580417336645162873119, 708713767398721337809629107989760271137717787930, 1151796019543683584915212041505571206301361534252, 41278637720562416563498774273562198366106105008, 69796346552658733766475001267285041190029755381, 459366475837133574597979692431231491490457423387, 719990520318696333937754171078776164365241746857, 595911485914207747779051672558094670244251938235, 780348846544327904014579629185545903813779011634, 69796346552658733766475001267285041190029755380, 512397478253132921069599719021683880242453713839, 11276752919974996128125063089015893227523958927, 905617103701427081067526546223393189340049567554, 739070208823765487451080854911983705447672906626, 1461501637330902918203686915170869725397159163570, 53031002415999346471620026590452388751996290452, 752787869932181580394057807181109454259441375641, 309705617787219333288474873665298519095797629319, 1420222999610340501640188140897307527031053058563, 1391705290778244184437211913903584684207129408190, 1002135161493769343605707222739638233906701740184, 741511117012206584265932744092093561031917416714, 865590151416695170424635242612775055152907225336, 681152790786575014189107285985323821583380151937, 1391705290778244184437211913903584684207129408191, 949104159077769997134087196149185845154705449732, 1450224884410927922075561852081853832169635204644, 555884533629475837136160368947476536057109596017, 722431428507137430752606060258886019949486256945]
3 Reply Quote Share
coin777Senior Member
Posts: 143 · Reputation: 970
#3Aug 1, 2022, 01:01 AM
For example, it could be used to reveal the source of the magic number 0x48ce563f89a0ed9414f5aa28ad0d96d6795f9c62, used in the half of the generator of secp160k1, see: https://www.youtube.com/watch?v=NGLR2N4EK58 As you can see, all of those four curves were generated in a similar way. So, if there was some regular point with some small x-value, for example (0x3,0xc77a53fd35585a1db7ff873cb32855f89c655d8), and the distance between this point, and the half of the generator, would be for example SHA-1 of something, or n-th root of some number, then it could be used to confirm, how that generator was picked. And if you get that value on a smaller curve, like secp160k1 or secp192k1, then it could be easier, than doing so on secp256k1. Also, all of those 160-bit values from the bounty, are valid x-values for points on secp160k1: And maybe the distance between those points, and the generator, could also be helpful, and form some patterns. If you think about directly mapping the points, then I don't think so. However, I think it is beneficial to start with easier challenges, and then proceed with the harder ones, if they would be solved. And this is one of the reasons, why I am focused on SHA-1 and secp160k1, instead of thinking about SHA-2 and secp256k1. Because I think it is unlikely to solve more difficult problems, without solving the easier ones before. And still, 160-bit space is huge enough, and contains a lot of unsolved mysteries. Even though in the long-term, it can provide only 80-bit security (or less, if that gcd or other approaches provide some speedup) then still, today we don't know many things behind those 160-bit numbers. Also, some properties of secp160k1 and secp256k1 are similar. For example, in both curves, you can swap p-value with n-value, and it will form a valid curve. Which means, that you can test some properties on the weaker curve, and get some conclusions for the stronger one. Also, if secp256k1 will ever be broken, then I guess it will happen first on secp160k1, just because it is easier. The same was also true in SHA-1 vs SHA-2. There is a known collision in the former, but we are still quite far from seeing similar things in the latter. Another thing is that when it comes to 160-bit curves, then there is some strong curve, where b=3, and divisors of "p-1" and "n-1" are in the form of "6 * prime", but when you try to find a similar value for 256-bit curves, then it is much harder to get such value, because it is far away from "2^256" or "2^256-2^32". Output:
5 Reply Quote Share

Related topics