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$;
Choose a prime in the form $p = kq+1$ and those are called DSA prime by poncho. They are cheap to generate.
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$.
Choose a prime of the form $2q+1$ and those are called safe 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 secure. 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.