RSA algorithm is the most commonly used asymmetric encryption algorithm, which can be used for both encryption and digital signature. The security of RSA is based on the difficulty of large number decomposition. Its public key and private key are functions of a pair of large prime numbers (100 to 200 decimal digits or more). The difficulty of recovering plaintext from public key and ciphertext is equivalent to decomposing the product of two large prime numbers.

We can understand the working principle of RSA through a simple example. For the convenience of calculation. In the following example, only prime numbers P, Q and E with small values are selected. Suppose that user A needs to RSA encrypt the plaintext "key" and then send it to user B, and the process is as follows: design public and private keys (e, n) and (d, n).

Let p=3, q= 1 1, and get n = p× q = 3×11= 33; f(n)=(p- 1)(q- 1)= 2× 10 = 20； Let e=3, (3 and 20 are coprime), then e×d≡ 1 mod f(n), that is, 3×d≡ 1 mod 20. Through trial calculation, we find that the congruence equation of e×d≡ 1 mod f(n) holds when d=7. Therefore, we can make d=7. So we can design a pair of public key and private key. The encryption key (public key) is KU =(e, n) = (3,33), and the decryption key (private key) is KR =(d, n) = (7,33).

Digitalization of English. Digitize plaintext information and group two numbers in each block. Assume that the simple English alphabet code table is arranged alphabetically. Then the plaintext information of the block key is: 1 1, 05,25.

Clear text encryption. User encryption keys (3, 33) encrypt digitized plaintext packet information into ciphertext. From C Me(mod n):

C 1 (ciphertext) ≡M 1 (plaintext) e (mod n) =11≡13mod33;

C2 (ciphertext) ≡M2 (plaintext) E (mod n) = = 26 ≡ 05 3mod33;

C3 (ciphertext) ≡M3 (plaintext) E (mod n) =16 ≡ 25 3mod33;

So the ciphertext is 1 1.26. 16.

Ciphertext decryption. User B receives the ciphertext, and if it is decrypted, it only needs to be calculated, namely:

M 1 (plaintext) ≡C 1 (ciphertext) d (mod n) =11≡17mod33;

M2 (plaintext) ≡C2 (ciphertext) d (mod n) = = 05 ≡ 26 7mod33;

M3 (plaintext) ≡C3 (ciphertext) d (mod n) = = 25 ≡167mod33;

Convert to plaintext 1 1.05.25. According to the above coding table, we converted it into English, and we got the original "key".

Of course, the practical application is much more complicated than this, because the length (modulus length) of the public key and private key of RSA algorithm can only be guaranteed to be 1024 bits or even 2048 bits. Therefore, the selection of P, Q and E, the generation of public key and private key, and the modular exponentiation of encryption and decryption all have certain calculation processes, which need to be completed by computers at high speed.