Factorization of large integers.

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

We can understand how RSA works through a simple example. For ease of calculation. In the following example, only decimal prime numbers p, q, and e are selected. Assume that user A needs to encrypt the plaintext "key" through RSA and pass it to user B. The process is as follows: Design the public and private keys (e, n) and (d) ,n).

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

English digitization. Digitize the plaintext information and group each block of two numbers. It is assumed that the plaintext English alphabetical encoding table is arranged in alphabetical order. Then the plain text information of the grouped key is: 11, 05, 25.

Plain text encryption. The user encryption key (3,33) encrypts the digital plaintext group information into ciphertext.

From C≡Me(mod n):

C1 (ciphertext)≡M1 (plaintext)^e (mod n) == 11≡11^3 mod 33;

C2(ciphertext)≡M2(plaintext)^e (mod n) == 26≡05^3 mod 33;

C3(ciphertext)≡M3(plaintext)^e (mod n) = = 16≡25^3 mod 33;