What about the case when $\mbox{gcd} (m, p q) \neq 1$ in RSA's key generation step?

Question

in key generation, gcd(m, p*q) = 1, so how to solve if it is not equal 1?

gcd(e, φ(n)) = 1

The key generation steps in RSA are as follows:

Randomly choose two different, large prime numbers p and q ○ Calculate the so-called RSA modulus (RSA number) n=p*q
Find the value of Euler's φ-function for n φ(n) = (p-1) * (q-1)
Randomly choose e for the public key such that 1 < e < φ(n), with gcd(e, φ(n)) = 1 (i.e., e and φ(n) coprime)
Calculate the inverse of e via the Extended Euclidean algorithm e * d mod φ(n) ≡ 1
The public key is (e,n), the private key is d

Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. — Community, Oct 21 '22 at 20:51
If you stumble over $1<m<n$ with $\gcd(m,n)>1$, you factored $n$ — Hagen von Eitzen, Oct 21 '22 at 21:41
@Community What I mean is these steps of key generation happens when gcd(m, pq) = 1. So what will happen if this gcd(m, pq) NOT EQUAL TO 1. I need to solve this equation — zain, Oct 22 '22 at 07:56
do you mean $\gcd(e, \varphi(n))$ or $\gcd(m,pq)$. The former is in the key-gen, the later is not! — kelalaka, Oct 22 '22 at 21:17

score 1 · Answer 1 · answered Oct 24 '22 at 19:07

Actually, we don't generate the key RSA like that

Textbook RSA little 101

Select target security $t$, today $t\geq 2048$
Select a public exponent $e$, $e= \{3, 5, 17, 257,65537\}$ are possible candidates;
Generate two uniform random prime $p$ and $q$ where each has 1024-bit ( or $t/2$)
Form the modulus $n = p \cdot q$
Calculate
- Euler's totient function $\phi(n) = (p-1)\cdot(q-1)$
- Actually we use Carmichael Function $\lambda(n) = \text{LCM}(p-1,q-1)$ that can produce shorter private exponent $d$.
Check $\gcd(e,\phi(n))=1$, if not 1 return to step 3.
Find $d$ with Ext-GCD such that $e \cdot d = 1 \bmod \phi(n)$.
Publish the public key as the pair $(n,e)$, the RSA modulus, and the public exponent.
Keep secret the private key $(n,e,d,p,q)$ ( possible more: $n,e,d, p, q, d_p,d_q,d_{inv}$. The values $d_p,d_q,d_{inv}$ are used for CRT based calculation that can speed up modular exponentiation up to 4-time s)

Now encrypt a message $m$ as $c = m^e \bmod n$ and decrypt with $m = c^d \bmod n$.

As you can see, we first select the $e$ so that we can use a smaller public exponent to reduce the cost when using $e$. We cannot control $d$, so it is a good idea to choose $e$ at the beginning. The common choice for $e$ is $\{3, 5, 17, 257 or 65537\}$ and notice that they are the Fermat primes ($2^{2^n}+1$) and they have 2 ones in their binary representation binary that reduces the calculation cost (double for every bit multiplication if 1 with modular repeated squaring) though that is vulnerable to the side channel attack and countermeasure are applied...

The choice of $e=3$ is problematic with Textbook RSA if you encrypt messages smaller than $\sqrt[3]{n}$ since taking a cube-root is easy and it is already called the cube-root attack on RSA. With proper padding, it is not a problem

Your case

If you have $\gcd(e,n) \neq 1$ then turn back to your step 3 and choose a new $e$. Note that finding such $m$ means that one can factor $n$ as long as $e \neq n$ and $e \neq 1$. Since the other two cases are either $p$ or $q$, you have found the factor randomly though you already know them during the generation and the probability of finding them is $2/(n-2)$ if we exclude the $1$ and $n$ from the random selection of $e$.

Note: TextBook RSA as the name suggests should never be used in practice.
- If you want to use RSA to encrypt some small messages use PKCS#1 v1.5 or OAEP padding to mitigate the attacks, see 20 years of RSA.
- If you want to use RSA for the signature, use it with PSS padding.

What about the case when $\mbox{gcd} (m, p q) \neq 1$ in RSA's key generation step?

1 Answers1