*The following content was written by Jean_Luc on July 02, 2020, 08:24:44 PM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

Could you give more info on this because I don’t see how to have efficient decomposition k.P= (k1+k2.lambda).P using such lambda.

Thanks

*The following content was written by gmaxwell on July 02, 2020, 08:44:10 PM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

Sure!

You rewrite k*P as k1*P + k2*lambda*P — lambda*P is trivial to compute, since its {beta * P.x, P.y} and k1 and k2 are 128-bit numbers instead of 256. Then this sum of products can be computed efficiently using Strauss’ algorithm (also called Shamir Trick) or similar.

Here is an implementation that splits k into k1 and k2 for secp256k1: https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar_impl.h#L268 with a couple scalar operations.

The endomorphism optimization in libsecp256k1 is (currently) disabled by default (and can be enabled via a configure option) because it’s potentially covered by a patent that expires pretty soon. (I think history suggests that the patent is actually invalid, but the benefit isn’t great enough to worry about it).

The implementation in libsecp256k1 is a little more complicated than described above due to some common and some novel optimizations in its version of Strauss’ algorithm. It uses WNAF so it pre-computes a small table of P times odd numbers using an efficient addition ladder. It then performs all the additions over an alternative isomorphic curve so that it’s able to treat the precomputed P multiplies as affine points without needing an inverse to reproject them. As a result the application of beta is done on demand late in the algorithm rather than needing to compute two tables.

*The following content was written by Jean_Luc on July 03, 2020, 07:52:19 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

@gmaxwell

Many thanks

I discovered this book “Guide to Elliptic Curve Cryptography” which is great

*The following content was written by Jean_Luc on July 03, 2020, 11:44:30 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

I implemented the algorithm 3.74 of the above book and I found different results:

At iteration #70/#71, I well found the same constants a1 and a2 that are mentioned in the comment of the code.

but b1 and b2 are different and strangely b2=a1 in the comment

I would expect b1 = -1839468DB3DC795B42AD17D3CA5C15137 and b2 = 4A5AC2BF7B5F37F9F1DB10D7A2A9C981.

I didn’t check yet g1 and g1 constants.

* (algorithm 3.74) to find k1 and k2 given k, such that k1 + k2 * lambda == k mod n, and k1

* and k2 have a small size.

* It relies on constants a1, b1, a2, b2. These constants for the value of lambda above are:

*

* – a1 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}

* – b1 = -{0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3}

* – a2 = {0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,0xd8}

* – b2 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}

t0=0

r0=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

s1=0

t1=1

r1=5363AD4CC05C30E0A5261C028812645A122E22EA20816678DF02967C1B23BD72

s2=1

t2=E

r2=5D4F819BEEB6D5E108DABF867C8D2F0842474284DC46CD122CA9B187ECB08EB

…

s70=FCE9B1DD4EB7DD2718A2906787061B2

t70=4A5AC2BF7B5F37F9F1DB10D7A2A9C981

r70=114CA50F7A8E2F3F657C1108D9D44CFD8 (>sqrt(n))

s71=4A5AC2BF7B5F37F9F1DB10D7A2A9C981

t71=1839468DB3DC795B42AD17D3CA5C15137

