Extensions of the Diffie-Hellman Key Agreement Protocol Based on Exponential and Logarithmic Functions

Abstract

We propose a method of constructing cryptographic key exchange protocols of the Diffie-Hellman type based on the exponential and logarithmic functions over the multiplicative group of integers modulo n. The security of the proposed protocols is based on the computational difficulty of solving a set of congruence equations containing a discrete logarithm. For the multiplicative group of integers modulo n we define the non-commutative group of their automorphisms. On the defined group we construct non-commutative key exchange protocol similar to the Anshel-Anshel-Goldfeld key exchange scheme.

1 Introduction

The Diffie-Hellman key exchange is one of the most utilized key agreement protocols in the secure network communication. There are symmetric and asymmetric (public) key exchange variants of the protocol. In case of the symmetric Diffie-Hellman key exchange protocol the users $\textrm{A}$ and $\textrm{B}$ agree the modulus p being the prime number and the primitive root r from the multiplicative group $(\textrm{Z}/(p))^*$ of integers modulo p. The user $\textrm{A}$ selects the number a and the user $\textrm{B}$ selects the number b from $(\textrm{Z}/(p))^*$. Both communicating parties exchange the numbers $r^{a} \mathrm{\;mod\;} p$ and $r^{b} \mathrm{\;mod\;} p$. The common key is $k_{a,b} = (r^{b})^{a} =(r^{a})^{b} \mathrm{\;mod\;} p$, [1, 2]. Security of the protocol is based on computational difficulty in determining the value of discrete logarithm $\log _{r}(r^{a}) \mathrm{\;mod\;} \varphi (p)$. The standard X9.42 defines the Diffie-Hellman public key exchange scheme in which the private-public keys is the pair $(a, g^a \mathrm{\;mod\;} p)$, $a, g\in (\textrm{Z}/(p))^*$, [2]. According to the standard, the modulo parameter should be a prime number of the form $p=jq + 1$, where q is a large prime and $j\ge 2$. The base g of the public key $g^a \mathrm{\;mod\;} p$ is of the form $g = h^{j} \mathrm{\;mod\;} p$, where h is any integer with $1< h < p-1$ such that $h^{j} \mathrm{\;mod\;} p > 1$. The base g does not have to be a generator of the cyclic group $(\textrm{Z}/(p))^*$. For $j=2$ we obtain the so called ‘safe prime’ numbers $p=2q+1$, where q is prime. The set of primitive roots $S^{(r)}_{2q+1}$ can be obtained by removing from the group $(\textrm{Z}/(2q+1))^*$ all elements raised to power two (the quadratic residues) and removing the element 2q, which is the unique element such that $(2q)^2=1 \mathrm{\;mod\;} (2q+1)$.

For the symmetric Diffie-Hellman key exchange protocol the crucial problem is determination of the primitive root elements from the group $(\textrm{Z}/(p))^*$. Unfortunately, there is no general formula which allows to determine it. In the preliminary section we discus the problem of finding the primitive root elements in cyclic groups. In the Lemma we define the set of primitive roots in the group $(\textrm{Z}/(p))^*$ as the common part of the complement of the sets of p-residues, see the formula (2). This definition allows in an efficient way to construct algorithms for searching the primitive root elements in cyclic groups. In the same section we define four types of functions which permute the elements of the group $(\textrm{Z}/(p))^*$. In Sect. 4 we propose the method of constructing Diffie-Hellman like key agreement protocols based on defined exponential and monomial functions. The security of the discussed protocols is based on the computational difficulty of solving a set of congruence equations containing the discrete logarithm. The public key exchange variants of the proposed protocols can be obtained straightforward.

With each of the defined functions we associate the subgroup of symmetric group of $p-1$ elements. In Sect. 5 we use these groups to construct a symmetric key agreement protocol based on the idea of the Anshel-Anshel-Goldfeld (AAG) key agreement scheme [3, 4].

2 Related Work

The idea of using the non-abelian groups in cryptography has its origin in the solutions of three famous problems in combinatorial group theory proposed by M. Dehn in 1911, [5]. These are the word problem, the conjugacy problem and the isomorphism problem for finitely presented groups, [6]. In [7] Wagner and Magyarik devised the first public-key protocol based on the unsolvability of the word problem for finitely presented groups. A non-deterministic public-key cryptosystem based on the conjugacy problem on braid group, similar to the Diffie-Hellman key exchange system, was proposed in [8]. The particular importance are the Anshel-Anshel-Goldfeld key agreement system and the public-key cryptosystem proposed in [3, 4, 9]. The authors used the braid groups where the word problem is easy to solve but the conjugacy problem is intractible. This is due to the fact that on braid groups the best known algorithm to solve the conjugacy problem requires at least exponential running time. Proposed in Sect. 5 the symmetric key agreement protocol is based on the idea of the Anshel-Anshel-Goldfeld (AAG) key agreement scheme.

