Self-study: The following is the text.

Rsa algorithm

1977, this algorithm was put forward by three young professors of Massachusetts Institute of Technology (MIT), Ronald Rivest, adi shamir and Ryan Aderman, and named RSA algorithm after their surnames Rivest, Chamil and Adlernan. This algorithm makes use of a fact in the field of number theory, that is, although it is very easy to multiply two large prime numbers to generate a composite number, it is very difficult to decompose a composite number into two prime numbers. Complex number decomposition is still an unsolved problem in the field of mathematics, and there is no efficient decomposition method so far. Compared with Diffie-Hellman algorithm, RSA algorithm has obvious advantages, because it does not need the sender and the receiver to participate in the encryption process at the same time, so it is very suitable for the encryption of e-mail systems.

The RSA algorithm can be expressed as follows:

(1) key configuration. Assuming that m is the message to be transmitted, we choose two very large prime numbers p and q, so:

( 12- 1);

Choose a positive integer e to make e and (p- 1) (q- 1) coprime; Here (p- 1) (q- 1) means the multiplication of the two. Then, by using division, we can get d, so:

( 12-2);

Where x mod y is an integer remainder operation, and the result is the remainder after x is divisible by y, such as 5 mod 3 = 2.

So:

(e, n), a public key for encryption, which can be made public; and

(d, n) is a special key used for decryption and must be kept secret.

(2) encryption process. Encrypt plaintext m with (e, n), and the algorithm is:

( 12-3);

C here is the ciphertext encrypted by m.

(3) Decryption process. Decrypt ciphertext c with (d, n), and the algorithm is:

( 12-4);

The resulting m is plaintext corresponding to the password C.

RSA algorithm is very simple to implement. It is said that a British programmer used only three lines of Perl program to realize encryption and decryption.

It is not difficult to prove that RSA algorithm is based on positive integer remainder operation while maintaining the nature of exponential operation. For example:

( 12-5);

( 12-6)。

The core of RSA public key encryption algorithm is Euler function ψ. For a positive integer n, ψ(n) is defined as the number of positive integers less than and coprime with n, for example ψ(6) = 2, because there are two numbers less than and coprime with 6: 1 and 5 * * *; Another example is ψ(7) = 6, because there are 1, 2, 3, 5, 6 * * 6 prime numbers.

Euler discovered a very interesting property of ψ function in more than 300 years BC, that is, for any positive integer m that is less than n and coprime with n, there is always mψ(n) mod n = 1. For example, 5 ψ (6) mod 6 = 52 mod 6 = 25 mod 6 =1. That is to say, under the operation of the remainder of n, the exponent ψ(n) is periodic.

When n is small, it is not difficult to calculate ψ(n), which can be obtained by exhaustive method. But when n is very large, it is very difficult to calculate ψ(n), and the amount of operation is equivalent to judging whether n is a prime number. However, under special circumstances, using two properties of ψ function can greatly reduce the amount of calculation.

Property 1: If p is a prime number, then ψ (p) = (p- 1).

Property 2: If both p and q are prime numbers, then ψ (p q) =ψ (p) ψ (q) = (p-1) (q-1).

RSA algorithm takes these two properties into account to design a public key encryption system. The product n of p and q can be published as a public key, and the factors p and q of n are contained in the private key, which can be used for decryption. If ψ (n) is needed for decryption, the receiver can easily calculate ψ (n) = (p- 1) (q- 1) because he knows the factors p and q, and it is difficult to find ψ(n) if the eavesdropper steals n but doesn't know its factors p and q. At this time, the eavesdropper either forcibly calculates ψ(n) or factorizes n to get P and Q, but we know that it is very difficult to decompose complex numbers in a large number range, so it is difficult for thieves to succeed.

With the understanding of ψ function, let's analyze the working principle of RSA algorithm:

(1) key configuration. Let m be the information to be encrypted, and choose two big prime numbers P and Q, so; Choose a positive integer e to make e and ψ (n) = (p- 1) (q- 1) coprime.

Calculate d by division so that ed mod ψ(n) =, that is, ed = kψ(n)+1, where k is a positive integer.

The public key is (e, n), which does not contain any information about the factors p and q of n.

The private key is (d, n), where d implies the information of factors p and q.

(2) encryption process. Encrypt plaintext m with formula (12-3) to obtain ciphertext c.

(3) Decryption process. Decrypt ciphertext c with (d, n), and the calculation process is as follows:

cd mod n = (me mod n)d mod n

= Medical mode number

= m(kψ(n) + 1) mod n

= (mkψ(n) mod n) (m mod n)

= m

M is plaintext recovered from ciphertext C.

For example, suppose that the plaintext code information we need to encrypt is m = 14, then:

Select e = 3, p = 5 and q =11;

Calculate n = p q = 55, (p- 1) (q- 1) = 40, d = 27；;

It can be verified that: (e d) mod (p-1) (q-1) = 81mod40 =1;

Encryption: c = me mod n =143mod55 = 49;

Decryption: m = cd mod n = 4927 mod 55 = 14.

About RSA algorithm, there are several points that need further explanation:

The reason why (1) requires e to be coprime with (P- 1) (Q- 1) is to ensure that Edmod (P- 1) (Q- 1) has a solution.

(2) In practice, we usually select E first, then find out and determine the prime numbers P and Q, so that they can satisfy the formula (12-3) after calculating D. Commonly used E's are 3 and 65537, both of which are numbers in Fermat series. Fermat's sequence was named after17th century French mathematician Fermat.

(3) The secret cracker mainly decrypts by decomposing N into p q, but there is no way to prove that this is the only way at present, and there may be a more effective way, because factorization is a developing field after all. Since the invention of RSA algorithm, many effective factorization methods have been found, which has reduced the difficulty of decoding RSA algorithm to some extent, but so far there is no way to shake the foundation of RSA algorithm.

(4) In RSA algorithm, the length of n is an important factor to control the reliability of the algorithm. At present, RSA encryption with 129 bits or even 155 bits is barely solvable, but most encryption programs at present adopt RSA algorithm with 23 1, 308 or even 6 16 bits, so RSA encryption is quite safe.

According to experts' calculation, it takes about 8 months to crack the RSA algorithm of 5 12-bit key; And a 768-bit key RSA algorithm can't be cracked before 2004. At present, it is technically impossible to predict how long it will take to crack RSA encryption algorithm with 2048-bit key. American Lotus Company offers a reward of $6,543.80 billion to anyone who can decipher the rs a algorithm of 65,438+0024-bit key in its Domino product. In this sense, the e-commerce system developed according to the SET protocol is absolutely safe.