
## Content

The Box-Muller transform is a method used to generate normally distributed random variables from uniformly distributed random variables.

Specifically, it involves selecting two random variables, $U_1$ and $U_2$, which are uniformly distributed over the interval $[0,1]$. The random variables $X$ and $Y$ are constructed as follows:

$$
X = \cos(2\pi U_1) \sqrt{-2\ln U_2}
$$

$$
Y = \sin(2\pi U_1) \sqrt{-2\ln U_2}
$$

Then, $X$ and $Y$ follow a normal distribution with a mean of 0 and a variance of 1.

## Derivation

Assume that $X$ and $Y$ are independent, normally distributed random variables with a mean of 0 and a variance of 1. Let $p(X)$ and $p(Y)$ be their probability density functions. Thus, we have:

$$
p(X) = \frac{1}{\sqrt{2\pi}} e^{-\frac{X^2}{2}}, \\ p(Y) = \frac{1}{\sqrt{2\pi}} e^{-\frac{Y^2}{2}}
$$

Since $X$ and $Y$ are independent, their joint probability density function is:

$$
p(X,Y) = \frac{1}{2\pi} e^{-\frac{X^2 + Y^2}{2}}
$$

We now perform a coordinate transformation by defining:

$$
X = R \cos(\theta), \\ Y = R \sin(\theta)
$$

Thus, the joint distribution in polar coordinates becomes:

$$
\int_{0}^{\infty} \int_{0}^{2\pi} \frac{1}{2\pi} e^{-\frac{R^2}{2}} R \, d\theta \, dR = 1
$$

From this, we can derive the distribution functions for $R$ and $\theta$, denoted as $P_R$ and $P_\theta$:

$$
P_R(R \leq r) = \\ \int_{0}^{r} \int_{0}^{2\pi} \frac{1}{2\pi} e^{-\frac{R^2}{2}} R \, d\theta \, dR = 1 - e^{-\frac{r^2}{2}}
$$

$$
P_\theta(\theta \leq \phi) = \\ \int_{0}^{\phi} \int_{0}^{\infty} \frac{1}{2\pi} e^{-\frac{R^2}{2}} R \, dR \, d\theta = \frac{\phi}{2\pi}
$$

It is evident that $\theta$ follows a uniform distribution over $[0, 2\pi]$. Let

$$
F_R = 1 - e^{-\frac{r^2}{2}}
$$

The inverse function is given by:

$$
R = F_R^{-1}(z) \\ = \sqrt{-2 \ln(1 - z)}
$$

When $z$ is uniformly distributed over $[0,1]$, the distribution function of $R$ is $F_R(r)$. Therefore, we can select two random variables $U_1$ and $U_2$, uniformly distributed over $[0,1]$, such that:

$$
\theta = 2\pi U_1, \\ 1 - z = U_2, \\ R = \sqrt{-2 \ln U_2}
$$

Substituting these into the earlier expressions, we obtain:

$$
X = R \cos(\theta), \\ Y = R \sin(\theta)
$$

Thus, the original expressions for $X$ and $Y$ are recovered, where they follow a normal distribution with mean 0 and variance 1.

## Verification

To generate a random variable $X \sim N(0,1)$ following a standard normal distribution, we note that the inverse of the error function $\mathrm{erf}^{-1}$ is not elementary. Using a series expansion to approximate this inverse can introduce significant computational error.

Elementary functions, on the other hand, have well-established high-precision algorithms. Thus, we aim to construct a normally distributed random variable from a uniformly distributed one using elementary functions.

Let $U, V \in (0,1)$ be uniformly distributed random variables. Consider the following transformations:

$$
X = \sqrt{-2\ln U} \cos(2\pi V), \\ Y = \sqrt{-2\ln U} \sin(2\pi V)
$$

Next, we verify that $X$ and $Y$ are independent and follow a standard normal distribution.

Define:

$$
R = \sqrt{X^2 + Y^2}, \\ \Theta = \arctan\left(\frac{Y}{X}\right)
$$

Note that $\Theta = 2\pi V$ and $R = \sqrt{-2\ln U}$. We now show that $R$ and $\Theta$, under the polar coordinate transformation, are independent and that they yield standard normal random variables.

Consider the probability density function of one variable when the other

is fixed. The probability density function of $\Theta$ is:

$$
P_\Theta(\Theta) = \frac{1}{2\pi}
$$

which is straightforward. For $R$, the cumulative distribution function is:

$$
P(R \leq R_0) = \\ P\left(U \leq \exp\left(\frac{-R_0^2}{2}\right)\right)
$$

Thus, the probability density function of $R$ is:

$$
P_R(R) = R e^{-\frac{R^2}{2}}
$$

Hence, the joint probability density of $R$ and $\Theta$ is:

$$
P(R, \Theta) = \frac{1}{2\pi} R e^{-\frac{R^2}{2}}
$$

Since the polar coordinates yield:

$$
R \, dR \, d\Theta = dX \, dY
$$

we obtain the joint probability density of $X$ and $Y$:

$$
P(X,Y) = \frac{1}{2\pi} e^{-\frac{X^2 + Y^2}{2}} \\ = \left(\frac{1}{\sqrt{2\pi}} e^{-\frac{X^2}{2}}\right) \left(\frac{1}{\sqrt{2\pi}} e^{-\frac{Y^2}{2}}\right)
$$

This is precisely the probability density function of two independent, normally distributed random variables $X$ and $Y$, each following a standard normal distribution.

## Code Implementation

```typescript
function randInterval(): number {
  return Math.random();
}

function boxMuller(mu: number, sigma: number): [number, number] {
  const u = randInterval();
  const v = randInterval();
  const x = Math.cos(2 * Math.PI * u) * Math.sqrt(-2 * Math.log(v));
  const y = Math.sin(2 * Math.PI * u) * Math.sqrt(-2 * Math.log(v));
  return [x * sigma + mu, y * sigma + mu];
}

// Usage example
const [value1, value2] = boxMuller(0, 1);
console.log(value1, value2);
// Outputs two normally distributed random numbers
```

To verify that the `boxMuller` function generates numbers that follow a normal distribution, one can generate a large set of random numbers and plot a histogram to compare with a standard normal distribution. You can use libraries such as `plotly` to visualize the histogram and evaluate the output.

Here is a test program that generates a dataset using the `boxMuller` function and performs basic statistical tests, along with plotting the histogram. Assuming you are running in a Node.js environment, you can use `plotly-nodejs` or directly use `plotly.js` in the browser to generate the graph.

First, install the required dependencies:

```bash
npm i plotly.js-dist
```

Then, execute the following code:

```typescript
import * as fs from "fs";
import * as plotly from "plotly.js-dist";

// Generate random numbers following a normal distribution using Box-Muller
function randInterval(): number {
  return Math.random();
}

function boxMuller(mu: number, sigma: number): [number, number] {
  const u = randInterval();
  const v = randInterval();
  const x = Math.cos(2 * Math.PI * u) * Math.sqrt(-2 * Math.log(v));
  const y = Math.sin(2 * Math.PI * u) * Math.sqrt(-2 * Math.log(v));
  return [x * sigma + mu, y * sigma + mu];
}

// Generate n normally distributed random numbers
function generateNormalDistribution(
  mu: number,
  sigma: number,
  n: number
): number[] {
  const values: number[] = [];
  for (let i = 0; i < n / 2; i++) {
    const [value1, value2] = boxMuller(mu, sigma);
    values.push(value1, value2);
  }
  return values;
}

// Generate the data
const mu = 0;
const sigma = 1;
const sampleSize = 10000; // Sample size
const values = generateNormalDistribution(mu, sigma, sampleSize);

// Calculate the mean and variance of the generated random numbers
const mean = values.reduce((acc, val) => acc + val, 0) / values.length;
const variance =
  values.reduce((acc, val) => acc + (val - mean) ** 2, 0) / values.length;

console.log(`Mean: ${mean}`);
console.log(`Variance: ${variance}`);

// Plot the histogram
const trace = {
  x: values,
  type: "histogram",
  xbins: {
    size: 0.1, // Bin size for the histogram
  },
  marker: {
    color: "blue",
  },
  opacity: 0.7,
  name: "Box-Muller Distribution",
};

const data = [trace];

const layout = {
  title: "Generated Normal Distribution",
  xaxis: { title: "Value" },
  yaxis: { title: "Frequency" },
  bargap: 0.05,
};

const graphOptions = {
  filename: "box-muller-distribution",
  fileopt: "overwrite",
};
fs.writeFileSync("box-muller.html", plotly.plot(data, layout, graphOptions));

console.log("Box-Muller distribution data saved as box-muller.html.");
```

This program uses the `boxMuller` function to generate 10,000 random numbers that follow a normal distribution. It calculates the mean and variance of the generated dataset. The random numbers are visualized using a histogram, allowing for a direct comparison with a standard normal distribution. The histogram is saved as a file named `box-muller.html`, which can be opened in a browser for viewing.


The Box-Muller transformation is a method to construct a random variable that follows a Gaussian distribution by using a random variable that follows a uniform distribution.

Box-Muller Transformation


## Algorithm Overview

Programmers are generally familiar with random numbers, and it is well-known that the random numbers generated by computers are often pseudo-random. What exactly is a pseudo-random sequence?

> **Pseudo-random numbers** are a sequence of numbers that appear random but are generated using a **deterministic** algorithm, meaning they are not truly random.