In Sect. 4 we construct a familly of Diffie-Hellman like key agreement protocols based on exponential and monomial functions which permute the cyclic group $(\textrm{Z}/(p))^*$. This is one of many generalization of the Diffie-Hellman key exchange protocol. For example, in [10] it was proposed a generalization of the Diffie-Hellman scheme called Algebraic generalization of Diffe-Hellman (AGDH). Its security is based on the hardness of a solution of the homomorphic image problem, which requires to compute the image of a given element under an unknown homomorphism of two algebras selected as a encryption platform. In [11] a matrix-based Diffie-Hellman key exchange protocol was proposed. The security of the proposed protocol is based on exploiting of a non-invertible public matrix in the key generating process. In [12] a polynomial time algorithm to solve the Diffie-Hellman conjugacy problem in braid groups was proposed. Security aspects of the algorithm was analysed and proved. In [13] was considered a Diffie-Hellman like key exchange procedure which security is based on the difficulty of computing discrete logarithms in a group matrices over noncommutative ring. In the algorithm the exponentiation is hidden by a matrix conjugation which ensures it security. In [14] a new computational problem called the twin Diffie-Hellman problem was proposed. The twin DH protocol allows to avoid the problem of an attack on the public keys exchanged in the standard Diffie-Hellman scheme. I. F. Blake and T. Garefalakis analyzed the complexity of the discrete logarithm problem, the Diffie-Hellman and the decision DH problem, [15]. The authors showed that if the decision DH problem is hard then computing the two most significant bits of the DH function is hard. In [16] the authors analyze complexity of the Group Computational Diffe-Hellman and Decisional Diffe-Hellman problems and their application in cryptographic protocols. The security of the group Diffe-Hellman key exchange is discussed, [17]. In [18] the authors apply the symbolic protocol analysis to cryptographic protocols which utilize the exponentiation calculations on cyclic groups. Using this analysis several security aspects of Diffie-Hellman like operations was proved.

3 Preliminaries

The multiplicative group $(\textrm{Z}/(n))^*$ is the set of elements from the ring $\textrm{Z}/(n)$ of integers modulo n coprime to n. The group $(\textrm{Z}/(n))^*$ is cyclic if and only if n is of the type $n = 1, 2, 4, p^m, 2 p^m$, where p is an odd prime number and $m\ge 1$, [19]. The generators of $(\textrm{Z}/(n))^*$ are called primitive roots. The order of a primitive root $r\in (\textrm{Z}/(n))^*$ is equal to the Euler totient function $\varphi (n)$, i.e., $\varphi (n)$ is the smallest number such that $r^{\varphi (n)} = 1 \mathrm{\;mod\;} n$. By $S^{(r)}_{n}$ we denote the set of all primitive roots in $(\textrm{Z}/(n))^*$. The cardinality of the set $S^{(r)}_{n}$ equals to $\varphi (\varphi (n))$. By $(\textrm{Z}/\varphi (n))^*$ we denote the multiplicative group of integers coprime to $\varphi (n)$, i.e., $(\textrm{Z}/\varphi (n))^* = \{ k \in \textrm{Z}/\varphi (n) : \gcd (k,\varphi (n))=1\}$. For any $i\in (\textrm{Z}/(n))^*$ and $k\in (\textrm{Z}/\varphi (n))^*$ the equation $i \cdot k = 0 \mathrm{\; mod \;} \varphi (n)$ implies that $i=0 \mathrm{\;mod\;} \varphi (n)$. From this implication it follows that the set $\{i^{k} \mathrm{\;mod\;} n : i\in (\textrm{Z}/(n))^*\}$ is equal to $(\textrm{Z}/(n))^*$ and the elements $r^{k} \mathrm{\;mod\;} n$, for given primitive root r, generate the whole set

$$\begin{aligned} S^{(r)}_{n} = \{ r^{k} \mathrm{\;mod\;} n : k \in (\textrm{Z}/\varphi (n))^*\}. \end{aligned}$$

(1)

Let p be a prime number and $\varphi (p)= p_0^{a_0} p_1^{a_1} \cdots p_k^{a_k}$, where $p_0=2$. The element $g\in (\textrm{Z}/(p))^*$ is a residue of degree $p_i$ modulo p if there exists $a\in (\textrm{Z}/(p))^*$ such that $a^{p_i} = g \mathrm{\;mod\;} p$. By $((\textrm{Z}/(p))^*)^{p_i}$ we denote the group of $p_i$-residues $\mathrm{\;mod\;} p$ and by

$$\begin{aligned} (((\textrm{Z}/(p))^*)^{p_i})^{C} = (\textrm{Z}/(p))^{*} \setminus ((\textrm{Z}/(p))^*)^{p_i}\end{aligned}$$

the set of $p_i$-non-residues, i.e., the complement of $((\textrm{Z}/(p))^*)^{p_i}$ in $(\textrm{Z}/(p))^{*}$. The group $((\textrm{Z}/(p))^*)^{p_i}$ is a cyclic of order $\varphi (p)/p_i$.

Lemma. For a prime number p and $\varphi (p)=p_0^{a_0} p_1^{a_1} \cdots p_k^{a_k}$ the set of primitive roots can be obtained from the formula

$$\begin{aligned} S^{(r)}_{p}= \bigcap _{i=0}^{k} (((\textrm{Z}/(p))^*)^{p_i})^{C}. \end{aligned}$$

(2)

Proof. Let $g=r^{b}, x=r^{a}\in (\textrm{Z}/(p))^*$ and $x^{p_i} = g \mathrm{\;mod\;} p$ for some root r. From $r^{a\cdot p_i} = r^{b} \mathrm{\;mod\;} p$ it follows that $a\cdot p_i = b \mathrm{\;mod\;} \varphi (p)$. If $\gcd (b, \varphi (p))=1$ then $p_i$ does not divides b, which means that $b\in (\textrm{Z}/\varphi (p))^*$ and $r^{b} \mathrm{\;mod\;} p \in S^{(r)}_{p}$ $\diamond$.

The formula (2) states that for a primitive root $r\in (\textrm{Z}/(p))^*$ the set of congruence equations $x^{p_i} = r \mathrm{\;mod\;} p, i\in [0,k]$ is not solvable. By

$$G^{p}_{p_0 \cdots p_k} = \bigcap _{i=0}^{k} ((\textrm{Z}/(p))^{*})^{p_i} = ((\textrm{Z}/(p))^{*})^{p_0 p_1 \cdots p_k}$$

