1
$\begingroup$

Let $n = P\cdot Q$ be the product of two safe primes $P = 2p+1$ and $Q=2q+1$. Let $g$ be a generator of $C_{p} \subset \mathbb{Z}_n^*$, the multiplicative subgroup of order $p$. In other words, $g^p = 1 \pmod n$. (But $p$ is still secret of course.)

Would it weaken a RSA modulus if $g$ was public? It is easy to compute such a generator when $q$ is known, but seems hard otherwise.

$\endgroup$

1 Answer 1

4
$\begingroup$

Yes, because $g^p\equiv 1\pmod n$ implies that $g^p\equiv 1\pmod Q$. By Fermat's little theorem we also know that $g^{2q}\equiv 1\pmod Q$ and thus $g^{ap+b(2q)}\equiv 1\pmod q$ for all integer $a$ and $b$. If we assume that $P$ and $Q$ are distinct (and also avoid the trivial case $P=5$), then $p$ and $2q$ are coprime so that there exist $a$ and $b$ such that $ap+b(2q)=1$ and hence $g\equiv 1\pmod Q$. In this case $\mathrm{GCD}(g-1,n)=Q$.

If $P=Q$ then $n$ is a perfect square and can be quickly factorised. Likewise if $P=5$ trial division suffices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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