Mathematics in War: Military Cryptography

Mathematics in War:

Military Cryptography!

After a year of systematic and specialized study, as a student majoring in Mathematics and Applied Mathematics, I have never stopped exploring the mysteries of mathematics. Taking advantage of summer social practice, we walked together, embarking on the door of cryptography with great interest.

Throughout history, the application of mathematics in war has often been overlooked, and its importance has been ignored. However, as a pillar of the scientific world, many disciplines derived from it play a crucial role in warfare. Military cryptography is one of them. Nowadays, we are often thrilled by the intelligence transmission in spy films and deeply impressed by their cleverness. With admiration for them, we embarked on this exciting journey.

Caesar’s Secret Message

——Caesar’s Cipher

In the “Commentarii de Bello Gallico”, it describes how Caesar used ciphers to transmit information, known as the “Caesar Cipher”. It is a substitution cipher that encrypts by shifting letters three places forward. For example, replacing the letter A with D and B with E. Therefore, Caesar is one of the ancient generals who first used encrypted messages, and this method of encryption is called the Caesar Cipher, which opens the door for us to understand cryptography.

Mathematics in War: Military Cryptography

Cryptographic System

——Basic Elements of Communication Cryptography

In cryptography, the text content that is clearly expressed in a universal language to be transmitted is called plaintext, and the symbols formed from plaintext through transformation for encrypted communication are called ciphertext. The process of transforming plaintext into ciphertext according to agreed transformation rules is called encryption, and the process of transforming ciphertext back into plaintext according to the transformation rules by the recipient is called decryption. The process of analyzing intercepted documents to find out the transformation rules by the enemy is called cryptanalysis. To enhance the security of the cipher, the transformation rules must be designed as complex as possible, and a “keyword” must be designed to derive the transformation rules. This keyword is called a key.

Crytography is an applied branch of theoretical mathematics, so each concept must be clearly defined: a cryptographic system consists of five parts:

Plaintext Set μ

Ciphertext Set π

Key Set K

Encryption Transformation Set E, Encryption Algorithm e

Decryption Transformation Set D, Decryption Algorithm d

This system is composed of these five parts.

War is a confrontational behavior; while some are encoding ciphers, others are decoding them. Cryptography consists of two parts: cryptographic encoding and cryptanalysis.

The cryptographer, when encoding a cipher, must assume that the cryptanalyst has some favorable conditions when attempting to decode a cipher. Based on these conditions, the methods of cryptanalysis can be divided into three categories:

Ciphertext-Only Attack (the cryptanalyst has some ciphertext)

Known-Plaintext Attack (the cryptanalyst has some ciphertext and its corresponding plaintext)

Chosen-Plaintext Attack (the cryptanalyst can obtain ciphertext corresponding to any plaintext of their choice)

DES Algorithm

——Binary Encoded Data

The DES (Data Encryption Standard) algorithm was publicly released in 1975 and established as a national standard by the US National Bureau of Standards in 1977. It was designed for US government agencies to encrypt computer systems or networks in non-military applications and was cracked in 1997.

DES is designed for binary encoded data, and it encrypts 64-bit binary numbers of plaintext into 64-bit binary numbers of ciphertext using a key. To force the US government to relax its export restrictions on encryption products, RSA Data Security Inc. launched a competition called the “Secret Key Challenge” in 1997. After 140 days, someone cracked it and won the competition and a reward. This announced to the world that DES was no longer secure. Although a specific key of DES can be cracked using an exhaustive search method, it indicates that there is no practical ciphertext-only attack method for DES. Therefore, to understand DES, the main steps of the DES encryption algorithm are as follows:

(1) Input plaintext, which is encoded in binary, processed in groups of 64 bits during encryption;

(2) Initial permutation, disrupting the order according to a fixed rule;

(3) Product transformation, the core part of the DES algorithm;

(4) Inverse initial permutation, the inverse transformation of the initial permutation;

(5) Output ciphertext.

In 1976, Diffie and Hellman proposed a new idea: a cryptographic system could be designed with two keys, one public and the other kept secret. This is known as “public key cryptography”, abbreviated as “public key“. The key determines the encryption and decryption transformations, which are inverse transformations of each other. However, deriving one from the other is not always easy. The year after Diffie and Hellman’s paper was published, Ronald Rivest, Adi Shamir, and Leonard Adleman proposed the first relatively complete public key cryptographic system, known as the RSA system.

It is worth mentioning that with the maturation of distributed computing and quantum computer theory, the security of RSA encryption is being challenged by computing speeds far exceeding those of classical computers. However, this also aligns with the characteristic of cryptography influencing and promoting other disciplines, and in the future, better cryptographic systems will undoubtedly emerge!

Purple Machine

——Japan’s “Enigma”

The “Purple Cipher” is a machine-generated cipher, and the machine used to create this cipher is called the 97式欧文印字机 in Japan. This cipher machine can not only input manually but also has encryption/decryption conversion functions. It controls the up and down movements of the conversion lever, reversing the input and output ends. During encryption, it is set to the “construction” position, and the “encryption” signal light is on; during decryption, it is set to the “interpretation” position, and the “decryption” signal light is on.

During encryption, the cipher operator must first consult a thick key starting book, according to the key to be used that day, insert the letter signal wires into the sockets of the connection board, and use the key wheel adjustment device to rotate the key wheel to align the numbers displayed in the key wheel window with those indicated in the key starting book. Then, the operator inputs plaintext on the typewriter. Each time a letter of plaintext is input, one or more key wheels rotate to a new position, thus changing the signal circuit path, i.e., changing the substitution table. The same letter in plaintext may be represented by different letters in ciphertext in different places, and a letter in ciphertext may represent different letters in plaintext in different places.

