How Does Bob Share A Secret With Alice, Without Ever Communicating With Her Before The Share?

The code I am going to demonstrate in this article is [here].
Photo by Ben Mullins on Unsplash

How Does Bob Share A Secret With Alice, Without Ever Communicating With Her Before The Share?

The code I am going to demonstrate in this article is [here].

Let’s say that Bob and Alice have never contacted each other, ever. But they have a shared trusted friend called Trent. How do they generate a shared secret (such as an encryption key), without ever communicating beforehand? Well, we can do this with the magic on crypto pairs and the MIRACL pairing library.

In theory

First, let’s keep it simple. Bob needs to send Alice a message and puts it in a box. He now has to create a key for the box. How does he get the key to Alice? Well, he knows that Alice knows Trent, and she trusts Trent. Trent then generates a secret value that only Alice and Bob will know. Let’s call it s. Bob then takes something about Alice’s ID and then takes a hash value of it (Q_A). He takes a hash of his own ID (Q_B) — of which Alice will know whenever he sends the box. Now with the magic of crypto pairing, he uses a special pairing function (e) to give:

e(s x Q_B, Q_A)

and in crypto pairing, this is the same as:

e(Q_B, s x Q_A)

and which will be the key that Alice will generate, and so will be able to open the box.

In practice

First, we have two curves (G1 and G2) and initially, we define a large prime number (q). The crypto pairing function — e() — defines that if we have two points on an elliptic curve (P and Q) then:

e(aP, Q) = e(P,aQ) = e(P,Q)^a

and where a is a scalar value, and which is used to add a point on the elliptic curve for a times.

Initially, Trent (the KGC — Key Generation Centre) creates a secret random value (s) and shares it with Bob and Alice. We then have a known ID for Bob (ID_bob) and for Alice (ID_alice). Their public key will then become the hash of these values mapped to a curve:

QA=H(ID_A)

QB=H(ID_B)

The secret key for Alice is then:

dA=s QA

And the secret key for Bob is then:

dB=s QB

Now, all Alice has to do to generate a shared key between Bob and Alice is to take Bob public key value of QA=H(IDA) and do a pairing of:

e(dA,QB)

For Bob it will be:

e(dB,QA)

And they should end up with the same shared key, as:

e(dA,QB)=e(sQA,QB)=e(QA,sQB)=e(QA,dB)

Coding

The outline coding using the MIRACL library is [code]:

package main
import (
	"fmt"
	"github.com/miracl/core/go/core"
	"github.com/miracl/core/go/core/BN254"
	"math/rand"
	"time"
	"os"
)
func FP12toByte(F *BN254.FP12) []byte {
	const MFS int = int(BN254.MODBYTES)
	var t [12 * MFS]byte
	F.ToBytes(t[:])
	return(t[:])
}
func randval() *core.RAND {
    s1 := rand.NewSource(time.Now().UnixNano())
    r1 := rand.New(s1)
    rng := core.NewRAND()
    var raw [100]byte
    for i := 0; i < 100; i++ {
       raw[i] = byte(r1.Intn(255))
    }
    rng.Seed(100, raw[:])
    return rng
}
func main() {

	BobID:="athome"
	AliceID:="myaddress"
	argCount := len(os.Args[1:])
        if (argCount>0) {BobID= (os.Args[1])}
        if (argCount>1) {AliceID= os.Args[2]}
    	q := BN254.NewBIGints(BN254.CURVE_Order)
	s:=BN254.Randomnum(q,randval())
	sh:=core.NewHASH256()
	for i:=0;i < len(BobID);i++ {
		sh.Process(BobID[i])
	}
	Q_B:=sh.Hash()

	sh=core.NewHASH256()
	for i:=0;i < len(AliceID);i++ {
		sh.Process(AliceID[i])
	}
	Q_A:=sh.Hash()
	QA := BN254.ECP_mapit(Q_A)
	// Alice's secret key: dA
	dA:=BN254.G1mul(QA,s)
	QB := BN254.ECP2_mapit(Q_B)
	// Bob's secret key: dB
	dB:=BN254.G2mul(QB,s)
	LHS:=BN254.Ate(QB,dA);  LHS=BN254.Fexp(LHS)
	RHS:=BN254.Ate(dB,QA); RHS=BN254.Fexp(RHS)
	

	fmt.Printf("Bob ID:\t\t%s\n",BobID)
	fmt.Printf("Alice ID:\t%s\n\n",AliceID)
	fmt.Printf("s:\t%s\n\n",s.ToString())
	fmt.Printf("QB:\t%s\n\n",QB.ToString())
	fmt.Printf("QA:\t%s\n\n",QA.ToString())
	fmt.Printf("\n\nPair 1 e(dA,QB) - first 20 bytes:\t0x%x\n",FP12toByte(LHS)[:20])
	fmt.Printf("Pair 2 e(dB,QA) - first 20 bytes:\t0x%x\n",FP12toByte(RHS)[:20])
        if LHS.Equals(RHS) { fmt.Printf("\nSignature match\n")}

}

A sample run is [here]:

Bob ID:		bob@home
Alice ID:	alice@home
s:	0e409f166d053aaa3fae721c48a6478065f58a44637dc0b58dd0fe83f8e758c2
QB:	([0e0c27fda99a9cebb9b647a99e3c3821ca7512ba40251577010f3d284ec5dce4,0739f52acb074f77826a1fd05e0ecb44f4e6ad38274f4d691a5ab55e97b15dd0],[0fc2a977d7e1ccfa2c070180855ea532c2c4da3538cda2bdab733c0f26e5e112,030ee76d93b45c313f43e15ddaf2fd301f9ca6ce32b37981d93283ce76ad4f2b])
QA:	(12274944c48d83c874fe2fd6f5bac76cb2a9062b0edbcd2d6a7eda4cdc75ccc4,074dc393de05a5d44a979a7645932ebf9c4c6bfc27f6de6e2227163011985426)
Pair 1 e(dA,QB) - first 20 bytes:	0x0a34a27d3b0379cf85811b7dcd4dce1fa2bbb15e
Pair 2 e(dB,QA) - first 20 bytes:	0x0a34a27d3b0379cf85811b7dcd4dce1fa2bbb15e
Secret match

Conclusions

Trust Centres are a great approach to cybersecurity and often a much better solution than PKI. In a trust centre approach, an organisation can carefully manage all of its secure connections, and all we need is for each system to contact the Trust Centre for a shared secret. In a world of large scale IoT, this is probably one of the best ways to set up a secure trust infrastructure.

Here is an outline of KDCs: