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.

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.