Moonlight Sonata

——Enigma Machine

Coventry is an ancient city with a long history, yet this historic city became a wasteland due to the bombing mission personally ordered by Hitler under the code name “Moonlight Sonata“! So, what caused all this? It relates to the intelligence war concerning ciphers.

In August 1939, British intelligence obtained an advanced German cipher machine called “Enigma” (also known as “the Riddle“). After research, it was discovered that the German army had equipped this cipher machine in its military communications departments as early as the early 1930s. Hitler had been using the accompanying codebook and confidently believed that this latest and most complex communication cipher could not be deciphered.

The British government immediately organized manpower and material resources to decipher the “Enigma”. After a long period of effort, this “super cipher” was ultimately deciphered by British cryptanalysts led by Turing. The film “The Imitation Game” vividly recreates this historical fact. Just as the German army was preparing for an air raid, someone raised doubts about the confidentiality of the “Enigma”, leading to the formulation of the bombing plan “Moonlight Sonata” to verify their suspicions. Of course, war is no child’s play; another reason for formulating the bombing plan was that Coventry was a major industrial city in the UK; its destruction could weaken Britain’s resistance capabilities, benefiting the German army’s offensive. When the UK intercepted this intelligence, Prime Minister Churchill faced a difficult choice, ultimately having to sacrifice Coventry for the greater good.

History ultimately proved that Churchill’s decision to sacrifice this small city for the larger picture was correct. Although Coventry suffered heavy losses, the British intelligence agency utilized this incident to dispel German doubts and intercepted significant enemy intelligence multiple times, contributing greatly to defeating German fascism and winning World War II.

The Dancing Man

——Sherlock Holmes

In one of the short stories of Sherlock Holmes titled “The Dancing Man”, Holmes first received the following drawing:

Firstly, for the same dancing man, some hold flags while others do not, so it must be assumed that in the first note given to Holmes, the phrase is short and can only slightly ascertain that the dancing man with a higher frequency represents E (E is the most common letter in English; it appears so frequently that it is the most common even in a short sentence. Among the fifteen symbols on the first note, four are exactly the same, making it reasonable to estimate it as E).

However, now comes the most difficult question. Because, apart from E, the order of frequency of the letters in English is not very clear. This order may be the opposite in ordinary printed text and a short sentence. Generally, the order of letters by frequency is T, A, O, I, N, S, H, R, D, L; however, T, A, O, I appear almost equally. If one were to try every combination until a meaningful one is found, it would be an endless task. Therefore, Holmes could only wait for new materials to arrive. When the second visit came, he indeed received two more short sentences and what seemed to be a single word, which was a combination of five symbols without flags. In this single word, Holmes found that the second and fourth symbols are both E. Following this line of thought, he ultimately deciphered the message conveyed by the dancing man.

This method of decryption follows more observation and experience, which is also the basic principle of cryptanalysis.

Ultimate Decryption

——Decryption of Ciphers

The methods of decrypting ciphers are opposed to the methods of encoding them. The decryption of ciphers, in principle, follows observation and experience, using inductive and deductive methods, and the steps include: analysis, hypothesis, speculation, and verification. The three key elements of decryption are: frequency characteristics, connection characteristics, and repetition characteristics. People use these three characteristics to decrypt ciphers. Below is a brief introduction to these three elements.

1. Frequency Characteristics: Cryptanalysts have long discovered that in various languages, the frequency of usage of each letter varies, some being higher and some lower; this phenomenon is called the bias phenomenon. Below is a simple program to illustrate this. First, we input a short article to analyze the letter usage frequency:

2. Connection Characteristics: For example, in English, the letter q almost always connects to u, except when it is omitted. This is the post-connection method in connection characteristics. For the letter x, it is almost always preceded by i and e, and only rarely connects with o and a. This is the pre-connection method in connection characteristics. Besides these two methods, there is also a disjoint connection method. For example, between two e’s, the appearance frequency of r is very high.

3. Repetition Characteristics: The phenomenon of strings of two or more characters repeating is called the repetition characteristic of the language. For example, in English: th, tion, tious are strings that appear repeatedly.

Examples

——Guessing Method

First, we can use the above three characteristics as breakthrough points to decrypt the cipher:

First, applying the frequency characteristics of the language to analyze this ciphertext, we can find and correspondingly speculate on the high-frequency letter groups. For example, we can speculate that e corresponds to N. From the frequency characteristics of the language, we can only obtain high-frequency letter groups. Therefore, we turn to the second characteristic of language: the connection characteristics of the language. First, we focus on the three high-frequency vowels in the plaintext: a, I, o. Their characteristic is that they almost do not connect with each other. Therefore, the ciphertext OUA is likely to represent AIO. As for which corresponds to which, it can be determined based on their connection frequency. It can be seen that OA=io, so U=a. NU appears five times, which can be assumed to be ea. Based on this step-by-step analysis, we find that T represents n, and Y is always connected to N (e), so it is similar to the characteristics of h, thus Y represents h. Based on this analysis, we can obtain a partial decryption text.

Next, we need to use some unique methods of cryptography: the guessing method to perform decryption.

Observing the beginning of the ciphertext, there is an ith, which allows us to guess that M represents w. Then we fill in M and see that the same line has the string with….n..nown, allowing us to guess that K is k and J is u, thus obtaining an incomplete decryption table.

If it is a password table generated by a key, then there must be an L between HJ and M. Therefore, we replace L with v to see if it holds, then fill in ABCDEFG… step by step to confirm. Finally, we observe that:

From the composition of the words, we can know that X must represent c. Thus, step by step decryption will eventually yield a complete cipher table.

END

Every like you give, I take it seriously as a fondness.

Related posts

Leave a Comment Cancel reply