In 2020, Eric Järpe from Halmstad University outlined an alternative Diffie-Hellman method [1]. It uses the \(\pmod{1}\) operation, and relies on the values calculated from the decimal part of a multiplication. Overall the method should be quantum robust. In this case, Bob and Alice share a value of \(x\). Alice creates a random value of \(a\) and then computes \(A=ax\pmod{1}\). Alice sends the value of \(A\) to Bob. Bob creates a random value of \(b\) and then computes \(B=bx\pmod{1}\). Bob sends the value of \(B\) to Alice. Alice computes the shared key of \(aB\pmod{1}\) and Bob computes the shared key of \(bA\pmod{1}\). If we have a value of \(5156.89227514554\), the value of \(5156.892275145543 \pmod{1}\) will be \(0.892275145543\).
An Alternative Diffie-Hellman Protocol |
Outline
The basic method is defined in [1] as:
Initially Bob and Alice share a value of \(x\) and which is a random number between 0 and 1.
For Alice:
Alice creates a random value \(a\) between 0 and \(2^{128}\).
Alice computes:
\(A=ax \pmod{1}\)
For Bob:
Bob creates a random value \(b\) between 0 and \(2^{128}\).
Bob computes:
\(B=bx \pmod{1}\)
Alice computes the share key of:
\(K_1=aB \pmod{1}\)
Bob computes the share key of:
\(K_2=bA \pmod{1}\)
The values of \(K_1\) and \(K_2\) should be the same. This works because \(ax \) will be:
\(ax = \lfloor ax \rfloor + \textrm{frac}(ax)\)
and where \(frac(ax)\) will be the fractional element of \(ax\). Then \(bx\) will be:
\(bx = \lfloor bx \rfloor + \textrm{frac}(bx)\).
The shared keys are then:
\(K_1 = a \times (\lfloor bx \rfloor + \textrm{frac}(bx)) = a \lfloor bx \rfloor + a \cdot \textrm{frac}(bx)\)
\(K_2 = b \times (\lfloor ax \rfloor + \textrm{frac}(ax)) = b \lfloor ax \rfloor + b \cdot \textrm{frac}(ax)\)
For a 16-bit example, we could start with the values of:
x=0.14845958875937193 a=34736 b=32601
The values of \(ax\) and \(bx\) will then be:
ax=5156.892275145543 bx=4839.931053144284
If we apply the \(\pmod{1}\) operation we get:
A= 0.89227514554335662921857874607667326927185058593750000 B= 0.93105314428428631590151098862406797707080841064453125
Alice takes the \(B\) value and multiplies by \(x\) to get
aB= 32341.06201985896946915488570084562525153160095214843750000 bA= 29089.06201985896946915488570084562525153160095214843750000
Alice and Bob then undertake a \(\pmod{1}\) operation to compute the shared key:
K1= 06201985896946915488570084562525153160095214843750000 K2= 06201985896946915488570084562525153160095214843750000
In Python we need to use the Decimal type in order to improve the precision of the multiplication, and also increase the precision of the multiplication to 256 bits with:
getcontext().prec = 256
The following is the code:
from random import uniform,randint from decimal import Decimal, getcontext import sys power=64 if (len(sys.argv)>1): power=int(sys.argv[1]) getcontext().prec = 256 x=uniform(0, 1) a= randint(0,2**power) b=randint(0,2**power) print (f"x={x}") print (f"a={a}") print (f"b={b}") print (f"\nax={a*x}") print (f"bx={b*x}") A=Decimal(Decimal(a)*Decimal(x))%1 B=Decimal(Decimal(b)*Decimal(x))%1 print ("\nA=",A) print ("B=",B) aB=(Decimal(a)*Decimal(B)) bA=(Decimal(b)*Decimal(A)) print ("\naB=",aB) print ("bA=",bA) K1=(aB)%1 K2=(bA)%1 print ("\nK1=",str(K1)[2:]) print ("K2=",str(K2)[2:]) if (K1==K2): print("The keys are the same")
A sample run for 16-bit random values:
x=0.5576767004114858 a=25250 b=12293 ax=14081.336685390015 bx=6855.5196781583945 A=ax (mod 1)= 0.3366853900154285206269832997350022196769714355468750 B=bx (mod 1)= 0.5196781583944420912501982456888072192668914794921875 aB= 13121.8734994596628040675057036423822864890098571777343750 bA= 4138.8734994596628040675057036423822864890098571777343750 K1=aB (mod 1)= 8734994596628040675057036423822864890098571777343750 K2=bA (mod 1)= 8734994596628040675057036423822864890098571777343750 The keys are the same
And we see the keys are the same. For a 128-bit test we get:
x=0.9612204629872735 a=8058062419293631556264055941246750874 b=269696538188156230175444633547731062728 ax=7.745574489453773e+36 bx=2.592378313032844e+38 A=ax (mod 1)= 0.94269854682539855339484802243532612919807434082031250 B=bx (mod 1)= 0.30815973027820664498221958638168871402740478515625000 aB= 2483170341694478801826800109916635475.95458497632847105762721184873953461647033691406250000 bA= 254242534633815485083335519834942732433.95458497632847105762721184873953461647033691406250000 K1=aB (mod 1)= 95458497632847105762721184873953461647033691406250000 K2=bA (mod 1)= 95458497632847105762721184873953461647033691406250000 The keys are the same
And for 256-bit random values:
x=0.3794502897619413 a=4281083017662430016243716424688908751217671408559612973094049316310932873193 b=110174259584945711128707576685528625111416443765163537880567169859935380782645 ax=1.624458191546935e+75 bx=4.180565472381499e+76 A=ax (mod 1)= 0.27265724731094509447615337194292806088924407958984375 B=bx (mod 1)= 0.26920598151795249730611203631269745528697967529296875 aB= 1152493155729652439539777385355727961393793748449475380289105175684471905250.83145636807120026912087951131979934871196746826171875 bA= 30039810342952805796291860861617805349835182773575628262888517667245002578149.83145636807120026912087951131979934871196746826171875 K1=aB (mod 1)= 83145636807120026912087951131979934871196746826171875 K2=bA (mod 1)= 83145636807120026912087951131979934871196746826171875 The keys are the same
Reference
[1] Järpe, E. (2020). An Alternative Diffie-Hellman Protocol. Cryptography, 4(1), 5. [paper].