Since randomness is simulated through an algorithm, what kind of algorithm can achieve an effect close to true randomness, and how does it work?

One of the simpler methods is the linear congruential generator (LCG).

The LCG is based on the recursive formula:

$$
N_{j+1} = (A * N_{j} + B) \% M
$$

The most important elements in the LCG are three integers: the multiplier $A$, the increment $B$, and the modulus $M$.

These values, $A$, $B$, and $M$, are constants set by the generator. The period of the LCG is at most $M$, though in most cases, it will be less than $M$. To achieve the maximum period, the following conditions must be met:

- $B$ and $M$ are coprime;
- All prime factors of $M$ divide $A-1$;
- If $M \% 4 = 0$, then $A-1$ must also be divisible by 4;
- $A$, $B$, and $N_{0}$ must be smaller than $M$, and $A$, $B$ must be positive integers.

The advantage of the LCG is that it is **very easy to implement and generates numbers quickly**. However, its drawback is also clear: for a 32-bit number, the maximum period is limited to $2^{32}$, which is inadequate for applications that require high-quality random numbers, such as cryptography.

## Randomness Analysis

With this understanding, one might wonder, how does the LCG simulate a random process? True randomness implies that any number can appear, meaning **all outcomes are equally probable, following a uniform distribution**. So, how does the LCG achieve uniform distribution?

First, we need to understand the period of the LCG. From the definition above, it is clear that for a modulus $M$, the sequence generated by the LCG has a maximum period of $M$. Suppose the recursive formula is $N_{j+1} = (A * N_{j} + B) \mod M$. If the period is $T$, then $N_{k+T} = N_{k}$, and since $N_{k+1} = (A * N_{k} + B) \mod M$, this implies that each value of $N_{k}$ uniquely determines the value of $N_{k+1}$. Thus, the period $T$ must be less than or equal to $M$, because there are only $M$ possible distinct integers when taken modulo $M$. The $(M+1)$-th number will necessarily be the same as one of the previous numbers, and since the recursive relationship is one-to-one, the subsequent sequence will repeat, leading to a period $T \leq M$.

Next, it is important that the multiplier and modulus be coprime. This is easy to understand: consider $N_{j+1} = (A * N_{j} + B) \mod M$. If $A$ and $M$ are not coprime, suppose $A = a * d$ and $M = m * d$ where $d > 1$. Expanding the recursive formula yields $N_{j+1} = A * N_{j} + B + k * M$. Since $B$ is constant, it can be treated as a shift, and by subtracting $B$ from both sides, we get $N_{j+1} - B = (a * (N_{j} - B) + a * B + k * m) * d$. This shows that all values of $N_{j+1} - B$ contain the factor $d$. For example, if $d = 2$, the sequence of $M$ possible numbers will only yield even numbers plus the shift $B$, meaning the period $T \leq M / 2$. This disrupts the uniform distribution of the sequence.

A few simple examples can illustrate this. Suppose $A = 3$, $M = 5$, and $N_0 = 2$, the sequence would be $\{2, 1, 3, 4, 2, 1, \dots\}$, with a period of 5. If we set $A = 6$, $M = 10$, and $N_0 = 2$, the sequence would be $\{2, 2, 2, \dots\}$, with a period of 1.

Returning to the initial question, how does the LCG achieve uniform distribution? As seen from the discussion above, with carefully chosen parameters, it is possible to construct a sequence with a period of $M$, where each number appears exactly once in each cycle. This ensures that the frequency of appearance for each number in the sequence is the same, thus satisfying the uniform distribution requirement.

## Solving Linear Congruences

Having understood the relationship between random distribution and the linear congruential method, let's extend our knowledge to learn how to solve linear congruences. This is not just a theoretical mathematical problem; it has numerous practical applications. For instance:

> On a circular track, two frogs, $A$ and $B$, start from positions $x$ and $y$ respectively, with $A$ jumping $m$ units and $B$ jumping $n$ units each time. The total circumference of the track is $L$. If both frogs start at the same time, they are said to meet if they land on the same point. The question is, after how many jumps will the two frogs meet at the earliest?

Based on these conditions, we can formulate the following equation:

$$
(x + m*k) ≡ (y + n*k) \pmod{L}
$$

Where $≡$ denotes congruence modulo $L$.

Expanding this gives:

$$
x + m*k = y + n*k + L*k'
$$

Rearranging terms, we get:

$$
x - y = (n - m)*k + L*k'
$$

Thus,

$$
(x - y) ≡ (n - m)*k \pmod{L}
$$

Let $n - m = a$ and $x - y = b$, \
yielding the standard linear congruence:

$$
a*k ≡ b \pmod{L}
$$

