# Can RSA be used to encrypt p?

In RSA you choose $n=pq$ where $p$ and $q$ are large primes with similar length. Then you choose $e$ that is coprime with $\phi(n)$ and find $d$ that is modular multiplicative inverse of $e$ modulo $\phi(n)$, so $ed \equiv 1 \mod \phi(n)$.

Then $(m^e)^d \mod n = m$ for any natural $m$ less than $n$.

As far as I have researched it, the exponentiation to the power $ed=k\phi(n)+1$ where $k$ is an integer relies on the Euler's theorem that states $a^{\phi(n)} \equiv 1 \mod n$ which is true if $a$ is coprime to $n$.

This leads me to a question, what happens if you choose $p$ as the message? Does RSA handle it in any way? I would like to know both about Textbook RSA and the Deployed RSA.

• The textbook version has two different proofs; one for the coprime case and one for the case where $m$ is a multiple of one of the primes. But I don't recall the proof right now, which is why I write this as a comment rather than an answer. Together those two proofs shows that it works for any $m < n$. However in real usage the case of $m$ being a multiple of one of the primes is so unlikely that in practice it doesn't happen. Sep 25 '17 at 7:36
• There's probably a duplicate somewhere... In any case, proofs based on the Chinese remainder theorem work for all messages. Sep 25 '17 at 8:57
• Is it that the requirement for $p \neq q$ is not only because then factoring is easy, but also that it wouldn't work for the message $p$ (if $p = q$)? Sep 25 '17 at 9:04
• possible duplicate of Does RSA work for any message M? Sep 25 '17 at 11:48

Yes, both textbook and practical RSA can reversibly encrypt $p$.

Textbook RSA can encrypt and decrypt any plaintext in $[0,N)$ as long as $N$ is squarefree (which is hypothetized or at least overwhelmingly likely); and that's including $p$. In a nutshell: Fermat's little theorem implies that $M^{e\,d}-M\equiv 0\pmod p$ for any $M$ and any prime $p$ dividing $N$. It follows that $M^{e\,d}-M\equiv 0\pmod N$ if $N$ is squarefree. Correct decryption for any $M\in[0,N)$ if $N$ is squarefree follows. See more detailed proof there.

However, encrypting $p$ is a particularly terrible use case of textbook RSA, because revealing the ciphertext allows factoring $N$ by computing $\gcd(\operatorname{Enc}(p),N)$ ; that's $p$, as explained there.

Practical RSA has no problem encrypting $p$ for many common parameters: the RSAES-OAEP encryption scheme in PKCS#1 can encipher octet strings of up to $\lceil (\log_{2}N)/8\rceil-2h-2$ octets, where $h$ is the width fo the hash in octets, and that's enough for $p$ when $N$ is larger than $4h+4$ octets and has factors of equal size, which is typically the case. RSAES_PKCS1_V1-5 has a slightly different capacity. When $p$ does not fit (e.g. 2048-bit RSAES-OAEP with SHA-512 has a capacity of 126 octets, which is typicality 2 octets short for $p$), the plaintext can be split into several cryptograms, or there's hybrid encryption.

You can encrypt $p$ using RSA. Since $p$ is co-prime to $q$:

$p^{k \cdotp \phi(n)}$mod $q \equiv p^{k \cdotp (p - 1) \cdotp (q - 1)}$mod $q \equiv p^{k'\cdotp \phi(q)}$mod $q \equiv 1$ mod $q$. (Fermat's little theorem)

Now, $(p^{\phi(n)})^{k} = 1 + u \cdotp q$. We multiply this equation by $p$:

$p \cdotp (p^{\phi(n)})^{k} = p + p \cdotp u \cdotp q = p + u \cdotp n$.

Therefore, $p \cdotp (p^{\phi(n)})^{k} \equiv p^{k \cdotp \phi(n) + 1} \equiv p^{d \cdotp e} \equiv p$ mod $n$

• Could you please explain what is $u$? Sep 25 '17 at 10:54
• It could be any natural number i.e. $u \in \mathbb{N}$ That is basically the definition of mod operator. Sep 25 '17 at 10:58
• More precisely, $u$ is the quotient of the Euclidean division of $p^{k\cdot \varphi(n)}$ by $q$ (the remainder is $1$). Sep 26 '17 at 1:59