0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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$ $\endgroup$
    – kelalaka
    Apr 26, 2021 at 15:28
  • $\begingroup$ The question has $𝑜𝑟𝑑(𝛼)≈2160$ where it is intended $\operatorname{ord}(\alpha)≈2^{160}$. Much of the confusion seems to come from that typographic error. $\endgroup$
    – fgrieu
    Feb 10, 2022 at 16:01

2 Answers 2

1
$\begingroup$

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 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.

$\endgroup$
2
  • $\begingroup$ "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 $\endgroup$
    – poncho
    Apr 26, 2021 at 14:35
  • $\begingroup$ @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. $\endgroup$
    – kelalaka
    Apr 26, 2021 at 14:53
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.