Suppose $m$ is a huge publicly known prime, like one of GIMPS Mersenne primes. Let $p$ and $q$ be large primes. If I let $n = pqm$ and do RSA $$c = x^{e} \mod n$$ $$x = c^{e'} \mod n$$

Where $ee' = 1 \mod \phi(n)$, is there any weakness introduced that would not have been present had I done RSA with $n = pq$? How about if $m$ was an arbitrary publically known huge prime (not Mersenne).


Yes, the introduction of an extra public prime factor $m$ in the public modulus $n$ would cause a serious security issue: the adversary knowing $e$, $m$, and ciphertext $c=(x^e\bmod n)$, but not $x$, can find $x\bmod m$, which is a leak about plaintext (representative) $x$, that has no equivalent in RSA with all prime factors of $n$ secret.

That is because $$\begin{align} c=(x^e\bmod n)&\implies c\equiv x^e\pmod n\\ &\implies c\equiv x^e\pmod m\;\text{ [since $m$ divides $n$]}\\ &\implies c^{(e^{-1}\bmod(m-1))}\equiv x^{e(e^{-1}\bmod(m-1))}\pmod m\\ &\implies c^{(e^{-1}\bmod(m-1))}\equiv x\pmod m\\ &\implies (x\bmod m)\;=\;(c^{(e^{-1}\bmod(m-1))}\bmod m)\\ \end{align}$$ Note: Obtaining the but-last line makes uses of a corollary of Fermat's little theorem: for any prime $m$, for any integer $x$, for any integer $k\ge0$, it holds that $x^{k(m-1)+1}\equiv x\pmod m$.
For $w>0$, the notation $u\equiv v\pmod w$ means that $w$ divides $u-v$; and the different notation $u=(v\bmod w)$ additionally means that $0\le u<w$.

Leaking $x\bmod m$ makes it such that the increase in ciphertext size caused by the introduction of $m$ comes with no increase in the useful plaintext capacity compared to textbook RSA.

In all the above, it is immaterial whether prime $m$ is a Mersenne prime or not.

Leaking $x\bmod m$ could be a practical issue, or not, depending on context; further, $m$ being one less than a power of two (by definition of a Mersene prime) could make things more damaging than for a haphazard prime $m$, by making the relation between $x$ and $x\bmod m$ simpler at the bit level.

There is another possible issue: it must be that $e$, times the bit size of $x$, remains very large compared to the bit size of $n$, which got increased by the introduction of $m$ (possibly a lot, since we know large Mersenne primes). Otherwise, the system could fall to the $e^\text{th}$ root attack, which simplest form relies on having $x^e<n$, allowing to compute $x$ from $c$ by taking its non-modular $e^\text{th}$ root.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.