# RSA asymmetric encryption algorithm

2020-11-08 18:11:39 HachikoT

# RSA

1977 year , Three mathematicians Rivest、Shamir and Adleman An algorithm is designed , Asymmetric encryption can be achieved . The algorithm is named after the three of them , be called RSA Algorithm .
RSA The security of the algorithm is based on judging whether a number is prime or not , But it is difficult to decompose a number into prime factors .

# RSA Public and private key generation steps

1. Find two large prime numbers $$P$$ and $$Q$$, The bigger the better , Calculation $$P$$ and $$Q$$ The product of the $$N$$

$N=P\times Q$

1. Calculation N The Euler function of $$\varphi(N)$$, Make it worth $$M$$

$M=\varphi(N)=(P-1)(Q-1)$

1. Find one and $$M$$ Reciprocal integers $$E$$

$gcd(E,M)=1$

1. Calculate the whole number $$E$$ model $$M$$ Multiplicative inverse element of $$D$$

$E\times D\equiv 1\,mod\,M$

Final , take $$(N,D)$$ As the private key ,$$(N,E)$$ As a public key

# RSA Encryption and decryption steps

The following is encrypted with the private key , The process of public key decryption ：

• encryption

$X^D\,mod\,N=Y$

• Decrypt

$Y^E\,mod\,N=X$

You can restore the encrypted data here because

\begin{align} (X^D)^E &\equiv X^{D\times E}\,mod\,N\\ &\equiv X^{kM}X\,mod\,N\\ &\equiv X^{k\varphi(N)}X\,mod\,N\\ &\equiv X\,mod\,N\\ \end{align}

Euler's theorem is used in the above derivation ：$$X^{\varphi(N)}\equiv 1\,mod\,N$$, But it takes $$X$$ And $$N$$ Coprime
When $$X$$ Not with $$N$$ Coprime , Only possible $$X=tP$$ perhaps $$X=tQ$$, Here we deduce $$X=tP$$ The situation of , Here you are $$tP$$ And $$Q$$ It must be reciprocal

\begin{align} (tP)^{DE} &\equiv (tP)^{k\varphi(P)\varphi(Q)}(tP)\,mod\,Q\\ &\equiv tP\,mod\,Q\\ \end{align}

Introduction

$(tP)^{DE}=t'Q+tP$

because $$P|t'Q$$ therefore

$(tP)^{DE}=t''PQ+tP$

The above formula is equivalent to

$(tP)^{DE}\equiv tP\,mod\,N$

$(X)^{DE}\equiv X\,mod\,N$

# RSA Security

RSA It can be seen from the generation process of public and private keys that , From you to $$E$$ Deduce $$D$$ Or vice versa , You have to know how to count $$N$$ The Euler function of $$\varphi(N)=(P-1)(Q-1)$$
therefore RSA The security of the algorithm is equivalent to that of large integers $$N$$ Factoring to find large prime numbers $$P$$ and $$Q$$, At present, there is no polynomial solution to prime factor decomposition , So it is possible to ensure that a public-private key pair cannot be cracked within a certain period of time