r71=3086D221A7D46BCDE86C90E49284EB15 (

*The following content was written by j2002ba2 on July 03, 2020, 01:53:22 PM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

@Jean_Luc Your code for EEA seems incorrect. Here are the correct values:

t70=-3086D221A7D46BCDE86C90E49284EB15

r70=114CA50F7A8E2F3F657C1108D9D44CFD8 (>=sqrt(n))

s71=-4A5AC2BF7B5F37F9F1DB10D7A2A9C981

t71=E4437ED6010E88286F547FA90ABFE4C3

r71=3086D221A7D46BCDE86C90E49284EB15 (

s72=1839468DB3DC795B42AD17D3CA5C15137

t72=-4A5D84C4FAD1D149815130F31C84462E4

r72=2228364F61BCD8F0CDA23C16C0AC386F

(a2, b2) = (r70, -t70) = (114CA50F7A8E2F3F657C1108D9D44CFD8, 3086D221A7D46BCDE86C90E49284EB15)

r70^2 + t70^2 = 13477B4472B4233ECA232A74B45B8E7F37640C02AF64BF4EEAEE3ABED3D0695F9

r72^2 + t72^2 = 159EC1A05B158DF471EAE76C8FA0CDA199E5599D41EC1E5915FBD403A750EC1B31

*The following content was written by Jean_Luc on July 04, 2020, 07:11:58 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

VanitySearch already use endomorphism and for kangaroo, I will see if it is possible to do something but I'm note sure it is possible to define equivalence classes for endomorphism as for symmetry.

But symmetry is not interesting on large range due to small cycle apparition in random walks. The overhead needed to limit cycle is more than the gain of using equivalence class, especially on GPU where the cache usage can drastically decrease performance.

*The following content was written by arulbero on July 04, 2020, 07:41:11 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

But symmetry is not interesting on large range due to small cycle apparition in random walks. The overhead needed to limit cycle is more than the gain of using equivalence class, especially on GPU where the cache usage can drastically decrease performance.

I did some tests with symmetry (python for cpu), with num_jumps = 32 you can get 1.6 / 1.7.sqrt(N) steps (instead of 2.08.sqrt(N)) if the DP is 12 or lower.

With longer paths you have to increase the number of the jumps, and that decreases the performance.

*The following content was written by COBRAS on July 04, 2020, 10:58:13 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

VanitySearch already use endomorphism and for kangaroo, I will see if it is possible to do something but I’m note sure it is possible to define equivalence classes for endomorphism as for symmetry.

Maybe 128 byte keys is more good I think. 256 byte is harde to fined !!! Implement please endomorphism in Kangaroo Bro ?

*The following content was written by gmaxwell on July 06, 2020, 01:30:05 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

*The following content was written by Jean_Luc on July 06, 2020, 05:44:23 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

Yes I know, but I don’t see how to use this property in the random walk. For the symmetry you can select the next point according to the sign of the y value and then select always the positive point which divide by 2 the search space. It is easy to calculate the corresponding distance at each step of the random walk but it generates useless cycles.

If I cube the x value of a DP and look for collision on x^3 then the gain is negligible due to the fact that the selection is not done at each step of the random walk.

Any idea would be welcome

*The following content was written by arulbero on July 06, 2020, 06:09:17 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

Yes I know, but I don’t see how to use this property in the random walk. For the symmetry you can select the next point according to the sign of the y value and then select always the positive point which divide by 2 the search space. It is easy to calculate the corresponding distance at each step of the random walk but it generates useless cycles.

If I cube the x value of a DP and look for collision on x^3 then the gain is negligible due to the fact that the selection is not done at each step of the random walk.

Any idea would be welcome

Each step (each jump) must depend on the last bits of x^3 mod p. But you have no advantage in the search in [-(a+b)/2,(a+b)/2] interval, you have a speedup only in the union of 3 intervals: [-(a+b)/2,(a+b)/2] U [-lambda*(a+b)/2,lambda*(a+b)/2] U [-lambda^2*(a+b)/2,lambda^2*(a+b)/2]

*The following content was written by Jean_Luc on July 06, 2020, 06:57:50 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

Yes and the overlap between these ranges will be very small unless you search on very large range.

I’m wondering if something can be do using x^(P-1)/3 (mod p) with give 1,beta or beta^2 with uniform distribution.

Of course computing a modexp is expensive but just for try…

1^((P-1)/3): 1

2^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

3^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

4^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

5^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

6^((P-1)/3): 1

7^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

8^((P-1)/3): 1

9^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

10^((P-1)/3): 1

11^((P-1)/3): 1

12^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

13^((P-1)/3): 1

14^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

15^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

16^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

17^((P-1)/3): 1

18^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

19^((P-1)/3): 1

20^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

*The following content was written by gmaxwell on July 06, 2020, 07:31:08 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

The speedup over the set of three intervals is still potentially interesting: e.g. imagine you have an elgammal encryption where the decryption leaves with with a point you need to take the discrete log. And you can arrange that the DL is in some small enough range that this isn’t unrealistic, and could potentially support the sparse ranges.

This shows up in things like electronic voting or in confidential transactions. (In CT I avoided the need to solve a DL in the receiver by sneaking an encryption of it into a sidechannel in the range proofs)…. or just for DL challenge bragging rights.

*The following content was written by COBRAS on July 06, 2020, 09:00:21 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

I’m wondering if something can be do using x^(P-1)/3 (mod p) with give 1,beta or beta^2 with uniform distribution.

Of course computing a modexp is expensive but just for try…

1^((P-1)/3): 1

2^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

3^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

4^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

5^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

6^((P-1)/3): 1

7^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

8^((P-1)/3): 1

9^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

10^((P-1)/3): 1

11^((P-1)/3): 1

12^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

13^((P-1)/3): 1

14^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

15^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

16^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

17^((P-1)/3): 1

18^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

19^((P-1)/3): 1

20^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

Good Day everybody.

128 bytes is big range i think, if endomorphism can solve so ranges it will be supper. But if no method for solve 128-256 bytes, I think all solutions will hard work with something another then puzzle addresses.

*The following content was written by Jean_Luc on July 06, 2020, 09:47:53 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

A 128bit range compared to a 256bit range is very very small. 340282366920938463463374607431768211456 times smaller

*The following content was written by COBRAS on July 06, 2020, 10:32:55 AM in the thread Using secp256k1 endomorphism. All content is owned by the author of the bitcointalk.org post. (original)*

Yes, but with endomorphism needed only 128 bytes for solve 256 and only 64 for solve 128 !!!

p.s. and as i know endomorphism +0.7 fester !!!