roynahar / endomorphism Goto Github PK

Let's delve into the fascinating world of endomorphisms and their application to the secp256k1 elliptic curve.

1. What is an Endomorphism?

   • In mathematics, an endomorphism is a morphism (a structure-preserving map) from a mathematical object to itself.
   • Specifically, an endomorphism that is also an isomorphism (a bijective morphism) is called an automorphism.
   • For example:
     • An endomorphism of a vector space V is a linear map f: V → V.
     • An endomorphism of a group G is a group homomorphism f: G → G .

2. Secp256k1 and Endomorphism:

   • Secp256k1 is a specific elliptic curve used in cryptographic applications, notably in Bitcoin.
   • It was designed to be a 256-bit size elliptic curve without a cofactor and admits an efficient endomorphism for optimization purposes .
   • The relevant parameters for secp256k1 are derived with these criteria in mind.
   • Let's explore the endomorphism acceleration function that speeds up ECDSA signature verification for secp256k1:

3. The Endomorphism Acceleration Function:

   • The goal is to optimize the validation of ECDSA signatures for Bitcoin transactions.
   • The key values involved are:
     • LAMBDA: A special value that allows quick multiplication of any point on the secp256k1 curve by LAMBDA using a single multiplication mod p .
       • LAMBDA = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72.
     • BETA: Another value related to the curve .
       • BETA = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee.
   • The endomorphism allows us to compute kQ more efficiently:
     • Break k into two parts, k1 and k2, each about half the width of n.
     • Compute Q' = LAMBDA * Q.
     • Then calculate kQ = k1Q + k2*Q' using the double multiplication algorithm.
     • Since k1 and k2 are half the length, this results in a speedup .

In summary, the secp256k1 endomorphism function enhances the efficiency of cryptographic operations on this curve, contributing to the security and performance of Bitcoin transactions.