Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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.
