Popular Science | Introduction to Cryptography (Part-1)

Author: Leo Whitehead

Translation & Proofreading: IAN LIU & Ajian

Source: Ethereum fans

– The popular encryption communication tool – OpenSSL, part of the code –

• Bakkt Bitcoin contract rose by 257% in a single day, exceeding 1100 copies
• Read the current situation and development trend of cryptocurrency wallet products
• Extreme market challenges major contract exchanges, BTCC contract performance is outstanding

The inner principles of cryptography have long been recognized as a field in which a few experts or mathematicians can get involved, and the technical details in it seem to be magical to most people. Considering the complexity of modern cryptography, we can understand why many people have these misunderstandings about cryptography; but without understanding cryptography, there may be many decisions that do more harm than good, such as the UK Encryption Ban. Australia's Assistance and Access Bill, etc.

In this guide, we will help you get started with the basics of learning cryptography, an introduction to the evolution of different cryptography systems, and the current three most popular cryptography areas—streaming ciphers, block ciphers, Public key cryptography for quick start-up guidance.

Password (Ciphers)

"Cipher" refers to an algorithm that encrypts or decrypts a message and is the cornerstone of cryptography. The encryption algorithm (E) encrypts the message (m) using the key (k) and generates the ciphertext (c); similarly, the decryption algorithm (D) decrypts the ciphertext (c) using the key (k) . As shown below:

– encryption algorithm 'E' and decryption algorithm 'D' –

The above process also means that an algorithm to be called a "password" (algorithm) must also satisfy the following consistency equation characteristics to ensure that the ciphertext can be decrypted.

The expression indicates that if you use the key K to encrypt the message, you can also use the key K to decrypt the ciphertext and get the same output as the original message.

One of the oldest and simplest passwords is the Caesar Cipher, which simply picks a specific location from the alphabet and replaces the characters in the original message.

– Caesar's password appeared in AD 50. Caesar's Emperor used the alphabet to jump three words to replace the original message content for military communications –

The following example is the ciphertext form after the last three characters have been replaced (the above one is the original text, the following one is the ciphertext):

The Caesar password can be expressed in the following equation:

Although this approach is consistent with our definition of passwords, it is very insecure. As long as the attacker knows that the ciphertext is encrypted in this way, it can be deciphered by trying another 25 combinations; even if the attacker does not know that the ciphertext uses the Caesar cipher, they can observe the rules in the ciphertext for deciphering.

Although this approach is consistent with our definition of passwords, it is very insecure. As long as the attacker knows that the ciphertext is encrypted in this way, it can be deciphered by trying another 25 combinations; even if the attacker does not know that the ciphertext uses the Caesar cipher, they can observe the rules in the ciphertext for deciphering.

Before we dive into the more secure encryption algorithms, we have to talk about what Xor operations are.

XOR (exclusive OR operation)

The Xor operation, also known as the XOR gate, is a Boolean variable logic that accepts 1 or 0 as input: if output 1 means that the two inputs are different; output 0 means the two inputs are the same. The truth table in the figure below lists all possible combinations of input and output after an XOR operation:

XOR operations are also often represented by the symbol ⊕:

0 ⊕ 0 = 0

0 ⊕ 1 = 1

1 ⊕ 0 = 1

1 ⊕ 1 = 0

There are several important features about XOR logic:

1. XOR operation law: a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c

XORing itself is 0: a ⊕ a = 0

XOR for 0, the result is itself: a ⊕ 0 = a

According to the above rule of the exclusive OR operation, we know that a ⊕ b ⊕ a is equivalent to a ⊕ a ⊕ b, which is also equal to 0 ⊕ b, and the operation result is b. It should be noted that these XOR functions only apply to 1 and 0, so you need to convert them to binary before they are XORed. E.g:

87 ⊕ 73 = 1010111b ⊕ 1001001b = 0011110b = 30

Then, we can start to introduce the first security password.

One-time password

In 1882, Frank Miller proposed the concept of a one-time pad—encryption: XORing a message with a private key to obtain a ciphertext; decrypting: XORing a key with a ciphertext to get the original message. This process is similar to a ⊕ b ⊕ a = b mentioned earlier. The definition of a one-time password is as follows:

The consistency equation for this password is also easy to prove:

One-time passwords are very easy to use. Suppose we want to encrypt a string of fields "Message". First we can convert "Message" to binary data (consisting of 1 and 0) through the ASCII character set.

