Abbreviation description: e is encryption, d is decryption) n, n is a number ($ NUMBER)
1. Randomly select two unequal prime numbers p and q.
Alice chose 6 1 and 53. (In practical application, the bigger these two prime numbers are, the more difficult it is to crack. )
2. calculate the product n of p and q.
n = 6 1×53 = 3233
The length of n is the key length. 3233 is written as binary11001,and a * * * has 12 bits, so this key is 12 bits. In practical application, the RSA key is generally 1024 bits, and it is 2048 bits in important occasions.
3. The n of Euler function φ(n) is called L.
According to the formula φ(n) = (p- 1)(q- 1).
Alice calculated that φ(3233) is equal to 60×52, which is 3 120.
4. Randomly select an integer e, which is the number used for encryption in the public key.
The condition is 1
Alice is between 1 and 3 120, and randomly chooses 17. (In practical application, 65537 is often selected. )
5. Calculate the modulo inverse d of e to φ(n). I.e. the number in the key used for decryption.
The so-called "modular inverse element" means having an integer d, which can divide the remainder of ed by φ(n) 1. ed ≡ 1 (mod φ(n))
Alice found 2753, that is, 17 * 2753 mode 3 120 = 1.
6. encapsulate n and e as public keys and encapsulate n and d as private keys.
In alice's example, n=3233, e= 17 and d=2753, so the public key is (3233, 17) and the private key is (3233, 2753).
In the above story, blob is encrypted with public key to secretly transmit the mobile number 6, that is, 617 mode 3233 = 824. Alice decrypts 824 after receiving it, that is, 824^2753 mod 3233 = 6. In other words, alice successfully received the number of mobile bits used by blob.
Let's review the whole process again:
p= 17，q= 19
n = 17 19 = 323
L = 16 18 = 144
E = 5(E needs to meet the following two conditions: 1
D = 29(D must meet two conditions, 1
Suppose someone needs to pass 123, then after encryption:123 5 mode 323 = 225.
After receiving 225, the receiver decrypts, 225 29 mode 323 = 123.
Looking back at the above key generation steps, six numbers appear in a * * *:
p
q
n
L is φ(n)
e
d
Of these six numbers, two (n and e) are used for public keys, and the other four numbers are not public. The most important thing is D, because N and D constitute the private key. Once d is leaked, it means that the private key is leaked. So, if n and e are known, is it possible to deduce d?
( 1)ed≡ 1 (mod φ(n))。 D can only be calculated by knowing e and φ(n).
(2)φ(n)=(p- 1)(q- 1). Only when we know p and q can we calculate φ(n).
(3)n=pq. Only by decomposing the n factor can we calculate P and Q..
Conclusion: If n can be factorized, D can be calculated, indicating that the private key has been cracked.
However, factorization of large integers is a very difficult thing. At present, no other effective methods have been found except violent cracking. Wikipedia wrote: "The difficulty of factoring 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. If someone finds a fast factorization algorithm, 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 method to attack RSA algorithm in the world. As long as the key length is long enough, information encrypted with RSA cannot be decrypted. "
However, although the security of RSA depends on the factorization of large numbers, it has not been proved theoretically that the difficulty of deciphering RSA is equal to the difficulty of factorization of large numbers. That is, one of RSA's major defects is that it can't grasp its confidentiality in theory. In addition, RSA has the following disadvantages:
A) It is very troublesome to generate keys. Due to the prime number generation technology, it is difficult to achieve one secret at a time.
B) The packet length is too large, and in order to ensure security, n should be at least 600bits, which makes the operation cost very high, especially the speed is slow, which is several orders of magnitude slower than that of symmetric cryptographic algorithm; And with the development of large number decomposition technology, this length is still increasing, which is not conducive to the standardization of data formats. So RSA can only encrypt a small amount of data, and a large amount of data encryption depends on symmetric encryption algorithm.
Encryption and decryption have existed since ancient times. I often watch detective movies. The brave and witty protagonist is troubled by a long list of meaningless numbers. Suddenly, he had a flash of inspiration and dug out a thick book. The first number corresponds to the page number, the second number corresponds to the number of lines, and the third number corresponds to a word in the line. Numbers become a series of very meaningful words:
Eat peanut tofu. Tastes like ham.
This encryption method scrambles the original information according to certain rules. Some kind of coding method is called password. The sender encrypts the information according to the key, while the receiver decrypts the information using the same key. Like a box with a lock. The sender put the message in a box and locked it with a key. The person who receives the message opens it with the same key. Encryption and decryption use the same key, which is called symmetric encryption.
If it is one-on-one, then two people need to exchange a key. One-to-many, such as communication between headquarters and multiple agents, can still use the same set of keys. But in this case, if the opponent steals a key, he will know all the information exchanged. Many results of the allied intelligence war in World War II came from cracking this symmetric encryption key.
In order to be more secure, the headquarters needs to design different keys for each agent. If it is a huge organization like the FBI, I am afraid it is difficult to maintain so many keys. In modern society, everyone's credit card information needs to be encrypted. If you design the key, the bank won't dare to kneel.
The weakness of symmetric encryption is that too many people are given keys. As long as the agents are locked up, it is easy for headquarters to keep the keys. The agent locked the information in the box, and no one could open it unless he went to the headquarters and opened it with a unique key. Only in this way, agents wear a lot of locks every time they go out, which is too easy to be seen through. The boss of the headquarters thought about it and simply made the lock-making technology public. Agents, or anyone else, can use local materials and make locks according to drawings, but they can't make keys according to drawings. There is only one key at headquarters.
The point above is that the technology of lock and key is different. Knowing the lock doesn't mean knowing the key. In this way, the bank can announce the method of "locking" to all users. Each user can use a lock to encrypt his credit card information. Even if someone eavesdrops, don't worry: only banks have keys! This encryption algorithm is called asymmetric encryption. The classical algorithm of asymmetric encryption is RSA algorithm. It comes from the wonderful combination of number theory and computer counting.
1976, two American computer scientists, Whitfield Diffie and Martin Hellman, put forward a brand-new idea that decryption can be completed without directly passing the key. This is called "Diffie-Hellman key exchange algorithm". This algorithm inspired other scientists. It is recognized that encryption and decryption can use different rules, as long as there is a corresponding relationship between the two rules, thus avoiding the direct transmission of keys. This new encryption mode is called "asymmetric encryption algorithm".
1977, three mathematicians, Rivest, Shamir and Adleman, designed an algorithm that can realize asymmetric encryption. This algorithm is named after the three of them, and it is called RSA algorithm. Since then, RSA algorithm has been the most widely used "asymmetric encryption algorithm". It is no exaggeration to say that RSA algorithm exists where there is a computer network.
1. Safe that can "crash" (asymmetric/public key encryption system, asymmetric/public key encryption).
Data encryption and decryption are very similar to door locks. At first, people only thought of the kind of lock that can only "lock" data with the key. If you encrypt data on your own computer, you can of course use the original form of the door lock, which is convenient, quick and easy to use.
But we are now in the age of communication. If both parties want to do secure communication, what should they do? If you use this method, communication is like sending passwords to each other ... and both parties must have keys for encryption and decryption. In other words, they both have the key to the safe. You put the data in, lock it with a key and send it to me. I use the same key to open the safe, then lock my data in the safe and send it to you.
There seems to be nothing wrong with it. However, the biggest problem here is: how do we get the same key in the same safe? It seems that the only way is for us to buy a safe together, and then each of us will take a key and use this safe in the future. But in modern communication society, in most cases, it is difficult to meet, let alone buy a safe together. What should we do?
So, people thought of the method of "hitting the door". I have a safe that I can bump into, or you can buy one yourself. At the beginning of the communication, I opened the safe and sent it to you like this. After you put the data in, you "bump" the safe and send it to me. After the collision, no one can open the safe except me. This is RSA. The public safe is a public key, but I can't open it until I get the private key.
2. Digital signature
This kind of lock looks very good, but there is such a serious problem during transportation: how can you be sure that the opened safe you received is mine? For a wise man, he can do this:
(a) posing as a transport worker. I'm transporting my safe to the other party. The transport worker made such a safe himself and changed it to his when transporting.
(2) After the other party receives the safe, there is no way to know whether it was originally sent by me or replaced by a transport worker. The other party puts the data in and hits the safe.
(c) When the transport workers come back, they use their own keys to open the safe and take away the data. Then copy or forge, make a data, put it in my safe, knock it open and send it to me.
From my point of view, from the other side's point of view, I will feel that there is no problem in this data transmission process. However, the transport workers have successfully obtained the data, and the whole process is still unsafe. The general process is as follows:
What should I do? The essential reason of this problem is that people can't know whether the safe was made by me or the transport workers. It's that simple, let's not make safes, let the authoritative organization make safes, and then carve a number on each safe with special tools. When the other party receives the safe, check the number on the bulletin board of the authority. If it is the same as the number on the safe, I will know that the safe is "mine" and put the data in a safe place. The general process is as follows:
How to make a safe with an unchangeable serial number? This involves another problem in public key system: digital signature.
You know, anyone can do such a thing as lettering. It's really a bit difficult to make a safe that can only be lettered by himself and can't be modified by others. So what should we do? This has actually troubled people for a long time. Until one day, people found out that we don't have to carve the right words on the safe, we just have to carve our own names on the safe. Besides, lettering is a bit troublesome. Why don't we take a piece of paper on it and let people write directly on it? Very simple and easy. Specifically, we embed a piece of paper in the safe, and then each safe produced has its own name, which is signed by the CEO of an authoritative organization. Then, the CEO signs the "bulletin board" of the administration. For example, the CEO is called "learning crisp", so the whole process is almost like this:
The basic principle of this method is that everyone can see whether the words on the safe are signed by the CEO of Su Xue. However, this font is the only font of Su Xue CEO. It is difficult for others to imitate. If we imitate it, we can distinguish it ourselves. If you really can't tell, please ask a handwriting expert to tell. This is not good. This is a digital signature in cryptography.
Although the above signature method is good, there is still a problem that hurts people. Because the appearance of the signature is public, smart people can make a copy of the public signature, build their own safe, and then embed the copied words in it. In this way, smart people can also build a safe with the same signature. A very simple way to solve this problem is to look at the signature on the safe, not only the font itself, but also whether the font is exactly the same as the public font. If it is exactly the same, we can consider that this signature may be photocopied. Even, check whether the font is exactly the same as that on other safes. Because in order to deceive everyone, smart people may not copy the public signature, but copy the signatures on other safes. Although this solution is simple, it is a bit troublesome to verify the signature. The trouble is that I need to compare not only whether the signature on the safe is the same as the public handwriting, but also whether the obtained signature is exactly the same as the public handwriting, even whether it is exactly the same as the signatures on all public safes. Is there a better way?
Of course, people have come up with a better way. That is to say, when the CEO of Su Xue signs it, he should not only sign his own name, but also bring the date of signing or the number of this safe. In this way, the signature on each safe is unique. This signature is the signature of CEO of Su Xue+the time or number written by CEO of Su Xue. In this way, even if someone forges it, they can only forge the used safe. This problem will be completely solved. This process goes something like this:
3 cost problem (key encapsulation mechanism)
To solve the above problems, we should consider the cost ... Although this kind of safe that can "crash" the door is good, the cost of this lock is generally higher than that of ordinary locks, and the production time of the lock will be longer. In cryptography, for the same "solid" lock, the cost of a lock that can "bump" the door is generally several thousand times that of an ordinary lock. At the same time, locks that can "bump" doors can only be installed in small safes. After all, such a complicated lock is very troublesome to install! Ordinary locks can be installed on any safe. If two people want to transmit a lot of data, it is much slower to use a large safe than a bunch of small safes. How to solve this problem? People have come up with another great method: we combine two kinds of locks. You can "crash" into the safe and put the key of an ordinary lock in it. Then build an ordinary safe to lock a lot of data. In this way, we are equivalent to giving a key that can "crash" the safe. After receiving two safes, the other party first opens the small safe with his own key and takes out the key. Then use this key to open the big safe. What's better, because the other party has the key, we don't need to "bump" the safe when we communicate in the future. We can just use the ordinary safe for a certain period of time, which is convenient and fast.
What is the relationship among the following reference digital signatures, digital certificates, SSL and https?
4. Digital signature
When data is transmitted between the browser and the server, it may be replaced by thieves who pretend to be content during the transmission. So how to ensure that the data is sent by the real server and has not been switched, and how to ensure that the transmitted data is not tampered with? In order to solve these two problems, digital signature must be used. Digital signatures are just like signatures in daily life. Once you leave your name on the contract, you will definitely sign it yourself in the legal sense, which is impossible for anyone to copy. What about the digital signature in the computer? Digital signature is used to verify whether the transmitted content is the data sent by the real server and whether the sent data has been tampered with. It does these two things, which is an application scenario of asymmetric encryption. However, he uses the private key for encryption and the paired public key for decryption.
Step 1, the server hashes the message to generate digest information, which is encrypted with a private key, and then generates a signature, and the server sends the signature and the message to the client.
Step 2: After receiving the data, the client extracts the signature and decrypts it with the public key. If Digest2 can be decrypted normally, it can be confirmed that it was sent by the other party.
Step 3: The client extracts the message text and performs the same hashing to obtain Digest 1, and then compares it with the previously decrypted Digist2. If the two are equal, it means that the content has not been tampered with, otherwise the content has been changed. Because as long as the text content changes slightly, it will hash out a completely different summary information.
5. Digital Certificate Authority
Digital certificate (CA) is a kind of recognition certificate issued by an authority to a website. This certificate is recognized by everyone (browser). Why do I need a digital certificate? Is it not safe enough to have a digital signature? In this case, the browser cannot determine whether all real servers are real. Let's give a simple example: manufacturer A installed a lock in your home and gave you the key. As long as the key can open the lock, you can be sure that the key and the lock are paired. If someone changes the key or lock, you can't open the door, and you know it must have been stolen. However, if someone replaces the lock and key with another set, which looks similar on the surface, but the quality is much worse. Although the key and lock are matched, you are not sure whether it is really given to you by manufacturer A. At this time, you can ask the quality inspection department to check whether this set of locks really comes from manufacturer A. The quality inspection department is an authoritative organization, and what he said can be recognized by the public (hehe).
Similarly, if someone (Zhang San) replaces the public key sent by the real server to the browser with his own public key, and Zhang San performs the same steps to hash and digitally sign the text with his own private key, the final result is no problem, but what the browser actually sees is not given by the real server, but is changed from the inside out (public key to private key) by Zhang San. So how do you ensure that the public key you are using now is sent to you by the real server? We use digital certificates to solve this problem. Digital certificates are generally issued by certification bodies and contain the public key of the real server and some other information of the website. The digital certificate authority encrypts it with its own private key and sends it to the browser, and the browser decrypts it with the public key of the digital certificate authority to obtain the public key of the real server. This process is based on the public key obtained by a recognized certificate authority, so it is a secure way.
Common symmetric encryption algorithms are DES, 3DES, AES, RC5 and RC6. Asymmetric encryption algorithm is widely used, such as SSH,
HTTPS, TLS, electronic certificate, electronic signature, electronic identity, etc.
Reference DES/3DES/AES differences