Эмулятор шифровальной машины Enigma C# .NET

14 декабря, 2020DEV

Наверное, две недели я занимался этим проектом и глядя на результирующее количество кода — трудно понять куда было потрачено столько времени и почему результат вышел настолько маленьким (относительно количества строк кода). Конечно, это были не фултайм две недели, а под настроение — когда хотелось и моглось. Тем не менее, по ощущениям прошло невероятно долгое исследование, забравшее колоссальное количество сил; наверное, непозволительное для меня сейчас. Но, как известно, оценивать код по количеству его строк это как оценивать взлётные качества самолёта по его весу (и это, конечно, не моя мысль). Да и, в целом, специфика сегодняшней темы весьма наукоёмкая и больше требовала чтения, разбирательств, чем самого непосредственного написания. Плюс больше волокиты по написанию тестов, чем самого кода. Но обо всём по порядку.

Привет! 🙂 Вся радость разработки в 2020 году в том, что мы имеем весь необходимый инструментарий и тысячу и один способ для конкретизации абстракций из головы. Это в какой-то степени похоже на 3D-принтер, в котором мы распечатываем идеи. То, что мы можем не выходя из дома и вооружившись одним лишь компьютером создать механическую шифровальную машину Энигму — это чудо чудное да диво дивное, которое меня не перестаёт торкать уже двадцать лет.

Итак, Энигма. Электромеханическая переносная «печатная машинка», позволяющая при помощи элегантного и относительно простого алгоритма шифровать и дешифровать текст. Сама идея и первые реализации известны ещё с 20х годов, но особенную популярность машинка получила сначала в коммерческой сфере, а уже потом в Германии во вторую мировую войну. Как правило, именно немецкая реализация имеется ввиду по-умолчанию, когда мы говорим про Энигму.

Наверняка, вы смотрели фильм «Игра в имитацию» 2014 года, про Алана Тьюринга и его вклад в дешифровку Энигмы. Утверждается, что его «криптографическая бомба», позволявшая получать секретную информацию третьего рейха во многом явилась решающим фактором в победе стран союзников. Если вы по какой-то причине ещё не смотрели это — настоятельно рекомендую посмотреть перед дальнейшим прочтением этого материала, для более глубокого вовлечения в контекст всей этой темы.

Ну и кроме всего прочего, это просто красивая и абсолютно стимпанковская штуковина, прекрасная идея и не менее прекрасная её реализация. Грех такое не сотворить самому, чем мы сегодня и займёмся.

Устройство

Энигма — в самом упрощённом и грубом представлении — это смесь механики и самой обыкновенной электрической цепи. Машинка имела клавиатуру (с подсветкой!) и систему вала, на который были насажены специальные диски с алфавитом (роторы). При каждом нажатии на клавишу — ток шёл от нужной буквы через все диски, по дороге поворачивая некоторые из них и тем самым изменяя саму цепь. Таким образом введённая буква проходила свой путь, видоизменялась по дороге и подсвечивалась в уже изменённом виде. Оператор это всё переписывал и отправлял куда надо.

Если говорить более подробно про устройство машины, то вышеуказанные ротеры служат основой и сердцем всего процесса — каждый в отдельности представляет собой алфавитный круг с 26 латинскими буквами, реализующий примитивный шифр замены. Т.е. при подаче, к примеру, буквы А мы заменяем её на какую-то иную букву, тем самым реализуем алгоритм замены. Сложность добивается тем, что ротеров несколько — сигнал проходит от одного к другому, они разного типа, важен их порядок установки, важно предыдущее значение ротера для вычисления текущего, они все вращаются по определённым правилам и в конце своего пути проходят через ещё один дополнительный специальный ротер (который называется рефлектором, потому что поворачивает направление движения — т.е. тока; важно — данный ротер не вращается) и мы проходим весь путь назад — вновь отбиваясь через все ротеры, но уже в другом направлении. В конце полученная буква подсвечивается лампочкой над клавиатурой. Звучит, наверное, не просто. Значительно проще, если посмотреть на всё это в схематическом представлении:

