{{ message }}

Instantly share code, notes, and snippets.

# paulmillr/secp256k1-endomorphism.md

Last active Jun 21, 2021
Speed-up secp256k1 by using endomorphism https://paulmillr.com/posts/noble-secp256k1-fast-ecc/

Hal Finney's explanation of secp256k1 "efficiently computable endomorphism" parameters used secp256k1 libraries, archived from source.

The same optimization could be applied to any Koblitz curve (e.g. Short Weistrass curve with a=0).

I implemented an optimized ECDSA verify for the secp256k1 curve, based on pages 125-129 of the Guide to Elliptic Curve Cryptography, by Hankerson, Menezes and Vanstone. I own the book but I also found a PDF on a Russian site which is more convenient.

secp256k1 uses the following prime for its x and y coordinates:

`p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f`

and the curve order is:

`n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141`

The first step is to compute values beta, lambda such that for any curve point Q = (x,y):

`lambda * Q = (beta*x mod p, y)`

This is the so-called efficiently computable endomorphism, and what it means is, you can multiply any curve point by this special value lambda very quickly, by doing a single mod-p multiply.

The book tells (well, hints) how to compute lambda and beta, and here are the values I found:

``````lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee
``````

Given that we can multiply by lambda quickly, here is the trick to compute k*Q. First use the shortcut to compute `Q' = lambda*Q`. Next, k must be decomposed into two parts k1 and k2, each about half the width of n, such that:

`k = k1 + k2*lambda mod n`

Then

`k*Q = (k1 + k2*lambda)*Q = k1*Q + k2*lambda*Q = k1*Q + k2*Q'`

That last expression can be evaluated efficiently via a double multiply algorithm, and since k1 and k2 are half length, we get the speedup.

The missing piece is splitting k into k1 and k2. This uses the following 4 values:

``````a1 = 0x3086d221a7d46bcde86c90e49284eb15
b1 = -0xe4437ed6010e88286f547fa90abfe4c3
a2 = 0x114ca50f7a8e2f3f657c1108d9d44cfd8
b2 = 0x3086d221a7d46bcde86c90e49284eb15
``````

(it's ok that `a1 = b2`)

Use these as follows to split k:

``````c1 = RoundToNearestInteger(b2*k/n)
c2 = RoundToNearestInteger(-b1*k/n)
k1 = k - c1*a1 - c2*a2
k2 = -c1*b1 - c2*b2
``````

With all this, I measure about a 25% speedup on raw signature verifications.

### amiwrcd commented Jun 20, 2021 • edited

 Hello @paulmillr ! Please tell me how you can add lambda and beta to code " keysubtracter" for endomorphism on the secp256k1 curve? To speed up the scalar multiplication process via the random function -R but unfortunately I do not know the C ++ language, so I ask for help! https://github.com/albertobsd/keysubtracter/blob/167abc54c978752a4fb3a9f233f7e966b93704fa/keysubtracter.c#L26 ``````const char *version = "0.1"; const char *EC_constant_N = "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141"; const char *EC_constant_P = "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"; const char *EC_constant_Gx = "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798"; const char *EC_constant_Gy = "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8"; void showhelp(); void set_bit(char *param); void set_publickey(char *param); void set_range(char *param); char *str_output = NULL; struct Point target_publickey,base_publickey,sum_publickey,negated_publickey,dst_publickey; ``````

### paulmillr commented Jun 21, 2021

 My knowledge of C++ is limited, so no help here.