[Back] Elliptic curves are used fairly extensively in public key encryption (such as in Bitcoin and Tor). A BN-curve (Barreto-Naehrig curve) [paper] defines an elliptic curve which can be used for pairings that allow for a high security and efficiency level. So how do we generate a shared key between three parties? This page implements the tripartite Diffie-Hellman algorithm [Paper] and what Bob (B), Alice (A) and Carol (C) share their key pairings and then can calculate a shared secret key. In this case a, b and c are the private keys generated by Alice, Bob and Carol, respectively. Bob, Alice and Carol then generate key public keys from curves G1 and G2. In this case we show the keys for Alice, which are pa (\(pa = a \times G1\)), and qa (\(qa = a \times G2\)). Alice then calculate the shared key by taking the public values passed from Bob and Alice, and then multiplying it by her secret key (a):

## tripartite Diffie-Hellman algorithm BN256 in Go |

## Theory

For an Elliptic Curve we generate a 256-bit random number for the private key (\(p\)), and then take a point (\(G\)) [x,y] on the Elliptic Curve and then multiply it by the private key to get another point \( (p \times x,p \times y)\). In this way we get \(P = p \times G\), and where \(G\) is a known point on the Elliptic Curve, \(P\) is our public key and \(p\) is our private key.

With pairings we can derive more complex relationships between the points, such as if \(P = G \times p\), \(Q = G \times q\) and \(R = G \times r\), we can check to see if \(r = p \times q \), but where we only know P, Q and R (the public values). At the current time we cannot compute \(p\) from \(P = p \times G\), even if we know \(P\) and \(G\). The exposure of the values is limited as we can calculate \(R = G \times p \times q\), and where it is not possible to determine \(p\) or \(q\).

## Checking linear constraints

So let's say I want to prove to you that I know the proof for:

\(2 p + 3 q = 5 r\)

I can then give you \(p \times G + q \times G\) and \(r \times G\).

These values will be \(P\), \(Q\) and \(R\). Next you can check:

I can then give you \(2 P + 3 Q\) and \(5 R\).

If it is correct, I have proven that I know \(p\), \(q\) and \(r\).

The values we have used are defined for the pairing are defined as a *bilinear map*, and following this:

\(e(P, Q + R) = e(P, Q) \times e(P, R)\)

\(e(P + S, Q) = e(P, Q) \times e(S, Q)\)

Our focus for this is to be able to add, subtract, multiply and divide encrypted values.

With elliptic curve pairing we map \(G2 \times G1\) to \(Gt\) using:

- G1 and which is an elliptic curve for the equation \(y^2 = x^3 + b\) and includes the module of a prime number (N)
- G2 and which is an elliptic curve which have the same points as G1 and which fit values of \(w\)- a "magic number" - for \(w^{12} - 18 w^6 + 82 = 0\). I will describe this in another article.
- Gt and which is the resulting object.

## Three-way handshake with BN pairings

The following code integrates with BN-256 code for the generation of a shared key between three parties (Bob, Alice and Carol). The pairings use two elliptic curves: G1 and G2. Each person will generate their public key from each of these curves. First Bob (B), Alice (A) and Carol (C) generate their private keys (a, b and c) and which are random numbers. Next they create their pairings (qa, pa), (qb, pb) and (qc, pc). These will be:

\(pa = a \times G1\)

\(qa = a \times G2\)

\(pb = b \times G1\)

\(qb = b \times G2\)

\(pc = c \times G1\)

\(qc = c \times G2\)

If we take the example of Bob, then he will receive qa from Alice and pc from Carol, and then create a pairing and multiple by his private key (b). The result is the shared key:

## Coding

