Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

This comment has been minimized.

Copy link

@amiwrcd amiwrcd commented Jun 20, 2021

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

This comment has been minimized.

Copy link
Owner Author

@paulmillr paulmillr commented Jun 21, 2021

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment