An Alternative Diffie-Hellman Method … and What is (mod 1)?

An Alternative Diffie-Hellman Method … and What is (mod 1)?

In 1978, Whitfield Diffie and Martin Hellman created the Diffie-Hellman key exchange method, and which has since become one of the foundation principles of cybersecurity. With this, Bob and Alice agree on a generator value (g) and a prime number (p). To generate a shared key, Alice generates a random value (a) and computes A=g^a (mod p), and sends A to Bob. Bob generates a random value (b) and computes B=g^b (mod p), and send B to Alice. Alice then calculates the shared value of B^a (mod p) and Bob calculates the shared value of A^b (mod p). This value will be g^{ab} (mod p), and where (mod p) is the remainder of an integer divide by p.

These days we tend not to use discrete log methods, and use elliptic curve methods, instead. With this A=aG, and B=bG, and where the shared secrets will be K_1=bA and K_2=aB. This method is known as Elliptic Curve Diffie-Hellman (ECDH) and where G is the base point on the curve.

In 2020, E Järpe outlined an alternative Diffie-Hellman method [1]. It uses the (mod1) operation and relies on the values calculated from the fractional part of a multiplication:

Initially, Bob and Alice share a value of x. Alice creates a random value of a and then computes A=ax (mod 1). Alice sends the value of A to Bob. Bob creates a random value of b and then computes B=bx (mod 1). Bob sends the value of B to Alice. Alice computes the shared key of aB(mod 1) and Bob computes the shared key of bA (mod 1). If we have a value of 5156.89227514554, the value of 5156.892275145543 (mod 1) will be 0.892275145543.

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¹²⁸.
• Alice computes: A=ax (mod 1)

For Bob:

• Bob creates a random value b between 0 and 2¹²⁸.
• Bob computes: B=bx (mod 1)

Alice computes the share key of:

K_1=aB (mod 1)

Bob computes the share key of:

K_2=bA (mod 1)

The values of K1 and K2 should be the same. 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 (mod1) 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 (mod1) 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 128 bits with [here]:

getcontext().prec = 128

The following is the code [here]:

from random import uniform,randint
from decimal import Decimal, getcontext 

getcontext().prec = 128
x=uniform(0, 1)

a= randint(0,2**128)
b=randint(0,2**128)

print (f"x={x}")
print (f"ax={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)

K1=(Decimal(a)*Decimal(B))%1
K2=(Decimal(b)*Decimal(A))%1

print ("\nK1=",str(K1)[2:])
print ("K2=",str(K2)[2:])

A sample run for 16-bit random values [here]:

x=0.7714183271158723
a=1758
b=1305

ax=1356.1534190697037
bx=1006.7009168862133

A= 0.153419069703550015049131616251543164253234863281250
B= 0.700916886213386103321454356773756444454193115234375

aB= 1232.211885963132769639116759208263829350471496582031250
bA= 200.211885963132769639116759208263829350471496582031250

K1= 211885963132769639116759208263829350471496582031250
K2= 211885963132769639116759208263829350471496582031250

And we see the keys are the same. For a 128-bit test we get:

x=0.8940304918561741
a=132250476565951886959772836379149516651
b=285978704055506799904619958164115983241

ax=1.182359586124714e+38
bx=2.55673681447136e+38

A= 0.0155619186099766881881123481434769928455352783203125
B= 0.5398494119055798901030129854916594922542572021484375

aB= 71395341998361800864237750375160214239.1034803342382943913690951376338489353656768798828125
bA= 4450377316698407060664435116322072389.1034803342382943913690951376338489353656768798828125

K1= 1034803342382943913690951376338489353656768798828125
K2= 1034803342382943913690951376338489353656768798828125

The code is here:

and here is the running demo:

I have been lucky to speak to Eric and his explaination of the proof is:

Since transcendental numbers (i.e. numbers with a non-repeating decimal part like Pi and square root of 2 and such) are impossible represent exactly in computers only rounding up to some finite numbers of decimals are possible. Thus, representing the numbers (public keys and transferred numbers) as integers, and calculating mod “10 to the number of decimals” one can make an attack simply based on the Euclidean algorithm. So the keys have to be so long that it would take this attack the desired amount of time to break.

Reference

[1] Järpe, E. (2020). An Alternative Diffie-Hellman Protocol. Cryptography, 4(1), 5. [paper].