Question

Suppose that instead of using a composite$\mathit{N}\mathbf{=}\mathit{p}\mathit{q}$in the RSA cryptosystem (Figure 1.9), we simply use a prime modulus p . As in RSA, we would have an encryption exponent e, and the encryption of a message $\mathit{m}\mathbf{}\mathit{m}\mathit{o}\mathit{d}\mathbf{}\mathit{p}$would be ${\mathbf{m}}^{\mathbf{e}}\mathbf{mod}\mathbf{}\mathbf{p}\mathbf{.}$Prove that this new cryptosystem is not secure, by giving an efficient algorithm to decrypt: that is, an algorithm that given and $\mathbf{p}\mathbf{,}\mathbf{e}\mathbf{,}$$\mathbf{and}\mathbf{}\mathbf{}{\mathbf{m}}^{\mathbf{e}}\mathbf{mod}\mathbf{}\mathbf{p}$ as input, computes . Justify the correctness and analyze the running time of your decryption algorithm.

Short answer

It can be proved that the given decryption algorithm works correct and the running time of the algorithm is$O\left(n^3\right)$

Step-by-step solution

Step 1:Explain RSA Cryptosystem

RSA cryptosystem is cryptographic algorithm that is asymmetric, that works on both public and private keys. The RSA is based on the larger integer that is difficult to factorize.

Justify the correctness and analyse the running time

Consider the RSA cryptosystem that uses a prime modulus p and encryption exponent e. The message$mmodp$ is encrypted as$m^{e}modp$ .

The requirement for e relatively prime to$\left(p-1\right)$ ,

So the decryption of the message will be as follows,

$d=e^1\mathrm{md}(p-1)$

Apply decryption over the given encrypted message as follows,

$$\begin{gathered} (m^e{)}^d\equiv m^{edmod(p-1)} \\ (m^e{)}^d\equiv mmodp \end{gathered}$$

Therefore, It is proved that the given decryption algorithm works correct and the running time of the algorithm is $O\left(n^3\right)$