[JAVA] I tried to implement Enigma

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.

Single substitution cipher

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 ** enigma.jpg

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.

Multi-substitution cipher

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 ** enigma.jpg

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.

Enigma

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.

Scrambler

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 ** enigma.jpg

In other words, this scrambler is a conversion table for encryption.

rotor

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 ** enigma.jpg

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 ** enigma.jpg

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 $.

Reflector

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 ** enigma.jpg

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.

Plug board

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 ** enigma.jpg

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.

Enigma key

The following three pieces of information are required for encryption and decryption of Enigma.

  1. Placement of scrambler
  2. Initial state of the rotor
  3. Plugboard settings

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.

Implement the Enigma

The mechanism of Enigma explained so far is implemented by a program (Java).

model

The class structure is as follows.

enigma.jpg

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.

enigma.jpg

Key and basic type

enigma.jpg

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 ʻatoz`.

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);
    }
    ...
}

Cryptographic rotor and scrambler

enigma.jpg

"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.

Plug board

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

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 plugboardInitializer` is an argument for passing the process for initializing the wiring of the" plugboard ", and it is imagined to be implemented as follows.

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);
    });

Actually move

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.

in conclusion

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.

reference

Recommended Posts

I tried to implement Enigma
I tried to implement a server using Netty
I tried to verify yum-cron
I tried to implement Stalin sort with Java Collector
[Java] I tried to implement Yahoo API product search
I tried to implement the Euclidean algorithm in Java
I tried to summarize Java learning (1)
I tried to summarize Java 8 now
I tried to chew C # (polymorphism: polymorphism)
I tried to explain Active Hash
[Rails] I tried to implement batch processing with Rake task
I tried to implement a buggy web application in Kotlin
I tried tomcat
I tried to summarize the Stream API
I tried refactoring ①
I tried to build AdoptOpenjdk 11 on CentOS 7
I tried to use Selenium like JQuery
I tried to touch JavaScript Part.2 Object-oriented
I tried FizzBuzz.
I tried JHipster 5.1
I tried to chew C # (basic of encapsulation)
I tried to output multiplication table in Java
I tried to link JavaFX and Spring Framework.
I tried to set tomcat to run the Servlet.
I tried to develop an application in 2 languages
I tried to create Alexa skill in Java
I tried to develop a website to record expenses.
I tried to break a block with java (1)
I tried node-jt400 (Programs)
I tried node-jt400 (execute)
I tried node-jt400 (Transactions)
I tried to draw animation with Blazor + canvas API
Rails6 I tried to introduce Docker to an existing application
~ I tried to learn functional programming in Java now ~
I tried to chew C # (reading and writing files)
I tried to find out what changed in Java 9
[Swift] I tried to implement Instagram profile-like UI with UICollectionView only with code without storyboard
I tried Spring State machine
I tried using Apache Wicket
I tried to summarize the basic grammar of Ruby briefly
I tried to link chat with Minecraft server with Discord API
I tried to build the environment little by little using docker
I tried to summarize personally useful apps and development tools (development tools)
I tried node-jt400 (SQL query)
I tried to convert a string to a LocalDate type in Java
I tried using Java REPL
I tried source code analysis
I tried the FizzBuzz problem
I tried node-jt400 (SQL stream)
I tried node-jt400 (IFS read)
I tried Rails beginner [Chapter 2]
I tried to summarize personally useful apps and development tools (Apps)
I tried using Dapr in Java to facilitate microservice development
I tried to touch JavaScript Part.1 Basic processing code system
[Rails] How to implement scraping
I tried to make a client of RESAS-API in Java
I want to implement various functions with kotlin and java!
[Java] How to implement multithreading
I tried to create a padrino development environment with Docker
I tried to get started with Swagger using Spring Boot
I tried to summarize object orientation in my own way.