Image for post
Image for post
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

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

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

package mainimport (	"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: 0e409f166d053aaa3fae721c48a6478065f58a44637dc0b58dd0fe83f8e758c2QB: ([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

Here is an outline of KDCs:

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store