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\bmod{p}$ then find $n$.

This page looks at the basic Diffie-Hellman key exchange system introduced in 1976. The following pages look at improvements and derivatives.

1. Diffie-Hellman Key Exchange - with a large cyclical subgroup
2. MQV Key Agreement - an improvement on Diffie-Hellman
3. ElGamal Encryption
4. Digital Signature Algorithm (DSA)

Basic Diffie-Hellman

The Diffie-Hellman 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 p-1$, and computes her public key $A = g^a \bmod p$, which is sent to party B (Bob). Similarly, Bob chooses a private key $b$ in the range $1 \lt b \lt p-1$, and computes his public key $B = g^b \bmod p$, which is sent to Alice. Both parties can independently compute a shared secret $Z=g^{ab}\bmod p$, as follows

Alice computes $(B)^a = (g^b)^a = g^{ab} \bmod p = Z$

Bob computes $(A)^b = (g^a)^b = g^{ab} \bmod p = Z$

An eavesdropper only sees $p$, $g$, $g^a$ and $g^b$. Given these values, the Diffie-Hellman Problem (DHP) is to find $g^{ab}\bmod 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 Diffie-Hellman method is secure against a passive eavesdropper, but it is not secure against an active "man-in-the-middle" 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.

Diffie-Hellman with a large cyclical subgroup

To prevent "small-group" attacks we make sure that the order $p-1$ of the group has a large prime divisor $q$ and that $g$ is a generator of the unique cyclical subgroup of order $q\bmod p$. The improved Diffie-Hellman 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 Diffie-Hellman method is still susceptible to a man-in-the-middle attack. MQV key agreement is a protocol that attempts to eliminate this problem.

ElGamal Encryption

ElGamal encryption uses the Diffie-Hellman 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,p-2]$. 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 Diffie-Hellman 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

1. Strictly speaking, “$x = y\bmod n$” ('mod' as a binary operation) 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}$” ('mod' as a congruence relation) 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$, $k\in \mathbb{Z}$. 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\bmod n = y\bmod n \quad\Longleftrightarrow\quad x\equiv y\pmod{n}. \]

2. It is conventional when describing Diffie-Hellman 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, 644-654. <pdf-link>

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 22 May 2023.