Rust, Crypto Pairing and When Bob Met Alice And Met Carol

Elliptic curves are used fairly extensively in public key encryption (such as in Bitcoin and Tor). A BN-curve (Barreto-Naehrig curve)…
Photo by Cytonn Photography on Unsplash

Rust, Crypto Pairing and When Bob Met Alice And Met Carol

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×G1), and qa (qa=a×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):

Theory

For an elliptic Curve we often 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×x,p×y). In this way we get P=p×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×p, Q=G×q and R=G×r, we can check to see if r=p×q, but where we only know P, Q and R (the public values). At the current time we cannot compute p from P=p×G, even if we know P and G. The exposure of the values is limited as we can calculate R=G×p×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:

2p+3q=5r

I can then give you p×G+q×G and r×G.

These values will be P, Q and R. I can then give you 2P+3Q and 5R.

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)×e(P,R)

e(P+S,Q)=e(P,Q)×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×G1 to Gt using:

  • G1 and which is an elliptic curve for the equation y²=x³+b and includes the modulus 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¹²−18w⁶+82=0. I will describe this in another article.
  • Gt and which is the resulting object.

Three-way handshake with BN pairings

In pairing we have the pairing operation of points on two curves (G1 and G2). If these points are P and Q, the pairing is: e(P,Q) and which returns the same result as e(Q,P). Along with this, these are all equivalent:

e(aQ,bP) = e(bQ,aP) = e(abQ,P) = e(Q,abP) = e(aQ,P)^b = e(Q,P)^{ab}

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×G1

qa=a×G2

pb=b×G1

qb=b×G2

pc=c×G1

qc=c×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:

This works because:

e(qc,pb)=e (cG1,bG2)=e (bcG1,G2)

Then, if we raise to the power of a we get:

Key=e (qc,pb)a=e (cG1,bG2)a=e (bcG1,G2)a=e (abcG1,G2)

And which should be the same value for Bob, Alice and Carol.

In Rust, we trust

In Rust we can use the BN library to implement most of the required code. In this case, we generate private keys for Alice (a), Bob (b) and Carol (c) and then each of them have two public keys: one on G1 and one on G2. Alice, for example, has public keys of pa and qa. These are passed to Bob and Carol [here]:

extern crate bn;
extern crate rand_core;
extern crate rand;


use bn::{G1,G2,Fr};
use crate::bn::{Group};

use bn::pairing;


use rand_core::OsRng;

use bincode::SizeLimit::Infinite;
use bincode::rustc_serialize::{encode};
use rustc_serialize::{Encodable};
use rustc_serialize::hex::{ ToHex};



pub fn into_hex<S: Encodable>(obj: S) -> Option {
    encode(&obj, Infinite).ok().map(|e| e.to_hex())
 }

fn main() {
   let rng = &mut rand::thread_rng();

// Generate private keys
let a =  Fr::random(rng);
let b = Fr::random(rng);
let c = Fr::random(rng);

// Public keys for Alice, Bob and Carol
let (pa, qa) = (G1::one() * a, G2::one() * a);
let (pb, qb) = (G1::one() * b, G2::one() * b);
let (pc, qc) = (G1::one() * c, G2::one() * c);

// Get secret share
let alice_ss = pairing(pb, qc).pow( a);
let bob_ss = pairing(pc, qa).pow(b);
let carol_ss = pairing(pa, qb).pow(c);


print!("\n\nAlice priv: {:}\n\nBob priv {:}\n\nCarol priv {:}",  into_hex(a).unwrap(), into_hex(b).unwrap(), into_hex(c).unwrap());
print!("\n\nAlice pupb: {:}\n\nBob pupb {:}\n\nCarol pupb {:}",  into_hex(pa).unwrap(), into_hex(pb).unwrap(), into_hex(pc).unwrap());
print!("\n\nAlice puqb: {:}\n\nBob puqb {:}\n\nCarol puqb {:}",  into_hex(qa).unwrap(), into_hex(qb).unwrap(), into_hex(qc).unwrap());

 if alice_ss == bob_ss && bob_ss == carol_ss {
     println!("\nSharing has worked!");
 }
 else {
    println!("\nSharing has failed!");
 }
}

And a sample run [here]:

Alice priv: 19a40ecc1ea7275e8fbf8e53b61883448da57ce34efaee6238956e09e2b0b7f0

Bob priv 07e7d2fd0b6ad87c65050ae21d0ce4e2ab04472727026d0fcf24ede405435b7e

Carol priv 0a66e780f1e0f06d042d6bc249b2b27e0d1767b366ac56cd74746e514d86331d

Alice pub1: 0422452ffb3090fb38952cf427b61d9037ffe0c13d7c6f97e343d18000c755561a2062615b57ce9ec35a66fb6bd599131f0ced98f9031d2fee6224a99d7d28381d

Bob pub1 042fa9f3c5c8902efe3e7ff6c03f093228d6ef7480afa7c095328a1e4870ee42560d6f896e83fb7bf073f5daa7a4897398a1d2e3288a5d1bcee49fef86111dd10d

Carol pub1 041f2712ca17e4e2ead6df07160771539340ba5b3cc41ce03ab555a5a3ca6017b80dffb67fb9ed662cef735465d1c4c9714d0dc4b86adf7b93c3259aa1eccaa361

Alice pub2: 0407b3964c852fc734f507b514c06dbb1d18b03c0a07db219c9d439b5f269f3476d711c5b2300254fe431c09e1c76bb2e8bb803e6251e7b85e33a578bd822c6c62072f2305ac36b66cb82fb49f930bb85a0a87cf7ed2eac92ec2759d978a587990be71df2bc5e2fecd20a002b6c71eebba92cb390973c23f486ec345d3d9e129bc

Bob pub2 040748b8f408ec05bc96fadf1eb0fe5e6f25e60cabadf0c1682b64de004fc500b0485b32102fbfeac03cab7e252d065905d77dfe5f063a32dea66e7fea5f46d82802acc96667f1e4c4c21a42be3157eeaa17e5f08ea7ee3380faf9a4015402c319655e9118690f0b7a2d56f28b55fc594cbaeb9c7ea9b3224db66fc1351b0aa604

Carol pub2 040540cbf4d173604b56844194053895a9d3cefd9349bc6e0814ce265888094ecac50f771538f3095aef05df48ff11a83ec24b0c2bbb0324294b281db796bf585d02cbdda866c5868ec7ea4ec8bc9709ada2ea65519d30d442e01fe7e078ddab8871efe2c7219b23a06ed3059803e2e2434b81134a2af4a10eb061cc7accbf7d11
Sharing has worked!

Conclusions

Apart from post-quantum crypto, pairing is one of the most interesting areas I’ve come across in the past few years. If you want more information on Rust and Crypto try here:

https://asecuritysite.com/rust/

and for pairing:

https://asecuritysite.com/rust/rust_pair01