# 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:

And here’s the unsafe prime 61: