Are relatively prime numbers used in RSA

Question

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.

Answer 1

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.

Answer 2

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.