Elliptic Curves, Base Points and Scalars

Elliptic Curves, Base Points and Scalars

I discovered the Diffie-Hellman method, and I loved it. Another great discovery was how RSA worked. But the real eye-opener was the discovery of how elliptic curves work in elliptic curve cryptography (ECC). It is a truly wonderful technique and protects your online safety like no other method. We see it in key exchanges with ECDH (Elliptic Curve Diffie Hellman), and in digital signatures with ECDSA (Elliptic Curve Digital Signature Algorithm).

Within elliptic curves, we can have a scalar value (a) and a base point on the curve (G). We then perform an add operation to produce another point on the curve as aG. This is the equivalent operation of adding the point G for a times. Normally we would define aG as a public key point, and a as a private key scalar value. Typically these operations are done within a finite field defined by a prime number (p).

In the case of Curve 25519, this prime number is 2²⁵⁵−19. With the Ed25519 curve, we only need one of the co-ordinate points, and so the public key point is the same length as the private key scalar value. With other curves (such as secp256k1) we will end up with a longer value for our points than the scalar values. With secp256k1 we have an equation of:

y² = x³+7 (mod p)

If we plot without the (mod p) part we get:

but introducing the (mod p) part gives us two y points for x coordinate values:

In elliptic curves, we pick a base point as one of the points, and then we perform simple operations, such as adding two points (P3=P1 + P2), or doubling a point (P2=P1+P1). The main operation we have is then aP, and which is P+P+ … +P (basically a P add, for a times).

The Kryptology library supports a wide range of curves, including BLS (such as BLS 12377), Ed25519, P256, K256 (secp256k1 — as used in Bitcoin and Ethereum) and Pallas. The Boneh–Lynn–Shacham (BLS) signature method produces short signatures and use elliptic curve pairing (and which are also known as bilinear maps). These are particularly useful for Zero-Knowledge Proofs (ZKPs). Ed25519 uses Curve 25519 and is known to be a fast and efficient method for processing elliptic curves operations.

In the following, we only show the y-coodinate point, as we can easily compute the x-coordinate point from the equation defining the curve. With the ToAffineCompressed() method for a point we just get the y co-ordinate, while the ToAffineUncompressed() method gives us the (x,y) point.

The following is an implementation for the supported curves (Ed25519, BLS 12377, sepc256k1, P256 and Pallas) [here]:

package main

import (
	"fmt"
	"os"
	"strconv"

	"github.com/coinbase/kryptology/pkg/core/curves"
)

func main() {

	val1 := 1

	argCount := len(os.Args[1:])

	if argCount > 0 {
		val1, _ = strconv.Atoi(os.Args[1])

	}

	curve := curves.ED25519()
	x := curve.Scalar.New(val1)
	G := curve.Point.Generator()
	xG := curve.Point.Generator().Mul(x)

	fmt.Printf("x=%x\n\n", x.Bytes())
	fmt.Printf("\n=== ED25519:\n G=%x\n xG=%x\n  xG(x,y)=%x\n",  G.ToAffineCompressed(), xG.ToAffineCompressed(), xG.ToAffineUncompressed())

	curve = curves.BLS12377G1()
	x = curve.Scalar.New(val1)
	G = curve.Point.Generator()
	xG = curve.Point.Generator().Mul(x)

	fmt.Printf("\n=== BLS12377G1:\n G=%x\n xG=%x\n  xG(x,y)=%x\n", G.ToAffineCompressed(),  xG.ToAffineCompressed(), xG.ToAffineUncompressed())

	curve = curves.K256()
	x = curve.Scalar.New(val1)
	G = curve.Point.Generator()
	xG = curve.Point.Generator().Mul(x)

	fmt.Printf("\n=== Sepc256k1:\n G=%x\n xG=%x\n  xG(x,y)=%x\n", G.ToAffineCompressed(),  xG.ToAffineCompressed(), xG.ToAffineUncompressed())

	curve = curves.P256()
	x = curve.Scalar.New(val1)
	G = curve.Point.Generator()
	xG = curve.Point.Generator().Mul(x)

	fmt.Printf("\n=== P256:\n G=%x\n xG=%x\n  xG(x,y)=%x\n", G.ToAffineCompressed(),  xG.ToAffineCompressed(), xG.ToAffineUncompressed())

	curve = curves.PALLAS()
	x = curve.Scalar.New(val1)
	G = curve.Point.Generator()
	xG = curve.Point.Generator().Mul(x)

	fmt.Printf("\n=== PALLAS:\n G=%x\n xG=%x\n  xG(x,y)=%x\n", G.ToAffineCompressed(),  xG.ToAffineCompressed(), xG.ToAffineUncompressed())

}

A sample run for x=3 [here]:

x=0300000000000000000000000000000000000000000000000000000000000000

=== ED25519:
 G=5866666666666666666666666666666666666666666666666666666666666666
 xG=d4b4f5784868c3020403246717ec169ff79e26608ea126a1ab69ee77d1b16712
  xG(x,y)=5ce2f8d35f4862ac86486281199843633ac8da3e74aef41f498f92224a9cae67d4b4f5784868c3020403246717ec169ff79e26608ea126a1ab69ee77d1b16712

=== BLS12377G1:
 G=a08848defe740a67c8fc6225bf87ff5485951e2caa9d41bb188282c8bd37cb5cd5481512ffcd394eeab9b16eb21be9ef
 xG=a1252b781171f507db36291b433a1f911a46543890a20ca9712e11f66a5d216e63d817bd8d96cef715abc604dcf6ec2e
  xG(x,y)=01252b781171f507db36291b433a1f911a46543890a20ca9712e11f66a5d216e63d817bd8d96cef715abc604dcf6ec2e014a00fa77c727e8987cc438b51bbe012c823a19955ae692c54ce572a61f0ea1fe5cd981533df419fd1330d1f6e6d802

=== Sepc256k1:
 G=0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
 xG=02f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
  xG(x,y)=04f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672

=== P256:
 G=036b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
 xG=025ecbe4d1a6330a44c8f7ef951d4bf165e6c6b721efada985fb41661bc6e7fd6c
  xG(x,y)=045ecbe4d1a6330a44c8f7ef951d4bf165e6c6b721efada985fb41661bc6e7fd6c8734640c4998ff7e374b06ce1a64a2ecd82ab036384fb83d9a79b127a27d5032

=== PALLAS:
 G=0100000000000000000000000000000000000000000000000000000000000080
 xG=90f5a1b1518221678711d4142c0e3dd70165e24af70694892bdd1b5026ae742f
  xG(x,y)=90f5a1b1518221678711d4142c0e3dd70165e24af70694892bdd1b5026ae742f38c29c75a9aa29af530dccb3003857e2c36eebc0c56ffa43b7ed4dc330de603f

Want to learn more about ECC:

https://asecuritysite.com/ecc/

And for secp256k1:

https://asecuritysite.com/secp256k1/

And for Curve 25519:

https://asecuritysite.com/curve25519/