Alan Turing was primarily responsible for breaking the German Enigma cipher system during World War II. Decrypting codes required extensive computation, and Turing understood that to do a good job, one must first sharpen their tools. Thus, a computer called COLOSSUS was developed in 1943, and a total of 10 such electronic computers were produced, successfully completing the code-breaking task.
Some even credit the victory in World War II to the invention of the Turing machine, which, while perhaps an exaggeration, undeniably accelerated the end of the war. The Turing machine did not defeat fascism but rather overcame the German Enigma cipher system. Prior to 1976, all encryption methods were symmetric, meaning the Turing machine also triumphed over symmetric encryption algorithms.
June 23rd is Alan Turing’s birthday. Interested readers can watch the film “The Imitation Game,” which is adapted from Andrew Hodges’ biography “Alan Turing: The Enigma.” Those who enjoy reading may find the original work particularly enlightening.
The story is told, and today I will introduce another type of encryption algorithm: asymmetric encryption, with RSA being one of the most widely used forms of asymmetric encryption. In fact, the RSA algorithm is a very simple formula that anyone can understand, even without advanced mathematics, as long as you have a curious mind like mine!
I have divided the content into three main sections. Why this division? It allows us to gradually understand RSA and unveil its secrets step by step.
1. Overview of Common Encryption Algorithms
2. Introduction to RSA Algorithm and Number Theory
3. RSA Encryption and Decryption Process and Formula Proof
1. Overview of Common Encryption Algorithms
Common encryption algorithms can be divided into three categories: symmetric encryption algorithms, asymmetric encryption algorithms, and hash algorithms.
Note: Base64 encoding is merely a coding format and not an encryption algorithm; it can be used to transmit longer identification information in an HTTP environment.
1. Symmetric Encryption
Before 1976, all encryption methods followed the same model of symmetric encryption, which uses symmetric key coding technology. Its characteristic is that the same key is used for both file encryption and decryption; that is, the encryption key can also serve as the decryption key. This method is known as symmetric encryption algorithms in cryptography. Symmetric encryption algorithms are simple and quick to use, with short keys and difficult decryption. Besides the Data Encryption Standard (DES), another symmetric key encryption system is the International Data Encryption Algorithm (IDEA), which is superior to DES in terms of encryption strength and has lower computational requirements. The IDEA encryption standard is used by the Pretty Good Privacy (PGP) system. Symmetric encryption can further be divided into stream encryption and block encryption, which I will not elaborate on here; interested readers can learn more on their own.
Characteristics of Symmetric Encryption:
Advantages: The advantages of symmetric encryption algorithms include public algorithms, small computational load, fast encryption speed, and high encryption efficiency.
Disadvantages: Before data transmission, the sender and receiver must agree on a secret key, which both parties must securely store. If one party’s key is leaked, the encrypted information becomes insecure.
Use Cases: Local data encryption, HTTPS communication, network transmission, etc.
Common Algorithms: AES, DES, 3DES, DESX, Blowfish, IDEA, RC4, RC5, RC6.
2. Asymmetric Encryption
In 1976, two American computer scientists, Whitfield Diffie and Martin Hellman, proposed a groundbreaking concept that allows decryption without directly transmitting the key. This is known as the “Diffie-Hellman key exchange algorithm.” This algorithm inspired other scientists, leading to the realization that encryption and decryption can use different rules as long as there is some correspondence between them, thus avoiding the direct transmission of keys. This new encryption model is known as “asymmetric encryption algorithms.”
Characteristics of Asymmetric Encryption:
Advantages: Asymmetric encryption is more secure compared to symmetric encryption.
Disadvantages: Encryption and decryption take longer, making it suitable only for encrypting small amounts of data.
Use Cases: Initial HTTPS sessions, CA digital certificates, information encryption, login authentication, etc.
Common Algorithms: RSA, ECC (for mobile devices), Diffie-Hellman, El Gamal, DSA (for digital signatures).
3. Hash Algorithms
The unique aspect of hash algorithms is that they are one-way algorithms. Users can generate a unique hash value of a specific length from target information using a hash algorithm, but cannot retrieve the target information from this hash value. Therefore, hash algorithms are commonly used in irreversible password storage, information integrity verification, and more.
Characteristics of Hash Algorithms:
Advantages: Irreversible, easy to compute, and characterized.
Disadvantages: Potential for hash collisions.
Use Cases: File or string consistency verification, digital signatures, authentication protocols.
Common Algorithms: MD2, MD4, MD5, HAVAL, SHA, SHA-1, HMAC, HMAC-MD5, HMAC-SHA1.
Choosing an Encryption Algorithm
-
Symmetric encryption algorithms cannot achieve signatures, so signatures can only be done with asymmetric algorithms.
-
Use hash algorithms for verifying file or character consistency.
-
For large data volumes, use symmetric encryption algorithms; for smaller amounts, asymmetric encryption can be used.
-
Asymmetric and symmetric encryption can also be integrated; see the detailed explanation of the HTTPS encryption process.
-
It is recommended to use 1024-bit numbers for RSA, 160-bit for ECC, and 128-bit for AES.