> Definition: If $a$ and $b$ are integers, the expression $a*x ≡ b \pmod{M}$, where $x$ is an unknown integer, is called a linear congruence. Here, $≡$ and $(\pmod{M})$ indicate that both sides are taken modulo $M$.

To solve a linear congruence, we proceed with the following transformations:

1. The standard linear congruence $a*x ≡ b \pmod{M}$ is equivalent to the Diophantine equation $a*x + M*y = b$.
2. Let $d$ be the greatest common divisor (gcd) of $a$ and $M$, denoted $gcd(a,M) = d$. If the equation has a solution, $d$ must divide $b$. We rewrite the equation as $a_0*x + M_0*y = b_0$, where $a = a_0*d$, $M = M_0*d$, and $b = b_0*d$. Here, $a_0$ and $M_0$ are coprime, meaning $gcd(a_0, M_0) = 1$.
3. Let $x = x_0*b_0$ and $y = y_0*b_0$. The equation becomes $a_0*x_0 + M_0*y_0 = 1$, or equivalently $a_0*x_0 ≡ 1 \pmod{M_0}$.

Finally, we use modular inversion to compute $x_0$.

> **Theorem:** If $a$ and $M$ are coprime integers and $M > 1$, there exists a unique inverse of $a$ modulo $M$.

This theorem can be proven as follows:

Since $a$ and $M$ are coprime, there exist integers $s$ and $t$ such that $s*a + t*M = 1$. (If $a$ and $M$ have a common divisor $d > 1$, then $s*a + t*M = d*k$, which cannot equal 1). Taking the equation modulo $M$, we get $s*a ≡ 1 \pmod{M}$. Thus, $s$ is the modular inverse of $a$ modulo $M$.

Let $\bar{a}$ denote the modular inverse of $a$ modulo $M$, so $x_0 ≡ \bar{a} \pmod{M_0}$, meaning $x_0 ≡ \bar{a} + k*M_0$.

For example:

To solve $5*x ≡ 7 \pmod{9}$:

1. Since $gcd(5,9) = 1$, we know that $5$ has an inverse modulo $9$. Using the extended Euclidean algorithm, we find $2*5 + (-1)*9 = 1$.
2. Therefore, $2$ is the inverse of $5$ modulo $9$. Multiplying both sides of the original equation by $2$ gives $2*5*x ≡ 2*7 \pmod{9}$.
3. Simplifying, we get $x ≡ 14 \pmod{9} ≡ 5 \pmod{9}$.
4. Thus, the solution is $x = 5 + 9k$.

