[One] Cryptography Notes - "Illustrated Cryptography" 3rd Edition

1. One-way Hash Function

When we download software from some large software portal websites, the software publisher usually publishes the hash value of the software at the same time as the software. The hash value is calculated using a one-way hash function, such as the common hash.

One-way hash functions guarantee integrity, not confidentiality.

2. Digital Signature

Digital signature is a cryptographic technology that can ensure integrity, provide authentication, and prevent denial.

3. Cryptographer's Toolbox

Symmetric cryptography, public-key cryptography, one-way hash function, message authentication code, digital signature, pseudo-random number generator

4. Steganography

Hiding the message itself, such as acrostic poems, digital watermarks. Cryptography hides the content, while steganography hides the message itself. And they can be used together.

5. Common Sense of Cryptography

• Do not use secret cryptographic algorithms
• Using low-strength cryptography is more dangerous than not using any encryption
• Any cryptography will be cracked one day
• Cryptography is only a part of information security

5.1 Do not use secret cryptographic algorithms

The secret of cryptographic algorithms will eventually be exposed without exception. Using secret cryptographic algorithms will cause the entire cryptographic system to collapse.

Developing high-strength cryptographic algorithms is very difficult. The strength of cryptographic algorithms cannot be strictly proven like mathematics. If the detailed information of the cryptographic algorithm and the source code of the program are all handed over to professional cryptanalysts, and a large number of plaintext and ciphertext samples are provided to them, and it still takes a considerable amount of time to decipher a piece of ciphertext under such circumstances, then it means this is high-strength cryptography.

6. Caesar Cipher

7. Simple Substitution Cipher

Replace the content that needs to be encrypted with other characters.

A substitution table is needed for decryption.

8. Terms frequently used in cryptography

8.1 Keyspace

The "set of all keys" that a cipher can use is called the keyspace. The larger the keyspace, the harder the cipher is to crack.

8.2 Frequency Analysis

It is a method of cryptanalysis. When you have enough ciphertext, patterns will emerge, and cryptanalysts will crack the cipher based on these patterns. Frequency analysis utilizes the characteristic that the frequency of letters in the plaintext is consistent with the frequency of letters in the ciphertext.

• In addition to high-frequency letters, low-frequency letters can also be clues
• Figuring out the beginning and end can be clues, figuring out the separation between words can also be clues
• The longer the ciphertext, the easier it is to crack
• The continuous appearance of the same letter can be a clue
• The speed of cracking will be faster and faster

8.3 Key Encrypting Key (KEK)

The key used to encrypt the communication key is called the key encrypting key.

8.4 Encoding

The operation of mapping things in the real world to bit sequences is called encoding.

8.5 XOR Exclusive OR

The full name of XOR is: Exclusive Or

XOR operation of 1 bit

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

If 0 is understood as an even number and 1 as an odd number, XOR can be linked to general addition operations.

Generally, is used to represent XOR, which can also be understood as Othello (Reversi).

XOR of bit sequences

If it is an XOR operation between long bit sequences, just perform the XOR operation on each corresponding bit. Suppose we call the bit sequence 01001100 A and the bit sequence 10101010 B, then the XOR operation of A and B can be calculated bit by bit as follows. Unlike addition, there is no carry in XOR.

Decryption steps for bit sequences

• Encrypt plaintext A with key B to get ciphertext AB
• Decrypt ciphertext AB with key B to get plaintext A

Applications of XOR

• Encrypting images
• Encrypting messages

8.6 One-time Pad

The one-time pad is known as a cipher that will absolutely never be cracked.

8.7 Stream Cipher

Born from the idea of the one-time pad. It does not use a truly random bit sequence, but a bit sequence generated by a pseudo-random number generator.

8.8 DES (Data Encryption Standard)

DES is a symmetric cryptographic algorithm that encrypts 64-bit plaintext into 64-bit ciphertext.

8.9 Block Cipher

Generally speaking, cryptographic algorithms that process in units of blocks are called block ciphers. DES is a type of block cipher.

8.10 The Importance of Keys

The key is the essence of secrecy.

Everyone can have the same brand of lock, but everyone has a different key. The design of the lock is public, but the key is secret. — "The Truth about Network Information Security"

9. One-time Pad

The one-time pad is known as a cipher that will absolutely never be cracked.

9.1 Principle

Perform XOR operation on the plaintext with a string of random bit sequences. For example:

9.2 Why is the one-time pad absolutely unbreakable?

Suppose we try to brute-force crack the ciphertext of a one-time pad. Someday we will try the same key used for encryption and decrypt the plaintext "midnight". This is an unquestionable fact. However - and this is very important - even if we can decrypt the string "midnight", we cannot judge whether it is the correct plaintext.

This is because in the process of attempting to decrypt the one-time pad, all 64-bit permutations and combinations will appear. This will include regular strings like aaaaaaaa, abcdefgh, zzzzzzzz, English words like midnight, onenight, mistress, and incomprehensible combinations like Ta_AjvX, HY(&JY!z, 5), ER#£6. Since all possible permutations and combinations of plaintext will appear, we cannot judge which one is the correct plaintext (that is, which key can decrypt it correctly). So-called brute-force cracking is a method of trying all keys in order and judging whether the result is the correct plaintext. However, in the one-time pad, since we cannot judge whether the result is the correct plaintext, the one-time pad cannot be cracked.

The one-time pad was proposed by Gilbert Vernam in 1917 and patented, so it is also called the Vernam cipher (the patent has expired). The property that the one-time pad cannot be cracked was proven mathematically by Claude Shannon in 1949. The one-time pad is unconditionally secure and theoretically unbreakable.

10. Some stories in cryptography

British cryptographers cracked Enigma, and Alan Turing, the father of modern computers, was also a member of the cracking team. What defeated Enigma was another machine: "The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography" "Alan Turing: The Enigma"