Сложность

Устойчивость шрифта для того времени была более чем достаточной, чтобы в рамках одного дня иметь надёжный способ для ведения шифрованных коммуникаций (так они думали 🙂 ). Положения трёх роторов (1 из 26 латинских букв), а также выбранный тип рефлектора (тот же ротер, по сути четвёртый, но который не вращается) позволяли реализовать многоалфавитный шифр подстановки.

Многоалфавитная змена позволяла шифровать одну букву всегда разными буквами, т.е. если нажимать на клавишу с буквой А — мы будем на выходе получать каждый раз разные буквы (т.к. ротеры вращаются). И, стоит заметить, никогда буква А не становилась на выходе буквой А. Т.е. шифруемая буква никогда не оставалась в первозданном виде, что давало некоторый плацдарм и облегчения для анализа при взломе этой машины.

Огромный вклад в взлом Энигмы внесли польские математики и криптографы, т.н. «польский этап», в котором по сути при помощи реверсинжиниринга удалось воссоздать принцип работы Энигмы. Удалось понять, что взлом энигмы это поиск ключа из 105456 (т.е. 3!*26^3) возможных вариантов, что было значительно меньше, чем недосягаемые 26!.

Позже Энигма изменилось и новая сложность достигалась тем, что в более поздних моделях шифровальной машинки был добавлен т.н. плагборд (на немецком Steckerbrett), в котором можно было самостоятельно перенаправлять цепь на самом последнем шагу шифрования. Как правило на данном этапе это ещё один вариант шифра замены, который можно было абсолютно самостоятельно варьировать (в отличи от ротеров, которые неизменяемые). Появление плагборда значительным образом усложняло взлом Энигмы, буквально — на многие порядки и результат данного усовершенствования по сути закрывал возможность для какой-либо мануальной дешифровки (и без того находящейся на грани возможного) и требовало уже конструирования специальных машин. Что, собственно, Алан Тьюринг переняв эстафету от польских коллег и сделал.

Специальные символы

Т.к. Энигма имела в своём багаже только 26 латинских букв — передача спецсимволов требовала особенной сноровки. Пробел мог пропускаться. Или же всегда заменялся редкой буквой, к примеру, X. Запятая заменялась на комбинацию из двух ZZ или Y, вопросительный знак — FRAGE или FRAQ. К тому же разные подразделения имели свой собственный «слэнг» замены спецсимволов и цифр.

Соль и мусор

Все шифруемые сообщения не были большими и для усложнения криптоанализа бились на маленькие части, каждая из которых шифровалась отдельным ключом. К тому же в тело сообщения часто вкраплялся текстовый мусор, состоящий из бессвязного набора букв. Тем самым добивались ещё большего усложнения для криптографов, которые занимались дешифовкой сообщений.

Самих ротеров было несколько. Поэтому ключом для дешифрации была схема из типов ротеров, их положения относительна друг-друга, начальных выставленных букв и типа рефлектора. К тому же плагборд, настройки которого также необходимо было знать иначе чуда не произойдет.

Типы ротеров

Для Энигмы выходило несколько ротеров, несколько их ревизий и поколений. Больше о возможных вариантах вы можете найти здесь. Для нас интересны ротеры, которые были в комплекте с Enigma I. И их было пять штук:

ТипABCDEFGHIJKLMNOPQRSTUVWXYZПоворот
IEKMFLGDQVZNTOWYHXUSPAIBRCJY
IIAJDKSIRUXBLHWTMCQGZNPYFVOEM
IIIBDFHJLCPRTXVZNYEIWGAKMUSQOD
IVESOVPZJAYQUIRHXLNFTGKDCMWBR
VVZBRGITYUPSDNHLXAWMJQOFECKH
Базовые ротеры для модели Enigma I

Типы рефлекторов

Кроме ротеров существовали ещё и рефлекторы, как я уже писал, это такие же ротеры, но с другой функциональной надобностью — они не поворачивались и меняли направление движение тока. Т.е. после захода в рефлектор наша буква возвращалась на ротер, с которого зашла. Рефлекторов было три вида: A, B и C:

