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
Mn = 2n − 1.
Mersenne primes are Mersenne numbers that are also prime. A necessary condition for Mn to be prime is for n to be prime. This condition is not sufficient. For example,
211 − 1 = 23 × 89.
But is necessary, for reasons we’ll get into shortly.
If Mn = 2q + 1, then q = Mn−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 M3 = 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 Mn stands a chance of being prime?
If a > 1, then xa − 1 can be factored:
xa − 1 = (x − 1)(xa−1 + xa−2 + … + 1)
If n can be factored into ab, then set x = 2b. This shows that 2ab − 1 has a factor, namely 2b − 1.
In the previous post we said that M127 − 1 has a lot of small factors. We can find some of those factors easily:
M127 − 1 = 2 M126 = 2 (2126 − 1)
and (2126 − 1) is divisible by 2k – 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 2k – 1 is a factor of M126 for k equal to each of these numbers. This is enough to fully factor 2126 − 1 into
3³ × 7² × 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.