For a finite field elliptic curve we have for a curve of \(y^2 = x^3 + ax +b\) and for a defined prime number (\(p\)). This is defined as a Weierstrass curve. We use a base point (\(G\)) and then multiply this with a given value (\(a\)) to get \(aG\). The multiplication can be achieve with a double-and-add approach, and which is equivalent to the square-and-multiply approach used in discrete logarithm methods. In this case we will use the secp256k1 curve (as used in Bitcoin) and which uses a curve of \(y^2 = x^3 +7 \mod p\), and where \(p=2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1\). In this case we will use the Montgomery ladder method in order to efficiently perform the \(n.G\) operation.
ECC Double-and-add for point multiplication (Kryptology and Golang) |
Theory
The basic method for \(d_i\) as the bit at position \(i\):
N ← P Q ← 0 for i from 0 to m do if di = 1 then Q ← point_add(Q, N) N ← point_double(N) return Q
For \(a=100\) we have a binary value of \(1100100\):
- 1100100, thus we double the point \((N=2G)\).
- 1100100, thus we double the point \((N=4G)\).
- 1100100, thus we add the point \((Q=4G)\), and then double the point \((N=8G)\).
- 1100100, thus we double the point \((N=16G)\).
- 1100100, thus we double the point \((N=32G)\).
- 1100100, thus we add the point \((Q=4G+32G=36G)\), and then double the point (\(N=64G)\).
- 1100100, thus we add the point \((Q=36G+64G=100G)\), and then double the point \((N=128G)\).
The result is then \(Q=4G+32G+64G=100G\).
Coding
The outline code is:
package main import ( "fmt" "os" "strconv" "github.com/coinbase/kryptology/pkg/core/curves" ) func reverse(str string) (result string) { for _, v := range str { result = string(v) + result } return } func main() { x := 3 c := curves.K256() name := "K256" argCount := len(os.Args[1:]) if argCount > 0 { name = (os.Args[1]) } if argCount > 1 { x, _ = strconv.Atoi(os.Args[2]) } if name == "K256" { c = curves.K256() } else if name == "P256" { c = curves.P256() } else if name == "ED25519" { c = curves.ED25519() } else if name == "PALLAS" { c = curves.PALLAS() } else if name == "BLS12377G1" { c = curves.BLS12377G1() } else if name == "BLS12377G2" { c = curves.BLS12377G2() } G := c.Point.Generator() N := G Q := c.NewIdentityPoint() b := fmt.Sprintf("%b", x) fmt.Printf("Curve: %s\n", c.Name) fmt.Printf("Binary representation of %d: %s\n\n", x, b) b = reverse(b) for i := 0; i < len(b); i++ { if b[i] == '1' { fmt.Printf("Bit=1. Add ") Q = Q.Add(N) } fmt.Printf("Double\n") N = N.Add(N) } fmt.Printf("\n%d.G\n\nCompressed Point: %x\n", x, Q.ToAffineCompressed()) if name == "K256" || name == "P256" { fmt.Printf("\nUncompressed Point: %x, %x\n", Q.ToAffineUncompressed()[1:33], Q.ToAffineUncompressed()[33:]) } else { len := len(Q.ToAffineUncompressed()) / int(2) fmt.Printf("\nUncompressed Point: %x, %x\n", Q.ToAffineUncompressed()[:len], Q.ToAffineUncompressed()[len:]) } }
Sample run
For secp256k1 and for \(100.G\) we get:
Binary representation of 100: 1100100 Double Double Bit=1. Add Double Double Double Bit=1. Add Double Bit=1. Add Double 100.G Compressed Point: 02ed3bace23c5e17652e174c835fb72bf53ee306b3406a26890221b4cef7500f88 Uncompressed Point: 04ed3bace23c5e17652e174c835fb72bf53ee306b3406a26890221b4cef7500f88e57a6f571288ccffdcda5e8a7a1f87bf97bd17be084895d0fce17ad5e335286e Uncompressed Point: ed3bace23c5e17652e174c835fb72bf53ee306b3406a26890221b4cef7500f88, e57a6f571288ccffdcda5e8a7a1f87bf97bd17be084895d0fce17ad5e335286e