Title: Faster computations on secp160k1 than lambda and beta, because of gcd(p-1,n-1) Post by: vjudeu on April 28, 2024, 07:25:38 AM When we have secp256k1, then gcd between "p-1" and "n-1" is equal to 6. It means, that using lambda and beta is all we can do, because other factors are different, so it is hard to map private and public keys. However, when it comes to secp160k1, it seems to be different:
Code: p=0xfffffffffffffffffffffffffffffffeffffac73 Code: 2 * 3 * 5 * 7 * 113 * 61588775277324185343602394973294691093621473 Title: Re: Faster computations on secp160k1 than lambda and beta, because of gcd(p-1,n-1) Post by: stilichovandal on April 28, 2024, 12:07:31 PM When we have secp256k1, then gcd between "p-1" and "n-1" is equal to 6. It means, that using lambda and beta is all we can do, because other factors are different, so it is hard to map private and public keys. However, when it comes to secp160k1, it seems to be different: Code: p=0xfffffffffffffffffffffffffffffffeffffac73 Code: 2 * 3 * 5 * 7 * 113 * 61588775277324185343602394973294691093621473 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] Title: Re: Faster computations on secp160k1 than lambda and beta, because of gcd(p-1,n-1) Post by: vjudeu on April 28, 2024, 01:25:49 PM Quote How does working with secp160k1 help secp256k1? 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=NGLR2N4EK58Quote Code: u1= 48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 (secp160k1) Also, all of those 160-bit values from the bounty (https://bitcointalk.org/index.php?topic=5469657.0), are valid x-values for points on secp160k1: Code: 04 3045ae6fc8422f64ed579528d38120eae12196d5 33f505091031a9f3fedf0de27523b755af69cd72 Quote Is there a way to map one to the other? 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". Code: p=0xfffffffffffffffffffffffffffffffffffbdf2b Code: 0x100000000000000000000aa2cbd03a810debcf3b3 |