Cryptography is a highly interdisciplinary field, including pure mathematics, computer science, and electronic engineering. “Many novices should have a big head when they see this.” Do you have to learn so much knowledge to understand cryptography? “Of course not.” If your idea is to become a researcher or domain expert in cryptography or cryptographic hashing, you must expert in cryptographic algorithm. But for a “beginner hacker”, we only need to understand the basic cryptographic systems such as the general terminology of cryptography, password encryption, and cryptanalysis.
Next, I will use this article to give some inspiration and guidance to friends who want to learn about cryptography!
What is cryptography?
Official definition: Cryptography is the technical science that studies the preparation and deciphering of passwords. The study of the objective laws of password changes is called coding when it is used to compile passwords to keep communication secrets; when it is used to decipher passwords to obtain communication information, it is called deciphering, or cryptography in general.
Popular understanding: Cryptography is the science and art of hiding information, so they are kept secret, and then “unhiding” them so that only the intended recipient can read them. Basically, we can say that cryptography is the science of secret messaging.
Algorithm and key
If the confidentiality of the algorithm is based on keeping the algorithm secret, this is called a restricted algorithm. Any algorithm can be reverse-analyzed, which is obviously insecure. Modern cryptography uses keys to solve this problem. The key is denoted by K, k1 is called the encryption key, and k2 is called the decryption key. If K1=K2, or k2 can be calculated from k1, the reverse is also true. Then such an algorithm is called asymmetric algorithm. If k1 is not equal to k2, and k1 and k2 cannot be derived from each other, then such an algorithm is called an asymmetric method, also called a public key algorithm.
Cryptanalysis: The science of replying to the plaintext without knowing the key.
Steganography: hide secret messages in other messages. The most common is to hide the message in the image, and you can directly use the copy command under the window to succeed.
Some important tools of cryptography
The following are some important cryptographic tools of cryptography are:
- symmetric cryptography
- public key cryptography
- one-way hash function
- digital signature
Symmetric cryptography refers to the method of using the same key for encryption and decryption. It is the most common encryption method. It encrypts and decrypts information by encoding information, using public encryption algorithms and secret keys. The encryption process and decryption process are symmetrical, so it is called asymmetric cipher.
The concept of open encryption algorithm appears here. People usually have a wrong view that secret encryption algorithm has higher security, which is called “concealed security” by modern cryptography. Because confidential encryption algorithms will be made public sooner or later as long as they are used, the cryptographic system that wants to rely on the confidentiality of the cryptographic algorithm itself to ensure confidentiality has collapsed. On the contrary, if the encryption algorithm has never envisaged confidentiality from the beginning, it will be baptized by various attacks, thereby achieving stronger confidentiality. Therefore, the encryption method of modern cryptography is basically composed of a “public encryption algorithm + secret key”.
Composition: public encryption algorithm + secret key;
Encryption process: When A sends encrypted information t to B, it needs to use an encryption algorithm and key to encrypt t;
Decryption process: the inverse process of the encryption process;
Advantages: The huge key space can resist brute force cracking, there are no weaknesses in the algorithm to resist other types of attacks, and the efficiency of encryption and decryption operations is high;
Disadvantages: key distribution problem (this is also the reason why other cryptographic techniques must be used);
Common cryptographic algorithms: DES, AES, etc.;
Purpose: Encrypt information;
Public key password
Public-key cryptography refers to the method of using different keys for encryption and decryption, which is the exact opposite of symmetric keys, so it is also called asymmetric cryptography.
Composition: public encryption algorithm + public key (public key) + secret key (private key);
Encryption process: When A sends encrypted information t to B, it needs to use an encryption algorithm and B’s public key to encrypt t;
Decryption process: B needs to use the decryption algorithm (usually the same as the encryption algorithm) and B’s private key to decrypt t;
Advantages: solve the problem of key distribution;
Disadvantages: The encryption and decryption algorithm is inefficient (meaning it cannot be used directly for information encryption), man-in-the-middle attack (B cannot determine that the ciphertext is sent by A, so new security technologies need to be introduced);
Common cryptographic algorithms: RSA, etc.;
Purpose: Encrypt symmetric keys, etc.;
One-way hash Function
First of all, the following technologies are not directly used for encryption. The one-way hash function has one input and one output. The input is called a message and the output is called a hash value. It maps x to y through an irreversible function y=f(x), and judges whether x has been tampered with by comparing the changes in y before and after transmission. For example: suppose that A wants to transmit t to B, and B must be able to determine whether someone has modified t during the transmission. What should we do? A can use a one-way hash function to find y=f(t), and send t and y together to B; after B gets t and y, use f(t)=y1 to determine whether y and y1 are the same, The difference means that there is an error in t or y during the transmission, and the information is incomplete, and the same means that t has not been modified during the transmission.
Composition: one-way hash function;
Advantages: high algorithm efficiency, identification of tampering;
Disadvantages: unable to distinguish camouflage (this requires new security technology to ensure);
Common password algorithms: MD5, SHA1, etc.;
Purpose: Judgment of tampering, password-based encryption, message authentication code, digital signature, etc.;
The previous section mentioned an authentication scheme, but there are still many shortcomings in some scenarios, such as the inability to prevent denial and the inability to resist man-in-the-middle attacks. It is impossible to prevent denial because the keys are the same, and it is impossible to determine who sent the message. Therefore, separating the key into an encryption key and a decryption key can solve the problem of inability to prevent denial. Is this similar to public key cryptography? Digital signatures can be regarded as the reverse process of public key cryptography, using private key encryption to generate signatures, and public key decryption to verify the signatures (this also requires the asymmetric encryption algorithm to be reversible. This is more awesome than RSA). However, the previous article discussed that the efficiency of the RSA algorithm is not high, so the practice of digital signature is usually: one-way hash function + RSA algorithm.
Composition: one-way hash function + public key cryptographic algorithm + public key;
Encryption process: A calculates the information t through a one-way hash function to obtain h, and uses A’s private key to encrypt h to obtain a digital signature s;
Authentication process: B receives t and s, uses A’s public key to decrypt s, then hashes t, and compares whether the two are consistent.
Advantages: able to identify tampering and disguise, and also prevent denial;
Disadvantages: Due to the use of public key cryptography, it still cannot ideally solve the man-in-the-middle attack, so the concept of certificate is proposed;
Common cryptographic algorithms: RSA and other algorithm combinations;
Purpose: various scenarios requiring certification;
Common types of cryptographic algorithms in modern cryptography:
Symmetric cryptographic algorithm is sometimes called traditional cryptographic algorithm, that is, the encryption key can be calculated from the decryption key, and vice versa. In most symmetric algorithms, the encryption and decryption keys are the same. These algorithms are also called secret-key algorithms or single-key algorithms, which require the sender and receiver to agree on a key before communicating securely. The security of the symmetric algorithm relies on the key. Leaking the key means that anyone can encrypt and decrypt the message. As long as the communication needs to be kept secret, the key must be kept secret.
1.1 DES: There are three entry parameters for the DES algorithm: Key, Data, and Mode. Key is 7 bytes and 56 bits in total, which is the working key of the DES algorithm; Data is 8 bytes and 64 bits, which is the data to be encrypted or decrypted; Mode is the working mode of DES, and there are two types: encryption Or decrypt. Its function is to recombine the input 64-bit data block bit by bit, and divide the output into two parts, L0 and R0, each part is 32 bits long. The replacement rule is to change the 58th bit of the input to the first bit. The 50th place is moved to the second place and so on, the last place is the original 7th place. L0 and R0 are the two parts after the transposition output, L0 is the left 32 bits of the output, R0 is the right 32 bits, for example: set the input value before the replacement to D1D2D3…D64, then the result after the initial replacement is: L0=D58D50……D8; R0=D57D49……D7.
After 16 iterations, L16 and R16 are obtained, which are used as input to perform inverse permutation. Inverse permutation is just the inverse operation of initial permutation, and thus the ciphertext output is obtained.
This algorithm is a representative of the symmetric encryption algorithm system and is widely used in computer network systems.
1.2 AES : Advanced Encryption Standard (English: Advanced Encryption Standard, abbreviation: AES), also known as Rijndael encryption in cryptography, is a block encryption standard adopted by the US Federal Government. This standard is used to replace the original DES, which has been analyzed by many parties and is widely used all over the world. After five years of selection process, the Advanced Encryption Standard was published by the National Institute of Standards and Technology (NIST) in FIPS PUB 197 on November 26, 2001, and became an effective standard on May 26, 2002. In 2006, the Advanced Encryption Standard has become one of the most popular algorithms in symmetric key encryption.
AddRoundKey — Each byte in the matrix is XORed with the round key; each subkey is generated by the key generation scheme.
SubBytes — Through a non-linear replacement function, each byte is replaced with the corresponding byte by means of a look-up table.
ShiftRows — cyclically shift each row in the matrix.
MixColumns — In order to fully mix the operations of each straight row in the matrix. This step uses linear transformation to mix the four bytes of each column.
Asymmetric key is also called public key encryption, which uses two mathematically related keys to encode information. In this system, one of the keys is called a public key, which can be sent to anyone who wishes to communicate securely with the key holder. The public key is used to encrypt information. The second key is the private key, which belongs to the key holder, and this person must carefully keep the private key. The key holder uses the private key to decrypt the received information.
2.1 RSA : The RSA algorithm is based on a very simple fact of number theory: it is easy to multiply two large prime numbers, but it is extremely difficult to factorize the product, so the product can be publicly used as an encryption key.
Because when the product of two large prime numbers is factored, apart from 1 and itself (the two are not in the decomposition range), there are only these two large prime numbers, but these two large prime numbers are not known when decomposing, only from the smallest It is very difficult to start with the prime number 2, and gradually try to divide until the smaller of the two large prime numbers.
In the public key cryptosystem, the encryption key (that is, the public key) PK is public information, and the decryption key (that is, the secret key) SK needs to be kept secret. Encryption algorithm E and decryption algorithm D are also public. Although the decryption key SK is determined by the public key PK, SK cannot be calculated from PK.
The RSA algorithm is an asymmetric cryptographic algorithm. The so-called asymmetric means that the algorithm requires a pair of keys. If one is used for encryption, the other can be decrypted.
The RSA algorithm involves three parameters, n, e1, and e2.
Among them, n is the product of two large prime numbers p and q, and the number of bits occupied by the binary representation of n is the so-called key length.
e1 and e2 are a pair of related values, e1 can be taken arbitrarily, but e1 and (p-1)*(q-1) are required to be relatively prime; then choose e2, requiring (e2*e1)mod((p-1) *(q-1))=1.
(N, e1), (n, e2) is the key pair. Among them, (n, e1) is the public key, and (n, e2) is the private key.
RSA encryption and decryption algorithms are exactly the same. Suppose A is plaintext and B is ciphertext, then: A=B^e2 mod n; B=A^e1 mod n; (In public key encryption systems, public key encryption is generally used, private Key decryption)
e1 and e2 can be used interchangeably, namely:
A=B^e1 mod n; B=A^e2 mod n;
The hash algorithm maps a binary value of any length to a shorter fixed-length binary value, and this small binary value is called a hash value. The hash value is a unique and extremely compact numerical representation of a piece of data. If you hash a piece of plaintext and even change only one letter of that paragraph, subsequent hashes will produce different values. It is computationally impossible to find two different inputs that are hashed as the same value, so the hash value of the data can check the integrity of the data, generally used for fast search and encryption algorithms. Simple explanation: Hash (Hash) algorithm, that is, hash function. It is a one-way cryptosystem, that is, it is an irreversible mapping from plaintext to ciphertext. There is only an encryption process and no decryption process. At the same time, the hash function can change the input of any length to get a fixed-length output. The one-way feature of the hash function and the fixed length of the output data make it possible to generate messages or data.
3.1 MD5 : MD5 is Message-Digest Algorithm 5 (message-digest algorithm 5), used to ensure complete and consistent information transmission. It is one of the hash algorithms widely used by computers (also translated digest algorithm, hash algorithm), and the mainstream programming language has generally been implemented in MD5. Calculating data (such as Chinese characters) into another fixed length value is the basic principle of the hash algorithm. The predecessors of MD5 are MD2, MD3, and MD4.
The MD5 algorithm has the following characteristics:
- Compressibility: For data of any length, the length of the calculated MD5 value is fixed.
- Easy to calculate: It is easy to calculate the MD5 value from the original data.
- Anti-modification: Any modification to the original data, even if only 1 byte is modified, the MD5 value obtained is very different.
- Strong anti-collision: Knowing the original data and its MD5 value, it is very difficult to find a data with the same MD5 value (ie fake data).
3.2 SHA-256 : 256-bit secure hash algorithm. SHA-1 is slightly more secure than MD5 (160-bit VS128-bit), but the algorithm takes time and SHA-1 is slightly slower.