Image for post
Image for post
Photo by Andrés Gómez on Unsplash

Password Juggling in Discrete Logs and Elliptic Curves

I love implementing things in discrete logs and then converting them into elliptic curve methods. Basically a exponentiation (g^x mod p) becomes a multiplication (xG), a multiplication (g^x g^y mod p) becomes a point addition (xG+yG), and a division (g^x /g^y mod p) becomes a point subtraction (xG-yG). In this article I will show all three of these operations, and show how we can convert from discrete logs into elliptic curve methods.

J-PAKE (Password Authenticated Key Exchange by Juggling) was created by Hao and Ryan [1]. It is a Password Authentication Key Exchange method, and where Bob and Alice share the same secret password. They can then generate a shared secret key. It involves two stages: a one-time key establishment; and a key confirmation stage. Overall, it does not need access to the PKI infrastructure.

In Round 1, Alice then generates two random values: x_1 and x_2. These are kept secret, and where Alice will send the following to Bob:

Image for post
Image for post

Bob then generates two random values: x_3 and x_4. These are kept secret, and where Bob will send the following to Alice:

Image for post
Image for post

In Round 2, Alice then calculates the following and sends to Bob:

Image for post
Image for post

Bob then calculates the following and sends to Alice:

Image for post
Image for post

Alice then calculates the shared key as:

Image for post
Image for post

Bob then calculates the shared key as:

Image for post
Image for post

The following is the code [here]:

import sys
import random
import hashlib
from Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes
from libnum import invmod
primebits=64
secret="Hello"
s=int(hashlib.md5(secret.encode()).hexdigest(),16)
if (len(sys.argv)>1):
primebits=int(sys.argv[1])
p = getPrime(primebits, randfunc=get_random_bytes)
g=3
x1 = random.randint(0, p-1)
x2 = random.randint(0, p-1)
x3 = random.randint(0, p-1)
x4 = random.randint(0, p-1)
g_x1 = pow(g,x1,p)
g_x2 = pow(g,x2,p)
g_x3 = pow(g,x3,p)
g_x4 = pow(g,x4,p)
A=pow(g_x1*g_x3*g_x4,x2*s,p)
B=pow(g_x1*g_x2*g_x3,x4*s,p)
K_inv1 = invmod(pow(g_x4,x2*s,p),p)
K_inv2 = invmod(pow(g_x2,x4*s,p),p)
print (f"Password: {secret}")
print ("===Alice parameters=== ")
print (f"Alice x1={x1}, x2={x2}\nAlice sends: g^x1 (mod p)={g_x1}, g^x2 (mod p)={g_x2}")
print ("\n===Bob parameters=== ")
print (f"Bob x3={x3}, x4={x4}\nBob sends: g^x3 (mod p)={g_x3}, g^x4 (mod p)={g_x4}")
print ("\n===Alice parameters=== ")
print (f"Alice sends A={A}")
print ("\n===Bob parameters=== ")
print (f"Bob sends B={B}")
print ("\nKey Alice:\t",pow(B*K_inv1,x2,p))
print ("Key Bob:\t",pow(A*K_inv2,x4,p))

And a sample run [here]::

Password: Hello
===Alice parameters===
Alice x1=157213077345404166232851178443413218352, x2=60882969011129026583507048344883123589
Alice sends: g^x1 (mod p)=56781426656681641144186196017500880545, g^x2 (mod p)=121860746084617583915988849727105883560
===Bob parameters===
Bob x3=45903653766348112533871178311001724528, x4=1638010860195229639042475084719695992
Bob sends: g^x3 (mod p)=132285796655680352374416311434659192709, g^x4 (mod p)=11399416518610155287102460214899329936
===Alice parameters===
Alice sends A=106163473460122235652996423416153745041
===Bob parameters===
Bob sends B=104256257064667401922110896172192982198
Key Alice: 161131477957450225970071118935386964443
Key Bob: 161131477957450225970071118935386964443

In Round 1, Alice then generates two random values: x_1 and x_2. These are kept secret, and where Alice will send the following points to Bob:

Image for post
Image for post

Bob then generates two random values: x3 and x4. These are kept secret, and where Bob will send the following points to Alice:

Image for post
Image for post