we denote the intersection of all $p_i$-residue groups $((\textrm{Z}/(p))^{*})^{p_i}$, $i\in [0,k]$. Because any root $r=r_0^{e} \mathrm{\;mod\;} p$, where $r_0 \in S^{(r)}_{p}$ and $e\in (\textrm{Z}/\varphi (p))^{*}$, then the group $G^{p}_{p_0 \cdots p_k}$ leaves the set of roots invariant and acts on $(\textrm{Z}/\varphi (p))^{*}$ as translations

$$T_{g}(r_0^{e})= g\cdot r_0^{e} = r_0^{e + \textrm{ind}_{}(g)} \mathrm{\;mod\;} p,$$

where $g\in G^{p}_{p_0 \cdots p_k}$ and $\textrm{ind}_{}(g)$ is the index of g. The order of the group $|G_{p_0 p_1 \cdots p_k}|= \frac{\varphi (p)}{p_0 p_1 \cdots p_k}$.

One of the first algorithms which allow to find a primitive root was defined by Gauss. In the algorithm it is used the fact that for the element $g\in (\textrm{Z}/(p))^*$ such that $g^{(p-1)/p_i}\ne 1$ the orders of $g^{(p-1)/p_i}$ and $g^{(p-1)/p_i^{a_i}}$ are equal to $\textrm{Ord}_{p}(g^{(p-1)/p_i})=p_i$ and $\textrm{Ord}_{p}(g^{(p-1)/p_i^{a_i}})=p_i^{a_i}$ respectively. If $p_i\ne p_j$, then by multiplying $g_i^{(p-1)/p_i^{a_i}}$ and $g_j^{(p-1)/p_j^{a_j}}$ one can obtain an element of order $\textrm{Ord}_{p}(g_i^{(p-1)/p_i^{a_i}} g_j^{(p-1)/p_j^{a_j}}) = p_i^{a_i} p_j^{a_j}$.

Gauss’s algorithm to find a primitive root.

• 1. Find the first $p_i$-non-residue, $i\in [0,k]$, i.e., the numbers $g_i$ such that $g_i^{(p-1)/p_i} \ne 1 \mathrm{\;mod\;} p$.

• 2. From the formula $g_i^{(p-1)/p_i^{a_i}} \mathrm{\;mod\;} p$ determine the elements of order $p_i^{a_i}$.

• 3. The product $\prod _{i=0}^{k} g_i^{(p-1)/p_i^{a_i}} \mathrm{\;mod\;} p$ is a primitive root.

As an example of application of the Gauss’s algorithm we find a primitive root in $\textrm{Z}/(p)^{*}$, where $p=4441$. Because $p-1=2^3 \cdot 3 \cdot 5\cdot 37$, for each prime $p_0=2$, $p_1=3$, $p_2=5$, $p_3=37$ the first 2th non-residue is 7, the first 3th, 5th and 37th non-residue is 2. The element $r=7^{4440/2^3}\cdot 2^{4440/3}\cdot 2^{4440/5}\cdot 2^{4440/37} = 2749 \mathrm{\;mod\;} 4441$ is a primitive root.

E. Bach modified the Gauss’s algorithm to the following form.

• 1. Find $B\ge 1$ such that $B \log B= C \log p$, $C=30$.

• 2. Factor $p-1=p_0^{a_0}\ldots p_s^{a_s} Q$, where $p_{i}<B$ and Q are free of primes $<B$.

• 3. For each $i=0, \ldots , s$ choose a prime $g_i\le 2 (\log p)^{2}$ such that $g_i^{(p-1)/p_i}\ne 1$.

• 4. For $g=\prod _{i=0}^{s} g_i^{(p-1)/p_i^{a_i}}$ construct the set $S=\{ g \cdot q^{(p-1)/Q} \mathrm{\;mod\;} p: q \mathrm{\;is \; prime\;and \;} q\le 5 \frac{(\log p)^4}{(\log \log p)^2}\}.$

In [20] E. Bach proved, assuming that the extended Riemann hypothesis is true, that the algorithm computes the set S of residues $\mathrm{\;mod\;} p$ such that S contains a primitive root and the cardinality of the set |S| is of order $O( \frac{(\log p)^4}{(\log \log p)^3})$. As an example of application of E. Bach algorithm we find a primitive root in $\textrm{Z}/(p)^{*}$, where $p=4441$. For the prime number $p=4441$ take $C=1$, $B=5$, $p_0=2$, $p_1=3$ and write $p-1=2^3 \cdot 3 \cdot Q$, where $Q=5\cdot 37$ and $g= 7^{4440/2^3}\cdot 2^{4440/3}=2690 \mathrm{\;mod\;} 4441$. For $q=2$ the element $r= g \cdot q^{4440/Q}= 2690\cdot 2^{4440/185}=3355 \mathrm{\;mod\;} 4441$ is a primitive root.

Table 1. The primitive roots in $\textrm{Z}/(p)^{*}$, $p-1=2^3 \cdot 3 \cdot 5\cdot 37$.

