Safe primes and unsafe primes

Secure communications like HTTPS, SSH, SFTP and others rely on cryptographic handshakes like the Diffie-Hellman key exchange to negotiate a shared key.

There are lots of ways to set up a Diffie-Hellman key exchange. The Logjam security vulnerability starts with a flaw in the negotiation process to ensure a relatively weak one is used – finite-field with a small prime – and ends up with a man-in-the-middle attack.

The paper uses the term “safe prime” and thought I would dig a little into exactly what that meant.

Refresher: a given prime p defines the Galois field GF(p). This contains p elements: 0 through p – 1 inclusive. Addition and multiplication are both modulo p. We can start with any one of these elements – call it g, for “generator” – and form the sequence 1, g, g2, g3, and so on, until we eventually come back to 1. Call the “period” (length) of this sequence x. It is a law of mathematics that x always evenly divides p – 1.

The vulnerable Diffie-Hellman key exchange goes something like this, skipping over some details:

  1. Alice has a secret key a; Bob has a secret key b.
  2. Alice and Bob start a conversation where the attacker Eve can hear them – they publicly agree to a particular prime p and a generator g.
  3. Alice calculates ga mod p and shares it; Bob calculates gb mod p and shares it.
  4. Alice calculates (gb)a mod p and Bob calculates (ga)b mod p. These are necessarily equal, and their shared value is used as a secret symmetric key for the rest of the conversation.

For cryptographic reasons, we want g’s period in GF(p) to be reasonably large. If the period is small, that gives Eve a reasonable chance to guess the shared secret, which is even worse than her man-in-the-middle attack from Logjam.

So how do we ensure the period is small? One way to do it (not necessarily a good way to do it) is to arrange for p – 1 to have very few divisors.

Could p – 1 be prime? Well, yes, there are two consecutive primes – namely, (2, 3) – but choosing p = 3 has some other cryptographic drawbacks which outweigh the benefit 🙂

OK, well, then, if p – 1 can’t be prime, can it be a semiprime?

Yes, it can. In fact, it can be of the form 2q where q is also prime. In this case, the prime pair (q, p = 2q + 1) are called a (Sophie Germain prime, safe prime) pair. This is the technical definition of “safe prime.”

To illustrate this, let’s choose a couple of primes and see what their generator cycles look like. In particular, let’s look at the safe prime 59 (59 – 1 = 2 * 29 so the corresponding Sophie Germain prime is 29) and the “unsafe prime” 61 (61 – 1 = 60 is a smooth number with quite a lot of factors.)

For each prime I made a table where the rows are all the possible generators g and the columns are the exponents i in gi. I highlighted the columns x where x is a factor of p – 1

Here’s the safe prime 59:

Generator cycles in GF(59)

And here’s the unsafe prime 61:

Generator cycles in GF(61)

Notice that there are only four periods for 59, in particular x = 1, 2, 29, and 58. These are the four factors of (59 – 1). When choosing a generator, periods 1 and 2 are of course to be avoided; this is easy to do. Period 58 is as good as possible. Period 29 might be accepted as good enough; but if you wanted to go the extra mile, you could detect and correct as follows.

  • Calculate g(p – 1)/2. This will always be -1 or 1.
  • If it’s -1, g has period p – 1, which is as good as it gets.
  • If it’s 1, g has period (p – 1)/2. Use –g instead, which has period p – 1, unless (q, p) = (2, 5), which we reject for the same reasons as (2, 3).

By contrast, there are no fewer than 12 periods for 61, in particular x = 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60. These are the factors of (61 – 1). It is not so easy to decide where the threshold of acceptability lies (30? 12?), and it is not so easy to correct generators with small periods, or even to detect them (other than 0, 1, and p – 1, which are still trivial to avoid.)

Real cryptographic primes are of course much, much bigger than 61, but this serves as an illustration of why safe primes are called “safe”.

One thought on “Safe primes and unsafe primes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s