Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "how to understand the encryption algorithm RSA". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

RSA encryption

We need to preview the knowledge returned to the math teacher first.

Euler function

In number theory, there is a positive integer n, which is less than n and whose number of positive integers is called n, denotes φ (n). For example:

There are 6 coprime numbers 1, 2, 3, 4, 5 and 6 corresponding to φ (7) 7, so φ (7) = 6.

φ (8) 8 corresponds to a number smaller than 8 which is coprime with 8. There are 4 in all, so φ (8) = 4.

φ (9) 9 corresponds to a number smaller than 9 which is coprime with 9. There are 7 numbers in total, so φ (9) = 7.

General formula (P is the prime factor of the number N)

φ (10) = 10 × (1-1max 2) × (1-1max 5) = 4

φ (30) = 30 × (1-1Compact 2) × (1-1Compact 3) × (1-1percusp5) = 8

φ (49) = 49 × (1-1x7) = 42.

If m n is coprime: φ (n * m) = φ (n) * φ (m), if n is a prime, then φ (n) = nmuri 1.

The decomposition prime factor is evaluated as follows: φ (12) = φ (4 * 3) = φ (2 ^ 2 * 3 ^ 1) = (2 ^ 2-2 ^ 1) * (3 ^ 1-3 ^ 0) = 4.

Euler theorem

If two positive integers m and n are coprime, then the φ (n) power of m is equal to 1 for n. M ^ φ (n) n ≡ 1.

Fermat's little theorem

There is a prime number p, and the integer an is not a multiple of p, then there is a ^ (pmur1)% p ≡ 1. Fermat's theorem is a special case of Euler's theorem. Because φ (p) = pMel 1 (any number is coprime with prime number).

Modular inverse element

If two positive integers e and x are prime, then there must be an integer d such that ed-1 is divisible by x, then d is said to be a modular inverse element of e to x. E * d% x ≡ 1, then e * d ≡ k*x+1.

From the above theorem, the following formulas are obtained:

M ^ φ (n) n ≡ 1

M ^ (k * φ (n))% n ≡ 1 multiplied by m

M ^ (k * φ (n) + 1) n ≡ m

E * d ≡ k * Xue1

M ^ e * d% n ≡ m replace step 3 k * φ (n) + 1

M ^ e * d% n ≡ m is a formula for asymmetric encryption that we need. M is plaintext, e and d correspond to public and private keys, respectively. Diffy Kalman secret key exchange split the formula:

M ^ e% n = c encryption

C ^ d% n = m decryption

Where c is the ciphertext encrypted by e, and then the plaintext m can be solved by d. Therefore:

Public key: e, n

Secret key: d, n

Plaintext: M

Ciphertext: C

RSA encryption process

Take two prime numbers p1 and p2

Determine the n value, n=p1 * p2, n value is generally very large, the length is usually 1024 binary bits.

Determine φ (n), φ (n) = (p1-1) * (p2-1)

Determine e value, 1

Determine the d value, eigend% φ (n) = 1

Encryption c = m ^ e% n

Decrypt m = c ^ d% n.

Actual verification:

P1x 3, p2m 7

N=p1 * p2o3 * 7y21

φ (n) = (p1-1) * (p2-1) = 2-6-12

one

E * d% φ (n) = 5 * d% 12x 1, get dumb17.

If you set the plaintext mroom3, then c = m ^ e% n = 3 ^ 5% 2131 12

Decrypt the ciphertext m = c ^ d% n = 12 ^ 17% 213c.

From the above explanation, we know several six parameters used in RSA encryption.

P1p2n φ (n) e d

Of these six digits, two (n and e) are used in the public key, and the other four digits are private. The most important of these is d, because n and d make up the private key, and once d is leaked, it is tantamount to private key disclosure.

So, is it possible to deduce d when n and e are known?

E% φ (n) = 1 (d can be calculated only if e and φ (n) are known.)

φ (n) = (p1-1) * (p2-1) (only when p1 and p2 are known can φ (n) be calculated.)

N=p1*p2 (p and Q can be calculated only by decomposing the n factor.)

Conclusion: if n can be decomposed by factor, d can be calculated, which means that the private key is cracked.

However, the factorization of large integers is a very difficult thing. At present, no other effective methods have been found except for violent cracking. Wikipedia wrote:

The difficulty of factoring a maximal integer determines the reliability of the RSA algorithm. In other words, the more difficult it is to factorize a maximal integer, the more reliable the RSA algorithm is.

If someone finds an algorithm for fast factorization, then the reliability of RSA will be greatly reduced. But the possibility of finding such an algorithm is very small. Today, only short RSA keys can be violently cracked. Until 2008, there was no reliable way to attack RSA algorithm in the world.

As long as the key length is long enough, the information encrypted with RSA cannot actually be deciphered. "

Maybe you don't believe it when you see it here. Can't I crack it if I write a program and try it next to it? For example, 21 you may quickly decompose into 3 × 7, but this number is a little larger, for example, this prime number 2 ^ 57885161-1, it has more than 17 million digits if a traditional computer verifies whether it is a prime number or not.

"how to understand the encryption algorithm RSA" content is introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.