Now, we need a set of 56-bit random binary numbers (private keys) to XOR the plaintext. The higher the randomness of the private key, the better!

– Random numbers generated from random.org –

We XOR each of the plaintext and private keys.

The result of the operation is our ciphertext! To solve the ciphertext is also very simple, we only need to XOR the ciphertext and the private key just generated, and transcode back to ASCII, you can get the original message.

This password is easy to use and has a very interesting feature. One-time passwords have so-called full confidentiality, which means that from a mathematical point of view, it is impossible for an attacker to extract the content of any original message from the ciphertext (the result of m⊕k), and certainly cannot be deciphered.

Since we already have passwords that are easy to use and impossible to decipher, why would we want to use other passwords? The root cause is that a one-time password is effective, but he has some major flaws.

The first drawback is that no matter what kind of message we want to encrypt, we need a private key that is as long or longer as the original message for encryption and decryption. Moreover, in order for the ciphertext recipient to decrypt the ciphertext, an absolutely secure communication method is needed to give the private key to the recipient; this forms a paradox. If there is such a secure channel, it is better to send the original message directly. .

The second defect can be found in the name of the "one-time password". For the different messages, the same private key can only be used once per call; if the same private key is reused for multiple messages, the problem caused by it can be seen from the mathematical derivation.

Suppose we have two messages, m1 and m2, which are encrypted using the same private key k (making our system a "secondary password"). Through the XOR operation, we will get the following ciphertext:

From the above figure, we can get m1⊕m2 from ciphertext C1⊕C2. For the attacker, they can obtain the content of the original message based on this correlation, through various statistical analysis, frequency analysis, pattern matching, or using the natural language processing method proposed in 2006. I will not explain in depth the specific harm caused by this kind of relevance (see here for an in-depth understanding of interest), here is just an image of the more times the same private key is used ("three times", "four times" …?), the lower the security of the password.

Now that we have the basics of XOR encryption and one-time passwords, it's time to learn about other more practical encryption methods.

Stream Ciphers

One-time passwords are very secure, which means that it is impossible for an attacker to decipher if there is only ciphertext on hand. However, good security is based on the private key whose length is greater than or equal to the original message. This makes the one-time password not practical, because if both the encryption and decryption have a good way to deliver the message and the private key, they can directly pass the message, no need Encrypt.

In order to make one-time passwords more practical, we introduce the concept of "streaming passwords". The core idea of ​​stream ciphers is to replace the "random" key in a one-time password with a "pseudo-random" key. The pseudo-random key is generated from a cryptographically secure pseudo-random number generator (CSPRNG, Cryptographically Secure Pseudo-random number). Generator ). It should be noted that CSPRNG is different from the general pseudo-random number generator because the data generated by CSPRNG must be indistinguishable from the real random number. CSPRNG is an algorithm (or function) that produces a long list of numbers, similar to the nature of a random number. Because random numbers are difficult to generate, CSPRNG relies on seeds to determine the initial state and future generations; CSPRNG generates massive random numbers from relatively small starting seeds (for example, generating several gigabytes from a 128-bit seed) random number). If the starting seed is known, then all numbers produced are known, that is to say CSPRNG is deterministic; this also leads to the number produced by CSPRNG, the degree of randomness of which depends entirely on the randomness of the seed. In order to make the one-time password more practical, we can replace the original private key with the output of the pseudo-random number generator according to the required length; in this case, just pass the initial seed. Because CPRNG is deterministic, the same seed can be used to get the same output (and the same key can be used for encryption and decryption).

For a better understanding, let's take a look at the original one-time password:

Replace the original private key K with the output G(K) of the pseudo-random number generator:

(Note: The legend is just one of the stream ciphers, called the sync stream cipher. There is also a method called "self-synchronizing stream cipher", which uses the first few digits in the ciphertext to calculate each bit in the key.)

The replaced private key can be much shorter than the message to be encrypted, making it easier to assign and manage the private key, further improving the problem that the one-time password is not practical. But this approach also brings new problems:

Replacing the original completely random private key with the output of the secure random number generator results in a shorter private key length than the original message, making our password no longer completely confidential. Therefore, the security of stream ciphers depends on the unpredictability of our pseudo-random number generator. If the output of CSPRNG can be predicted, a plaintext message can be obtained. Here are some of the well-known cryptosystems that use weak stream ciphers:

