Section 5 Applications of the discrete logarithm problem
The discrete logarithm problem can be stated as follows (in multiplicative and in additive groups as well). If \(G\) is a multiplicative group, then we try to find \(x\) for which
\begin{equation*}
g^x=h,\quad g,h\in G.
\end{equation*}
If \(H\) is an additive group, then we look for \(n\) such that
\begin{equation*}
nP=Q,\quad P,Q\in H.
\end{equation*}
Computing discrete logarithms is a computationally difficult problem. So it is natural to use this problem as the basis for cryptographic protocols.
Subsection 5.1 Diffie-Hellman key exchange
In 1976 Diffie and Hellman published a key exchange procedure. The goal of the Diffie-Hellman key exchange algorithm is as follows. Alice and Bob want to share a secret key for use in a cipher. However their only means of communication is insecure. The difficulty of the discrete logarithm problem provides here a possible solution. The first step is for Alice and Bob to agree on a large prime \(p\) and a nonzero \(g\bmod{p}.\) Alice and Bob make the values of \(p\) and \(g\) public.- Alice picks a secret integer \(a\) and computes \(g^a\bmod{p},\)
- Bob picks a secret integer \(b\) and computes \(g^b\bmod{p},\)
- Alice sends \(g^a\) to Bob,
- Bob sends \(g^b\) to Alice,
- Alice and Bob use their secret keys to compute \((g^b)^a\bmod{p}\) and \((g^a)^b\bmod{p},\) respectively. The common value\begin{equation*} g^{ab}\equiv (g^b)^a\equiv (g^a)^b \pmod{p} \end{equation*}is their exchanged key.
The Diffie-Hellman key exchange can be generalized to any number of participants. Let us consider the case with three participants. Alice, Bob and Carol wish to construct a shared key together. They agree on a fixed prime \(p\) and primitive root \(g\bmod{p},\) and choose their own encryption exponents \(a,b\) and \(c.\)
- Alice publishes \(g^a,\) Bob publishes \(g^b\) and Carol makes public \(g^c\) modulo \(p.\)
- Alice uses \(g^b\) and \(g^c\) to compute \(g^{ab}\) and \(g^{ac}\) modulo \(p.\) Bob computes \(g^{bc}\bmod{p}.\)
- Alice sends \(g^{ab}\) to Carol and Carol computes \((g^{ab})^c.\) Alice sends \(g^{ac}\) to Bob and he computes \((g^{ac})^b.\)
- Bob sends \(g^{bc}\) to Alice and she uses it to get \((g^{bc})^a.\)
- The secret key is\begin{equation*} g^{abc}\equiv (g^{bc})^a\equiv (g^{ac})^b\equiv (g^{ab})^c\pmod{p}. \end{equation*}
The Diffie-Hellman key exchange can be used with additive groups as well. Alice and Bob agree on a finite field \(\mathbb{F}\) and an elliptic curve over it and also they fix a point on the elliptic curve, let say \(P.\)
- Alice chooses a secret value \(a\) and computes \([a]P,\)
- Bob chooses a secret value \(b\) and computes \([b]P,\)
- Alice sends \([a]P\) to Bob and he computes \([b]([a]P),\)
- Bob sends \([b]P\) to Alice and she computes \([a]([b]P).\)
- The secret key is\begin{equation*} [ab]P=[b]([a]P)=[a]([b]P). \end{equation*}
Let us consider a multiplicative group example in SageMath.
We also provide an example using elliptic curves.Subsection 5.2 ElGamal cryptosystem
In 1985 Taher ElGamal described a public key cryptosystem based on the discrete logarithm problem. Let us provide some details of the procedure. Bob creates a key and publish it using the following steps.- Bob selects a large prime \(p\) and a primitive root \(g\pmod{p}.\)
- Bob chooses a random element \(a\) such that \(2\leq a\leq p-2. \)
- Bob computes \(g^a\) and the public key is given by\begin{equation*} (p,g,g^a). \end{equation*}
\begin{equation*}
(g^k)^{p-1-a}\equiv g^{-ak}\pmod{p}.
\end{equation*}
From here Bob only needs to determine
\begin{equation*}
( m_i\cdot (g^a)^k)\cdot g^{-ak}\pmod{p}.
\end{equation*}
In SageMath we can follow these steps based on the code given below. Let us see now how to provide an ElGamal cryptosystem using elliptic curves over finite fields. - Bob chooses a finite field \(\mathbb{F}_q\) and an elliptic curve \(E: y^2=x^3+Ax+B\) over this finite field. These are public. The order of the Mordell-Weil group is denoted by \(N.\) The private key is \(a\) and the public key is \((E,P,aP),\) where \(P\) is a point on the elliptic curve.
- Alice fixes a random exponent \(k\) and computes \(kP, m+k(aP),\) where \(m\) is the message represented as a point on the elliptic curve.
- Alice send \(kP\) and \(m+k(aP)\) to Bob.
- Bob determines \(-a(kP)\) and than computes \((m+k(aP))-a(kP)=m.\)
Subsection 5.3 Massey-Omura encryption
Massey-Omura encryption is based on the discrete logarithm problem and it does not use shared keys. The method works in any finite group. We describe it in a simple case first.- Alice and Bob share (public) a prime \(p.\)
- They choose private keys \((e_A,d_A)\) and \((e_B,d_B)\) satisfying\begin{equation*} e_Ad_A\equiv 1\pmod{p-1}\quad\mbox{ and } e_Bd_B\equiv 1\pmod{p-1}. \end{equation*}
- Alice wants to send the message \(m.\) She computes \(m^{e_A}\pmod{p}\) and sends it to Bob.
- Bob computes \((m^{e_A})^{e_B}\pmod{p}\) and sends it back to Alice.
- Alice determines \(((m^{e_A})^{e_B})^{d_A}\pmod{p}\) and sends it to Bob.
- Bob can read the message by computing\begin{equation*} (((m^{e_A})^{e_B})^{d_A})^{d_B}\pmod{p}. \end{equation*}
\begin{equation*}
e_Ad_A=K_A(p-1)+1,\qquad e_Bd_B=K_B(p-1)+1.
\end{equation*}
Therefore
\begin{equation*}
(m^{e_Ad_A})^{e_Bd_B}\equiv (m^{K_A(p-1)+1})^{K_B(p-1)+1}\equiv m^{K_B(p-1)+1}\equiv m\pmod{p}.
\end{equation*}
In SageMath we may compute examples using the following implementation. An other interesting version is based on elliptic curves over finite fields. The are similar, but here we work with points on elliptic curves. - Alice and Bob choose a finite field \(\mathbb{F}_q\) and an elliptic curve \(E\) over this finite field. These are public. Let us denote the order of the group by \(N,\) that is \(N=\# E(\mathbb{F}_q).\)
- They choose private keys \((e_A,d_A)\) and \((e_B,d_B)\) satisfying\begin{equation*} e_Ad_A\equiv 1\pmod{N}\quad\mbox{ and } e_Bd_B\equiv 1\pmod{N}. \end{equation*}
- Alice wants to send the message \(M\in E(\mathbb{F}_q)\) She computes \(eA\cdot M\) and sends it to Bob.
- Bob computes \(e_B(e_A\cdot M)\) and sends it back to Alice.
- Alice determines \(d_A(e_B(e_A\cdot M))\) and sends it to Bob.
- Bob can read the message by computing\begin{equation*} d_B(d_A(e_B(e_A\cdot M))). \end{equation*}
\begin{equation*}
e_Ad_A=K_A N+1,\qquad e_Bd_B=K_B N+1.
\end{equation*}
Thus it follows that
\begin{equation*}
d_Ae_A\cdot M=(K_A N+1)M=K_A\infty + M=M,
\end{equation*}
where we used Lagrange's theorem. We may implement these computations in SageMath as follows. Subsection 5.4 The \(AA_{\beta}\) cryptosystem
Ariffin and Abu proposed a new cryptosystem in 2009 called \(AA_{\beta}\) cryptosystem. It is a Diffie-Hellman type key agreement scheme. The idea behind the cryptosystem is that the discrete logarithm problem modulo 1 is difficult to solve. If we consider real numbers \(x,y\in [0,1],\) then we would like to find an integer \(n\) such that the fractional part of \(nx\) is the same as the fractional part of \(y.\) Let us now provide details of the key agreement. Given two public integers \(a\) and \(b,\) also a public real number is known \(x\in [0,1)\) (as it was pointed out by Ariffin and Abu, real numbers cannot be represented on computers, hence certain approximation is supposed to be used here). In the procedure two matrices are used, these are as follows
\begin{equation*}
A_0=\begin{pmatrix}
1 \amp a\\
1 \amp 0
\end{pmatrix}\quad\mbox{ and }\quad
A_1=\begin{pmatrix}
b \amp 1\\
1 \amp 0
\end{pmatrix}.
\end{equation*}
- Alice chooses a random \(k\) bit binary string \(b_1b_2\ldots b_k.\) She computes the matrix product\begin{equation*} A_{b_k}A_{b_{k-1}}\cdot A_{b_2}A_{b_1}. \end{equation*}The top left entry \(n_A\) of the resulting matrix is her private integer. In a similar way Bob fixes a random \(k\) bit binary string and computes the corresponding matrix product. The top left entry \(n_B\) of this matrix is his private key.
- Alice determines \(r_A=n_A\cdot x\pmod{1}\) and send it to Bob. Similarly, Bob computes \(r_B=n_B\cdot x\pmod{1}\) and sends it to Alice.
- Alice computes \(n_Ar_B\pmod{1}\) and Bob calculates \(n_Br_A\pmod{1},\) so the shared key is\begin{equation*} n_An_Bx\pmod{1}. \end{equation*}
SageMath summary.
- EllipticCurve()
Returns an elliptic curve.
- GF()
Returns a finite field.
- gens()
Returns generators of a given structure.
- gens_orders()
Returns the orders of the generator elements.
- gens_values()
Returns the values of the generator elements.
- order()
Returns the order of a group.
- primitive_root()
Returns a primitive root.
- unit_group()
Returns the group of invertable elements.