Cryptanalysis|Simon Singh| Amazon
When I was reading Simon Singh's "Cryptanalysis", there was an explanation about the mechanism of Enigma, and it seemed that I could implement it unexpectedly, so I made it.
The source code is on GitHub.
Enigma converts one character entered on the keyboard into another and encrypts it.
A cipher that converts a character entered in this way into another character is called a ** substitution cipher **. Caesar cipher is famous as the same substitution cipher.
In Caesar cipher, characters are encrypted by shifting them by a certain number. For example, in the Caesar cipher that shifts three characters, characters are converted such as "a-> X", "b-> Y", "c-> Z", and "d-> A".
** Caesar cipher conversion table that shifts 3 characters **
Since there is only one type of conversion table, a cipher such as Caesar cipher is called ** single transliteration cipher **.
Since the Caesar cipher simply shifts the characters, the same characters in the plaintext are always encrypted with the same characters (the "a" in the plaintext is always the "X" in the cipher). As a result, the single transliteration type cipher has a feature that the tendency of the appearance frequency of characters does not change between plaintext and ciphertext.
For example, the letter "e" appears most often in English. In the Caesar cipher that shifts three characters, "e" is converted to "B". Therefore, the most frequently appearing character in ciphertext is likely to be "B".
Although it is a little information, many single transliteration ciphers can be deciphered by analyzing such hints by adding the grammar of the plaintext language and the characteristics of words.
In this way, the method of deciphering the code based on the statistical information of characters is called frequency analysis. Single transliteration ciphers such as the Caesar cipher are vulnerable to frequency analysis.
The problem with single substitution ciphers is that there is only one type of conversion table for encryption. As a result, the same characters in plaintext are always encrypted into the same characters, leaving the statistical characteristics of plaintext in the ciphertext.
Therefore, an encryption method (** multi-substitution cipher **) in which a plurality of conversion tables are prepared has been devised. In multi-table substitution cipher, multiple conversion tables are prepared and the conversion table used is switched for each plaintext character.
** Simple multi-substitution cipher example **
Here, the conversion table is switched by increasing the shift amount of the Caesar cipher character by character. (* Actually, it is necessary to switch complicated conversion tables that are harder to guess)
As a result, the ciphertext "GCIHJ" was obtained from the plaintext "hello". Here, the character "l" that appears in plain text is replaced with different characters "I" and "H" in the ciphertext. By switching the conversion table for each character in this way, it becomes possible to encrypt the same character in plaintext into different characters, which makes it difficult to decipher by frequency analysis.
The actual multi-substitution cipher is [Vigenère cipher](https://ja.wikipedia.org/wiki/%E3%83%B4%E3%82%A3%E3%82%B8%E3%83% The code A5% E3% 83% 8D% E3% 83% AB% E6% 9A% 97% E5% 8F% B7) is famous.
The Vigenère cipher was initially said to be unbreakable. However, it has come to be deciphered by exploiting the weakness that the conversion table used has periodicity.
The Enigma is a cryptographic machine invented by the German Arthur Scherbius in 1918 and was adopted by the German army during World War II.
Enigma works by typing characters on the keyboard and the encrypted characters on the lampboard light up. (* If you search for "Enigma", you can find various images, so please refer to that.)
Between this keyboard and the lamp board, there is an encryption device called ** scrambler **. The scrambler stirs (scrambles) the characters typed on the keyboard and passes them to the ramp board. As a result, the input character is converted (encrypted) into another character.
** Image of scrambler **
In other words, this scrambler is a conversion table for encryption.
Encryption that is simply passed through a scrambler is only a single substitution cipher. Single substitution ciphers are easily deciphered, so this alone is not a strong cryptographic device.
The Enigma scrambler, also known as the ** Rotor **, can rotate, as the name implies. The rotor is designed to rotate one character each time a character is input.
** Image of rotating rotor **
As a result, the Enigma operates as a multi-substitution cipher in which a different conversion table is used each time a character is input.
The above figure has only 5 letters a to e for simplification, but in reality there are 26 letters in the alphabet. Therefore, one scrambler uses 26 types of conversion tables.
However, this means that the same conversion table is used every 26 characters. The repetition of this conversion table is also a weak point of the Vigenère cipher, and it is desirable to avoid using the same conversion table as much as possible.
Therefore, in the actual Enigma, three rotors are installed, and the second rotor shifts by one after one week of the first rotor, and the third rotor shifts by one after one week of the second rotor. It is designed to be connected. (* Three rotors were the early Enigma, and the number of rotors was increased during the war)
** Image of three rotors connected **
As a result, the conversion table pattern is $ 26 \ times 26 \ times 26 = 17,576 $.
Furthermore, the scrambler set on the rotor can be replaced. In other words, three scramblers can be set in any combination of three rotors. Since there are 6 patterns, the conversion table pattern is actually $ 17,576 \ times 6 = 105,456 $.
In the above schematic diagram, the lamp board was next to the third rotor, but in reality, a special rotor called a ** reflector ** is attached.
The reflector operates to reflect the input electric signal and return it to the rotor 3. The reflected electric signal returns to rotor 2 and rotor 1, and then connects to the lamp board.
** Reflector reflection **
In the state shown above, for example, "a" is input with the keyboard. If you follow the arrow, you will finally reach the "C" on the ramp board.
Next, consider the case where "c" is input with the keyboard. You may notice it while following the arrow again, but this is nothing more than following the reverse of the route when you entered "a" earlier. Naturally, we will eventually reach the "A" on the lamp board.
In other words, if the initial state of the rotor matches the time of encryption, the plaintext can be obtained by inputting the ciphertext.
Enigma also has a mechanism called ** plugboard **.
The plugboard is a mechanism that replaces two specific characters entered on the keyboard with each other, and a total of six replacements can be set.
** Image with characters replaced on the plugboard **
In this example, two replacements of "a" and "c" and "e" and "f" are set.
There are 100,391,791,500 patterns for choosing 6 pairs from 26 characters. By multiplying this by the pattern of the conversion table by the rotor, brute force attack by human power becomes extremely difficult.
The following three pieces of information are required for encryption and decryption of Enigma.
So this is the key to Enigma.
The Germans used to change this key once a day (at the end of the war, it changed several times a day). This is called a ** day key ** because it changes daily. Which key to use on which day was summarized and distributed in the codebook.
The keys are exchanged every day, so it seems safe. However, the amount of messages exchanged in a day is enormous. The more ciphertexts encrypted with the same day key are available, the more likely it is to be deciphered.
For this reason, a shorter key (message key) was actually used for each message.
The message key determines the initial state of the rotor and is represented by three letters such as "XYZ" [^ 1]. Letters are engraved on the rotor so that the position of rotation can be adjusted with the letters. That is, "XYZ" means that the position of the first rotor is set to "X", the second position is set to "Y", and the third position is set to "Z".
When exchanging messages, the message key is randomly determined first. Then, the message key is encrypted with the Japanese key and sent to the communication partner. After that, only the initial state of the rotor is replaced with the message key among the Japanese keys, and the ciphertext is exchanged.
By doing this, the ciphertext created by the Japanese key was minimized.
[^ 1]: Actually, two consecutive data such as "XYZXYZ" were encrypted and sent so that you can check if the data is damaged due to the communication status.
The mechanism of Enigma explained so far is implemented by a program (Java).
The class structure is as follows.
The "Enigma" class serves as the entrance, converts the input character string, and returns the result as a character string.
The input character string information is decomposed into units called "keys" one by one and passed to the "plugboard" and "encryption rotor". The circuit reflections of the Enigma reflector are reproduced in the form of method return values.
The "key" finally returned by the "plugboard" is the value at which the conversion is completed, and this is returned to the character string as the return value of "Enigma".
It is difficult to understand in the class diagram because it is not possible to express that there are three "encryption rotors", but in the object diagram it looks like the following.
The basic types used in the program are "key", "number of law 26", "rotation amount", "input / output position", and "offset".
The "key" represents each key entered on the Enigma keyboard and has one of the 26 characters from ʻato
z`.
Key
public class Key {
...
static Key of(char c) {
return new Key(c);
}
static Key of(Modulo26 value) {
char key = (char)(value.getValue() + 'a');
return new Key(key);
}
private final char value;
private Key(char value) {
if (!('a' <= value && value <= 'z')) {
throw new IllegalArgumentException("value is a-One of z");
}
this.value = value;
}
char getChar() {
return this.value;
}
Modulo26 toNumber() {
return Modulo26.of(this.value - 'a');
}
...
}
The number 26, which represents the number of characters in the alphabet, appears in various places such as the "rotation amount", "input / output position", and "offset" of the rotor. In addition, since the rotor is rotating, all of these numbers have the property of returning to 0 again when they reach 26.
Since this can be said to be a "number with 26 as the law", we have prepared a class called "the number with the law 26" for ease of handling.
Modulo26
public class Modulo26 implements Serializable {
private final int value;
public static Modulo26 of(int value) {
return new Modulo26(value);
}
private Modulo26(int value) {
this.value = Math.floorMod(value, 26);
}
boolean isZero() {
return this.value == 0;
}
int getValue() {
return this.value;
}
Modulo26 plus(Modulo26 other) {
return this.plus(other.value);
}
Modulo26 minus(Modulo26 other) {
return this.plus(-1 * other.value);
}
Modulo26 plus(int n) {
return new Modulo26(this.value + n);
}
...
}
"Rotor" is defined as an interface. Then, the rotor used for encryption ("encryption rotor") and the "reflector" can be treated as the same "rotor".
Rotor
public interface Rotor {
IOPosition input(IOPosition position);
void rotate();
}
EncryptionRotor
public class EncryptionRotor implements Rotor {
private final Offset offset;
private final Scrambler scrambler;
private final Rotor nextRotor;
private RotateAmount rotateAmount;
EncryptionRotor(Offset offset, Scrambler scrambler, Rotor nextRotor) {
this.offset = Objects.requireNonNull(offset);
this.scrambler = Objects.requireNonNull(scrambler);
this.nextRotor = Objects.requireNonNull(nextRotor);
this.rotateAmount = RotateAmount.ZERO;
}
@Override
public IOPosition input(IOPosition position) {
IOPosition scrambled = this.scrambler.scramble(position, this.offset, this.rotateAmount);
IOPosition reflected = this.nextRotor.input(scrambled);
IOPosition reversed = this.scrambler.reverse(reflected, this.offset, this.rotateAmount);
this.rotate();
return reversed;
}
@Override
public void rotate() {
this.rotateAmount = this.rotateAmount.rotate();
if (this.rotateAmount.isZero()) {
this.nextRotor.rotate();
}
}
}
Reflector
public class Reflector implements Rotor {
@Override
public IOPosition input(IOPosition position) {
return position.plus(13);
}
@Override
public void rotate() {
// Reflector does not rotate.
}
}
By doing so, the "next rotor" of the "encryption rotor" can be abstracted by the "rotor" type. Then, it is not necessary to distinguish between the "next rotor (the substance is the rotor 3)" of the rotor 2 and the "next rotor (the substance is the reflector)" of the rotor 3. As a result, all three rotors can be created as one instance of "encryption rotor".
Due to the specifications of Enigma, the placement of the "scrambler" must be freely changeable. Therefore, "rotor" and "scrambler" were extracted as separate classes.
The "rotor" manages the initial position and the state of rotation as if it were rotating, and the "scrambler" is only responsible for the conversion process.
Scrambler
public class Scrambler implements Serializable {
private final Map<IOPosition, IOPosition> map;
private final Map<IOPosition, IOPosition> reverseMap;
public static Scrambler newInstance(Random random) {
...
}
Scrambler(Map<IOPosition, IOPosition> map) {
...
}
IOPosition scramble(IOPosition input, Offset offset, RotateAmount rotateAmount) {
IOPosition shifted = input.minus(offset, rotateAmount);
IOPosition scrambled = this.map.get(shifted);
return scrambled.plus(offset, rotateAmount);
}
IOPosition reverse(IOPosition input, Offset offset, RotateAmount rotateAmount) {
IOPosition shifted = input.minus(offset, rotateAmount);
IOPosition reversed = this.reverseMap.get(shifted);
return reversed.plus(offset, rotateAmount);
}
public void store(Path path) {
...
}
public static Scrambler load(Path path) {
...
}
}
The "scrambler" allows you to instantiate random wires with newInstance (Random)
.
Also, since this class is serializable, the created instance can be output to a file with the store ()
method and restored with the load ()
method.
Plugboard
public class Plugboard {
private final Rotor rotor;
private final Map<Key, Key> exchangeMap = new HashMap<>();
Plugboard(Rotor rotor) {
this.rotor = Objects.requireNonNull(rotor);
}
public void exchange(Key one, Key other) {
...
this.exchangeMap.put(one, other);
this.exchangeMap.put(other, one);
}
Key input(Key inputKey) {
Key exchanged = this.exchangeMap.getOrDefault(inputKey, inputKey);
IOPosition position = IOPosition.of(exchanged.toNumber());
IOPosition reversed = this.rotor.input(position);
Key reversedKey = Key.of(reversed.getValue());
return this.exchangeMap.getOrDefault(reversedKey, reversedKey);
}
}
For the "plugboard", set the key conversion rule in advance with the ʻexchange ()` method. Then, the input key and the key returned by the rotor are converted according to the rules.
Enigma
public class Enigma {
private final Plugboard plugboard;
public static Enigma newInstance(
Key firstKey,
Scrambler firstScrambler,
Key secondKey,
Scrambler secondScrambler,
Key thirdKey,
Scrambler thirdScrambler,
Consumer<Plugboard> plugboardInitializer) {
Reflector reflector = new Reflector();
EncryptionRotor thirdRotor = new EncryptionRotor(toOffset(firstKey), firstScrambler, reflector);
EncryptionRotor secondRotor = new EncryptionRotor(toOffset(secondKey), secondScrambler, thirdRotor);
EncryptionRotor firstRotor = new EncryptionRotor(toOffset(thirdKey), thirdScrambler, secondRotor);
Plugboard plugboard = new Plugboard(firstRotor);
plugboardInitializer.accept(plugboard);
return new Enigma(plugboard);
}
private static Offset toOffset(Key key) {
return Offset.of(key.toNumber());
}
private Enigma(Plugboard plugboard) {
this.plugboard = Objects.requireNonNull(plugboard);
}
public String input(String text) {
StringBuilder sb = new StringBuilder();
for (char c : text.toCharArray()) {
Key key = Key.of(c);
Key result = this.plugboard.input(key);
sb.append(result.getChar());
}
return sb.toString();
}
}
"Enigma" not only accepts input and output, but also has a role as a factory.
By passing the information required for initialization (Enigma key) to newInstance ()
, various instances are created and ʻEnigmainstances are returned.
Consumer
Enigma encryption = Enigma.newInstance(
Key.D, firstScrambler,
Key.K, secondScrambler,
Key.F, thirdScrambler,
plugboard -> {
plugboard.exchange(Key.A, Key.R);
plugboard.exchange(Key.E, Key.K);
plugboard.exchange(Key.O, Key.T);
plugboard.exchange(Key.P, Key.Q);
plugboard.exchange(Key.Z, Key.M);
plugboard.exchange(Key.Y, Key.C);
});
import java.security.SecureRandom;
public class Main {
public static void main(String[] args) {
//Generate scrambler
SecureRandom random = new SecureRandom();
Scrambler firstScrambler = Scrambler.newInstance(random);
Scrambler secondScrambler = Scrambler.newInstance(random);
Scrambler thirdScrambler = Scrambler.newInstance(random);
//Create an Enigma instance for encryption
Enigma encryption = Enigma.newInstance(Key.D, firstScrambler, Key.K, secondScrambler, Key.F, thirdScrambler, Main::initializePlugboard);
//encryption
String encrypted = encryption.input("helloxxworld"); // "xx"Is a temporary string to represent a blank space
System.out.println(encrypted);
//Create an Enigma instance for decryption with the same key information
Enigma decryption = Enigma.newInstance(Key.D, firstScrambler, Key.K, secondScrambler, Key.F, thirdScrambler, Main::initializePlugboard);
//Decryption
String plainText = decryption.input(encrypted);
System.out.println(plainText.replace("xx", " "));
}
private static void initializePlugboard(Plugboard plugboard) {
plugboard.exchange(Key.A, Key.R);
plugboard.exchange(Key.E, Key.K);
plugboard.exchange(Key.O, Key.T);
plugboard.exchange(Key.P, Key.Q);
plugboard.exchange(Key.Z, Key.M);
plugboard.exchange(Key.Y, Key.C);
}
}
Execution result
rsonmcqycsjk
hello world
It seems that it was able to encrypt and decrypt properly. [^ 2]
[^ 2]: To be honest, I haven't tested it well, so there may be a problem somewhere.
Translator's postscript (Omitted) Where is the secret of Shin's talent? (Omitted) It is possible to write complicated contents even for experts so that even amateurs can easily understand them, and not just stroking the upper surface, but to feel a solid response. (Omitted) For example, many books have been published that explain the cryptographic machine Enigma, but "If you go back to the beginning of the 20th century by time travel, ** If you read this, you can assemble the Enigma machine by yourself. This book was the only book ** that I thought would be possible.
Cryptanalysis (bottom) (Shincho Bunko) From the translator's postscript
This is the expected result.
"Cryptanalysis" covers a wide range of cryptographic history, from medieval cryptography to public key cryptography as well as Enigma.
Public-key cryptography is an important technology that supports the current Internet communication, but this book describes the history of various cryptography until human beings arrived at public-key cryptography, and the drama of many cryptographers and decipherers involved in it. It is very interesting to be able to read. For example, when you learn about cryptography normally, it is often written only with a simple content that "public key cryptography can solve the key distribution problem", but how the solution of the key distribution problem is in the history of human cryptography You can tell if it was a revolutionary invention by reading this book.
I recommend it.
Recommended Posts