SPEKE (Simple Password Exponential Key Exchange) supports password-authenticated key agreement [1]. Bob and Alice share a secret password (\(\pi\)) and a shared prime number (\(p\)). This password is then hashed and used to determine a generator (\(g\)): \(g=H(\pi)^2 \pmod 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 \(g^a \pmod p\) and Bob sends \(g^b \pmod p\). Alice computes the shared key as \({(g^b \pmod p)}^a \pmod p\) and Bob computes the shared key as \({(g^a \pmod p)}^b \pmod p\). The resultant key is \(g^{ab} \pmod p\). [SPEKE][SPEKE (Elliptic Curve)].
SPEKE (Simple Password Exponential Key Exchange) |
Theory
SPEKE (Simple Password Exponential Key Exchange) supports password-authenticated key agreement. Bob and Alice share a secret password (\(\pi\)) and a shared prime number (\(p\)). This password is then hashed and used to determine a generator (\(g\)):
\(g=H(\pi)^2 \pmod 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 \pmod p\)
and Bob sends:
\(B=g^b \pmod p\)
Alice computes the shared key as:
\(K_1=B^a \pmod p\)
and Bob computes the shared key as:
\(K_2=A^b \pmod p\)
The resulting key is:
\(K= B^a \pmod p = {(g^b \pmod p)}^a \pmod p = g^{ab} \pmod p\)
Also, because of Euler's theorem, this will work:
\(K= g^{ab \pmod {(p-1)}} \pmod p\)
These two methods will be used to check the key generated in this code:
import sys import hashlib import random from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes primebits=64 pi = "Hello" 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) ab = (a*b) K = pow(g,ab,p) print ("\nCheck Key [g^{ab} (mod p)]:\t",K) ab = (a*b) % (p-1) K = pow(g,ab,p) print ("Check Key [g^{ab (mod p-1)} (mod p)]:\t",K)
A sample run for a 128-bit prime is:
Password: Hello123 g: 142345162370348897154126017638602458683 p: 238141073873582172999450895158495810241 Bob sends: 145381451067367466068276515942582867847 Alice sends: 176808224073090206230384361742739892175 Key 1: 24761591562022732295597275428334577403 Key 2: 24761591562022732295597275428334577403 Check Key [g^{ab} (mod p)]: 24761591562022732295597275428334577403 Check Key [g^{ab (mod p-1)} (mod p)]: 24761591562022732295597275428334577403
and for 256-bit prime:
Password: Hello123 g: 1869207960081585396477125349058195931888425135389578305412209568115658763611 p: 92423760040340306739583751517271991115736643590937213053055774908728350832011 Bob sends: 35390209860378979558581478347832649337280022332171399666587980466456420066038 Alice sends: 42696198221044417524808495556288861103134506694900286912834014787942278710010 Key 1: 29236980691979467508198147330675899319732323607492288571483926502586897101901 Key 2: 29236980691979467508198147330675899319732323607492288571483926502586897101901 Check Key [g^{ab} (mod p)]: 29236980691979467508198147330675899319732323607492288571483926502586897101901 Check Key [g^{ab (mod p-1)} (mod p)]: 29236980691979467508198147330675899319732323607492288571483926502586897101901
Presentation
References
[1] Jablon, D. P. (1996). Strong password-only authenticated key exchange. ACM SIGCOMM Computer Communication Review, 26(5), 5-26 [here].