ТипABCDEFGHIJKLMNOPQRSTUVWXYZ
UKW-AEJMZALYXVBWFCRQUONTSPIKHGD
UKW-BYRUHQSLDPXNGOKMIEBFZCWVJAT
UKW-CFVPJIAOYEDRZXWGCTKUQSBNMHL
Рефлекторы для Enigma I

Модульная арифметика

Важным условием к пониманию математики Энигмы является модульная арифметика. Именно ею здесь всё прошито красной нитью и это основной математический принцип высчитывания сквозного состояния (т.е. «между») ротеров. Нам нужно будет математическое сложение или вычитание букв по модулю 26, в зависимости от направления движения тока.

В .NET нет коробочной поддержки арифметической операции MODULO, т.е. остаток от деления работает только с положительными числами. Эта оказалось для меня сюрпризом, т.к. я никогда не работал с остатком от деления в отрицательных диапозонах. Тем не менее, если вы введёте в гугле -19 % 26, то получите 7, а если тоже самое сделает при помощи C# — получите -19. А нам, собственно, нужно 7 🙂 Но изменения для получения правильного модуло — тривиальны и выглядят следующим образом:

x < 0 ? ((x % m) + m) % m : x % m;

К слову, в этой статье на википедии есть список с полным описанием того как именно реализована операция MODULO в разных языках программирования.

Разбор алгоритма

Окей, мы почти готовы. Но для полноты понимания давайте проведём шаг за шагом одну букву через все хитросплетения электрических схем Энигмы. Допустим мы устанавливаем рефлектор типа UKW_B, а также слева-направо ротеры I, II, III в положение букв ‘H’, ‘D’, ‘X’. При вводе на клавиатуре символа A мы в итоге получим символ K и всё движение будет выглядеть так:

Картинка взята мной из Flash версии Энигмы (пришлось для этого даже поставить Adobe Flash Player 🙂 ). И на самом деле не всё так просто, как на этой картинке (хотя для неподготовительного человека и на картинке не очень всё очевидно 🙂 ). Скажем так, красная линия (идущая к рефлектору) и зелёная (идущая от рефлектора назад) — уже посчитаны и мы лицезреем уже результат этого вычисления.

Код

Теория теоритически ясна и мы можем перейти непосредственно к коду. Мы будем реализовывать армейскую Enigma I, как самую распространённую. Некоторой проблемой было то, что сегодня оказалось достаточно трудно найти исторически правильную\истинную реализацию алгоритма. Многие сайты противоречат друг-другу и у меня до сих пор нет уверенности, что нужный набор ротеров, их значения и алгоритм «течения» тока и букв соответствует реальной исторической действительности. Я полагался на книги, специализированные статьи с конкретными примерами, википедию и на максимальное соответствие моей версии с многими онлайн-версиями. Она работает ровно также как и другие варианты в сети. А значит будем считать это верной реализацией.

Создадим новый проект в Visual Studio и назовём его Enigma. Добавим одноимённый с проектом класс Enigma и классы, проецирующие реальные устройства — Rotor и Plugboard. Также нам понадобится вал, на котором будут «крутиться» наши виртуальные ротеры — Rotors. Плюс добавим «базу данных» ротеров HistoricData — т.к. ротеры являются предустановленными, по сути захардкоженными и нам нужно где-то это хранить. Последними файлами пусть будут Common (для хранения статических методов, констант и алфавита) и Enums для перечислений (их будет немного).

Начнём с конца. Давайте вычленим и конкретизируем типы. Наши типы, ротеры и рефлектора:

public enum Type : uint
{
    Unknown = 0,
    Reflector = 1,
    Keyboard = 2,
    Rotor = 3,
}

public enum RotorType : uint
{
    Unknown = 0,
    Rotor_I,
    Rotor_II,
    Rotor_III,
}

public enum ReflectorType : uint
{
    Unknown = 0,
    UWK_A,
    UWK_B,
    UWK_C,
}

