This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

This chapter introduces the implementation process, mechanisms, and characteristics of symmetric cipher algorithms using several typical examples, and helps understand the application background of cipher algorithms.

Content Overview

Chapter-4: Symmetric Cipher Technology

Several classic classical cipher schemes
Data Encryption Standard DES
Advanced Encryption Standard AES
Stream cipher algorithms
Block cipher algorithm operating modes

Classical Ciphers

Classical ciphers are mainly divided into two types: transposition ciphers and substitution ciphers

Transposition Ciphers

Transposition ciphers are characterized by keeping all characters of the plaintext unchanged, only using permutation to rearrange the positions and order of the plaintext characters. That is, changing the structure of the plaintext without changing the plaintext content.

Encryption and decryption are achieved by changing the positions of plaintext characters
Typical examples: Rail fence cipher, row transposition cipher, etc.

Substitution Ciphers

Replacing plaintext letters with other letters, numbers, or symbols
If the plaintext is viewed as a bit sequence of 0s and 1s, then the ciphertext is another representation of a 0 or 1 bit sequence. Simple and straightforward Typical example: Caesar cipher

Caesar Cipher

The earliest known substitution cipher
Invented by Julius Caesar, first used in military communications
Basic idea: Encryption and decryption by shifting letters by a certain number of positions
e.g., each letter is replaced by the letter three positions after it (also called a shift cipher)

Plaintext	a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
Ciphertext	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C

Encryption/Decryption Method 1: Lookup table above

Encryption Method 2: Formula calculation

Encode plaintext: $a=0,b=1,…,z=25$ , then plaintext $P=p1p2…pn$
Encryption operation: $c_i=p_i+k \bmod 26,i=1,2,…,n$
Obtain ciphertext: $C=c_1c_2…c_n$

Decryption Method 2: Formula calculation

Ciphertext: $C=c_1c_2…c_n$
Decryption operation: $p_i=c_i-k \bmod 26,i=1,2,…,n$
Decrypted plaintext: $P=p_1p_2…p_n$

That is, the Caesar cipher encryption/decryption algorithms are:

Encryption algorithm: $c = E(p) = (p+k) \bmod (26)$
Decryption algorithm: $p = D(c) = (c-k) \bmod (26)$

Cryptanalysis:

The Caesar cipher has only 25 possible keys
Can be simply tested one by one through exhaustive attack
Frequency analysis-based decryption method
The decrypted plaintext needs to be recognizable

e.g.: Decrypt ciphertext "GCUA VQ DTGCM"

dzrx sn aqdzj( k=3 )
easy to break ( k=2 ) There it is!

Monoalphabetic Substitution Cipher

You can read the blog: Monoalphabetic Substitution Cipher System

Characteristics:

Not simply ordered letter shifting
Letter order can be arbitrarily scrambled
Each plaintext letter maps to a different random ciphertext letter
The substitution relationship can be one-to-many, but must ensure reversibility
Number of keys: 26! (26 factorial)

Seems very secure, but in fact it can still be analyzed through language frequency analysis

Human languages are redundant
Letter usage frequencies differ
For example, in English, E is the most frequently used letter
Some letters are rarely used
Single-letter, double-letter, and triple-letter combination statistics

Polyalphabetic Substitution Cipher (Vigenere Cipher)

The main difference between polyalphabetic substitution ciphers and monoalphabetic substitution ciphers is that polyalphabetic substitution has multiple substitution tables.

Different substitution tables are used alternately for encryption
Letter frequency distribution becomes more uniform
The order of substitution tables used for encryption and decryption is the same
The typical example is: Vigenere cipher

The Vigenere cipher is the simplest polyalphabetic substitution cipher, composed of multiple Caesar shift ciphers. Its plaintext character set is a~z, 26 English letters. Cyclically shifting letters by k positions forms a substitution table.

The Vigenere square is shown below:

For example, suppose the plaintext is: ATTACKATDAWN

Select a keyword and repeat it to match the plaintext length (truncate if too short) to obtain the key. For example, with keyword LEMON, the key is: LEMONLEMONLE
For the first plaintext letter A, corresponding to the first key letter L, use the L row alphabet in the table for encryption, obtaining the first ciphertext letter L
Similarly, the second plaintext letter is T, using the corresponding E row in the table for encryption, obtaining the second ciphertext letter X. And so on:

Plaintext: ATTACKATDAWN
Key: LEMONLEMONLE
Ciphertext: LXFOPVEFRNHR

The decryption process is the reverse of encryption.

The first key letter L corresponds to the L row alphabet. The first ciphertext letter L is found in column A, so the first plaintext letter is A
The second key letter E corresponds to the E row alphabet, and the second ciphertext letter X is in column T of this row, so the second plaintext letter is T. And so on to obtain the plaintext.

That is, the Vigenere cipher encryption/decryption algorithms are:

Encryption algorithm: $c_i = E_{k_i}(p_i) = (p_i+k_i) \bmod 26$
Decryption algorithm: $p_i = D_{k_i}(c_i) = (c_i-k_i) \bmod 26$

