How safe is the prime 2²⁵⁵ – 19?

A while back we talked about safe primes and unsafe primes and we gave some small examples of safe primes and unsafe primes.

Recap: A has a secret key a and a public key (ga mod p) with a known prime p and generator g. It is crucial that an attacker not be able to take the discrete logarithm a = logg ga mod p. If they could do that, the attacker would have A‘s private key, without even having to eavesdrop on any communications!

The Pohlig–Hellman algorithm allows an attacker to perform this discrete logarithm. It takes time proportional to the largest prime factor of p – 1. So if p – 1’s prime factors are all small, the attacker can extract private keys easily from public keys. But if there is at least one large prime factor of p – 1, then we’re OK; the larger, the better.

So the unsafest primes are the Fermat primes where p = 2n + 1 for some n. The largest prime factor of p – 1 is only 2!

The safest primes are those of the form p = 2q + 1 where q is a Sophie Germain prime. The largest prime factor of p – 1 is (p – 1) / 2 = q.

How safe is the prime p = 2255 – 19 = 57896044618658097711785492504343953926634992332820282019728792003956564819949? Let’s factor p – 1 and see.

p – 1 = 2255 – 19 – 1 = 2255 – 20 is divisible by 2 – and even by 4 – but not by 8. So we have p – 1 = 22(2253 – 5). So far so good.

What about 2253 – 5? It’s NOT divisible by 5. What about by 3?

With a little bit of thought we can see that it is divisible by 3. 2 = -1 mod 3 and 5 = -1 mod 3, so substituting we have 2253 – 5 = (-1)253 – (-1) = -1 – (-1) = 0 mod 3. (2253 – 5)/3 doesn’t seem to have a nice concise form but we can just write it out in full.

So far we have p – 1 = 22 3 4824670384888174809315457708695329493886249361068356834977399333663047068329. What about 4824670384888174809315457708695329493886249361068356834977399333663047068329?

A quick poke at it with Miller-Rabin shows that it is NOT prime but does not offer a hint as to any factors. So we turn to brute-force trial division and after some time we find that it is divisible by 65147.

So far we have p – 1 = 22 3 65147 74058212732561358302231226437062788676166966415465897661863160754340907. What about 74058212732561358302231226437062788676166966415465897661863160754340907?

Miller-Rabin suggests that this COULD BE prime. In fact, it is prime. Here’s a proof.

The largest prime factor of p – 1 is pretty big. So p is pretty safe. Good.

We also have to take care when choosing a generator not to fall into any of the small cycles of length 2a 3b 65147c with a ∈ {0, 1, 2}, b ∈ {0, 1}, c ∈ {0, 1}.

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