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:

1. Randomly choose two different, large prime numbers p and q ○ Calculate the so-called RSA modulus (RSA number) n=p*q

2. Find the value of Euler's φ-function for n φ(n) = (p-1) * (q-1)

3. Randomly choose e for the public key such that 1 < e < φ(n), with gcd(e, φ(n)) = 1 (i.e., e and φ(n) coprime)

4. Calculate the inverse of e via the Extended Euclidean algorithm e * d mod φ(n) ≡ 1

5. The public key is (e,n), the private key is d

Answer 1

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

Textbook RSA little 101

1. Select target security $t$, today $t\geq 2048$
2. Select a public exponent $e$, $e= \{3, 5, 17, 257,65537\}$ are possible candidates;
3. Generate two uniform random prime $p$ and $q$ where each has 1024-bit ( or $t/2$)
4. Form the modulus $n = p \cdot q$
5. 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$.
6. Check $\gcd(e,\phi(n))=1$, if not 1 return to step 3.
7. Find $d$ with Ext-GCD such that $e \cdot d = 1 \bmod \phi(n)$.
8. Publish the public key as the pair $(n,e)$, the RSA modulus, and the public exponent.
9. 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.