We have a number of possible types of elliptic curve methods. These have a field (the prime number used), the order (the number of elliptic curve points), an \(a\) value, a \(b\) value, and a generator point (\(G\)). For a Weierstrass curve the standard form is \(y^2=x^3+ax+b\). With a twisted Edwards curve (such as Ed25519) we have the form of \(ax^2+y^2=1+dx^2y^2\). A Montgomory curve has the form of \(by^2=x^3+ax^2+x\). This page implements some of the most important curves, including K256, P256 and Ed25519, and computes \(n.G\), and where n is a scalar value and \(G\) is the base point.
Elliptic Curve Types and nG (Kryptology) |
Coding
The outline code is:
package main import ( "fmt" "os" "strconv" "github.com/coinbase/kryptology/pkg/core/curves" ) func print_point(name string, x int) { c := curves.K256() 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() y := c.Scalar.New(x) Y := G.Mul(y) fmt.Printf("Curve: %s\nPoint: %d.G\n\nCompressed Point: %x\n", c.Name, x, Y.ToAffineCompressed()) fmt.Printf("\nUncompressed Point: %x\n", Y.ToAffineUncompressed()) if name == "K256" || name == "P256" { fmt.Printf("Uncompressed Point: %x, %x\n", Y.ToAffineUncompressed()[1:33], Y.ToAffineUncompressed()[33:]) } else { len := len(Y.ToAffineUncompressed()) / int(2) fmt.Printf("Uncompressed Point: %x, %x\n", Y.ToAffineUncompressed()[:len], Y.ToAffineUncompressed()[len:]) } } func main() { x := 1 ctype := "K256" argCount := len(os.Args[1:]) if argCount > 0 { ctype = (os.Args[1]) } if argCount > 1 { x, _ = strconv.Atoi(os.Args[2]) } print_point(ctype, x) }
Sample run
For P256 and for 1000.G we get:
Curve: P-256 Point: 1000.G Compressed Point: 03b8fa1a4acbd900b788ff1f8524ccfff1dd2a3d6c917e4009af604fbd406db702 Uncompressed Point: 04b8fa1a4acbd900b788ff1f8524ccfff1dd2a3d6c917e4009af604fbd406db7029a5cc32d14fc837266844527481f7f06cb4fb34733b24ca92e861f72cc7cae37 Uncompressed Point: b8fa1a4acbd900b788ff1f8524ccfff1dd2a3d6c917e4009af604fbd406db702, 9a5cc32d14fc837266844527481f7f06cb4fb34733b24ca92e861f72cc7cae37
We can compress a point, but only storing the x-axis value, and whether the y-axis point is odd or even. A compressed point that starts with a "03" is an odd vale, or "02" for an even value. For a compressed point, we do not need to store the y-axis point, as we can derive this from the x-axis point. A "04" identifies a uncompressed point for sepc256k1 and P256.