RSA asymmetric encryption algorithm

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 \]

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

\[M=\varphi(N)=(P-1)(Q-1) \]

3. Find one and \(M\) Reciprocal integers \(E\)

\[gcd(E,M)=1 \]

4. 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