As can be seen, the only difference between the Vigenere cipher and monoalphabetic substitution cipher is: in the monoalphabetic shift cipher, the shift amount k is a fixed constant; while in the Vigenere cipher, ki varies -- different positions use different shift amounts.

The JavaScript code for the encryption/decryption process is as follows:

/*
 * @Author: cos
 * @Description: Vigenere encryption and decryption process
 * @FilePath: \secure\exp_1\Vigenere.js
 */
class Vigenere {
  ascii; // ascii[i] represents the ASCII code of the i-th letter
  matrix;
  constructor() {
    this.ascii = new Array(26).fill(0).map((v, i) => String.fromCharCode(65 + i));
    this.matrix = new Array(26).fill(0).map(() => new Array(26));
    for (let i = 0; i < 26; ++i) for (let j = 0; j < 26; ++j) this.matrix[i][j] = this.ascii[(i + j) % 26]; // Column master key
  }
  // Generate key from plaintext and keyword
  buildKey(plain, keyword) {
    let [len1, len2] = [plain.length, keyword.length];
    if (len1 <= len2) return keyword.substr(0, len1);
    let cnt = Math.floor(len1 / len2);
    return keyword.repeat(cnt) + keyword.substr(0, len1 - len2 * cnt);
  }
  // Encrypt using plaintext and keyword
  encrypt(plain, keyword) {
    let capitalPlain = plain.toUpperCase(); // Note: convert key and plaintext to uppercase first
    let key = Vigenere.prototype.buildKey(capitalPlain, keyword.toUpperCase());
    let len = capitalPlain.length;
    let res = '';
    for (let i = 0; i < len; ++i) {
      let idx = key.charCodeAt(i) - 65; // Use the idx-th row
      let jdx = capitalPlain.charCodeAt(i) - 65;
      let nowchar = this.matrix[idx][jdx];
      res += plain[i] <= 'Z' ? nowchar : nowchar.toLowerCase(); // If lowercase, ciphertext is also lowercase
    }
    return res;
  }
  // Decrypt using ciphertext and keyword
  decrypt(encrypted, keyword) {
    let capitalEd = encrypted.toUpperCase(); // Note: convert key and ciphertext to uppercase first
    let key = Vigenere.prototype.buildKey(capitalEd, keyword.toUpperCase());
    let len = capitalEd.length;
    let res = '';
    for (let i = 0; i < len; ++i) {
      let idx = key.charCodeAt(i) - 65; // Use the idx-th row
      let jdx = this.matrix[idx].findIndex((v) => v == capitalEd[i]); // Find the ASCII code corresponding to the ciphertext in this row
      let nowchar = this.ascii[jdx];
      res += encrypted[i] <= 'Z' ? nowchar : nowchar.toLowerCase(); // If lowercase, decrypted letter is also lowercase
    }
    return res;
  }
  printMatrix() {
    console.log('Square matrix:');
    for (let i = 0; i < 26; ++i) console.log(this.matrix[i].join(''));
  }
}
module.exports = new Vigenere();

Main function

/*
 * @Author: cos
 * @Description: Main class
 * @FilePath: \secure\exp_1\Main.js
 */
// Test function
const v = require('./Vigenere');
function testCase(plain, keyword) {
  console.log(`Plaintext: ${plain}, Key: ${keyword}`);
  let encrypted = v.encrypt(plain, keyword);
  console.log(`Ciphertext: ${encrypted}`);
  let decrypted = v.decrypt(encrypted, keyword);
  console.log(`Decrypted: ${decrypted}`);
}
let testCases = [
  ['ATTACKATDAWN', 'LEMON'],
  ['HelloWorld', 'haoye'],
  ['QwQqwqOVO', 'WHXHP'],
  ['BUS', 'YELLO'],
  ['abcdEFGhiJK', 'NaHCOx'],
  ['DidILoveU', 'cos'],
];
for (let i = 0; i < testCases.length; ++i) {
  console.log(`----------------Test Case ${i}----------------`);
  testCase(...testCases[i]);
}
v.printMatrix();

Output results:

Other typical polyalphabetic substitution ciphers include: Hill cipher, rotor cipher, etc.

Data Encryption Standard DES

How to implement a symmetric cipher algorithm with identical encryption/decryption processes and identical keys?

The Data Encryption Standard DES is a well-known block cipher algorithm.

The US National Bureau of Standards publicly solicited cryptographic algorithms for encryption protection of computer data during transmission and storage in May 1973.

In 1975, the National Bureau of Standards accepted a cipher algorithm submitted by IBM and solicited public comments.
In 1977, the algorithm was officially adopted as the US Data Encryption Standard.
In December 1980, the American National Standards Institute officially adopted this algorithm as the US commercial encryption algorithm.

Requirements set by the National Bureau of Standards for the encryption algorithm:

Provide high-quality data protection, preventing unauthorized data disclosure and undetected modification.
Have sufficiently high complexity so that the cost of breaking it exceeds the potential gains, while being easy to understand and master.
The security of the cipher system should not depend on algorithm secrecy; its security should be based solely on key secrecy.
Be economical to implement, efficient to operate, and suitable for many completely different applications.

Overview

DES is a block cipher algorithm where encryption and decryption use the same key
DES has a block length of 64 bits
Uses a 64-bit key (including 8 parity check bits); the key is expanded to produce 16 subkeys
16 rounds of substitution and permutation on the plaintext block
DES algorithm steps include IP permutation, key permutation, E expansion, S-box substitution, P-box permutation, and inverse initial permutation IP-1... (oh no)

...To be supplemented based on question types! Let's look at the blog first. I don't think the specific steps will be tested: Data Encryption Algorithm -- Detailed DES Algorithm Principles and Implementation

What is the advantage of having identical encryption/decryption keys? Users only need to remember one key for both encryption and decryption.

Small computational cost for encryption and decryption, fast speed, simple and easy to use, suitable for encrypting massive amounts of data.
Why was the length chosen as 64 bits? Parity checking can be performed; every 8 bits can be used for parity checking

Key length is 64 bits, but the actual data length is only 56 bits, with 8 bits for parity checking
For error-checking codes, the 3B1B video is recommended: Hamming codes part 2, the elegance of it all

Advanced Encryption Standard AES

How to design a symmetric cipher algorithm with mathematically provable security?

In April 1997, NIST initiated the process of soliciting an Advanced Encryption Standard, aiming to identify a publicly available, globally free block cipher algorithm as the new data encryption standard.

On September 12, 1997, the US Federal Register published the official call for AES candidate algorithms. As a condition for entering the AES selection process, developers committed to waiving intellectual property rights for the selected algorithm.

NIST's requirements for AES algorithms:

The algorithm should be faster than Triple DES, and at least as secure
Should have a 128-bit block length and 128/192/256-bit key lengths

64-bit keys can already be broken

On August 12, 1998, at the first AES conference, NIST received 15 candidate algorithms. On March 22, 1999, the second AES conference reduced the candidate list to 5:

MARS (IBM), RC6 (MIT), Rijndael (Belgium), Serpent (UK, Israel, US), Twofish (US)

On April 13, 2000, at the third AES conference, analysis results of these 5 candidate algorithms were discussed.

On October 2, 2000, NIST announced the winner:
The Rijndael algorithm designed by Belgian cryptographers Vincent Rijmen and Joan Daemen

In November 2001, the final standard FIPS PUB197 was published, and the algorithm was named AES: Advanced Encryption Standard.

Rijndael Algorithm

Block length of 128 bits, key length of 128/192/256 bits
Uses a substitution-permutation network design rather than the Feistel structure, with fast software and hardware implementations
Basic properties
- Can resist all known attacks
- Runs fast on various platforms with compact code
- Simple design

AES Basic Operation Flow

AES consists of multiple rounds, with the number of rounds determined by block and key length.

AES operates on a 4 x n byte array (matrix) called the State, where n is the key byte count divided by 4.

AES Data Structure

Described as a byte-based square matrix: input block in, intermediate array State, output block out, key block K
Arrangement order: data in the matrix is arranged top to bottom, left to right

Allows block and key lengths to be extended in multiples of 8 bytes based on 128 bits
- Therefore 192, 256-bit blocks or keys are organized as 4x6, 4x8 matrices
The AES standard uses $N_b$ $N_{b}$ and $N_k$ $N_{k}$ to represent the number of columns in the block matrix and key matrix respectively
- For example, when the block is a 4x6 matrix, $N_b=6$ ; when the key is a 4x8 matrix, $N_k=8$
The number of rounds in the AES algorithm flow depends on key length; the standard uses $N_r$ to represent the number of rounds.
AES includes 3 block cipher suites: AES-128, AES-192, AES-256, with corresponding $N_k$ values of 4, 6, 8, key lengths of 128, 192, and 256 bits, corresponding round counts $N_r$ of 10, 12, 14, and all block lengths of 128 bits.

Detailed operation flow omitted here: Detailed Introduction and Implementation of AES Encryption Algorithm

Other block cipher algorithms: IDEA algorithm, Blowfish algorithm, RC5/RC6 algorithm

Stream Cipher Algorithm RC4

How to implement a symmetric cipher algorithm with "infinite" key length?

Master key: A fixed-length key shared by both communicating parties

RC4 Algorithm

Generates a pseudo-random key byte stream of arbitrary length (byte-based) from the master key using a key scheduling algorithm
XORs byte by byte with the plaintext stream to generate the ciphertext stream
Decryption XORs the ciphertext stream with the same key stream byte by byte to recover the plaintext byte stream.

OK, Symmetric Encryption Stream Cipher RC4

Block Cipher Operating Modes

Electronic Codebook (ECB) mode
Cipher Block Chaining (CBC) mode
Cipher Feedback (CFB) mode
Output Feedback (OFB) mode
Counter (CTR) mode

Introduction to Information Security Review 2: Chapter 4 Symmetric Cipher Technology