# What is the use of Mersenne Primes in cryptography

There is an international search for Mersenne Primes. The project is huge. But what is the use of Mersenne Primes in cryptography? Do they have any other properties other than the $2^n-1$ form?

• While we use mersenne primes in crypto, we only use medium sized numbers. So the search for larger (mersenne) primes doesn't have crypto applications. – CodesInChaos Oct 22 '14 at 20:39

I can think of two places where we use a Mersenne Prime within cryptogaphy:

• As a modulus within a prime elliptic curve. $2^{521}-1$ is a prime, and so we can define an elliptic curve using $GF(2^{521}-1)$, which is in moderately common use. One reason we use such a modulus (rather than another prime of approximately the same size) is that the special form of the prime makes computing $x \bmod 2^{521}-1$ easy.

• In the (rather obscure) Carter Wegmen Counter mode, we use the fact that $2^{127}-1$ is prime; we use that prime, rather than another value, because it is approximately the correct size, and (as above) computing $x \bmod 2^{127}-1$ is easy.

In both cases, the special property that we take advantage of is that they make computing the modulo operation cheap (by using shifts and adds).

• Some ECC implementation use extension fields with characteristic $2^{127}-1$. One example is snowshoe. – CodesInChaos Oct 22 '14 at 20:47
• Addtion: If $2^n-1$ is prime, it becomes easier to ascertain that the feedback of a LFSR of order $n$ makes it maximum-length: it is then enough to show that the LFSR loops after $2^n-1$ steps, which is easy (otherwise, we would also need to show that it does not loops after $2^n-1\over p$ steps for each prime divisor $p$ of $2^n-1$). $\;$ That observation is not so useful, though: LFSR by themselves are poor keystream generators (we need to combine them, see the ASG). – fgrieu Oct 22 '14 at 21:17

I don't believe there's any particular use for them, to be honest. RSA uses large pseudoprimes, but the prime factors don't have to be Mersenne primes. In fact, given how few Mersenne primes there are, using them would be extremely detrimental to security as they can be easily enumerated.

• @poncho has a great point. Mersennes can be useful when you need a non-secret prime number that is fast to compute modulo on. – Stephen Touset Oct 22 '14 at 19:56

There is a relatively new public key cryptosystem that utilizes Mersenne primes. It exploits the fact that performing modular reduction modulo a Mersenne prime does not modify the hamming weight of the result.

Mersenne-756839 is the name of a cryptosystem built on these ideas that was submitted to NIST's call for post-quantum algorithms.

Here is a quote from the first linked paper which provides a gist of the technique:

Our cryptosystem is based on arithmetic modulo so called Mersenne numbers, i.e., numbers of the form $$p = 2^n − 1$$, where $$n$$ is a prime. These numbers have a simple and extremely useful property: for any number $$x$$ modulo $$p$$, and $$y = 2^z$$, where $$z$$ is a positive integer, $$x · y$$ is a cyclic shift of $$x$$ by $$z$$ positions and thus the Hamming weight of $$x$$ is unchanged under multiplication by powers of $$2$$. Our encryption scheme is based on the simple observation that, given a uniformly random $$n$$-bit string $$R$$, when we consider $$T = F · R + G \mod p$$, where the binary representation of $$F$$ and $$G$$ modulo $$p$$ has low Hamming weight, then $$T$$ appears pseudorandom, i.e., it seems hard to obtain any non-trivial information about $$F$$, $$G$$ from $$R$$, $$T$$.

The public-key is chosen to be the pair $$(R, T)$$, and the secret key is the string $$F$$. The encryption scheme also requires an efficient error correcting code with encoding function $$E : \{0, 1\}^k → \{0, 1\}^n$$ and decoding function $$D : \{0, 1\}^n → \{0, 1\}^k$$. In order to encrypt a message $$m ∈ \{0, 1\}^k$$, the encryption algorithm chooses three random numbers $$A, B_1, B_2$$ of low Hamming weight modulo $$p$$ and then outputs $$C := (C_1, C_2)$$, where $$C_1 = A·R+B_1$$, and $$C_2 = (A·T +B_2)⊕ E(m)$$ where ⊕ denotes the bitwise XOR operation.

Given the private key, one can compute $$C^*_2 := C_1 · F = (A · T + B_2) − A · G − B_2 + B_1 · F$$ . Since $$A, B_1, B_2, F, G$$ have low Hamming weight, the Hamming distance between $$A · T + B_2$$ and $$C^∗_2$$ is expected to be low, and so we get that $$D(C_2 ⊕ C^∗_2)$$ is equal to to $$m$$ with high probability.

• The submission to the NIST PQ Crypto competition is called Mersenne-756839. – CodesInChaos Dec 25 '17 at 18:02

Generalized Mersenne Prime Numbers are used in Elliptical Curve Cryptography and Random Number Generation.

• Two issues with the cited random number paper: a) it doesn't actually talk about Mersenne primes, but numbers of a related form, and b) I don't believe that the random number generators cited are actually cryptographical (that is, indistinguishable from a truly random bit generator). – poncho Oct 22 '14 at 20:32
• @poncho Those RNGs are more or less academic exercises. – torrho Oct 22 '14 at 20:51