91影视

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鈥檚 little theorem can be used. Fermat鈥檚 little theorem is given as, 鈥淚f $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. 鈥淚f $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:

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:

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.