Public key cryptography using discrete logarithms
This is an introduction to a series of pages that look at public key cryptography using the properties of discrete logarithms.
We outline some of the important cryptographic systems that use discrete logarithms; explain the mathematics behind them; and give simple examples, using small numbers to illustrate the mechanics. We assume you understand arithmetic modulo $p$ and maybe a bit of group theory.
All the systems use the properties of the multiplicative group modulo p, denoted $\mathbb{Z}_p^*$, for a prime $p$. Their security ultimately depends on the intractability of solving the Discrete Logarithm Problem (DLP): namely, if you are given $g \in \mathbb{Z}_p^*$ and $g^n\pmod{p}$ then find $n$.
This page looks at the basic DiffieHellman key exchange system introduced in 1976. The following pages look at improvements and derivatives.
 DiffieHellman Key Exchange  with a large cyclical subgroup
 MQV Key Agreement  an improvement on DiffieHellman
 ElGamal Encryption
 Digital Signature Algorithm (DSA)
Basic DiffieHellman
The DiffieHellman Key Exchange method was first published in 1976 [DH76]. It enables two parties independently to compute a shared secret that cannot be obtained by an eavesdropper.
In its most basic form, two parties agree on and make public a large prime $p$ (the modulus) and a generator $g$ that generates the group $\mathbb{Z}_p^*$ or a large subgroup of it. Party A (Alice) chooses a private key $a$ in the range $1 \lt a \lt p1$, and computes her public key $A = g^a \mod p$, which is sent to party B (Bob). Similarly, Bob chooses a private key $b$ in the range $1 \lt b \lt p1$, and computes his public key $B = g^b \mod p$, which is sent to Alice. Both parties can independently compute a shared secret $Z=g^{ab}\mod p$, as follows
Alice computes $(B)^a = (g^b)^a = g^{ab} \mod p = Z$
Bob computes $(A)^b = (g^a)^b = g^{ab} \mod p = Z$
An eavesdropper only sees $p$, $g$, $g^a$ and $g^b$. Given these values, the DiffieHellman Problem (DHP) is to find $g^{ab}\mod p$. This is considered to be an intractable problem for a large enough prime $p$, say, over 1000 bits long. Obviously if we could solve the Discrete Logarithm Problem (DLP) we could also solve the DHP. It is conjectured that the DHP is at least as hard as the DLP.
The basic DiffieHellman method is secure against a passive eavesdropper, but it is not secure against an active "maninthemiddle" attacker. It is also vulnerable if an attacker can trick users into using parameters $(p,g)$ where $g$ only generates a small subgroup. The attacker can then do a brute force search of this much smaller set.
Improvements and derivatives
In the following pages we look at improvements to the basic method.
 DiffieHellman with a large cyclical subgroup
 To prevent "smallgroup" attacks we make sure that the order $p1$ of the group has a large prime divisor $q$ and that $g$ is a generator of the unique cyclical subgroup of order $q\mod p$. The improved DiffieHellman Key Exchange method uses the domain parameters $(p,q,g)$. These parameters are used by all the derivatives we discuss below.
 MQV Key Agreement
 The original DiffieHellman method is still susceptible to a maninthemiddle attack. MQV key agreement is a protocol that attempts to eliminate this problem.
 ElGamal Encryption
 ElGamal encryption uses the DiffieHellman domain parameters $(p,q,g)$ and private/public key pair $(b,B) for recipient party B$ to encrypt a message encoded as an integer $m$ in the range $[1,p2]$. The resulting ciphertext is a pair of integers $(c_1,c_2)$ both about $p$ bits long.
 Digital Signature Algorithm (DSA)
 The Digital Signature Algorithm also uses the DiffieHellman domain parameters $(p,q,g)$ and private/public key pair $(a,A)$ for a signing party A. It creates a digital signature of a message digest as two integers $(r,s)$ both about $q$ bits long. This is very compact compared to the size of the modulus $p$.
Notation

Strictly speaking, “$x = y\mod n$”
means $x$ is equal to the remainder on dividing $y$ by $n$ where $x$
is a unique value in the range $0\leq x\lt n$;
and “$x\equiv y\pmod{n}$”
means $x$ and $y$ have the same remainder when divided by $n$.
In the latter case
$x$ has an infinite range of possible values of the form $x=y+kn$. We are usually interested in the unique value of $x$ in the range
$0\leq x\lt n$ anyway, so we might be a bit sloppy in their use.
These expressions are related by the equivalence $x\mod n = y\mod n \quad\Leftrightarrow\quad x\equiv y\pmod{n}$.
 It is conventional when describing DiffieHellman algorithms to use a notation that is completely different from the notation used in any other publication. Extra credit can be obtained by using the same symbols as others use, but swopping the variables they represent :).
References
 [DH76] W. Diffie and M. Hellman (1976). New directions in cryptography, IEEE Transactions on Information Theory 22, 644654. <pdflink>
Contact us
To comment on this page or to contact us, please send us a message.
This page first published 25 August 2013. Last updated 1 October 2016.