Mersenne primes are unsafe

In the previous post I mentioned that a particular Mersenne prime would be unsuitable for cryptography. In fact, all Mersenne primes are unsuitable for cryptography.

A prime number p is called safe" if

p = 2q + 1

where q is also a prime. Safe primes are called safe because p - 1 does not have small factors (other than 2). The factors of p - 1 correspond to subgroups of the group used for encryption, and small groups can be exploited to attack encryption.

Mersenne numbers are numbers of the form

M_n = 2ⁿ - 1.

Mersenne primes are Mersenne numbers that are also prime. A necessary condition for M_n to be prime is for n to be prime. This condition is not sufficient. For example,

2¹¹ - 1 = 23 * 89.

But is necessary, for reasons we'll get into shortly.

If M_n = 2q + 1, then q = M_n-1. But if n is a prime, then n - 1 is not a prime, with one exception: n = 3. So the only Mersenne prime that is a safe prime is M₃ = 7, which is not a particularly large prime. Public key cryptography uses numbers in the thousands of digits, not single digits.

Why does n have to be prime before M_n stands a chance of being prime?

If a > 1, then x^a - 1 can be factored:

x^a - 1 = (x - 1)(x^a-1 + x^a-2 + ... + 1)

If n can be factored into ab, then set x = 2^b. This shows that 2^ab - 1 has a factor, namely 2^b - 1.

In the previous post we said that M₁₂₇ - 1 has a lot of small factors. We can find some of those factors easily:

M₁₂₇ - 1 = 2 M₁₂₆ = 2 (2¹²⁶ - 1)

and (2¹²⁶ - 1) is divisible by 2^k - 1 for every k that divides 126.

The nontrivial factors of 126 are 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, and so 2^k - 1 is a factor of M₁₂₆ for k equal to each of these numbers. This is enough to fully factor 2¹²⁶ - 1 into

3^3 * 7^2 * 19 * 43 * 73 * 127 * 337 * 5419 * 92737 * 649657 * 77158673929

given in the footnote from the previous post. You could easily come up with this factorization using pencil and paper, though it would not be easy to determine by hand that the last factor is a prime number.

The post Mersenne primes are unsafe first appeared on John D. Cook.