In Round 2, Alice then calculates the following point and sends to Bob:

Image for post
Image for post

Bob then calculates the following point and sends to Alice:

Image for post
Image for post

Alice then calculates the shared key as:

Image for post
Image for post

Bob then calculates the shared key as:

Image for post
Image for post

The following is the code [here]:

from secp256k1 import curve,scalar_mult, point_add,point_neg
import random
import hashlib
import sys
secret="Hello"
if (len(sys.argv)>1):
secret=sys.argv[1]
s=int(hashlib.md5(secret.encode()).hexdigest(),16)# Alice generates
x1 = random.randint(0, curve.n-1)
x2 = random.randint(0, curve.n-1)
# Bob generates
x3 = random.randint(0, curve.n-1)
x4 = random.randint(0, curve.n-1)
# Alice generates
x1G = scalar_mult(x1, curve.g)
x2G = scalar_mult(x2, curve.g)
# Alice generates
x3G = scalar_mult(x3, curve.g)
x4G = scalar_mult(x4, curve.g)
# A= (G1 + G3 + G4) x [x2*s]
A = point_add(x1G,x3G)
A = point_add(A,x4G)
A = scalar_mult(x2*s,A)
# B=(G1 + G2 + G3) x [x4*s]
B = point_add(x1G,x2G)
B = point_add(B,x3G)
B = scalar_mult(x4*s,B)
# Ka = (B - (G4 x [x2*s])) x [x2]
Ka = scalar_mult(x2,point_add(B,point_neg(scalar_mult(x2*s,x4G))))
# Bob computes Kb = (A - (G2 x [x4*s])) x [x4]
Kb = scalar_mult(x4,point_add(A,point_neg(scalar_mult(x4*s,x2G))))
print (f"Shared password: {secret}")
print ("===Alice parameters=== ")
print (f"Alice x1={x1}, x2={x2}\nAlice sends: x1G ={x1G}, x2G (mod p)={x2G}")
print ("\n===Bob parameters=== ")
print (f"Bob x3={x3}, x4={x4}\nBob sends: x3G ={x3G}, x4G ={x4G}")
print ("\n===Alice parameters=== ")
print (f"Alice sends A={A}")
print ("\n===Bob parameters=== ")
print (f"Bob sends B={B}")
print (f"\nAlice key: {Ka[0]}")
print (f"Bob key: {Kb[0]}")

And a sample run [here]:

Shared password: Hello
===Alice parameters===
Alice x1=109223778996008288522752313848072201758184207182558942631021579873936392111849, x2=70164035479348133703302704351481332338501967890693555425529073473167539752301
Alice sends: x1G =(25757379941637732465573935070442020365879599102324511094843713901095524531800, 54326101113419731239507117799777645852329796924147840511329613587119920683693), x2G (mod p)=(5706311334803882186027182100991396833153739570993758136649404286549554001570, 106168453431397971102840065735250567879463130661919689523977025175625629858690)
===Bob parameters===
Bob x3=113328284219482995795681121841598407747113363163727872101184389718131489417226, x4=94863383611815555242143536561323826445308191135350794049205403770770601196846
Bob sends: x3G =(40880339132884486501685633826331351175176673629328173409146139796674827176388, 27794339853952991181191384213539267701325905882975701216294183824555854013681), x4G =(108245762028214747089045785337280106838812776556601588479474228996536995423797, 105254641585474920614907618522803316359119132070853766923246033513721029568275)
===Alice parameters===
Alice sends A=(113708982016570409852826497024398419040874810528428747983711214340060038552407, 12449611840362587536436172331378674267418812633125332589127742521395727671735)
===Bob parameters===
Bob sends B=(32362610944530295763556764702321503631851749992465430289848515183640872056976, 2507094715922200386410039051112915477205177066245229095569452807229671828742)
Alice key: 39828201834688558297506388516640559720610311763003967947405469276609917171305
Bob key: 39828201834688558297506388516640559720610311763003967947405469276609917171305

And that’s it! You can try here:

and:

[1] Hao, F., & Ryan, P. Y. (2008, April). Password authenticated key exchange by juggling. In International Workshop on Security Protocols (pp. 159–171). Springer, Berlin, Heidelberg [here].

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