(For algorithm enthusiasts, star it to hone your programming skills)
Source: labuladong
The “password” discussed here is not the same concept as the passwords we use daily.
This article discusses the encryption algorithms that primarily address the problems of encryption and decryption in information transmission. It is assumed that the data transmission process is insecure, and all information is being eavesdropped on, so the sender must encrypt the information, and the receiver must know how to decrypt it after receiving the information.
The interesting thing is, if you can let the receiver know how to decrypt, then can’t the eavesdropper also know how to decrypt it?
So cryptography is quite magical. I was amazed when I first saw the Diffie-Hellman key exchange algorithm: two people can share a common secret in front of you by exchanging a few numbers; and you know these numbers and the specific steps of the algorithm they used, but you can never calculate this secret.
Below, we will introduce symmetric encryption algorithms, the Diffie-Hellman key exchange algorithm, asymmetric encryption algorithms, digital signatures, and public key certificates, to see the bumpy road to solving secure transmission issues.
1. Symmetric Encryption
Symmetric encryption, also known as shared-key encryption, uses the same key for both encryption and decryption.
For example, let’s talk about a very simple symmetric encryption method. First, we know that information can be represented as a sequence of 0s and 1s, and we know that the result of XORing two identical bit sequences is 0.
So we can generate a random bit sequence of the same length as the original information as the key, and then XOR it with the original information to generate the ciphertext. Conversely, XORing the ciphertext again with the same key will recover the original information.
This is a simple example, but it is overly simplistic and has many issues. For example, the key length is exactly the same as the original information; if the original information is large, the key will also be large, and generating a large number of truly random bit sequences is computationally expensive.
Of course, there are many more complex and excellent symmetric encryption algorithms that solve these problems, such as the Rijndael algorithm and Triple DES algorithm. They are algorithmically flawless, possessing a huge key space that is basically impossible to brute-force, and the encryption process is relatively fast.
However, the Achilles’ heel of all symmetric encryption algorithms is key distribution. Since encryption and decryption use the same key, the sender must find a way to send the key to the receiver. If the eavesdropper can steal the ciphertext, they can certainly steal the key; thus, even the most flawless algorithm becomes vulnerable.
So, we will introduce two of the most common algorithms to solve the key distribution problem, namely the Diffie-Hellman key exchange algorithm and asymmetric encryption algorithms.
2. Key Exchange Algorithm
The key we refer to is generally a large number, used by the algorithm for encryption and decryption. The problem is that the channel is insecure, and all outgoing data can be intercepted. In other words, is there a way for two people to openly exchange a secret in front of everyone and securely deliver the symmetric key to the receiver?
The Diffie-Hellman key exchange algorithm can achieve this. To be precise, this algorithm does not securely “send” a secret to the other party, but rather allows both parties to “generate” a common secret in their minds through some shared numbers, and this secret cannot be generated by a third-party eavesdropper.
Perhaps this is the legendary telepathy.
The rules of this algorithm are not complicated; you can even try sharing secrets with a friend. I will briefly outline its basic process later. Before that, it is important to clarify one issue: not all operations have inverse operations.
The simplest example is the well-known one-way hash function; given a number<span>a</span> and a hash function<span>f</span>, you can quickly compute<span>f(a)</span>, but if you are given<span>f(a)</span> and<span>f</span>, deriving<span>a</span> is practically impossible. The key exchange algorithm appears so magical because it utilizes this irreversible property.
Next, let’s look at the flow of the key exchange algorithm. According to naming conventions, the two parties preparing to execute the key exchange algorithm are called Alice and Bob, while the bad person trying to intercept their communication is called Hack.
First, Alice and Bob agree on two numbers<span>N</span> and<span>G</span> as generators. Of course, the negotiation process can be eavesdropped on by Hack, so I will place these two numbers in the middle to indicate that all three parties know:
Now Alice and Bob each think of a number, called<span>A</span> and<span>B</span> respectively:
Now Alice calculates a number<span>AG</span> using her number<span>A</span> and<span>G</span>, and sends it to Bob; Bob calculates a number<span>BG</span> using his number<span>B</span> and<span>G</span>, and sends it to Alice:
The situation now is as follows:
Note that, similar to the example of the hash function, knowingAG and G does not allow one to deduce the value of A, and the same applies to BG.
PS: The specific calculation process involves modular arithmetic (mod) and exponentiation; the reason it cannot be reversed is that mathematicians have not yet discovered a fast algorithm for calculating discrete logarithms.
Then, Alice can use<span>BG</span> and her<span>A</span> to perform some operations to obtain a number<span>ABG</span>, and Bob can also use<span>AG</span> and his<span>B</span> to perform some operations to obtain<span>ABG</span>. This number is the shared secret between Alice and Bob.
As for Hack, he can intercept<span>G</span>,<span>AG</span>, and<span>BG</span>, but due to the irreversibility of the calculations, he cannot derive<span>ABG</span><code><span>:</span>
PS: In the specific algorithm, N is used for modular arithmetic, so it is omitted in the diagram.
This is the basic process. As for the specific values of the numbers, there are certain intricacies, and the specific methods can be easily found online; due to space constraints, I will not detail them here.
This algorithm can, under the premise of third-party eavesdropping, compute a secret that others cannot calculate as the key for symmetric encryption algorithms, allowing symmetric encrypted communication to begin.
For this algorithm, Hack has thought of a method to crack it, not by eavesdropping on Alice and Bob’s communication data, but by directly impersonating both Alice and Bob, which is what we call a man-in-the-middle attack:
In this way, neither party can detect that they are sharing secrets with Hack, resulting in Hack being able to decrypt and even modify the data.
Clearly, the key exchange algorithm does not fully resolve the key distribution problem, as it lacks the ability to verify the identity of the other party. Therefore, it is generally necessary to verify the identity of the other party before executing the key exchange algorithm, for example, by using digital signatures.
3. Asymmetric Encryption
The idea behind asymmetric encryption is to simply not secretly transmit the key; instead, I separate the encryption key and decryption key. The public key is used for encryption, and the private key is used for decryption. I only send the public key to the other party, and then they begin sending me encrypted data, which I can decrypt using my private key. As for the eavesdropper, obtaining the public key and encrypted data is useless because only my private key can decrypt it.
You can think of it this way: the private key is the key, while the public key is the lock; you can publicly share the lock and let others lock data and send it to you; however, the key must remain with you for unlocking. The commonly known RSA algorithm is a typical example of an asymmetric encryption algorithm, and its specific implementation is quite complex; I will not detail it here as there are plenty of resources online.
In practical applications, asymmetric encryption is much slower than symmetric encryption, so when transmitting large amounts of data, the public key is generally not used to directly encrypt the data; instead, the symmetric encryption key is encrypted and sent to the other party, after which both parties use symmetric encryption algorithms to transmit data.
It is important to note that, similar to the Diffie-Hellman algorithm, asymmetric encryption algorithms cannot verify the identities of the communicating parties and are still susceptible to man-in-the-middle attacks. For example, if Hack intercepts the public key sent by Bob and impersonates Bob to send his public key to Alice, then Alice, unaware, will encrypt confidential data using Hack’s public key, allowing Hack to decrypt and steal it using his private key.
So, both the Diffie-Hellman algorithm and the RSA asymmetric encryption algorithm can solve the key distribution problem to some extent, but they share the same flaw. What are the differences in their application scenarios?
In simple terms, based on the basic principles of the two algorithms:
If both parties have a symmetric encryption scheme and wish to encrypt communication without letting others obtain the key, then the Diffie-Hellman algorithm can be used to exchange the key.
If you want anyone to be able to encrypt information while only you can decrypt it, then use the RSA asymmetric encryption algorithm and publish the public key.
Next, we will try to solve the problem of authenticating the sender’s identity.
4. Digital Signatures
As mentioned earlier, asymmetric encryption allows the public key to be used for others to encrypt data and send it to you, and only your corresponding private key can decrypt the ciphertext. In fact, the private key can also be used to encrypt data; for the RSA algorithm, data encrypted with the private key can only be decrypted with the public key.
Digital signatures also utilize the properties of asymmetric keys, but they are completely reversed compared to public key encryption: the public key is still published, but you encrypt data with your private key and then publish the encrypted data; this is the digital signature.
You might ask, what’s the use of this? Since the public key can decrypt data encrypted with the private key, isn’t that redundant?
Yes, but the purpose of a digital signature is not to guarantee data confidentiality but to prove your identity, showing that this data was indeed sent by you.
Consider this: if the data encrypted with your private key can only be decrypted by your public key, then if a piece of encrypted data can be decrypted by your public key, doesn’t that prove that the data was published by you (the holder of the private key)?
Of course, the encrypted data is only a signature; the signature should be sent alongside the data. The specific process should be as follows:
1. Bob generates a public and private key pair, then publishes the public key while keeping the private key.
2.He encrypts the data with his private key as a signature and then publishes the data along with the signature.
3.4.Alice receives the data and signature, checks whether this data was sent by Bob, and attempts to decrypt the signature using the public key previously sent by Bob, comparing the result of the decrypted data with the signature. If they match, it indicates that the data has not been tampered with and was indeed sent by Bob.
Why is Alice so sure? After all, both the data and the signature can be tampered with. The reasons are as follows:
1.If someone modifies the data, Alice will decrypt the signature and find a mismatch, thus detecting the anomaly.
2.If someone replaces the signature, Alice can only decrypt a string of garbled text using Bob’s public key, which is clearly inconsistent with the data.
3.Perhaps someone attempts to modify the data and create a signature for the modified data, making it impossible for Alice to detect inconsistencies; however, once the signature is decrypted, it cannot be re-signed because the private key of Bob is not available.
In summary, digital signatures can to some extent authenticate the source of the data. The reason it is said to be to some extent is that this method can still be subject to man-in-the-middle attacks. Once the public key is published, the receiver may receive a fake public key from a man-in-the-middle, leading to incorrect authentication; this problem is unavoidable.
Interestingly, digital signatures are a way to verify the identity of the other party, but the premise is that the identity of the other party must be genuine… This seems to fall into a chicken-or-egg dilemma, to determine the identity of the other party, you must have a trusted source; otherwise, no amount of processes will truly solve the problem.
5. Public Key Certificates
A certificate is essentially a public key + signature issued by a third-party certification authority.Introducing a trusted third party is a feasible solution to end the trust cycle.
The certificate authentication process is roughly as follows:
1.Bob goes to a trusted certification authority to verify his true identity and provides his public key.
2.Alice wants to communicate with Bob, first requests Bob’s public key from the certification authority, which sends a certificate (Bob’s public key and the authority’s signature on that public key) to Alice.
3.Alice checks the signature to confirm that the public key was indeed sent by the certification authority and has not been tampered with.
4.Alice encrypts data with this public key and starts communication with Bob.
PS: The above image is for illustration; in practice, certificates only need to be installed once and do not require repeated requests to the certification authority; usually, the server sends the certificate directly to the client instead of the certification authority.
Some may ask, if Alice wants to determine the validity of a certificate through a digital signature, she must have the (certification) public key of the authority; doesn’t this return to the previous trust cycle?
All legitimate browsers we install have pre-installed certificates from legitimate certification authorities (including their public keys) to confirm the authority’s identity, which is why certificate authentication is trustworthy.
During Bob’s process of providing the public key to the authority, he must provide a lot of personal information for identity verification, which is relatively strict, so it is considered reliable.
With Bob’s trusted public key, the communication between Alice and Bob is completely secure, protected by the encryption algorithm.
In summary, each side of this triangle is relatively reliable, making it costly for hackers to attempt an attack.
Most legitimate websites now use HTTPS, which adds an SSL/TLS security layer between the HTTP protocol and the TCP protocol. After your browser and the website server complete the TCP handshake, the SSL protocol layer will also perform an SSL handshake to exchange security parameters, which includes the website’s certificate for browser verification of the site’s identity. Once SSL security layer validation is complete, all upper-layer HTTP protocol content will be encrypted, ensuring safe data transmission.
As a result, traditional man-in-the-middle attacks have almost no room for survival; attack methods can only shift from technical flaws to deception. In fact, deception can be even more effective, as I have found many download sites online that publish browsers with not only messy navigation and bookmarks but also some unregulated certification authority certificates.Anyone can apply for a certificate, and these unregulated certificates can pose security risks.
6. Conclusion
Symmetric encryption algorithms use the same key for encryption and decryption, making them difficult to crack and fast in encryption speed, but they have key distribution problems.
The Diffie-Hellman key exchange algorithm allows both parties to “generate” a common secret, partially solving the key distribution problem, but it cannot verify the identities of the communicating parties, making it susceptible to man-in-the-middle attacks.
Asymmetric encryption algorithms generate a pair of keys, separating the tasks of encryption and decryption.
The RSA algorithm, as a classic asymmetric encryption algorithm, has two uses: if used for encryption, it can publish the public key for encryption, with only its private key able to decrypt, ensuring data confidentiality; if used for digital signatures, after publishing the public key, it encrypts data with the private key as a signature to prove that the data was sent by the private key holder. However, regardless of the use, involving the publication of the public key cannot avoid man-in-the-middle attacks.
Public key certificates consist of a public key + signature, issued by a trusted third-party certification authority. Since legitimate browsers come pre-installed with trusted authorities’ public keys, they can effectively prevent man-in-the-middle attacks.
The SSL/TLS security layer in HTTPS combines the above encryption methods, therefore do not install unregulated browsers or randomly install certificates from unknown sources.
Cryptography is only a small part of security; even HTTPS sites certified by legitimate authorities do not mean they are trustworthy, as they only ensure that data transmission is secure. Technology can never truly protect you; the most important thing is to enhance personal security awareness, be vigilant, and handle sensitive data cautiously.
Finally, if you find this article well-written, give it a look and share it; if the data is good, I will write more.
Do you find this article helpful? Please share it with more people.
Follow “Algorithm Enthusiasts” and star it to hone your programming skills.
Great article, I’m looking at it ❤️