802.11b WEP: WEP is an algorithm for encrypting WiFi data. The stream password used is called RC4. Because the same key cannot be used in the stream password, the long-term key contains a value of "IV" that changes every time; however, "IV" has only 24 bits, which means that after encrypting more than 5000 messages, There is a 50% probability that the same key appears.

CSS: The DVD Forum uses the Content Scramble System (CSS) to manage the digital rights of DVDs so that only authorized applications can access DVD content. CSS uses a 40-bit key, while the 40-bit key space is small and can be brute-forced relatively quickly. (Although the key is 40 bits, considering the technical characteristics of CSPRNG, the system may be completely cracked after guessing the 17-bit combination.)

Now that we have mastered the knowledge of stream ciphers, we can further discuss the next cryptosystem – block ciphers.

Block Ciphers

Block ciphers are another way to encrypt and decrypt data. The block cipher contains two algorithms: E for encryption, D for decryption, and the key K.

The core of the block cipher is that the plaintext to be encrypted and the ciphertext output are always the same, which is a fixed amount. This fixed amount is called "block size" (Translator's Note: don't confuse the "block size" in the blockchain context; later translate the word into "message size"), the size depends on the Block cipher algorithm. In addition, the length of the private key K is called a key size and is also a fixed amount. The two common block ciphers are 3DES and AES – 3DES has a 64-bit message size and a 168-bit key; AES has a 128-bit message size and a 128, 192, or 256-bit key.

Because block ciphers map possible blocks to every other block, they are also called "Keyed Permutations" or "Pesudorandom Permutations". It is very important that the private key determines the mapping between the input block and the associated ciphertext block, and is one-to-one, so that the ciphertext can be decrypted by knowing the private key.

The first important block cipher was the Data Encryption Standard (DES) developed by IBM in the 1970s, but DES was not secure and was quickly replaced by 3DES; followed by 3DES, the Advanced Encryption Standard (AES) developed in 1997. Replace. AES is a standardized block cipher developed at the request of the National Institute of Standards and Technology. AES is the most common block cipher used today and is significantly more important than DES and 3DES, so I will focus on AES.

Before I explain how AES works, let me remind you that I will skip a lot of technical details. If anyone is interested in this area, you can get what you want from here.

AES and most of the block ciphers operate through iterations, and incoming text messages are encrypted in an iterative manner using successive keys. The first step is to get a key K, which is usually 128-bit, 192-bit or 256-bit. Here we only demonstrate 128-bit AES; then use this key to derive a series of Round Keys to encrypt our Message.

In the example above, we enter a 128-bit (16-byte) key and expand the key into 11 16-byte subkeys via the Rijndael key method. Next, AES puts the original message into the round function R(k _n , m) for independent encryption calculation, and takes the extended round key k _n and the message state m as input for each calculation, for a total of 10 times.

Because AES can only be used on 128-bit messages, we represent the input message m as a single-byte unit of a 4×4 matrix, and we can also represent the round key as a 4×4 matrix, so that we can use the message and its contents. The state is XORed.

First, the input message is XORed with the first round key, and then the byte state is replaced by (ByteSub), line shift (ShiftRows), column confusion (MixColumns), etc., and the converted message state is output as a result (these steps) Will be explained later). We then repeat these steps 10 times using different round keys, the only difference being that the last calculation does not include column confusion ( MixColumns ). The final message state is XORed with the eleventh round key (k ₁₀ ) to obtain the final output. The following is a brief description of the three steps involved in the calculation of each round:

ByteSub (ByteSub): Replaces each byte in the message state matrix with the corresponding byte according to the substitution table.

– In the replacement table used by AES, each byte unit is represented in hexadecimal. For example, byte 9a will be replaced with b8 –

ShiftRows: Quantitatively move each line. The first line does not move, the second line shifts one bit to the left, the third line shifts to the left by two, and the fourth line shifts to the left by three.

Column Columns: Linearly transforms each column in the message state. So far, we have been able to use AES to encrypt data. However, you may soon find the limitations of AES—there is no way to encrypt more than 128 bits (or 16 bytes) of messages with only one AES. To encrypt messages larger than 16 bytes, we need to introduce the concept of Modes of operation .

(unfinished)

We will continue to update Blocking; if you have any questions or suggestions, please contact us!