Теперь нам нужны константы и весьма скромная математика, которую давайте положим в Common:

public static class Common
{

    public static char[] ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();

    public const int MODULO_MAX_LETTERS = 26;

    public static char CharPlusN(int c, int n) => ALPHABET[(c + n) % MODULO_MAX_LETTERS];

    public static int Mod(int f, int t) => (Math.Abs((f - t) * MODULO_MAX_LETTERS) + (f - t)) % MODULO_MAX_LETTERS;

}

ALPHABET — наш алфавит-словарь, а константа MODULO_MAX_LETTERS по сути является хранилищем для нашего вычисления по модулю.

Метод Mod реализует правильное модуло и позволяет посчитать дистанцию между любыми буквами. Для A-Z мы должны получить 25, для B-C1, а также для «инвертированных» запросов, в которых первая буква идёт после второй, к примеру: C-B — также 1, как и Z-A25.

Метод CharPlusN — приплюсовывает к букве N букв. Если к A добавить 2 — мы получим С. Если к F приплюсовать 5 — выходит K и т.д..

Класс ротора — самый большой (хотя, на самом деле, относительно любых других проектов — это вполне обычный класс):

public class Rotor
{

	#region Fields & Properties

	private readonly char[] _chars;

	private int _head;

	public char Notch { get; set; }

	public char Turnover { get; set; }

	public Rotor Prev { get; set; }

	public Rotor Next { get; set; }

	public Type Type { get; set; }

	public bool IsFirst { get; set; }

	public char Current
	{
		get => Common.ALPHABET[this._head];
		set => this.SetHead(value);
	}

	#endregion

	public Rotor(Type type, string chars)
	{
		this._chars = chars.ToCharArray();
		this.Type = type;
	}

	public static int GetAlphabetCharIndex(char @char) => Array.IndexOf(Common.ALPHABET, char.ToUpper(@char));

	public char GetFromAlphabet(char @char)
	{
		int index = GetAlphabetCharIndex(@char);
		return this._chars[index];
	}

	public char GetFromRotor(char @char)
	{
		int index = Array.IndexOf(this._chars, char.ToUpper(@char));
		return Common.ALPHABET[index];
	}

	public void SetHead(char @char) => this._head = GetAlphabetCharIndex(@char);

	public char Enter(char @char)
	{
		if (this.Current == this.Turnover && this.Type == Type.Rotor)
			this.Prev.Rotate();
		if(this.IsFirst)
			this.Rotate();

		int from = Array.IndexOf(Common.ALPHABET, char.ToUpper(this.Current));
		int to = this.Next == null ? 0 : Array.IndexOf(Common.ALPHABET, char.ToUpper(this.Next.Current));
		int index = Array.IndexOf(Common.ALPHABET, char.ToUpper(@char));

		int distance = Common.Mod(from, to);
		char get = Common.CharPlusN(index, distance);

		char map = GetFromAlphabet(get);
		return map;
	}

	public char Reverse(char @char)
	{
		int f = Array.IndexOf(Common.ALPHABET, char.ToUpper(this.Current));
		int t = this.Prev == null ? 0 : Array.IndexOf(Common.ALPHABET, char.ToUpper(this.Prev.Current));
		int nn = Array.IndexOf(Common.ALPHABET, char.ToUpper(@char));

		int d = Common.Mod(f, t);
		char get = Common.CharPlusN(nn, d);

		char map = GetFromRotor(get);
		return map;
	}

	public void Rotate()
	{
		if (this._head + 1 >= this._chars.Length)
			this._head = 0;
		else
			this._head++;
	}

}

Пришла очередь хранилища исторических данных — HistoricData:

public static class HistoricData
{

    /// <summary>
    /// Keyboard
    /// </summary>
    public static Rotor Keyboard
    {
        get => new Rotor(Type.Keyboard, "ABCDEFGHIJKLMNOPQRSTUVWXYZ")
        {
            Notch = '\0',
            Turnover = '\0',
        };
    }

