Speaking of prime numbers, I think everyone is familiar with them. An integer greater than 1 is called a prime number or a prime number other than itself and 1. Such as 2, 3, 5, 7, etc. In the primary school class, we may just remember this concept, but here I talk about some of my own ideas to help you understand that prime numbers are just like the basic elements of numbers. Think about it, a hydrogen molecule is only composed of two hydrogen atoms, so a non-prime number of 6=3*2 means that it is composed of two "3" elements or three "2" elements. Where "3" or "2" is an element that cannot be split again (3 and 2 are prime numbers). So factorizing a non-prime number is like dissecting an object deeply and splitting it into inseparable elements. Mathematicians put forward these mathematical concepts in this way, which is actually a generalization of understanding and thinking about the digital world, similar to the way we understand things around us in our daily life.
Knowing prime numbers, let's look at the relationship between coprime, so what is coprime? In other words, two numbers that do not have the same factor are called coprime relations. We decompose the factor 6 into the product of prime numbers, that is, 6 = 3 * 2 and 35=5*7. If they don't have the same factor, they are said to be 6 and 35 coprime, just as hydrogen molecules are only composed of hydrogen atoms and oxygen molecules are only composed of oxygen atoms, which is a manifestation of coprime.
Therefore, coprime is only the embodiment of whether there is the same factor relationship between a number and a number (common divisor is also called common divisor), and it has nothing to do with whether they are prime numbers or not. Of course, there must be a coprime relationship between prime numbers, because they are all different elements that make up numbers. Mathematically, the coprime of a and b is generally expressed by gcd (a, b) = 1. That is, the greatest common divisor of a and b is 1.
Is the relationship between prime number and coprime easy to understand? But the great mathematician Mr. Euler did not stop there. Mathematicians always ask abstract and general questions, hoping to find rules, such as
If we can find this rule, whether the number is 10 or 100000, we can easily calculate the number of coprime relations according to this criterion. Have you found that numbers are also a world, really a world in a flower! Well, back to the topic, Mr. Euler gave the answer to this question. He replied like this:
First of all, the above problems can be described as a function: \Phi(n)
This is also an old problem for mathematicians. In their view, any problem is the solution of a function. Since this function was put forward by Euler, we call it Euler function. Fortunately, this function is very simple, with only one variable, which is a given positive integer n. The next step is to analyze this n.
When n = 1, this problem is extremely simple:
\Phi(n)= 1
Because 1 has a coprime relationship with any number including itself. 1 itself is a prime number, not a factor of other numbers, because any number multiplied by 1 is itself.
Let's think about it. If n is a prime number and there is no factor in itself, those numbers that are not mutually prime (have a common divisor) must have a factor equal to n after factorization. For example, if n = 3 is a prime number, then 6 = 3 * 2 and 3 are non-coprime, because there is a common divisor 3. Therefore, we find that the numbers that are non-coprime relations with n are all multiples of n, that is, (kn), because kn >；; =n, so the number of coprime with n is less than n, that is,
\Phi(n)=n- 1
Remember the prime numbers we mentioned before? Is the element that constitutes a number, so if n is not a prime number, then it can be factorized into the product of multiple prime numbers. For example, 24 = 6 * 4 = 3 * 8 = 2 * 2 * 3, for example, 6=2*3, the product of these prime factors can also form the following situation:
When we multiply the same prime factor, it is easy to decompose a non-prime number into the product of two coprime relations, such as 24 = 6 * 4 = 2 * 2 * 2 * 3 = 3 * 8.
From a simple point of view, that is, n is divided into the product of two coprime relations:
that is
n=p*q
P and q are coprime, then according to the remainder theorem:
\ Phi \ left(pq \ right)= \ Phi(p)* \ Phi(q)
As for how to prove it? Honestly, I don't know. In my understanding, numbers that are coprime with 24 have such a characteristic: after factorization, their factors do not include 3 and 2 (because 8=2*2*2). So the number that is coprime with 3 is defined as set A, and this number is
\ Phi \ left (3 \ right)
The number that is coprime with 8 is defined as set b, and the number is.
\ Phi \ left (8 \ right)
These two groups of numbers of AB can be combined and multiplied in pairs between groups to form a number that is coprime with 24. Therefore, by multiplying two groups of numbers, we can know the combined number of products and the number of coprime with 24. This proof is not rigorous, but you can remember it first.
It is also necessary to remember that Euler function is a product function, that is, if n consists of multiple prime numbers (n=a*b*c*d ...), then
\ Phi \ left(n \ right)= \ Phi \ left(a \ right)* \ Phi \ left(b \ right) ....
That is, n is a multiple of a prime number, for example, 27 = 3 * 3 * 3 = 3 3 27 is a multiple of 3. Then the numbers that are less than 27 and have non-coprime relations must all be multiples of 3, that is, 1*3, 2 * 3, 3 * 3...9 * 3 * * 9, so 3 3-9 = 3 3-3 2. So to sum up, if p is a prime number, find the reciprocity with p n.
(1*p), (2*p), (3*p), ... (p n-1* p) are eliminated, and the rest will be coprime with p n (remember that p is a prime number), so we draw the following conclusions:
\ phi \ left(p^{k}\right)=p^{k}-p^{k- 1}=p^{k}( 1-\dfrac { 1 } { p })
When k = 1
\Phi \left( p\right)=p- 1
Back to the previous expression when n is a prime number. It can also be seen here that mathematics pursues simplicity and universality, and even complex laws can be transformed into concise and abstract expressions.
For example, 24 = 6 * 4 = 3 * 8 = 2 * 2 * 3, because there is a coprime relationship between prime numbers, and the power of prime numbers is also a coprime relationship.
Let's evolve 24: 24 = 2 3 * 3, that is, merge the same prime number into a power of prime numbers. In this way, 2 3 and 3 are coprime relations (even multiples of prime numbers are coprime relations), so when we find the number of numbers that are coprime with 24, we can apply the previous formula, namely:
\ phi \ left(24 \ right)= \ phi \ left(2^{3}*3\right)=\phi \left(2^3\right)*\phi \left(3\right)=(2^{3}-2^{3- 1})(3- 1)= 8
Because p 1, p2 further induces ... pm, etc. Are prime numbers.
n = p_{ 1}^{k_{ 1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}}
So because Euler function is a product function, then:
\ phi \ left(n \ right)= \ phi \ left(p_{ 1}^{k_{ 1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}}\right)= \ phi \ Left (p _ {1} {k _ {1}} \ right) * \ phi \ left (p _ {2} {k _ {2}} \ right) * ... \ phi \ left (p _)
The conclusion that n is the power of prime number in the previous section
\ phi \ left(p^{k}\right)=p^{k}-p^{k- 1}=p^{k}( 1-\dfrac { 1 } { p })
It can be concluded that:
\φ\ left(p_{ 1}^{k_{ 1}}\right)* \φ\ left(p_{2}^{k_{2}}\right)*...\ phi \ left(p_{m}^{k_{m}}\ right)=p_{ 1}^{k_{ 1}}p_{2}^{k_{2}}...p_{m}^{k_{m}}*( 1-\dfrac { 1 } { p _ { 1 } })*( 1-\ dfrac { 1 } { p _ { 2 } })...( 1-\dfrac { 1}{p_{m}})
rule
\ Phi \ left(n \ right)= n *( 1-\ dfrac { 1 } { p _ { 1 } })*( 1-\ dfrac { 1 } { p _ { 2 } })...( 1-\dfrac { 1}{p_{m}})
At this point, we still calculate 24 prime numbers.
\ phi \ left(24 \ right)= \ phi \ left(2^{3}*3\right)=\phi \left(2^3\right)*\phi \ left(3 \ right)= 24 *( 1-\ dfrac { 1 } { 2 })( 1-\ dfrac { 1 } { 3 })= 8
What I said above actually boils down to the following truth: when we try to find the number of numbers that are less than a certain number range and are coprime with it, it is nothing more than dividing n into prime numbers or non-prime numbers.
Knowing Euler function, we can understand a concept of congruence. Simply put, the remainder of 25 divided by 3 is 1, and the remainder of 1 divided by 2 is 1. Then we say that the congruence of 25 and 1 is modulo 3, which means that the remainder obtained by dividing 25 and 1 by 2 is the same in human terms. In mathematical terms, the process of finding the remainder is called modular operation. That's why the above statement is so awkward. But it doesn't matter, mathematics likes simplicity without verbosity, so we came up with the following expression to express the above statement:
25 \ equiv 1 \ left (mod \ 3 \ right)
in other words
25 \% 3 = 1\%3= 1
Have you noticed? The above expression can also be expressed as follows: the remainder obtained by dividing 25 by 3 is 1. Around the concept of congruence, Master Euler combined with his Euler function to create a euler theorem. Let's see what he found.
In addition, according to the rules of modular operation:
a^{b}\%p = ((a \% p)^{b}) \% p
We can also draw a conclusion.
(a {\ phi \ left (n \ right)}) {k} \ equiv1\ left (modulation \ n \ right)
because
(a^{\phi \left(n\right)})^{k} \ % n=(a^{\phi \left(n\right)}\%n)^{k}\%n= 1^k\%n = 1
Let's give an example: for example
{ \ Phi \ left( 10 \ right)} = { \ Phi \ left(2 * 5 \ right)} = { \ Phi \ left(2 \ right)} * { \ Phi \ left(5 \ right)} =(2- 1)*(5- 1)= 4
So according to euler theorem: Because 9 and 10 are coprime, so
9 {\ phi \ left (10 \ right)} = 9 4 \ equiv1\ left (mod \ 10 \ right).
So (9^4 )^k divided by 10 equals 1.
If a and n are coprime, we must find a number.
Ab \ equiv 1 \ left (mod \ n \ right)
Then B is called the modular inverse of A, which we can prove by euler theorem.
A {\ phi \ left (n \ right)} = 1 \ left (mod \ n \ right)
A {\ phi \ left (n \ right)} = a * a {\ phi \ left (n \ right)-1} \ equiv 1 \ left (mod \ n \ right)
The concept of modular inverse element is of great significance for calculating the appropriate private key when the public key is known.
With these mathematical knowledge, you may feel that these things seem isolated and can't see any function and value, but let's look at how RSA works, and you will find out how these seemingly useless things produce value.
From the expressions of encryption and decryption, it can be seen that there is no difference between public key and private key in mathematical principle. You can use public key encryption and private key decryption, or you can use private key encryption and public key decryption. But for cryptography, the requirements of public key and private key are different.
In addition, it should be noted that the plaintext value here cannot be greater than or equal to n, otherwise the decryption result is not equal to plaintext.
Because the encryption formula is:
x^e mod n = y
The decryption formula is
Y d module n = x
As can be seen from the above expression, there is no difference in mathematical principle between public key and private key. You can use public key encryption and private key decryption, or you can use private key encryption and public key decryption.
So according to:
y=x^e kn
And because y d mod n = X.
y^D \equiv x (mod\ n)
So the essence of the process of deciding whether encryption and decryption are feasible is to prove:
(x^e-kn)^d equal ratio x (mod\ n) (1. 1)
According to binomial theorem
[image upload failed ... (image-ca75c7-1530364603810)]
(x e-kn) d is extended and evolved into
x^ed-m_{ 1}x^{e(d- 1)}kn+m_{2}x^{e(d-2)}(kn)^2...m_{n}(kn)^{d}
You will find that after binomial expansion, only x^ed does not contain n, so to prove the expression of 1. 1, we must combine the modular addition rule (a+b)% p = (a% p+b% p)% p:
x^{ed} \equiv x (mod\ n)
because
ed \ equiv 1(mod \ { \ Phi \ left(n \ right)})
therefore
ed = h { \ Phi \ left(n \ right)})+ 1
So from the evidence,
X {ed} \ equiv x (mod \ n) evolved into proof.
X {h {\ phi \ left (n \ right)} * x \ equiv x (mod \ n)
If x and n are coprime, according to euler theorem,
X {{\ phi \ left (n \ right) }}\equiv 1 (mod\ n)
Based on euler theorem, according to the rules of modular operation, it can be concluded that
X {h {\ phi \ left (n \ right)} \ equiv1(mod \ n)
Still based on the multiplication rule of modular operation, we can draw a conclusion.
X {h {\ phi \ left (n \ right)} x \ equiv x (mod \ n)
The original formula was thus proved.
So if x and n are not coprime, because n=p*q and both p and q are prime numbers, and the factors of n are only p and q, because x and n are not coprime, then we can think that:
x = k _ { 1 } P0 & lt； u & ltq
or
x = k _ { 2 } q 0 & ltk
Please pay attention to the range of k value, and remember that plaintext value must be greater than 0 and less than n value.
Let's define it first.
x=kq
0 & ltk & ltp
Then because p and q are prime numbers, according to K.
For prime numbers, a and n are coprime. If you forget something, you can go back to the front to see the relevant instructions. )
A {n-1} \ equiv1\ left (modulation \ n \ right)
therefore
(kq) {p-1} \ equiv1\ left (mod \ p \ right)
According to Fermat's last theorem, we can deduce the expression.
A {\ phi \ left (n \ right)} \ equiv 1 \ left (mod \ n \ right)
Draw (a conclusion)
((kq) {p-1}) {h * (q-1)} \ equiv1\ left (mod \ p \ right)
namely
(kq) {h * (q-1) (p-1)} \ equiv1\ left (mod \ p \ right)
According to the operation definition of modular operation:
Draw (a conclusion)
(kq)^{h*(q- 1)(p- 1)} = 1+u * p
Where u is an arbitrary integer, then both sides are multiplied by kq.
(kq)^{h*(q- 1)(p- 1)}*kq = 1+u * k * q * p
Because n=pq x=kq, then
(x) {\ phi \ left (n \ right)+1} = x+u*k*n
Or according to the previous modular operation definition.
(x) {h \ phi \ left (n \ right)+1} \ equiv x \ left (mod \ n \ right)
That is, the original formula has been proved.
The security of RSA depends largely on whether the value of n is large enough, so that it is still difficult to find D when the public key E and modulus N are known. According to the aforementioned key pair calculation method:
E*D \equiv 1 (modulus \ m)
If you want to calculate d, you must calculate m, M = (p- 1)(q- 1) and n = p * q. To calculate m, you need to know p and q, that is, you need to separate two big prime numbers from a huge number. The prime factorization of large numbers is considered to be a difficult problem, and even modern computers are very difficult to deal with, so many encryption systems are based on it.
At present, the safest way is to choose rsa-2048. The date is 65438+February 2009 65438+February 2009, and the number of RSA-768 (768 bits, 232 bits) is also decomposed successfully. This incident threatened the security of the current 1024-bit key. Here, 2048 represents the modulus n.
The binary bit of is 2048 bits. However, in the world of general public key, 65535 is generally chosen, which is a more suitable value under the comprehensive consideration of security and computing speed. Because encryption and decryption functions are exponential operations, the execution speed of public key encryption and decryption will be considered as much as possible in engineering. After all, the public key is for external use.
In addition, I remember that the size of rsa encrypted plaintext cannot be greater than n, or its number of bits cannot exceed the limit of n's number of bits. Once the decrypted ciphertext does not match the original data, it is necessary to adopt segmented encryption technology. On the other hand, the value of plaintext cannot be 0 or 1,-1, which leads to the ciphertext being 0, 1 or-1. There is another question. If a piece of illegal data is decrypted with a private key, will it be a decryption failure or a meaningless decryption content? At this time, rsa filling technology is needed. For an understanding of this concept, please refer to the article about RSA padding.
After learning some simple concepts of number theory, such as prime number, Euler function, modular inverse element and so on. We also know the general process of RSA algorithm. Generally speaking, a public-private key pair needs to calculate the following data:
The security of RSA is not only based on the theory that the prime factors of large numbers are difficult to decompose, but also on how to select these values in engineering. By studying rsa, I can further understand the relationship between engineering and theory. Theory determines the feasibility of the direction, and engineering practice should ensure that the theoretical results can be applied to solve problems of a specific scale under limited resources. In the field of encryption algorithm, once there is deviation in engineering practice, it is often easy to produce security loopholes, although the algorithm theory proves to be safe. For example, the selection of p q value in rsa. Here I list several engineering problems that children's shoes that I am interested in can be further discussed: