0
$\begingroup$

When we pick $e$: $$e \in \{1,2,3,4,...,\phi(p\cdot q)-1\}$$ where $\gcd(e,\phi(p\cdot q))=1$. Similarly when computing $d$ which is the modular inverse of $e$ (the private key) we use the extended Euclidean algorithm as $$\operatorname{EA}(e, \phi(p\cdot q))$$ so that $$e\cdot d \ \equiv \ 1\pmod{\phi(p\cdot q)}$$ So having a message $X$ why does simultaneously encrypting and decrypting message as $$ {(X^e)}^d \equiv X \pmod{\phi(p\cdot q)}$$ not work, as it should be equivalent to $X^{e\cdot d}$ and $e\cdot d$ are the inverse of each other in the set of $\{1,2,3,4,...,\phi(p\cdot q)-1\}$ so they are supposed to cancel each other which is supposed to be the idea of RSA.

I know that $e\cdot d$ result in plaintext to be decrypted to 0.00 if I follow the normal encryption/decryption process (since I tried it)

Can anyone explain why it does not work as described?

$\endgroup$
  • 1
    $\begingroup$ e is the public key and d is the private key. What is gained by putting them together? Assuming it works, isn't it just turning RSA into a resource-hungry symmetric cipher? $\endgroup$ – Modal Nest Nov 28 '20 at 8:48
  • $\begingroup$ @ModalNest I'm not putting them together I'm just demonstrating the process of encrypting then decryption at the same time. $\endgroup$ – Khaled Gaber Nov 28 '20 at 8:50
  • $\begingroup$ I don't think your question is clear. Although it might just be my lack of mathematical ability. If you are simultaneously encrypting and decrypting, what is the purpose? Why would you do it? Do you mean it should work, but it doesn't, and you are asking mathematically why it doesn't? $\endgroup$ – Modal Nest Nov 28 '20 at 9:06
  • $\begingroup$ @ModalNest yes this is exactly what i mean which is it should decrypt correctly . $\endgroup$ – Khaled Gaber Nov 28 '20 at 9:34
  • $\begingroup$ I've submitted an edit to your question which makes it clear I think (i left the maths alone!). The first answer suggests it wasn't clear to people who understood the maths too. $\endgroup$ – Modal Nest Nov 28 '20 at 10:11
3
$\begingroup$

There are two reasons for not using $\varphi(n)$ during encryption.

The first one is that it doesn't work - you can verify this by looking at the RSA correctness proof. It requires, that the modulus is $n$.

The second one is - if you know $\varphi(n)$ you can efficiently compute $d$ given $e$, and therefore know the private key.

$\endgroup$
  • $\begingroup$ Breaking both functionality and security in one fell swoop. $\endgroup$ – Maeher Nov 28 '20 at 11:16
  • $\begingroup$ @the linked RSA correctness proof is formally incorrect: it applies Fermat's little theorem [ that is $a^{p-1}\equiv1\pmod p$ if $p$ is prime and $a\not\equiv0\pmod p$ ] for $a=m$, without consideration about $m\equiv0\pmod p$, which holds for $q$ messages $m$ (which if both a large and a small proportion of $m$). Also it does not explain why it is safe to assume $p\ne q$, which is necessary to apply the CRT as it does, and for the formula given for $\varphi(n)$ to hold. $\endgroup$ – fgrieu Nov 28 '20 at 13:46

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.