    /// <summary>
    /// Enigma I
    /// </summary>
    public static class EnigmaI
    {

        public static Rotor I
        {
            get => new Rotor(Type.Rotor, "EKMFLGDQVZNTOWYHXUSPAIBRCJ")
            {
                Notch = 'Y',
                Turnover = 'Q',
            };
        }

        public static Rotor II
        {
            get => new Rotor(Type.Rotor, "AJDKSIRUXBLHWTMCQGZNPYFVOE")
            {
                Notch = 'M',
                Turnover = 'E',
            };
        }

        public static Rotor III
        {
            get => new Rotor(Type.Rotor, "BDFHJLCPRTXVZNYEIWGAKMUSQO")
            {
                Notch = 'D',
                Turnover = 'V',
            };
        }

    }

    /// <summary>
    /// Reflectors
    /// </summary>
    public static class Reflectors
    {

        public static Rotor ReflectorA
        {
            get => new Rotor(Type.Reflector, "EJMZALYXVBWFCRQUONTSPIKHGD");
        }


        public static Rotor ReflectorB
        {
            get => new Rotor(Type.Reflector, "YRUHQSLDPXNGOKMIEBFZCWVJAT");
        }

        public static Rotor ReflectorC
        {
            get => new Rotor(Type.Reflector, "FVPJIAOYEDRZXWGCTKUQSBNMHL");
        }

    }

}

Класс вала ротеров Rotors позволяет нам добавлять, т.е. «нанизывать» нужные нам ротеры в порядке слева-направо. Здесь же нам необходимо установить нужный рефлектор, а также произвести настройку всего этого «оборудования» — выставить положения букв:

public class Rotors
{

    private List<Rotor> _list = new List<Rotor>();

    private Rotor _keyboard = HistoricData.Keyboard;

    public Rotor Reflector { get; private set; }

    public Rotors()
    {
        this.Reflector = HistoricData.Reflectors.ReflectorB;
    }

    public void Add(RotorType type, char head)
    {
        Rotor rotor;
        switch (type)
        {
            case RotorType.Rotor_I:
                rotor = HistoricData.EnigmaI.I;
                break;
            case RotorType.Rotor_II:
                rotor = HistoricData.EnigmaI.II;
                break;
            case RotorType.Rotor_III:
                rotor = HistoricData.EnigmaI.III;
                break;
            default:
                throw new Exceptions.EnigmaRotorsException();
        }
        rotor.SetHead(head);
        this.Add(rotor);
    }

    public void Add(Rotor rotor) 
    {
        rotor.IsFirst = this._list.Count == 0;
        if (rotor.IsFirst)
            this._keyboard.Prev = rotor;
        else
        {
            rotor.Next = this._list[this._list.Count - 1];
            this._list[this._list.Count - 1].Prev = rotor;
        }
        this._list.Add(rotor);
        this.Reflector.Prev = rotor;
    }

    public void Clear()
    {
        this.Reflector.Prev = null;
        this._keyboard.Prev = null;
        this._list.Clear();
    }

    public void SetHead(params char[] heads)
    {
        if (heads.Length != this._list.Count)
            throw new Exceptions.EnigmaRotorsException();

        for (int i = 0; i < heads.Length; i++)
            this._list[i].SetHead(heads[i]);
    }

    public void SetReflector(ReflectorType type)
    {
        Rotor rotor;
        switch (type)
        {
            case ReflectorType.UWK_A:
                rotor = HistoricData.Reflectors.ReflectorA;
                break;
            case ReflectorType.UWK_B:
                rotor = HistoricData.Reflectors.ReflectorB;
                break;
            case ReflectorType.UWK_C:
                rotor = HistoricData.Reflectors.ReflectorC;
                break;
            default:
                throw new Exceptions.EnigmaRotorsException();
        }

        this.Reflector = rotor;
        if(this._list.Count > 0)
            this.Reflector.Prev = this._list[this._list.Count - 1];
    }

