Elliptic Curve Diffie Hellman (ECDH) is used to create a shared key. In this we use the elliptic curve defined as secp256k1 to generate points on the curve. Bob will generate a public key (\(B\)) and private key (\(b\)), as will Alice (\(A\) and \(a\)). They then exchange their public keys, and the shared key will then be \(a \times b \times G\), and where \(G\) is the generator point on the elliptic curve. In this case we will use the Kryptology library and implement the method in Golang.
ECDH with Golang and Kryptology |
Outline
The Internet was created with very little concept of security. Basically, we just need to get data from one place to another in a reliable way. The foundation protocols we created, such as IP, TCP, HTTP and FTP had no real integration of security. Luckily Whitfield Diffie and Marty Hellman came along and showed us it was possible for Bob and Alice to openly communicate, and for them to share a secret key. This key could then be used with symmetric key encryption, and thus secure their communications. It’s almost like Newton’s Law of Physics, applied in cybersecurity, and is known as the Diffie-Helman (DH) method. Its concept is based on discrete logs.
With DH, Bob and Alice generate their private keys (b and a), and then compute their public keys (B and A). These are exchanged, and then we can compute a shared secret, and from this, we can generate a shared key using HKDF (HMAC Key Derivation Function):
But, discrete logs have become a little cumbersome as computing power has improved. These improvements have meant it has become easier to crack the discrete log method for relatively small prime numbers, and so, the prime numbers involved have become fairly large (up to around 4,096 bits long). To solve this problem, elliptic curve cryptography (ECC) has provided a ‘drop-in’ solution, and where we can use elliptic curve methods rather than discrete logs. These use prime numbers that are much smaller, such as for just 256-bits for the Bitcoin curve (secp256k1). With this, we have a base point on the curve (G), and then multiply this base point with the private key value to be a public key point:
Theory
Elliptic Curve Diffie Hellman (ECDH) is used to create a shared key. In this example we use secp256k1 (as used in Bitcoin) to generate points on the curve. Its format is:
\(y^2 = x^3+7 \pmod p\)
with a prime number (\(p\)) of \( 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 \)
Bob will generate a public key and a private key by taking a point on the curve. The private key is a random number (\(b\)) and the Bob's public key (\(B\)) is a point on the curve, and will be:
\(B = b \times G\)
Alice will do the same and generate her public key point (\(A\)) from her private key (\(a\)):
\(A = a \times G\)
They then exchange their public keys. Alice will then use Bob's public key and her private key to calculate:
SharekeyAlice\( = a \times B\)
This will be the same as:
SharekeyAlice\( = a \times b \times G\)
Bob will then use Alice's public key and his private key to determine:
SharekeyBob \(= b \times A\)
This will be the same as:
SharekeyBob\( = b \times a \times G\)
And the shared secret should match. All we have to do now, is to feed it into a Key Derivation Function to produce the shared key.
Implementation
The following is an implementation for the supported curves (Ed25519, BLS 12377, sepc256k1, P256 and Pallas) and use the Kryptology library. To generate Alice's private we just select a random number and define as a scalar value (\(a\)). Next, we generate multiply this scalar value by the generator point on the curve (\(G\)) to get the public key (\(A\)). We can display our private key by converting the scalar value into a byte array, and then displaying with hexademical, and the public key point can be uncompressed, and then displayed in a hexademical format.
a := curve.Scalar.Random(rand.Reader) A := curve.Point.Generator().Mul(a) fmt.Printf("a = %x\n", a.Bytes()) fmt.Printf("aG = %x\n", A.ToAffineUncompressed())
package main import ( "crypto/rand" "crypto/sha256" "fmt" "io" "os" "strings" "github.com/coinbase/kryptology/pkg/core/curves" "golang.org/x/crypto/hkdf" ) func getCurve(s string) *curves.Curve { s=strings.ToLower((s)) if strings.Contains(s, "p256") { return curves.P256() } else if strings.Contains(s, "k256") { return curves.K256() } else if strings.Contains(s, "25519") { return curves.ED25519() } else if strings.Contains(s, "g1") { return curves.BLS12381G1() } else if strings.Contains(s, "g2") { return curves.BLS12381G2() } else if strings.Contains(s, "pallas") { return curves.PALLAS() } return curves.K256() } func main() { ctype := "k256" argCount := len(os.Args[1:]) if argCount > 0 { ctype = os.Args[1] } curve := getCurve(ctype) fmt.Printf("Curve type: [%s]\n", curve.Name) a := curve.Scalar.Random(rand.Reader) A := curve.Point.Generator().Mul(a) fmt.Printf("a = %x\n", a.Bytes()) fmt.Printf("aG = %x\n", A.ToAffineUncompressed()) b := curve.Scalar.Random(rand.Reader) B := curve.Point.Generator().Mul(b) fmt.Printf("b = %x\n", b.Bytes()) fmt.Printf("bG = %xn\n\n", B.ToAffineUncompressed()) K1 := A.Mul(b) K2 := B.Mul(a) fmt.Printf("K1 = %x\n", K1.ToAffineUncompressed()) fmt.Printf("K2 = %x\n", K2.ToAffineUncompressed()) kdf := hkdf.New(sha256.New, K1.ToAffineUncompressed(), []byte(""), []byte("")) key1 := make([]byte, 16) _, _ = io.ReadFull(kdf, key1) fmt.Printf("Derived key (after HKDF) = %x\n", key1) }
A sample run:
Curve type: [secp256k1] a = 5093fd0affa329c145db851ac22d5e9f48dc912ea0b0a85e3ab5d8cb586ce7af aG = 04f3fc671c8494bf04eec985f3b5bffeaaa2fa8f0caf98143d3134daaf7fc1369eedbff25f6106bd632b5a0c33a4ecf7dcbc403ccd0329e6fb7ab12786603b92ca b = 13cce3ab86703d6b6476c8d50a38c39598a753b56e5de419b426e7231aa49b10 bG = 04ba66371b117da5bda77b6a62d3e3fa5a8193f56b0954e4ff19a6ef6a8c99a237e43d555af4eb57580a4696262a048a1749427a6bacaa6ac76be35f7c8dbd4be4n K1 = 044a2275612a8069bb8a4a052e9776841da553de568b49237163751d2ed01000c6e9cc88437341bcb4383e52142166f92f0823ee7a6f65059f89f31028f4a38645 K2 = 044a2275612a8069bb8a4a052e9776841da553de568b49237163751d2ed01000c6e9cc88437341bcb4383e52142166f92f0823ee7a6f65059f89f31028f4a38645 Derived key (after HKDF) = 15d6bf77a6c3d13c8ca198e789fbb616
Notice that the uncompressed point starts with a '0x04', and which identifies that it is an uncompressed elliptic curve point.