Question

Show that if $\mathit{P}\mathbf{=}\mathit{N}\mathit{P}$ then the RSA cryptosystem (Section 1.4.2) can be broken in polynomial time.

Short answer

It is proved that RSA can be broken in polynomial time when $P=NP$.

Step-by-step solution

Explain RSA

One of the earliest public-key cryptography schemes was RSA. The basic concept is to encrypt a message using a public key and decrypt it with a private key. Factoring a semi prime that is a product of two primes appeared to be more difficult than multiplying two primes to figure out what semi prime they make up.

The general concept is to utilize a huge semi prime as your public key and the pair of primes that make up that semi prime as your private key.

Here, Fermat’s little theorem can be used. Fermat’s little theorem is given as, “If $N$ is prime, then $c^N=modN=cmodN$.

Therefore, it requires a method consist of two steps so that the first step can be used for encryption and the second step can be used for decryption.

Consider the following rule to carry out encryption and decryption. “If $N$is a semi-prime, then $N=p.q$, where $p$and $q$ are prime, and $c^{\left(p-1\right)\left(q-1\right)}modN=cmodN$.

Encryption of Message

Encryption:

For a given pair of primes$p$ and q ,$\left(p-1\right)\left(q-1\right)+1$ is a number that is not prime. Therefore, it can be represented using product of two whole numbers $r$ and $s$.To encrypt the message, use the following steps;

Select two large prime numbers$p$ and $q$

Calculate the product $N$.

Select $r$ and $s$ .

Now public key will be $r$and $N$. Message can be encrypted using public key.

Decryption of Message

Decryption:

Assume is a private key. To decrypt the encrypted message, increase the $s^{th}$power $\mathrm{mod}N$. It will generate the plaintext. If $N$is known to attacker then $p$and $q$can be computed easily. Thus, attacker can also find out the value of and decrypt the message.

In present, there is no method to factor large semi primes. If $P=NP$ , then prime factorization can be solved easily.

So, anyone can calculate private keys quickly.

In this way, it is proved that RSA can be broken in polynomial time when $P=NP$.

Hence, the given statement is proved.