    public void SetReflector(Rotor reflector)
    {
        if (reflector.Type != Type.Reflector)
            throw new Exceptions.EnigmaRotorsException();

        this.Reflector = reflector;
    }

    public char Enter(char @char, Plugboard pb)
    {
        char result = @char;

        if (pb.Exist(result))
            result = pb.Get(result);

        for (int i = 0; i < this._list.Count; i++)
            result = this._list[i].Enter(result);
        result = this.Reflector.Reverse(result);
        for (int i = this._list.Count - 1; i >= 0; i--)
            result = this._list[i].Reverse(result);
        result = this._keyboard.Reverse(result);

        if (pb.Exist(result))
            result = pb.Get(result);

        return result;
    }

}

И, конечно, сама машинка Enigma:

public class Enigma
{

    public Rotors Rotors { get; private set; }

    public Plugboard Plugboard { get; private set; }

    public Enigma()
    {
        this.Rotors = new Rotors();
        this.Plugboard = new Plugboard();
    }

    public string Encrypt(string data)
    {
        if (data == null)
            throw new ArgumentNullException(nameof(data));

        StringBuilder sb = new StringBuilder();
        foreach (char d in data.ToCharArray())
            if (char.IsLetter(d))
            {
                char r = this.Rotors.Enter(d, this.Plugboard);
                sb.Append(r);
            }
            else
                sb.Append(d);
        return sb.ToString();
    }

}

В данной статье представлен код не весь, а только основные его части. Плюс в последствии я планирую его отрефакторить и, возможно, что он изменится и начнёт отличаться от представленного в статье (хотя, конечно, я постараюсь держась эти версии идентичными). За полным листингом прошу перейти в репозиторий GitHub.

Пример использования

Вот небольшой пример использования моей Энигмы, который кодирует фразу «The quick brown fox jumps over the lazy dog» (это панграмма, т.е. предложение, в котором есть все буквы алфавита — лучше для тестирования шифрования и не придумаешь):

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("Enigma machine emulator:");
        
        string data = "The quick brown fox jumps over the lazy dog";
        Enigma e = new Enigma();

        //Plugboard
        e.Plugboard.Add('X', 'D');
        e.Plugboard.Add('A', 'V');
        
        //Rotors
        e.Rotors.Add(RotorType.Rotor_I, 'A');
        e.Rotors.Add(RotorType.Rotor_II, 'B');
        e.Rotors.Add(RotorType.Rotor_III, 'C');

        //Reflector
        e.Rotors.SetReflector(ReflectorType.UWK_B);

        string result = e.Encrypt(data);

        Console.WriteLine("Input: " + data);
        Console.WriteLine("Output: " + result);

        Console.WriteLine();
        Console.Read();
    }
}

Данный код в консоль выведет следующий текст:

Enigma machine emulator:
Input: The quick brown fox jumps over the lazy dog
Output: CAK OAZIJ MOGPG ZTP ATOWC FIAQ EJM ZCKT SGO

Тесты

Подобный проект трудно сделать без тестов. Я бы даже сказал, что реализация подобного проекта — хороший пример того ПОЧЕМУ и ЗАЧЕМ нужны тесты вообще. Когда реализация требует гигантского стека в вашей голове и куда легче проверять подобное автоматически, т.е. делегировать на написанные тесты. Я не покрывал на 100% код, но покрывал те вещи, которые этого требовали. Плюс ко всему это неплохой способ проверять работоспособность всех компонентов и сравнивать их с доступными в онлайне другими реализациями.

Выводы

Собственно, всё. Не так страшен чёрт, как говорится. Проект с моей реализацией Энигмы вы сможете найти в моём профиле GitHub в одноимённом репозитории. Конечно, это всё предварительные наброски и через некоторое время я допишу новых тестов, подключу плагборд и отрефакторю весь код, причешу его. Но и уже доступной версии достаточно, чтобы понять как это всё работает. Спасибо за внимание, надеюсь, что немного вам помог разобраться с Энигмой и понять тонкости её реализации 🙂

Leave a comment

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Prev Post