There are signatures in real life, and there are signatures on the Internet. Signature has two functions, one is authentication and the other is data integrity verification. Digital signature ensures that the received data has not been tampered with by digest algorithm, and then it is encrypted by the signer's private key, and only the corresponding public key can decrypt it, thus ensuring the identity consistency.
Digital certificate is generated by putting personal information and digital signature together and encrypting them with the private key of CA organization. Of course, a certificate that is not signed by CA itself is called a self-signed certificate. As the basic organization in the Internet cryptographic system, CA organization has quite advanced security protection capabilities. The basic assumption or premise in all certificate systems is that the private key of CA organization will not be stolen. Once something happens to CA J, the whole information chain will no longer be safe.
The generation process of CA certificate is as follows:
Certificates participate in information transfer. The process of encryption and decryption is as follows:
The relationship of coprime: coprime is the common divisor of two integers with only1; 1 and 1 coprime; 13 and 13 are not coprime.
Euler function: indicates any given positive integer n, and among the positive integers less than or equal to n, how many of them have a coprime relationship with n, and its expression is:
Where, if p is a prime number, its expression can be abbreviated as:
Situation 1: φ( 1)= 1
1 and any number are coprime, so φ (1) =1;
Case 2: n is a prime number, φ(n)=n- 1.
Because n is a prime number, it is coprime with all numbers less than itself, so φ (n) = n-1;
Case 3: If n is the power of a prime number, that is, n = p k (p is a prime number and k is an integer greater than or equal to 1), then φ (n) = (p- 1) p (k- 1).
Because p is a prime number, all numbers less than n are prime numbers of n except multiples of p;
Case 4: If n can be decomposed into the product of two coprime integers, n = p 1 × p2, then φ (n) = φ (p1p2) = φ (p1) φ (p2).
Case 5: Based on case 4, if both p 1 and p2 are prime numbers and n=p 1 × p2, then φ (n) = φ (p1p2) = φ (p1) = (p/kloc).
The basic principle of RSA algorithm is the fifth case in Euler function, namely: φ (n) = (p1-1) (p2-1);
If two positive integers A and N are coprime, then the integer B must be found so that ab- 1 can be divisible by N, or the remainder of ab divided by N is 1. At this time, B is called the "modular inverse element" of A, and euler theorem can be used to prove the existence of modular inverse element.
It can be seen that the φ(n)- 1 power of a is the modular inverse of a to module n.
N = pxq = 3233,3233 is written as11001,and a * * * has 12 bits, so this key is 12 bits.
In practical use, the general scene selection length is 1024 bits, and the scene selection length with higher security requirements is 2048 bits. Here, as an example, p=6 1 and Q = 53 are selected.
Because n, p and q are prime numbers, φ (n) = (p-1) (q-1) = 60× 52 = 3120.
Note that φ(n) is used here to replace the coprime of n! Suppose the selected value is 17, that is, e =17;
The modular inverse element means there is an integer d, so the remainder of ed divided by φ(n) is 1. It is expressed as: (ed-1) = φ (n) y->17d = 3120y+1,and a set of solutions is calculated as (2753, 15), that is, d=2753.
Note that 3 1 19 cannot be selected here, otherwise the public key and private key are the same.
Public key: (n, e)=(3233, 2753)
Private key: (n, d)=(3233, 17)
The public key is public, that is to say, m=p*q=3233 is public, so how to find the e- quilt? Using the modular inverse function, we get e, 17d = 3120y+1,and e-opening equals17. At this time, if you want to ask d, you need to know 3 120, which is φ(n), which is φ(3233), which is 330 to put it bluntly.
In general, we can factorize 3233 into 6 1*53, but for very large numbers, human beings can only factorize by enumeration, so the essence of RSA security is that the difficulty of factorizing the largest integer determines the reliability of RSA algorithm. In other words, the more difficult it is to decompose the largest integer, the more reliable the RSA algorithm is.
The largest integer of human decomposition is:
The largest integer decomposed by human beings is 232 decimal digits and 768 binary digits. Factorization larger than this has not been reported, so the longest RSA key cracked at present is 768 bits. Therefore, the 1024-bit key in actual use is basically secure, and the 2048-bit key is absolutely secure.
There is a joke on the Internet:
The composition of public key and private key has been obtained:
Public key: (n, e)=(3233, 2753)
Private key: (n, d)=(3233, 17)
The process of encryption is
The decryption process is as follows:
Where m is the number to be encrypted, c is the output result after encryption, and m
In a word, RSA encryption is the process of encrypting and solving numbers by using modular inverse function. In practical use, because m
Although symmetric encryption is fast, it has a fatal disadvantage, that is, it needs to transmit keys. Although asymmetric encryption can complete encryption and decryption without passing the key, its fatal disadvantage is that it is not fast enough to be used in high-frequency and large-capacity encryption scenarios. So there is a complementary relationship between them. Asymmetric encryption is used when transmitting symmetric encryption keys, and symmetric encryption is used after key transmission, which can complement each other perfectly.