package main import ( "crypto/rand" "fmt" "github.com/clearmatics/bn256" ) func main() { // Each of three parties, a, b and c, generate a private value. a, _ := rand.Int(rand.Reader, bn256.Order) b, _ := rand.Int(rand.Reader, bn256.Order) c, _ := rand.Int(rand.Reader, bn256.Order) // Then each party calculates g1 and g2 times their private value. pa := new(bn256.G1).ScalarBaseMult(a) qa := new(bn256.G2).ScalarBaseMult(a) pb := new(bn256.G1).ScalarBaseMult(b) qb := new(bn256.G2).ScalarBaseMult(b) pc := new(bn256.G1).ScalarBaseMult(c) qc := new(bn256.G2).ScalarBaseMult(c) k1 := bn256.Pair(pb, qc) k1.ScalarMult(k1, a) k2 := bn256.Pair(pc, qa) k2.ScalarMult(k2, b) k3 := bn256.Pair(pa, qb) k3.ScalarMult(k3, c) fmt.Printf("a: %x\n",a) fmt.Printf("b: %x\n",b) fmt.Printf("c: %x\n",c) fmt.Printf("\npa: %s\n",pa) fmt.Printf("\npb: %s\n",pb) fmt.Printf("\npc: %s\n",pc) fmt.Printf("\nqa: %s\n",qa) fmt.Printf("\nqb: %s\n",qb) fmt.Printf("\nqc: %s\n",qc) fmt.Printf("\nFirst 20 bytes of shared key") fmt.Printf("\nK1: %x\n",k1.Marshal()[:20]) fmt.Printf("K2: %x\n",k2.Marshal()[:20]) fmt.Printf("K3: %x\n",k3.Marshal()[:20]) }

## Sample run

a: 27f147a74c59d741623144885af95d03d1a11b424fe03576c3de8c95116f3e90 b: 19540c18454c629bb6b8ff84a79254dac85ab06ea890c3982ac65aa34f56f4b9 c: ea240c8c842993ae46cc67cf51ee3708a8df958f15ca712564b0cf7bc8d6587 pa: bn256.G1(0ec528f12a7477e921ef1caf4d07e3f1c5397dfd29c8d754940373ccf2af1053, 1e050afe00a93161f838842bdefa5a162dc1398029904a45377715ed21678838) pb: bn256.G1(0ab5e0f229e5020eab9217e4810a55c6dc8cc8a9693cc6305e88a7adb0e13f87, 2195fe9ab413b814c400c30c4ab6f794fe84cb576f53883a8d67909ae2d4aaf7) pc: bn256.G1(2760546fce84e889e12b3a8d5c90f38aae71b12af77a78323960f763daaa5ad6, 036af4216d8b91f00e4572b3f31577a6772aca48111507cb1493fdad1a1f9569) qa: bn256.G2((2ec77298a75678f796d75563e90aec7ca33a4d94b2eb406f8d318e1fbe27f5a5, 1b463ac2f92f0f7f46ba1038ea0bc19f42295a2ab41a17be930f5c03d26d5832), (18f8a4f7a6d1ef741b42994660f80c8dc504e30828fbd19078ac8aeae07bc52a, 20a3004e0830249f38d886e4352a82724abefc108bfd66a24fec48896bd05d57)) qb: bn256.G2((1f3f43c36500bcc715d620152d25165606062fc53c6af324c9414f95db8511d1, 1d2f3eedab8b5576a97c22b5dd6d5bc61fe8ad0b41a427e73a9433cb5b0beae7), (1f2a2766e97595516b3a77324687a214d3cfe9f5e98a09192283e28b1cb36254, 0d05e441eb921eef214bb55c74694b075b42deabfce4f399034a2afc7f80ac12)) qc: bn256.G2((18c5d8f1be0a8f687b5d29ba86a0fdc2a99c7578a9b0dfe1035d263c7425146d, 11a9dc3a232a9f2052983713fcca4dfd8f10f4d8c0873e52285f8d7b35cf6714), (26d2876edf113344dec5bf2df8f2780e42a2ce644f8f3f57f09b070d8677c9f8, 057ba3af6e04b4f3e082645efbfd22d7772d98b6b95df84a72f0813c82e88efb)) First 20 bytes of shared key K1: 134917f18c5816ac7214c7dce306c269aeb60bc5 K2: 134917f18c5816ac7214c7dce306c269aeb60bc5 K3: 134917f18c5816ac7214c7dce306c269aeb60bc5