What is the use of Mersenne Primes in cryptography

Question

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?

Answer 1

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).

Answer 2

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.

Answer 3

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.

Answer 4

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