9
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – kasperd Sep 25 '17 at 7:36
  • $\begingroup$ There's probably a duplicate somewhere... In any case, proofs based on the Chinese remainder theorem work for all messages. $\endgroup$ – fkraiem Sep 25 '17 at 8:57
  • 2
    $\begingroup$ 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$)? $\endgroup$ – desowin Sep 25 '17 at 9:04
  • 1
    $\begingroup$ possible duplicate of Does RSA work for any message M? $\endgroup$ – mikeazo Sep 25 '17 at 11:48
7
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$

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

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.