From the formula (2) and the fact that the product of two k-residues is k-residue and the product of k-residue and k-non-residue is k-non-residue one can find a non-prime primitive root following the rule. For each $i\in [0,k]$ find a pair $(g_{i}, g'_{i})$ of elements $g_{i}\in ((\textrm{Z}/(p))^*)^{p_i}$ and $g'_{i} \in (((\textrm{Z}/(p))^*)^{p_i})^{C}$ such that $\forall _{i\in [1,k]} \; g_{i}\cdot g'_{i} = g_{0}\cdot g'_{0} \mathrm{\;mod\;} p$, then the common value is a primitive root. In the Table 1 it was shown how to find a primitive root using proposed rule for $p=4441$. The best know unconditional estimate for the smallest primitive root is due to Burgess [21]. Based on Burgess’s results in [22] Shparlinski constructed a deterministic algorithm which finds a primitive root in a finite field $F_p$ in time $O(p^{\frac{1}{4}+\epsilon })$, for any $\epsilon >0$. V. Shoup in [23], assuming the extended Riemann hypothesis proved that the least primitive root $g_p$ is bounded by a polynomial in $\log p$

$$g_p = O(\omega ^4 (1+\log \omega )^4 (\log p)^2) = O((\log p)^6),$$

where $\omega \equiv \omega (p-1)$ is the number of distinct prime factors of $p-1$. E. Bach conjectured that the least primitive root for prime p is $O((\log p)(\log \log p))$, [24].

Let us define four invertible functions on $(\textrm{Z}/(p))^*$ determined by elements of the group

$$\begin{aligned} \left\{ \begin{array}{l} R(x) = r^{x} \mathrm{\;mod\;} p, \;\;r\in S^{(r)}_{p},\\ E(x) = x^{e} \mathrm{\;mod\;} p, \;\;e\in (\textrm{Z}/\varphi (p))^*, \\ M(x) = m \cdot x \mathrm{\;mod\;} p, \;\; m,\; x \;\in (\textrm{Z}/(p))^*,\\ C_{n}(x) \mathrm{\;mod\;} p,\;\; \gcd (n,p^2--1)=1, \end{array}\right. \end{aligned}$$

(3)

where p is a prime number, $C_{n}(x)$ are Chebyshev polynomials of the first kind, [25]. The exponential function R(x) is determined by the primitive root r of the group $(\textrm{Z}/(p))^*$. The monomial function E(x) is determined by the element e from $(\textrm{Z}/\varphi (p))^*$. Each of the function (3) defines permutation of the set $(\textrm{Z}/(p))^*$. By R, E, M, $C_{n}$ we denote the permutation matrices determined by the functions R(x), E(x), M(x), $C_{n}(x)$. Composition of these functions corresponds to the multiplication of permutation matrices. For example, the composition of two functions $R_1(x)$ and $R_2(x)$, defined by $R_1\circ R_2(x) = R_2(R_1(x))$, corresponds to the multiplication of matrices $R_1 R_2$. We denote by $G^{(r)}_{p}$ the permutation group determined by the exponential functions R(x). By $G^{(e)}_{p}$, $G^{(m)}_{p}$, $G^{(C)}_{p}$ we denote the groups generated by the functions E(x), M(x) and $C_{n}(x)$ respectively. The group $G^{(r)}_{p}$ is non-abelian, and $G^{(e)}_{p}$, $G^{(m)}_{p}$ and $G^{(C)}_{p}$ are abelian subgroups of $G^{(r)}_{p}$ for prime $p>11$.

4 Extensions of Diffie-Hellman Protocol

The first extension of the Diffie-Hellman key exchange protocol utilises the exponential and monomial functions defined in (3).

• The DH $_{r,e}$ algorithm.

  • 1. The users $\textrm{A}$ and $\textrm{B}$ agree the primitive root r from $(\textrm{Z}/(p))^*$ and the element $e \in (\textrm{Z}/\varphi (p))^*$.

  • 2. The user $\textrm{A}$ selects a number a , calculates $r^{a^{e}} \mathrm{\;mod\;} p$ and sends it to $\textrm{B}$.

    The user $\textrm{B}$ selects a number b, calculates $r^{b^{e}} \mathrm{\;mod\;} p$ and sends it to $\textrm{A}$.

  • 3. For given $a^{e}$ and $r^{b^{e}}$ the user $\textrm{A}$ calculates

    $$k_A= (r^{b^{e}})^{a^{e}} = r^{b^{e} a^{e}} = r^{(ba)^{e}} \mathrm{\;mod\;} p.$$

    For given $b^{e}$ and $r^{a^{e}}$ the user $\textrm{B}$ calculates

    $$k_B= (r^{a^{e}})^{b^{e}} = r^{a^{e} b^{e}} = r^{(ab)^{e}} \mathrm{\;mod\;} p.$$

    The common key is $k_{a,b} = r^{(ab)^{e}} \mathrm{\;mod\;} p.$

Let’s illustrate the algorithm with a simple example on the $(\textrm{Z}/(4441))^*$ group. Let $r=21, e=53,a=121, b=61 \in (\textrm{Z}/(4441))^*$ then $a^e = 3535$, $r^{b^e} = 3209$ and $b^e = 972$, $r^{a^e} = 862$ $\mathrm{\;mod\;4441}$. The common key is $k_{A}=3209^{3535} = k_{B} =862^{972} =385$ $\mathrm{\;mod\;4441}$.

The attacker can intercept the numbers r, e and $u = r^{a^{e}} \mathrm{\;mod\;} p$. To decipher the number $a^e \mathrm{\;mod\;} p$ he has to solve the logarithmic equation $\log _{r}(u) = w \mathrm{\;mod\;} \varphi (p)$. Using encryption for multiple exponents $\{e_{i}\}_{i}$ we force the attacker to decipher the secret a, which require to solve set of equations $\log _{r}(u) = w \mathrm{\;mod\;} \varphi (p)$, $w=a^{e_i} \mathrm{\;mod\;} p$ with two unknown parameters w and a.

The next modification of the Diffie-Hellman protocol utilizes composition of the exponential functions from (3).

• The DH $_{2r}$ algorithm.

  • 1. The users $\textrm{A}$ and $\textrm{B}$ agree two primitive roots $r_1$, $r_2$ from $(\textrm{Z}/(p))^*$.

  • 2. The user $\textrm{A}$ selects a number a , calculates $r_1^{r_2^{a}} \mathrm{\;mod\;} p$ and sends it to $\textrm{B}$. The user $\textrm{B}$ selects a number b , calculates $r_1^{r_2^{b}} \mathrm{\;mod\;} p$ and sends it to $\textrm{A}$.

  • 3. For given $r_1^{r_2^{b}} \mathrm{\;mod\;} p$ and $r_2^{a} \mathrm{\;mod\;} p$ the user $\textrm{A}$ calculates

    $$k_A= (r_1^{r_2^{b}})^{r_2^{a}} = r_1^{r_2^{a} r_2^{b}} = r_1^{r_2^{a+b}} \mathrm{\;mod\;} p.$$

    For given $r_1^{r_2^{a}} \mathrm{\;mod\;} p$ and $r_2^{b} \mathrm{\;mod\;} p$ the user $\textrm{B}$ calculates

    $$k_B= (r_1^{r_2^{a}})^{r_2^{b}} = r_1^{r_2^{a} r_2^{b}} = r_1^{r_2^{a+b}} \mathrm{\;mod\;} p.$$

    The common key is $k_{a,b} = r_1^{r_2^{a+b}} \mathrm{\;mod\;} p.$

The following example illustrates how the algorithm works. Let $r_1=44, r_2=94, a=121, b=61 \in (\textrm{Z}/(4441))^*$ then $r_1^{r_2^b} =939$, $r_2^a =3386$ and $r_1^{r_2^a} =2593$, $r_2^b =3031$, $\mathrm{\;mod\;4441}$. The common key is $k_{A}=939^{3386} = k_{B} =2593^{3031} = 450$ $\mathrm{\;mod\;4441}$.

The attacker has the three numbers $r_1$, $r_2$ and $u=r_1^{r_2^{a}} \mathrm{\;mod\;} p$. To decipher the secret a he has to solve the set of two equations for discrete logarithm $\log _{r_1}(u)=w \mathrm{\;mod\;} \varphi (p)$ and $\log _{r_2}(w) = a \mathrm{\;mod\;} \varphi (p)$ for unknown variables w and a.

The third modification of the Diffie-Hellman protocol utilizes the inverse of the exponential function and the monomial functions from (3).

• The DH $_{e,\log }$ algorithm.

  • 1. The users $\textrm{A}$ and $\textrm{B}$ agree the primitive root r from $(\textrm{Z}/(p))^*$ and the element $e\in (\textrm{Z}/\varphi (p))^*$.

  • 2. The user $\textrm{A}$ selects a primitive root $r_a$, calculates $(\log _{r_a}(r))^{e} \mathrm{\;mod\;} \varphi (p)$ and sends it to $\textrm{B}$. The user $\textrm{B}$ selects a primitive root $r_b$, calculates $(\log _{r_b}(r))^{e} \mathrm{\;mod\;} \varphi (p)$ and sends it to $\textrm{A}$.

  • 3. For given $(\log _{r_b}(r))^{e}$ and $(\log _{r}(r_a))^{e}$ the user $\textrm{A}$ calculates

    $$k_A = (\log _{r_b}(r))^{e} (\log _{r}(r_a))^{e} = (\log _{r_b}(r_a))^{e} \mathrm{\;mod\;} \varphi (p).$$

    For given $(\log _{r_a}(r))^{e}$ and $(\log _{r}(r_b))^{e}$ the user $\textrm{B}$ calculates

    $$k_B = (\log _{r_a}(r))^{e} (\log _{r}(r_b))^{e} = (\log _{r_a}(r_b))^{e} \mathrm{\;mod\;} \varphi (p).$$

    Because $(\log _{r_b}(r_a))^{e} = (\log _{r_a}(r_b))^{-e} \mathrm{\;mod\;} \varphi (p)$ the common key is

    $$k(r_a,r_b) = (\log _{r_b}(r_a))^{e} \mathrm{\;mod\;} \varphi (p).$$

As an example we will calculate the common key $k(r_a,r_b)$ on the $(\textrm{Z}/(4441))^*$ group. Let $e=53, r=21, r_a=104, r_b=168 \in (\textrm{Z}/(4441))^*$ then $\log _{r_b}(r)=2527$, $\log _{r}(r_a)=1913$, $\log _{r_a}(r)= 3377$, $\log _{r}(r_b)=1063$ $\mathrm{\;mod\;4440}$. Bacause $k_{A}=2527^{53} \;1913^{53}=2231$ and $k_{B} =3377^{53} \;1063^{53}=3431$ $\mathrm{\;mod\;4440}$ then the common key is $k(r_a,r_b)=2231$ $\mathrm{\;mod\;4440}$.

The attacker has primitive root r, exponent e and $u_a=(\log _{r_a}(r))^{e} \mathrm{\;mod\;} \varphi (p)$. To determine $r_a$ it has to solve the set of equations $u_a = (w_a)^{e} \mathrm{\;mod\;} \varphi (p)$ and $w_a=\log _{r_a}(r) \mathrm{\;mod\;} \varphi (p)$ for two unknown variables $w_a$ and $r_a$.

5 The Key Agreement Protocol on Permutation Group

Let us denote by $V((\textrm{Z}/(p))^*)$ the set of ordered $\varphi (p)$-tuples with elements from the group $(\textrm{Z}/(p))^*$. By $v_0=(1, \ldots , \varphi (p)) \in V((\textrm{Z}/(p))^*)$ we denote the tuple ordered in ascending order. The functions from (3) define the permutation of $V((\textrm{Z}/(p))^*)$

$$\begin{aligned} \left\{ \begin{array}{l} R_{} v_{0} = ( r_{}^{1}, \ldots , r_{}^{p-1} ) \mathrm{\;mod\;} p, \;\; r_{}\in S^{(r)}_{p},\\ E_{} v_{0} = ( 1^{e_{}}, \ldots , (p-1)^{e_{}} ) \mathrm{\;mod\;} p, \;\; e_{} \in (\textrm{Z}/\varphi (p))^*,\\ M_{} v_{0} = ( m_{}\cdot 1, \ldots , m_{} \cdot (p-1)) \mathrm{\;mod\;} p, \;\; m_{} \in (\textrm{Z}/(p))^*,\\ C_{n} v_{0} = ( C_{n}(1), \ldots , C_{n}(p-1) ) \mathrm{\;mod\;} p,\;\; \gcd (n,p^2--1)=1.\\ \end{array} \right. \end{aligned}$$

(4)

The sets of matrices (4) we denote as $S^{(R)}_{p}$, $S^{(E)}_{p}$, $S^{(M)}_{p}$ and $S^{(C)}_{p}$ respectively. From the composition rules of the functions $R_i\circ R_j(x) = r_j^{r_i^{x}} \mathrm{\;mod\;} p$ follows the non-commutativity of the group $G^{(r)}_{p}$ generated by the matrices R, i.e., $R_i R_j \ne R_j R_i \in G^{(r)}_{p}$. From the composition rules of the monomials $E_{i}\circ E_{j}(x)= (x^{e_i})^{e_j} = x^{e_i e_j} \mathrm{\;mod\;} p$, $x\in (\textrm{Z}/(p))^*$, $e_i, e_j \in (\textrm{Z}/\varphi (p))^*$, follows the commutativity of the group $G^{(e)}_{p}$, i.e., $E_i E_j = E_j E_i$. The matrices $M_{i}$, $i\in [1, \varphi (p)]$ generate the finite abelian group $G^{(m)}_{p}$ isomorphic to $(\textrm{Z}/(p))^*$, called the automorphism group of $(\textrm{Z}/(p))^*$, [26]. From the equation $R \circ E(x) = r^{x e} = (r^{e})^{x}\mathrm{\;mod\;} p$ it follows that $R E \in S^{(R)}_{p}$ which implies that $G^{(e)}_{p} \subset G^{(r)}_{p}$. The formula (1) written in terms of matrices has the form

$$ S^{(R)}_{p} = \{ R E_i \, \}_{i=1}^{\varphi (\varphi (p))}.$$

From the equations $E \circ M(x) = M(E(x)) = m x^{e} \mathrm{\;mod\;} p$ and $M \circ E(x) = E(M(x)) = (m x)^{e} \mathrm{\;mod\;} p$ it follows that the abelian groups $G^{(e)}_{p}$ and $G^{(m)}_{p}$ does not commute, i.e., $[G^{(e)}_{p}, G^{(m)}_{p}] \ne 0$. For $n=11$ the group $G^{(r)}_{11}$ is the alternating group of the set of ten elements. For prime number $p>11$ the group $G^{(r)}_{p}$ is the symmetric group $\textrm{Sym}((\textrm{Z}/(p))^*)$ of the set $(\textrm{Z}/(p))^*$. The orders of the groups $G^{(e)}_{p}$ and $G^{(m)}_{p}$ are equal to $\varphi (\varphi (p))$ and $\varphi (p)$ respectively.

The construction of the symmetric cryptographic key on the group $G^{(r)}_{p}$ was motivated by the AAG symmetric key exchange protocol, [3, 4]. The cryptographic key exchange we define by the formula

$$k_{a,b} = a_0 b_{N+1} a_{N+1}^{-1} b_0^{-1},$$

where $a_0, b_{N+1}, a_{N+1}, b_0 \in G^{(r)}_{p}$. The construction of the protocol can be explained on the following example. The users $\textrm{A}$ and $\textrm{B}$ agree the set of elements $S^{(g)}=\{g_{0,1}, g_{1,1}, g_{1,2}, g_{2,1}\}$ from the group $G^{(r)}_{p}$. The user $\textrm{A}$ selects the set $S_{a}= \{a_0, a_1, a_2, a_3\}$, such that $a_3= g_{0,1} g_{1,1} g_{2,1}$, calculates

$$S^{(g)}_{a}= \{ u_{0,1} = a_{0} g_{0,1} a_{1}^{-1}, \begin{array}{l} u_{1,1} = a_{1} g_{1,1} a_{2}^{-1}, \\ u_{1,2} = a_{1} g_{1,2} a_{2}^{-1}, \\ \end{array} u_{2,1} = a_{2} g_{2,1} a_{3}^{-1} \}$$

and sends $S^{(g)}_{a}$ to $\textrm{B}$. Similarly, the user $\textrm{B}$ selects the set $S_{b}=\{b_0, b_1, b_2, b_3\}$, such that $b_3= g_{0,1} g_{1,2} g_{2,1}$, calculates

$$S^{(g)}_{b}= \{ w_{0,1} = b_{0} g_{0,1} b_{1}^{-1}, \begin{array}{l} w_{1,1} = b_{1} g_{1,1} b_{2}^{-1}, \\ w_{1,2} = b_{1} g_{1,2} b_{2}^{-1}, \\ \end{array} w_{2,1} = b_{2} g_{2,1} b_{3}^{-1} \}$$

and sends $S^{(g)}_{b}$ to $\textrm{A}$. The user $\textrm{A}$, using the formula $w_{0,1} w_{1,1} w_{2,1} = b_0 a_3 b_3^{-1}$, calculates the common key $k_{a,b}^{-1}=(b_0 a_3 b_3^{-1} a_0^{-1})^{-1}$. The user $\textrm{B}$, using the formula $u_{0,1} u_{1,2} u_{2,1} = a_0 b_3 a_3^{-1}$, calculates the common key $k_{a,b} = (a_0 b_3 a_3^{-1}) b_0^{-1}$. In this trivial example, the attacker can easily calculate the cryptographic key $k_{a,b}$ because for a given matrices g and u from the sets $S^{(g)}_{}$, $S^{(g)}_{a}$ to determine the unknown variable $a_0$ it’s enough to solve the set of equations

$$ \left\{ \begin{array}{l} a_0 g_{0,1} = u_{0,1} a_1, \\ a_1 g_{1,1} = u_{1,1} a_2, \\ a_1 g_{1,2} = u_{1,2} a_2,\\ a_2 g_{2,1} = u_{2,1} a_3. \end{array} \right. $$

Because we know the formula $a_3= g_{0,1} g_{1,1} g_{2,1}$ the set of equations can be trivially solved. In the proposed algorithm, we hide the last variable in the set $S_{a}$ in order to make it difficult to find the element $a_0$ and the key $k_{a,b}$. To do this, we introduce a graph $G^{\textrm{cipher}}_{2N}$ which nodes are elements of the set

$$S^{(g)}_{x}= \{ u_{0,1} = x_{0} g_{0,1} x_{1}^{-1}, \begin{array}{l} u_{i,1} = x_{i} g_{i,1} x_{i+1}^{-1}, \\ u_{i,2} = x_{i} g_{i,2} x_{i+1}^{-1}, \\ \end{array} u_{N,1} = x_{N} g_{N,1} x_{N+1}^{-1} \}_{i=1}^{N-1},$$

where $x_{i}, g_{i,1}, g_{i,2} \in G^{(r)}_{p}$. Example of the such graph $G^{\textrm{cipher}}_{6}$ build of six nodes is shown on Fig. 1. A path

Fig. 1.

The graph $G^{\textrm{cipher}}_{6}$ for generation of the cryptographic key.

$$p_{a}(u)=(u_{0,1},\ldots , (u_{i,1}||u_{i,2}), \ldots , u_{N,1})$$

from the root node $u_{0,1}$ to the leaf node $u_{N,1}$ defines uniquely the product of matrices

$$\begin{aligned} x_{0} = u_{0,1}\ldots (u_{i,1}||u_{i,2}) \ldots u_{N,1}, \;\; i\in [1,N-1], \end{aligned}$$

(5)

from which follows the form of the $a_{N+1}$ element

$$\begin{aligned} x_{N+1} = g_{0,1}\ldots (g_{i,1}||g_{i,2}) \ldots g_{N,1}, \;\;i\in [1,N-1]. \end{aligned}$$

(6)

The expression $(g_{i,1}||g_{i,2})$ means that in the product (6) either the matrix $g_{i,1}$ or $g_{i,2}$ appears, depending on the selected path in $G^{\textrm{cipher}}_{2N}$. The number of possible values for the matrix $x_{N,1}$ is equal to the number of all possible paths from the root node $u_{0,1}$ to the leaf node $u_{N,1}$. For the graph $G^{\textrm{cipher}}_{2N}$ build of 2N nodes there are $2^{N-1}$ such paths. For sufficiently large number of nodes in $G^{\textrm{cipher}}_{2N}$ one can regard the matrix $x_{N+1}$ as unknown parameter. On Fig. 1, it is shown the graph $G^{\textrm{cipher}}_{6}$ build of six nodes, $N=3$, in which there are four paths between the root and the leaf node. To calculate the key $k_{a,b}$, calculated for two paths $p_{a}(u)$ and $p_{b}(w)$ in the graph $G^{\textrm{cipher}}_{2N}$, the attacker should solve the set of matrix equations

$$\begin{aligned} \left\{ \begin{array}{l} x_{i} \; g_{i-1,1}^{-1} g_{i-1,2} = u_{i-1,1}^{-1} u_{i-1,2} \; x_{i}, \\ x_{i} \; g_{i,1} g_{i,2}^{-1} = u_{i,1} u_{i,2}^{-1} \; x_{i}, \;\;\;i\in [2,N], \end{array} \right. \end{aligned}$$

(7)

where $g_{i,1}, g_{i,2}$, $u_{i,1}, u_{i,2}$ are known parameters. For a given solution $x_{i}=a_{i}$ of (7), using the formulas for $u_{i,1}$, $u_{i,2}$ from $S^{(g)}_{a}$ and $x = a_{i}^{-1} x_{i}$ we obtain the following set of matrix equations

$$\begin{aligned} \left\{ \begin{array}{l} x \; g_{i-1,1}^{-1} g_{i-1,2} = g_{i-1,1}^{-1} g_{i-1,2} \; x \\ x \; g_{i,1} g_{i,2}^{-1} = g_{i,1} g_{i,2}^{-1} \; x, \;\;\;i\in [2,N] \end{array} \right. \end{aligned}$$

(8)

If the solution of (8) is trivial then the solution of (7) is unique. For a non-trivial solution $g_{0}$ of the equations (8), also any matrix $g_{0}^k$ is a solution of (8). The two solutions $a_{i}$ and $a'_{i}$ of (7) are related by the formula

$$a'_{i} = a_{i}\; (g_{0})^k, \;\;\; k\in [1, |g_{0}|],$$

where $g_{0}$ is the solution of (8), i.e., belongs to the centralizer $C_{g_{i,1} g_{i,2}^{-1}}$ of the element $g_{i,1}g_{i,2}^{-1}$ and $|g_{0}|$ is order of the element $g_{0}$. If centralizers $C_{g_{i,1} g_{i,2}^{-1}}$, $i\in [2,N]$, are nontrivial then the solution of the set of equations (7) is not unique. The security of the proposed algorithm depends on the difficulty of finding the proper solution of the equations (7), i.e., depends on the number of solutions of (7). Below we give the detailed description of the algorithm.

• The key agreement algorithm in $G^{(r)}_{p}$.

  • 1. The users $\textrm{A}$ and $\textrm{B}$ agree the set of elements $S^{(g)}=\{g_{0,1}, g_{i,1}, g_{i,2}, g_{N,1}\}_{i=1}^{N-1}$ from the group $G^{(r)}_{p}$ with non trivial centralizers $C_{g_{i,1} g_{i,2}^{-1}}$.

  • 2. The user $\textrm{A}$ selects the set $S_{a}=\{a_i\}_{i=0}^{N+1} \subset G^{(r)}_{p}$ and the path $p_{a}(u)$ in the graph $G^{\textrm{cipher}}_{2N}$, such that formula (5) for $a_{0}$ is satisfied. The user $\textrm{A}$ calculates $S^{(g)}_{a}=\{u_{0,1}, u_{i,1}, u_{i,2}, u_{N,1} \}_{i=1}^{N-1}$ and sends the set $S^{(g)}_{a}$ to the user $\textrm{B}$. Similarly, the user $\textrm{B}$ selects the set $S_{b}=\{ b_i \}_{i=0}^{N+1} \subset G^{(r)}_{p}$, and the path $p_{b}(w)$ in the graph $G^{\textrm{cipher}}_{2N}$, such that formula (5) for $b_{0}$ is satisfied. The user $\textrm{B}$ calculates $S^{(g)}_{b}=\{w_{0,1}, w_{i,1}, w_{i,2}, w_{N,1}\}_{i=1}^{N-1}$ and sends the set $S^{(g)}_{b}$ to $\textrm{A}$.

  • 3. For the selected path $p_{a}(u)$ the user $\textrm{A}$ calculates $k_{a,b}^{-1} = ((b_{0} a_{N+1} b_{N+1}^{-1})a_{0}^{-1})^{-1}$. For the selected $p_{b}(w)$ the user $\textrm{B}$ calculates $k_{a,b} = (a_{0} b_{N+1} a_{N+1}^{-1}) b_{0}^{-1}$. The common key is $k_{a,b}$.

We apply the proposed algorithm to the group $G^{(r)}_{17}$, which is isomorphic to the symmetric group of the set of $(\textrm{Z}/(17))^{*}$. The graph $G^{\textrm{cipher}}_{8}$, $N=4$, is build of eight nodes. There are $2^{3}$ paths in $G^{\textrm{cipher}}_{8}$. The agreed set $S^{(g)}$ and selected secret sets $S_{a}$ and $S_{a}$ are

$$ \begin{array}{l} S^{(g)}= \{ E_{3}, E_{5}, E_{7}, E_{9}, E_{11}, E_{13}, E_{15}, E_{3}\},\\ S_{a}= \{ R_{14}, R_{12}, R_{11}, R_{10}, R_{7}, E_{3} E_{5} E_{11} E_{15} E_{3} \},\\ S_{b}= \{ R_{3}, R_{5}, R_{7}, R_{10}, R_{11}, E_{3}E_{7}E_{9}E_{13}E_{3}\}, \end{array}$$

where the matrices $R_{j}\in G^{(r)}_{17}$ are determined by the primitive roots $j\in S^{(r)}_{17}$ and $E_{i}\in G^{(e)}_{17}$. The paths selected by the users $\textrm{A}$ and $\textrm{B}$ are

$$ \begin{array}{l} p_{a}(u) = (u_{0,1},u_{1,1},u_{2,2},u_{3,2},u_{4,1}),\\ p_{b}(w) = (w_{0,1},w_{1,2},w_{2,1},w_{3,1},w_{4,1}), \end{array}$$

where $u_{i,j}=a_{i}g_{i,j}a_{i+1}^{-1}$ and $w_{i,j}=b_{i}g_{i,j}b_{i+1}^{-1}$, $i\in [0,4]$, $j=1,2$. The common key calculated by communicating parties is given by the formula

$$k_{a,b}= R_{14}(E_{3}E_{7}E_{9}E_{13}E_{3})(E_{3}E_{5}E_{11}E_{15}E_{3})^{-1} R_{3}^{-1},$$

and can be written in matrix form $k_{a,b} v_0= (3, 6, 9, 12, 15, 2, 5, 8, 11, 14, 1, 4, 7, 10, 13, 16)$, where $v_0=(1,\ldots , 16)$.

6 Conclusions

We proposed three cryptographic key exchange protocols of the Diffie-Hellman type based on the exponential and logarithmic functions over the multiplicative group of integers modulo prime number p. The security of the proposed protocols is based on the computational complexity in solving a set of congruence equations containing the discrete logarithm. For the multiplicative group of integer numbers modulo p we constructed the non-commutative group $G^{(r)}_{p}$ of their automorphisms. On the defined group we constructed a non-commutative key exchange protocol similar to the Anshel-Anshel-Goldfeld key exchange scheme. The security of the proposed protocols is based on the difficulty of finding path in a defined cipher graph $G^{\textrm{cipher}}_{2N}$ build of 2N nodes and solution of the set of certain matrix equations in $G^{(r)}_{p}$.