Image for post
Image for post
Photo by Jason Dent on Unsplash

Bob has a secret and Alice has the same secret. Why can’t they create a shared encryption key based on their secrets? Well, they can do this with Password Authentication Key Exchange (PAKE). So, let’s look at a simple method using discrete logs, and then we will convert it to elliptic curve methods. While discrete logs have been used in the past for Diffie-Hellman key exchange methods, we are increasing moving towards elliptic curve implementations.

SPEKE (Simple Password Exponential Key Exchange) supports password-authenticated key agreement. Bob and Alice share a secret password (π) and a shared prime number (p). This password then hashed and used to determine a generator (g):

g=H(π)² (mod p)

The square function of the hash makes sure that g is a generator for the prime number p. After this, we can use a standard Diffie-Hellman type exchange. For this, Alice generates a random number a and Bob generates a random number b. Alice then sends:

A=g^a (mod p)

and Bob sends:

B=g^b (mod p)

Alice computes the shared key as:

K1=B^a(mod p)

and Bob computes the shared key as:

K2=A^b (mod p)

The resulting key is:

K=B^a(modp)=(g^b(mod p))^a (mod p)=g^{ab}(mod p)

The code is [here]:

import sys
import hashlib
import random
from Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes
primebits=64
pi = "HellHe"
if (len(sys.argv)>1):
primebits=int(sys.argv[1])
if (len(sys.argv)>2):
pi=(sys.argv[2])
p = getPrime(primebits, randfunc=get_random_bytes)
g=pow(int(hashlib.sha1(pi.encode()).hexdigest(), 16),2,p)
a = random.randint(0, p-1)
b = random.randint(0, p-1)
Alice_to_send = pow(g,a,p)
Bob_to_send = pow(g,b,p)
AliceK= pow(Bob_to_send,a,p)
BobK= pow(Alice_to_send,b,p)
print ("Password: ",pi)
print ("g: ",g)
print ("p: ",p)
print ("\nBob sends:",Bob_to_send)
print ("Alice sends:",Alice_to_send)
print ("\nKey 1:",AliceK)
print ("Key 2:",BobK)

A sample run is:

Password:  Hello
g: 73525324253897172423132549165310937396
p: 229932236240047387625280325764254732773
Bob sends: 220636637171481361964163894933309078043
Alice sends: 199794325878831155787034700209907371004
Key 1: 183965511264117905740718415139891954828
Key 2: 183965511264117905740718415139891954828
Check Key [g^{ab} (mod p)]: 183965511264117905740718415139891954828

SPEKE (Simple Password Exponential Key Exchange) supports password-authenticated key agreement [1]. With the elliptic curve version, Bob and Alice share a secret password (π) and a pre-defined shared elliptic curve. The password is then hashed and matched to the nearest point on the elliptic curve (Ppass). After this, we use a standard Diffie-Hellman type exchange. Alice generates a random number a and Bob generates a random number b. Alice then sends:

A=a P_pass

and Bob sends:

B=b P_pass

Alice computes the shared key as:

Ka=ab P_pass

and Bob computes the shared key as:

Kb=ba P_pass

The resultant key is:

K=ab P_pass

The code is [here]:

from secp256k1 import curve,scalar_mult,is_on_curve
import random
import hashlib
import sys
print("Basepoint:\t", curve.g)pi="Hello12"if (len(sys.argv)>1):
pi=(sys.argv[1])
a = random.randrange(1, curve.n)
b = random.randrange(1, curve.n)
sha1 = hashlib.sha1()
sha1.update(pi.encode())
pi_val=int(sha1.hexdigest(),16)
while (True):
Gpass=scalar_mult(pi_val,curve.g)
print (pi_val)
if (is_on_curve(Gpass)): break
pi_val = pi_val+1
A = scalar_mult(a,Gpass)
B= scalar_mult(b,Gpass)
K1= scalar_mult(b,A)
K2= scalar_mult(a,B)
print ("Password: ",pi)
print ("\nG Password:\t",Gpass)
print ("\na (Alice):\t",a)
print ("b (Bob):\t",b)
print ("\nA (Alice):\t",A)
print ("B (Bob):\t",B)
print ("\nKey (Alice):\t",K1[0])
print ("Key (Bob):\t",K2[0])
ab = (a*b) % curve.n
K = scalar_mult(ab,Gpass)
print ("\nCheck Key (abG):\t",K[0])

A sample run is:

Basepoint:	 (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
1415821221623963719413415453263690387336440359920
Password: Hello
G Password: (65263944084342197025982124855390080779660665968109789976012065852149178226136, 109090808538266950129139030441868732836608221927863983502692128997257182831796)a (Alice): 48185787601198123356043137125673840923931232500115760542256524798506782078508
b (Bob): 29639847004469692476331743385978312761531585925135259595814894165542797423162
A (Alice): (21085828653989277334674342610986873409847711531993257586241279793917261226755, 92221957071356973682119674658656669322901778695497344614187149567674647993412)
B (Bob): (8796344150785726626550877995972978159779090732523192035287428403371731204637, 4585514135139190939947207782465169045619890452614570058646501179659359957650)
Key (Alice): 96208563962866347524960918151313886255531149937798325149439757292973279449065
Key (Bob): 96208563962866347524960918151313886255531149937798325149439757292973279449065
Check Key (abG): 96208563962866347524960918151313886255531149937798325149439757292973279449065

And that’s it … magic!

Interested in learning more? Here’s OPAQUE:

Written by

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

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