11
$\begingroup$

Generally in RSA we encrypt as $m^e \pmod n$. Will RSA work if we replace the power by normal multiplication? $E = (m \times e) \mod n$ and decryption as $c \times d \mod n$. What will be $d$ disadvantage if it works ?

$\endgroup$
17
$\begingroup$

Suppose an RSA public key is still $(e, N)$ and the private key is still $d$. We have $Enc = (m*e) \text{ mod } N$ and $Dec = (c*d) \text{ mod } N$. The correctness of the scheme depends on the fact that $Dec(Enc(m)) = (m*e*d) \text{ mod } N = m \text{ mod } N$. This implies $e*d = 1 \text{ mod } N$. It is thus trivial to compute the private key given only the public key (i.e. compute $d = e^{-1} \text{ mod } N$). Hence this scheme is completely broken.

Note that this scheme only works if $e$ and $N$ are coprime otherwise no $d$ such that $e*d = 1 \text{ mod } N$ exists.

$\endgroup$
9
$\begingroup$

Assumption: $e$ and $d$ are prime with $N$.

If we use the multiplication instead of the power. We have $d \equiv e^{-1} \pmod N$ :

\begin{align}c \times d &= m &\mod N\\ m \times e \times d &= m &\mod N\\ e \times d &= 1 &\mod N \end{align} (It has to work for any $m$ so we can suppose $m$ prime).

$e$ and $N$ are publicly known, to compute $d$ the inverse of $e$, you just need the Extended Euclidean Algorithm : $e$ is prime with $N$, therefore there exists $u, v$ such as $$e \times u + N \times v = 1$$ by Bezout's Theorem $$e \times u = 1 \pmod N$$ Therefore $u = d = e^{-1}$ which is easily computed.

$\endgroup$

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.