Faster computations on secp160k1 than lambda and beta, because of gcd(p-1,n-1)

[vjudeu]

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
n=0x0100000000000000000001b8fa16dfab9aca16b6b3
print(factor(p-1))
print(factor(n-1))
print(gcd(p-1,n-1))

This is the output:

Code:

2 * 3 * 5 * 7 * 113 * 61588775277324185343602394973294691093621473
2 * 3 * 5 * 8837 * 42918291593381467397 * 128449012680369359431471
30

Which means, that if the greatest common divisor is equal to 30, instead of 6, then it should be possible to get a better speedup, than by using lambda and beta alone. If so, then how this "efficiently computable endomorphism" looks like for secp160k1? Because using lambda and beta from secp256k1, and changing constants into secp160k1 will obviously give some results, but if the divisor is 30 instead, then I guess those equations are different, and it is possible to create a faster implementation. Am I right? Do you know, how to get those equations, where gcd is bigger than 6?

[1715471927]

1715471927

[1715471927]

1715471927

[1715471927]

1715471927

[stilichovandal]

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
n=0x0100000000000000000001b8fa16dfab9aca16b6b3
print(factor(p-1))
print(factor(n-1))
print(gcd(p-1,n-1))

This is the output:

Code:

2 * 3 * 5 * 7 * 113 * 61588775277324185343602394973294691093621473
2 * 3 * 5 * 8837 * 42918291593381467397 * 128449012680369359431471
30

Which means, that if the greatest common divisor is equal to 30, instead of 6, then it should be possible to get a better speedup, than by using lambda and beta alone. If so, then how this "efficiently computable endomorphism" looks like for secp160k1? Because using lambda and beta from secp256k1, and changing constants into secp160k1 will obviously give some results, but if the divisor is 30 instead, then I guess those equations are different, and it is possible to create a faster implementation. Am I right? Do you know, how to get those equations, where gcd is bigger than 6?

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]

[vjudeu]

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=NGLR2N4EK58

Code:

u1=        48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 (secp160k1)
u2=0554123b78ce563f89a0ed9414f5aa28ad0d96d6795f9c66 (secp192k1)
u3=      3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 (secp224k1)
u4=      3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 (secp256k1)

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:

Code:

04 3045ae6fc8422f64ed579528d38120eae12196d5 33f505091031a9f3fedf0de27523b755af69cd72
04 bd71344799d5c7fcdc45b59fa3b9ab8f6a948bc5 6441e8714d66ae3077e617136353a8d0bdc56318
04 c49d360886e704936a6678e1139d26b7819f7e90 d40dfa96a30216857f8d0a768e1bfb7e7efbca98
04 a335926aa319a27a1d00896a6773a4827acdac73 7a8d7a04b47ca665132a5a98fbd950c69a328a90
04 d09e8800291cb85396cc6717393284aaa0da64ba d8b87c1b9c2eb455f3804ce0689368de2c43028c

And maybe the distance between those points, and the generator, could also be helpful, and form some patterns.

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
P=GF(p)
aP=P(0x0)
bP=P(0x3)
curve=EllipticCurve(P,(aP,bP))
n=curve.order()
print(hex(n))
print(factor(n-1))

p=0x100000000000000000000aa2cbd03a810debcf3b3
P=GF(p)
aP=P(0x0)
bP=P(0x3)
curve=EllipticCurve(P,(aP,bP))
n=curve.order()
print(hex(n))
print(factor(n-1))

Output:

Code:

0x100000000000000000000aa2cbd03a810debcf3b3
2 * 3 * 243583606221817153033947606057310293537891253747
0xfffffffffffffffffffffffffffffffffffbdf2b
2 * 3 * 243583606221817153033947472119380503275988712071