# Are relatively prime numbers used in RSA

We know that the Totient function is multiplicative. Which means that when $$p$$ and $$q$$ are relatively prime, then $$\varphi(p q)$$ is equal to $$\varphi(p) \varphi(q)$$. My question is, are only prime numbers used in RSA or can they also be coprime like e.g. 11 and 16? I am asking this because I understand why RSA is multiplicative when p and q are prime but not when they are relatively prime.

• Comments are not for extended discussion; this conversation has been moved to chat. – Ella Rose Jan 31 '19 at 21:39

## 2 Answers

are only prime numbers used in RSA ?

That depends on what is meant by "numbers used in RSA". I'll restrict to a reading of the question where these are $$p$$ and $$q$$, with $$N=p\,q$$ the public modulus in the RSA public key.

That also depends of the defintion of RSA. In the original definition, or when we see $$N=p\,q$$ in an applied RSA cryptography context, we think of $$p$$ and $$q$$ primes, large and randomly seeded, and perhaps deliberately distinct. In this case, $$p$$ and $$q$$ are primes. They are distinct either deliberately or with overwhelming probability, and distinct primes are coprime.

In some modern definitions including PKCS#1v2.2, RSA is extended to $$N$$ the product of $$u\ge2$$ distinct (odd) primes. In this case, when $$u>2$$ and if we nevertheless still write $$N=p\,q$$ (which is highly unusual), then at least one of $$p$$ or $$q$$ is not prime, but still $$p$$ and $$q$$ are coprime.

On the other hand, from a mathematical standpoint, we can define RSA for any positive $$N$$: if $$\gcd(e,\varphi(N))=1$$ then the function $$x\mapsto x^e\bmod N$$ is a bijection of $$\Bbb Z_N^*$$, that is of the subset of $$x$$ in $$\Bbb Z_N$$ with $$\gcd(x,N)=1$$. That function is also a bijection in $$\Bbb Z_N$$ if and only if $$N$$ is square-free (equivalently, if and only if $$p$$ and $$q$$ are coprime in any factorization of $$N$$ as $$N=p\,q$$). Whenever pulling a factor out of $$N$$ is hard, overwhelmingly most elements of $$\Bbb Z_N$$ belong to $$\Bbb Z_N^*$$, thus the distinction $$N$$ square-free or not is immaterial for random $$x$$ (as used in good practice). In that mathematical definition of RSA, we might have $$N=p\,q$$ with $$p$$ and $$q$$ prime or not, coprime or not. For example for $$N=11\cdot16$$ we can write $$N=p\,q$$ with $$p=8$$ and $$q=22$$, neither is prime, and they are not coprime. Yet $$(N,e=3)$$ and $$(N,d=7)$$ are a valid RSA key pair when we restrict to odd integers in $$[0,n)$$ for message and ciphertext (we can, but need not, exclude multiples of $$11$$).

I understand why RSA is multiplicative when $$p$$ and $$q$$ are prime but not when they are relatively prime.

RSA is multiplicative no matter what, in the sense that for all $$x_0$$ and $$x_1$$ it holds that $$E(x_0\cdot x_1\bmod N)=E(x_0)\cdot E(x_1)\bmod N$$ for $$E$$ the function $$x\mapsto x^e\bmod N$$. That's because $$(x_0\cdot x_1)^e\equiv x_0^e\cdot x_1^e\pmod N$$, and that holds for all positive $$e$$ and $$N$$, without consideration of $$N$$ being the product of coprime integers, and from what set $$x_0$$ and $$x_1$$ are taken.

We have a Multi-Prime RSA standard which supports that the public key $$(n,e)$$ can be a product of distinct odd primes where the number of distinct odd primes $$\geq 2$$.

When you have formed your modulus $$n =pq$$ with your coprime numbers $$p,q$$, then you need to check that $$n$$ is a square-free modulus. If it is not square-free then the functionality (decryption) of the RSA will fail. See this answer with examples.

In your example, $$n = 11 \cdot 16 = 11 \cdot 2^4$$ which is not a square-free number. Therefore your modulus will not work.