Then let me explain RSA to you, and try to make it easier for you to understand:

*RSA is an asymmetric encryption system, which means that a public key is used for encryption and a private key is used for decryption. , these two keys are different, this is very, very important.

In fact, RSA is very simple, but beautiful

Process

1. Find two large prime numbers p, q n=p*q=33 N=( p-1)*(q-1)=20

The public key e is generally 3, and the private key d must be calculated through the public key e

e*d=1(mod N) That is to say, the product of e and d modulo N is 1. That is, e and d are inverse elements of each other modulo N

3*7=1 (mod 20) It can be seen that d=7

< p>The encrypted plain text is set to M and the encrypted cipher text is set to c

Encryption process: C=M^e(mod n)

Decryption process: M=C^d (mod n)

Give a specific example if M=2

Encryption process: C=2^3(mod 33)=8(mod 33)

< p>Decryption process: M=8^7(mod 33)=2097152(mod 33)=2(mod 33) It can be seen that the and the original plaintext are the same.

The principle can be understood as M=M^(ed) (mod n)

In this example, e*d=21, which means that the power of M^21 is equal to M

This characteristic of RSA is derived from Fermat’s theorem in number theory

Let’s talk about the details. For example, if the poster encrypts 26 letters, then the plaintext value is from 1 to 26

< p>Let’s take n=33. The value of the encrypted ciphertext is 1 to 33. This is normal

But after decryption, it must be the same as the value of the plaintext, which is 1 to 26

In actual situations, public key e is public and private key d is confidential

For example, A wants to send something to B. B’s public key is public, so A knows it but A does not know B’s private key.

A first encrypts the ciphertext with B's public key. Since B's private key is confidential and only he knows it, security is guaranteed

RSA The biggest security issue is the decomposition of n. As long as n is decomposed into p*q, then N=(p-1)(q-1)

According to e*d=1 (mod N), you can pass e Calculate d, then the private key has been calculated, so there is no security.

But unfortunately, the decomposition of large numbers is a one-way function. If you know p and q, it is easy to calculate n. But knowing n to calculate p, q is quite difficult

I emphasize that n is used for encryption and decryption, and N is used to calculate d if you know e

The poster didn’t say what you want to do, just understand it if you want. So much

If you want to implement this algorithm:

You must know two points:

1.p, the generation of two large prime numbers q, which involves Primeness testing is a chapter in number theory, so I can’t explain it to you

2. Modulo operation, since the encryption and decryption process may take the modulus of dozens of powers of a number, so this must be used A simple algorithm is used to resolve the complexity, which is the modular repeated square algorithm.

If you want to use it in programming, it is too easy

Go to the next dll

It is quite easy to have classes that can be used for RSA directly in Java

If you want to study more deeply, you can send me your email address RSA. I have made a ppt before