In summary, we can solve a general linear congruence $a*x ≡ b \pmod{L}$ by transforming it into a standard congruence $a_0*x_0 ≡ 1 \pmod{M_0}$. After solving the standard congruence, we map the solution back. If the solution to the standard equation is $x_0 \in \{x = p + q*M_0\}$, then the solution to the original equation is $x \in \{x = \frac{b}{d}*p + q'*M_0\}$.

Through this, we have outlined the process of solving linear congruences and deepened our understanding of the linear congruential method.

## Insecurity of the Linear Congruential Method

The linear congruential method (LCG) is a pseudo-random number generation technique based on deterministic mathematical algorithms. Although it can meet the needs for general pseudo-random numbers, it is not suitable for high-security applications, such as cryptography or applications requiring strong randomness. Below are some key considerations regarding the insecurity of LCG:

1. **Determinism**: LCG is deterministic, meaning that the same seed and parameters will always produce the same sequence of random numbers. This poses a security risk, as an attacker could reproduce the sequence by guessing the seed and parameters, breaking the randomness.
2. **Periodicity**: The random number sequences generated by LCG are periodic. Once the sequence reaches its period, it starts repeating. This periodicity can cause problems in applications that require long-term randomness.
3. **Non-uniformity**: In some cases, LCG-generated sequences may not be uniformly distributed, especially when parameters are poorly chosen, leading to statistical biases.
4. **Security**: LCG is unsuitable for cryptographic or high-randomness security applications. For such use cases, cryptographically secure pseudo-random number generators (CSPRNGs) must be employed.

In conclusion, while LCG can be used for general pseudo-random number generation in simulations, games, or random testing, it should not be used in applications that require high security and strong randomness.

## Code Implementation

Below is the implementation of a Linear Congruential Generator (LCG) using TypeScript, along with a simple program to test the effectiveness of its randomness.

### LCG Implementation

```typescript
class LinearCongruentialGenerator {
  private seed: number;
  private readonly a: number;
  private readonly c: number;
  private readonly m: number;

  constructor(
    seed: number,
    a: number = 1664525,
    c: number = 1013904223,
    m: number = 2 ** 32
  ) {
    this.seed = seed;
    this.a = a;
    this.c = c;
    this.m = m;
  }

  public next(): number {
    this.seed = (this.a * this.seed + this.c) % this.m;
    return this.seed;
  }

  public nextFloat(): number {
    return this.next() / this.m;
  }
}

// Example usage
const lcg = new LinearCongruentialGenerator(12345);
console.log(lcg.next());
// Outputs a random integer
console.log(lcg.nextFloat());
// Outputs a random floating-point number between 0 and 1
```

### Code to Test Randomness

We can test the randomness of the generator by generating a set of random numbers and plotting their distribution. Below is a simple test program:

```typescript
function testRandomness(
  generator: LinearCongruentialGenerator,
  iterations: number = 10000
): void {
  const results: number[] = new Array(10).fill(0);

  for (let i = 0; i < iterations; i++) {
    const randomValue = Math.floor(generator.nextFloat() * 10);
    results[randomValue]++;
  }

  console.log("Randomness Test Results:");
  results.forEach((count, index) => {
    console.log(`${index}: ${"*".repeat(count / 100)}`);
  });
}

// Example usage
const lcgTest = new LinearCongruentialGenerator(12345);
testRandomness(lcgTest);
```

This test program generates a set of random numbers and counts the occurrences of each number. By observing the distribution of the output, we can make an initial assessment of the randomness of the generator.


Linear congruential method is a pseudo-random number generation method that generates a random number sequence based on a deterministic mathematical algorithm.

Linear Congruential for Pseudorandom Number


This article will introduce some commonly used classical ciphers, which have been applied in history, reflecting the wisdom of ancient people. In ancient times, with low productivity and backward computing devices, classical ciphers had a certain protective effect. However, with the improvement of computer computing power nowadays, these classical ciphers have become very vulnerable and no longer practical.

Nowadays, there are many methods for breaking these classical ciphers. When I have the opportunity later on, I will summarize some of the decryption techniques for classical ciphers.

## Caesar Cipher

When it comes to classical ciphers, one classic example is the Caesar Cipher. The Caesar Cipher is a simple substitution encryption method based on letter shifting.

Core Idea: The core idea of the Caesar Cipher is to obtain the ciphertext by shifting each letter in the plaintext by a fixed number. This number of shifts is called the offset or key.

Algorithm Steps:

1. Determine the offset, i.e., the number of shifts.
2. For encryption, shift each letter in the plaintext backward by the offset to obtain the ciphertext.
3. For decryption, shift each letter in the ciphertext forward by the offset to obtain the plaintext.

TypeScript Implementation:

```typescript
function caesarCipherEncrypt(plainText: string, shift: number): string {
  let result = "";
  for (let i = 0; i < plainText.length; i++) {
    let char = plainText[i];
    if (char.match(/[a-z]/i)) {
      let code = plainText.charCodeAt(i);
      if (code >= 65 && code <= 90) {
        char = String.fromCharCode(((code - 65 + shift) % 26) + 65);
      } else if (code >= 97 && code <= 122) {
        char = String.fromCharCode(((code - 97 + shift) % 26) + 97);
      }
    }
    result += char;
  }
  return result;
}

function caesarCipherDecrypt(cipherText: string, shift: number): string {
  return caesarCipherEncrypt(cipherText, 26 - shift);
}
```

This TypeScript implementation provides encryption and decryption functions for the Caesar Cipher. The encryption function accepts plaintext and the offset as parameters and returns ciphertext, while the decryption function accepts ciphertext and the offset as parameters and returns plaintext.

## Rail Fence Cipher

The Rail Fence Cipher is a classical substitution encryption method based on rearranging the letters in the plaintext. The core idea of the Rail Fence Cipher is to rearrange the letters in the plaintext to form a matrix with a specific number of rows, and then read the letters in the matrix in a certain order to obtain the ciphertext.

Algorithm Steps:

1. Determine the height of the rail fence, i.e., the number of rows in the matrix.
2. Write the plaintext into a matrix according to the height of the rail fence.
3. Read the letters in the matrix in a specific order to obtain the ciphertext.
4. For decryption, knowing the height of the rail fence is necessary to correctly rearrange the letters in the ciphertext to obtain the plaintext.

Idea:
The Rail Fence Cipher is a substitution encryption method based on rearranging letters. Encryption and decryption are achieved by reading the letters in the matrix in a specific order.

TypeScript Implementation:

```typescript
function railFenceCipherEncrypt(plainText: string, height: number): string {
  let rail: string[][] = new Array(height).fill(null).map(() => []);
  let directionDown = false;
  let row = 0;
  for (let char of plainText) {
    rail[row].push(char);
    if (row === 0 || row === height - 1) {
      directionDown = !directionDown;
    }
    directionDown ? row++ : row--;
  }
  let result = "";
  for (let i = 0; i < height; i++) {
    result += rail[i].join("");
  }
  return result;
}

function railFenceCipherDecrypt(cipherText: string, height: number): string {
  let rail: string[][] = new Array(height).fill(null).map(() => []);
  let directionDown = false;
  let row = 0;
  for (let char of cipherText) {
    rail[row].push("x"); // Placeholder, will be replaced later
    if (row === 0 || row === height - 1) {
      directionDown = !directionDown;
    }
    directionDown ? row++ : row--;
  }
  let index = 0;
  for (let i = 0; i < height; i++) {
    for (let j = 0; j < rail[i].length; j++) {
      if (rail[i][j] === "x") {
        rail[i][j] = cipherText[index++];
      }
    }
  }
  directionDown = false;
  row = 0;
  let result = "";
  for (let i = 0; i < cipherText.length; i++) {
    result += rail[row].shift();
    if (row === 0 || row === height - 1) {
      directionDown = !directionDown;
    }
    directionDown ? row++ : row--;
  }
  return result;
}
```

This TypeScript implementation provides encryption and decryption functions for the Rail Fence Cipher. The encryption function accepts plaintext and the height of the rail fence as parameters and returns ciphertext, while the decryption function accepts ciphertext and the height of the rail fence as parameters and returns plaintext.

## Route Cipher

The Route Cipher, also known as the Path Transposition Cipher, is a substitution encryption method based on matrix rearrangement. Its core idea is to read the characters in the matrix according to a predetermined path order to encrypt or decrypt messages. The essence of the Route Cipher is to arrange the plaintext into a matrix along a specific path and then read the characters in the matrix according to the predetermined path order to obtain the ciphertext.

Algorithm Steps:

1. Arrange the plaintext into a matrix along a specific path.
2. Read the characters in the matrix according to the predetermined path order to obtain the ciphertext.
3. For decryption, read the characters in the ciphertext according to the same path order to reconstruct the plaintext.

TypeScript Implementation:

```typescript
function routeCipherEncrypt(plainText: string, rows: number, cols: number, path: number[][]): string {
  let matrix: string[][] = new Array(rows).fill(null).map(() => new Array(cols).fill(""));
  let index = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (index < plainText.length) {
        matrix[r][c] = plainText[index++];
      }
    }
  }
  let result = "";
  for (let step of path) {
    let [r, c] = step;
    result += matrix[r][c];
  }
  return result;
}

function routeCipherDecrypt(cipherText: string, rows: number, cols: number, path: number[][]): string {
  let matrix: string[][] = new Array(rows).fill(null).map(() => new Array(cols).fill(""));
  let index = 0;
  for (let step of path) {
    let [r, c] = step;
    matrix[r][c] = cipherText[index++];
  }
  let result = "";
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      result += matrix[r][c];
    }
  }
  return result;
}
```

This TypeScript implementation provides encryption and decryption functions for the Route Cipher. The encryption function accepts plaintext, the number of rows and columns in the matrix, and the path as parameters, and returns ciphertext. The decryption function accepts ciphertext, the number of rows and columns in the matrix, and the path as parameters, and returns plaintext.

It is worth noting that:

- The Route Cipher is based on path transposition.
- It uses a matrix (usually a square matrix) to represent the plaintext, and then selects characters for encryption by following a predetermined path in the matrix.
- Encryption paths can be straight lines, curves, or any other shape, with each path representing a key.
- During decryption, knowledge of the same path is required to reverse the operation.

## Vigenère Cipher

The Vigenère Cipher is a polyalphabetic substitution cipher and is one of the most famous ciphers in classical cryptography. It encrypts plaintext using a keyword, employing the concept of multiple Caesar ciphers to achieve a more complex substitution encryption.

Core Idea:
The core idea of the Vigenère Cipher is to encrypt plaintext using a keyword (key). Each letter in the keyword corresponds to a shift number in the alphabet, forming a set of Caesar ciphers. Then, for each letter in the plaintext, a shift is performed using the corresponding shift number from the keyword to obtain the ciphertext.

Algorithm Steps:

1. Choose a keyword as the key.
2. Repeat the keyword until it matches the length of the plaintext.
3. For encryption, shift each letter in the plaintext by the corresponding letter of the keyword at the same position to obtain the ciphertext.
4. For decryption, use the same keyword to shift each letter in the ciphertext by the corresponding letter of the keyword at the same position in reverse to obtain the plaintext.

The Vigenère Cipher is a polyalphabetic substitution cipher that achieves encryption and decryption by using a keyword and the concept of multiple Caesar ciphers. Compared to a single Caesar cipher, the Vigenère Cipher provides a more complex encryption method, making decryption more difficult.

TypeScript Implementation:

```typescript
function vigenereCipherEncrypt(plainText: string, key: string): string {
  const alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  let encryptedText = "";
  key = key.toUpperCase();
  for (let i = 0, j = 0; i < plainText.length; i++) {
    const char = plainText[i].toUpperCase();
    if (alphabet.includes(char)) {
      const shift = alphabet.indexOf(key[j % key.length]);
      const charIndex = alphabet.indexOf(char);
      const encryptedIndex = (charIndex + shift) % alphabet.length;
      encryptedText += alphabet[encryptedIndex];
      j++;
    } else {
      encryptedText += char;
    }
  }
  return encryptedText;
}

function vigenereCipherDecrypt(cipherText: string, key: string): string {
  const alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  let decryptedText = "";
  key = key.toUpperCase();
  for (let i = 0, j = 0; i < cipherText.length; i++) {
    const char = cipherText[i].toUpperCase();
    if (alphabet.includes(char)) {
      const shift = alphabet.indexOf(key[j % key.length]);
      const charIndex = alphabet.indexOf(char);
      const decryptedIndex = (charIndex - shift + alphabet.length) % alphabet.length;
      decryptedText += alphabet[decryptedIndex];
      j++;
    } else {
      decryptedText += char;
    }
  }
  return decryptedText;
}

// Example usage
const plainText = "HELLO";
const key = "KEY";
const encryptedText = vigenereCipherEncrypt(plainText, key);
console.log("Encrypted Text: ", encryptedText); // Output encrypted text
const decryptedText = vigenereCipherDecrypt(encryptedText, key);
console.log("Decrypted Text: ", decryptedText); // Output decrypted text
```

In this example, the `vigenereCipherEncrypt` function encrypts plaintext, and the `vigenereCipherDecrypt` function decrypts ciphertext. These functions use a keyword to encrypt plaintext and decrypt ciphertext, employing the concept of the Vigenère Cipher.

The Vigenère Cipher has been widely used historically and still holds value in modern cryptography. While it can be cracked using modern cryptographic analysis techniques, it still provides a certain level of protection under certain conditions.

## Baconian Cipher

The Baconian cipher is an ancient cryptographic technique named after the 16th-century English philosopher, Francis Bacon. This cipher utilizes the form of letters to encrypt textual information into a series of different symbols.

In the Baconian cipher, typically two different symbols, often represented as "A" and "B" (or "a" and "b"), are used to represent different letters in the plaintext. For example, "A" might represent the letter "A" in the plaintext, while "B" might represent other letters. Through this method, textual information can be transformed into a sequence of "A" and "B" characters, thus achieving encryption.

Below are the algorithm steps for the Baconian cipher:

1. Firstly, create a Baconian cipher alphabet, which includes the mapping relationship between plaintext letters and their corresponding Baconian cipher symbols. Typically, two symbols, A and B, are used to represent letters.

2. Convert the plaintext to uppercase and remove any characters other than letters.

3. Iterate over each letter in the plaintext:
   - For each letter, find its corresponding Baconian cipher symbol in the alphabet.
   - Concatenate the found Baconian cipher symbols to form the ciphertext.

Here's a TypeScript implementation:

```typescript
class BaconCipher {
  private static baconianAlphabet: { [key: string]: string } = {
    A: "AAAAA",
    B: "AAAAB",
    C: "AAABA",
    D: "AAABB",
    E: "AABAA",
    F: "AABAB",
    G: "AABBA",
    H: "AABBB",
    I: "ABAAA",
    J: "ABAAB",
    K: "ABABA",
    L: "ABABB",
    M: "ABBAA",
    N: "ABBAB",
    O: "ABBBA",
    P: "ABBBB",
    Q: "BAAAA",
    R: "BAAAB",
    S: "BAABA",
    T: "BAABB",
    U: "BABAA",
    V: "BABAB",
    W: "BABBA",
    X: "BABBB",
    Y: "BBAAA",
    Z: "BBAAB",
  };

  public static encrypt(plaintext: string): string {
    // Convert plaintext to uppercase and remove non-alphabetic characters
    plaintext = plaintext.toUpperCase().replace(/[^A-Z]/g, "");

    let ciphertext = "";
    for (let i = 0; i < plaintext.length; i++) {
      const letter = plaintext[i];
      const baconianLetter = this.baconianAlphabet[letter];
      if (baconianLetter) {
        ciphertext += baconianLetter;
      }
    }
    return ciphertext;
  }

  public static decrypt(ciphertext: string): string {
    let plaintext = "";
    for (let i = 0; i < ciphertext.length; i += 5) {
      const chunk = ciphertext.substr(i, 5);
      const letter = this.getBaconianLetter(chunk);
      if (letter !== null) {
        plaintext += letter;
      }
    }
    return plaintext;
  }

  private static getBaconianLetter(baconianCode: string): string | null {
    for (const [key, value] of Object.entries(this.baconianAlphabet)) {
      if (value === baconianCode) {
        return key;
      }
    }
    return null; // If no matching letter found
  }
}

// Example usage:
const plaintext = "HELLO";
const ciphertext = BaconCipher.encrypt(plaintext);
console.log("Plaintext:", plaintext);
console.log("Ciphertext:", ciphertext);

const decryptedText = BaconCipher.decrypt(ciphertext);
console.log("Decrypted Text:", decryptedText);
```

This TypeScript code implements the encryption and decryption functionality of the Baconian cipher. You can pass the plaintext to the `BaconCipher.encrypt()` method for encryption or pass the ciphertext to the `BaconCipher.decrypt()` method for decryption.

## Affine Cipher

The Affine cipher is an ancient substitution cipher that combines the concepts of the Caesar cipher and linear algebra. It encrypts each letter in the plaintext by using two values called the encryption key (a) and the offset key (b).

The encryption formula for the Affine cipher is $E(x) = (ax + b) \mod m$, where:

- $x$ is the numerical representation of the plaintext letter in the alphabet (usually starting from 0, where 'a' is 0, 'b' is 1, and so on).
- $a$ and $b$ are the encryption keys.
- $m$ is the size of the alphabet (usually 26 for English).

To decrypt, the modular multiplicative inverse of the encryption key is used. The encryption key $a$ must be coprime with the alphabet size $m$ to ensure that each letter can be correctly encrypted and decrypted.

Below are the algorithm steps for the Affine cipher:

1. Choose appropriate encryption key $a$ and offset key $b$.
2. Convert each letter in the plaintext to its numerical representation $x$ in the alphabet.
3. Apply the Affine encryption formula to each numerical value $x$ to obtain the corresponding ciphertext value.
4. Convert the ciphertext numerical values back to letter representations in the alphabet.

Here's a TypeScript implementation:

```typescript
class AffineCipher {
  private static readonly alphabetSize: number = 26; // Size of the English alphabet

  public static encrypt(plaintext: string, a: number, b: number): string {
    let ciphertext = "";
    plaintext = plaintext.toUpperCase().replace(/[^A-Z]/g, ""); // Convert to uppercase and remove non-alphabetic characters
    for (let i = 0; i < plaintext.length; i++) {
      const char = plaintext[i];
      const charCode = char.charCodeAt(0) - "A".charCodeAt(0); // Convert letter to numerical value from 0 to 25
      const encryptedCharCode = (a * charCode + b) % this.alphabetSize; // Affine encryption formula
      const encryptedChar = String.fromCharCode(encryptedCharCode + "A".charCodeAt(0)); // Convert numerical value back to letter
      ciphertext += encryptedChar;
    }
    return ciphertext;
  }

  public static decrypt(ciphertext: string, a: number, b: number): string {
    let plaintext = "";
    const aInverse = this.modInverse(a, this.alphabetSize); // Calculate the modular inverse of encryption key a
    for (let i = 0; i < ciphertext.length; i++) {
      const char = ciphertext[i];
      const charCode = char.charCodeAt(0) - "A".charCodeAt(0); // Convert letter to numerical value from 0 to 25
      const decryptedCharCode = (aInverse * (charCode - b + this.alphabetSize)) % this.alphabetSize; // Affine decryption formula
      const decryptedChar = String.fromCharCode(decryptedCharCode + "A".charCodeAt(0)); // Convert numerical value back to letter
      plaintext += decryptedChar;
    }
    return plaintext;
  }

  private static modInverse(a: number, m: number): number {
    for (let i = 1; i < m; i++) {
      if ((a * i) % m === 1) {
        return i;
      }
    }
    return -1; // If no modular inverse exists, return -1
  }
}

// Example usage:
const plaintext = "HELLO";
const a = 5; // Encryption key
const b = 8; // Offset key
const ciphertext = AffineCipher.encrypt(plaintext, a, b);
console.log("Plaintext:", plaintext);
console.log("Ciphertext:", ciphertext);

const decryptedText = AffineCipher.decrypt(ciphertext, a, b);
console.log("Decrypted Text:", decryptedText);
```

This TypeScript code implements the encryption and decryption functionality of the Affine cipher. You can pass the plaintext to the `AffineCipher.encrypt()` method for encryption or pass the ciphertext to the `AffineCipher.decrypt()` method for decryption.


This article explores classical ciphers historically used. In the past, amid low productivity and primitive computing, these ciphers offered protection.

原点日志

CRYPTOGRAPHY

Box-Muller Transformation

Linear Congruential for Pseudorandom Number

Some Classical Ciphers and Implementations