# DHKE Square and Multiply

Given is a DHKE algorithm. The modulus 𝑝 has 1024 bit and 𝛼 is a generator of a subgroup where 𝑜𝑟𝑑(𝛼)≈2160.

Assuming the public keys have already been computed, how many number of modular multiplication and modular squaring are there in the session key.

Using the square and multiply algorithm on $$2^{160}$$ :

160 = 10100000 in Binary

1 First One list Number 2

0 Zero calls for Square $$(2){^2}$$

1 One calls for Square + Multiply $$((2){^2}){^2}$$ * 2

0 Zero calls for Square $$(((2){^2}){^2}$$ * 2)$${^2}$$

0 Zero calls for Square $$((((2){^2}){^2}$$ * 2)$${^2}$$)$${^2}$$

0 Zero calls for Square $$(((((2){^2}){^2}$$ * 2)$${^2}$$)$${^2}$$)$${^2}$$

0 Zero calls for Square $$((((((2){^2}){^2}$$ * 2)$${^2}$$)$${^2}$$)$${^2}$$)$${^2}$$

0 Zero calls for Square $$(((((((2){^2}){^2}$$ * 2)$${^2}$$)$${^2}$$)$${^2}$$)$${^2}$$)$${^2}$$

Thus, there should be a total of 7 squares and 1 multiplication for exponent of 160.

Similarly, if we assume now that α is such a short element (e.g., a 16-bit integer).

Using the square-and-multiply algorithm we should get that there is a total of 4 squares and 0 multiplications for exponent of 16.

Is this a correct understanding of number of modular multiplication and squaring using square-and-multiply algorithm for the session key?

• Note: I wrote a little extensive answer to this since recently, there are Q that misunderstood DHKE. Your calculation is wrong since $2^{160} = 1461501637330902918203684832716283019655932542976$. Your result is $1208925819614629174706176$ Apr 26 at 15:28

## Standard DHKE

Standard DHKE is defined on the multiplicative groups. Alice and Bob agree on the cyclic group $$G$$ of order $$n$$ and a generator $$g$$ then the key agreement is performed as follows;

$$\begin{array}{lcl} \text{Alice} & \text{Transmit} & \text{Bob}\\ \hline a \stackrel{R}{\leftarrow} [1,n-1]& & b \stackrel{R}{\leftarrow} [1,n-1]\\ \text{calculates } A = g^a & \xrightarrow{A} & \text{calculates } B = g^b\\ & \xleftarrow{B} & \text{calculates } s = B^a = (g^a)^b = g^{ab} \\ \text{calculates } s = A^b = (g^b)^a = g^{ab} & & \end{array}$$

Therefore both sides have agreed on the $$s = g^{ab}$$ and

## Group Selection

We can use the below 3 prime classes to choose the $$p$$;

1. Choose a prime in the form $$p = kq+1$$ and those are called DSA prime by poncho. They are cheap to generate.

2. Choose a prime of the form $$p = 2qr+1$$ and those are called Lim-Lee primes where both $$q$$ and $$r$$ primes around the half size of $$p$$.

3. Choose a prime of the form $$2q+1$$ and those are called sage primes and $$q$$ is called Sophie Germain prime.

Generation easiness and order of security of these groups are $$1<2<3$$

If you choose $$\mathbb{Z}_p$$ then the multiplicative order is $$p-1$$ which is not a prime and the group may vulnerable to Pohlig-Hellman. With the above methods, we guarantee that we have an element with large order $$q$$.

## Modular Exponentiation

def modular_pow(base, exponent, modulus):
if modulus == 1:
return 0
result = 1
base = base % modulus

while exponent > 0:
if (exponent % 2 == 1):
result = (result * base) % modulus
exponent = exponent //2
base = (base * base) % modulus
return result


## Calculation

Let's take ffdhe2048 from RFC 7919

• $$p = p = 2^{2048} - 2^{1984} + (\lfloor(2^{1918} \cdot e \rfloor + 560316 ) \cdot 2^{64} - 1$$
• $$g = 2$$
• $$q = 2*p+1$$, so we have a safe prime.
• $$n = q = (p-1)/2$$, and
• a = 160
Exponent =  0
Squaring   , base   =  4
Exponent =  0
Squaring   , base   =  16
Exponent =  0
Squaring   , base   =  256
Exponent =  0
Squaring   , base   =  65536
Exponent =  0
Squaring   , base   =  4294967296
Exponent =  1
Multiplying, result =  4294967296
Squaring   , base   =  18446744073709551616
Exponent =  0
Squaring   , base   =  340282366920938463463374607431768211456
Exponent =  1
Multiplying, result =  1461501637330902918203684832716283019655932542976
Squaring   , base   =  115792089237316195423570985008687907853269984665640564039457584007913129639936

Result =  1461501637330902918203684832716283019655932542976


Note on 160

The exponent is too small to be square. When the attackers see the result and compared to the

p=16158503035655503650076756738912581681244028566744537587294217069634903417068105001396028181320082342729278178967665408464414511540286736312636777371230622870513101263958286486431353150162631714106572883465707111827110470555674314995828739134017115276543174525317778856109593945166364784848064871928120870618118612598673201345927898883988411507312698966529007613429365380598766218233737927730357521948422470183065248848906427147979329798783525641926066392234261462752284136439556860049465936979571687087918913000139017486599276030303766617061301627342044060015552953742140501997483478059848478124314516169036419563519

They simply will consider that you used a small number and will search it by brute force. The $$a$$ must be chosen uniformly random as $$a \stackrel{R}{\leftarrow} [1,n-1]$$.

Actually, we don't need $$a \stackrel{R}{\leftarrow} [1,n-1]$$ for the security $$a \stackrel{R}{\leftarrow} [1,2^{224}]$$ is enough between 2019 and 2030 according to NIST ( see as keylenght.com). As stated poncho on the commends, this is more efficient.

Performance

Now the number of operations is quite countable. We have to square for every bit of the exponent ( $$160_{10} = [10100000]_2$$) and a multiplication whenever a bit is 1 ( 2 times for 160 sine $$160= 128+32$$).

The above function is not optimal to calculate modular exponentiation and vulnerable to side-channel since there is a conditional that depends on the exponent bits.

## MITM

Standard DHKE is vulnerable to MITM attack and Telegram had a different one too. To mitigate the MITM attack digital signatures are required.

• "The $a$ must be chosen uniformly random as $a \stackrel{R}{\leftarrow} [1,n-1]$"; does that mean that there is an attack if $a$ is chosen uniformly random from the range $[1, 2^{256}]$? I ask because $a$'s from that range are significantly more efficient Apr 26 at 14:35
• @poncho As of now, I'm not aware of such an attack, and as you said it is more efficient and it is given in the keylength.com, too. Thanks, let me update. Apr 26 at 14:53

The generation of session key is to power public key with private key where private key is an integer $$< 2^{160}-1$$, which is 160 bit. Therefore, it takes 159 squares and 0.5*160 multiple(in average).