14.11.2022
Шифровальная машина немцев. Криптоанализ «Энигмы
All specialists unanimously agreed that a reading is impossible.
Admiral Kurt Fricke, Chief of Naval War Command
Энигма - роторная шифровальная машина, использовавшаяся нацистской Германией в годы Второй мировой войны. Благодаря влиянию, оказанному на ход войны, взлом Энигмы стал, возможно, самым ярким моментом в многовековой истории криптоанализа. В этом топике я бы хотел рассказать о методе взлома, использовавшимся в Блетчли-парк, а так же описать устройство самой машины.
Роторные машины
Впервые шифровальные роторные машины начали использоваться в начале 20 века. Основным компонентом таких устройств является диск (он же ротор) с 26 электрическими контактами на обоих сторонах диска. Каждый контакт соответствовал букве английского алфавита. Соединение контактов левой и правой сторон реализовывало шифр простой замены. При вращении диска контакты смещались, изменяя тем самым подстановку для каждой буквы. Один диск обеспечивал 26 различных подстановок. Это означает, что при шифровании одного и того же символа, получаемая в результате последовательность начинает повторяться через 26 шагов.Для увеличения периода последовательности можно использовать несколько роторов, соединенных последовательно. При совершении полного оборота одного из дисков, следующий диск сдвигается на одну позицию. Это увеличивает длину последовательности до 26 n , где n - количество соединенных последовательно роторов.
В качестве примера рассмотрим следующее изображение упрощенной роторной машины:
Приведенная машина состоит из клавиатуры (для ввода символа), трех дисков, индикатора (для отображения криптотекста) и реализует шифрование 4 символов: A, B, C, D. В начальной позиции первый диск реализует подстановку: A-C; B-A; C-B; D-D. Подстановки второго и третьего дисков равны A-B; B-C; C-A; D-D и A-A; B-C; C-B; D-D соответственно.
При нажатии буквы B на клавиатуре замыкается электрическая цепь, зависящая от текущего положения роторов, и на индикаторе загорается лампочка. В приведенном выше примере буква B будет зашифрована в C. После чего первый ротор сдвинется на одну позицию и настройки машины приобретут следующий вид:
Энигма
Энигма является наиболее популярным представителем мира шифровальных роторных машин. Она использовалась германскими войсками во время второй мировой войны и считалась практически не взламываемой.Процедура шифрования Энигмы реализована как в приведенном выше примере за исключением некоторых дополнительных штрихов.
Во-первых, число роторов в разных версиях Энигмы могло отличаться. Наиболее распространенной была Энигма с тремя роторами, но использовался так же вариант с четырьмя дисками.
Во-вторых, процесс расшифровки демонстрационной роторной машины, описанной выше, отличается от процесса шифрования. Каждый раз для расшифровки придется менять левый и правый ротор местами, что может быть не совсем удобным. Для решения этой проблемы в Энигме был добавлен еще один диск, который назывался рефлектор. В рефлекторе все контакты были соединены попарно, реализуя тем самым повторное прохождение сигнала через роторы, но уже по другому маршруту. В отличие от остальных роторов рефлектор всегда находился в фиксированном положении и не вращался.
Добавим рефлектор, реализующий замену (A-B; C-D) к нашей демонстрационной шифровальной машине. При нажатии на клавишу B сигнал проходит через роторы и поступает в рефлектор через контакт C. Здесь сигнал «отражается» и возвращается обратно, проходя через роторы в обратном порядке и по другому пути. В результате чего буква B на выходе преобразуется в D.
Обратите внимание, что если нажать клавишу D, то сигнал пойдет по той же самой цепи, преобразовывая D в B. Таким образом наличие рефлектора делало процессы шифрования и дешифрования идентичными.
Еще одно свойство Энигмы, связанное с рефлектором, заключается в невозможности шифрования какой-либо буквы в саму себя. Это свойство сыграло очень важную роль при взломе Энигмы.
Получившееся устройство уже очень похоже на настоящую Энигму. С одной незначительной оговоркой. Стойкость подобной машины упирается в секретность внутренней коммутации роторов. Если устройство роторов будет раскрыто, то взлом сводится к подбору их начальных позиций.
Так как каждый ротор может находится в одной из 26 позиций, для трех роторов получаем 26 3 =17476 вариантов. При этом сами роторы тоже могут располагаться в произвольном порядке, что увеличивает сложность в 3! раз. Т.е. пространство ключей такой машины составит 6*17576=105456. Этого явно не достаточно для того, чтобы обеспечить высокий уровень безопасности. Поэтому Энигма было оснащена еще одним дополнительным инструментом: коммутационной панелью
. Соединяя на коммутационной панели буквы попарно можно было добавить еще один дополнительный шаг к шифрованию. 
К примеру, предположим что на коммутационной панели буква B соединена с буквой A. Теперь при нажатии на A сперва происходит подстановка A-B, и на вход первого ротора подается буква B.
Аналогичным образом происходит расшифровка сообщения. При нажатии клавиши D роторы и рефлектор производят преобразование D-D-D-D-C-B-A-B. После чего коммутационная панель преобразует B в A.
Анализ стойкости Энигмы
Реальная Энигма отличалась от описанной демонстрационной машиной только в одном. А именно в устройстве роторов. В нашем примере ротор изменяет свое положение только при совершении полного оборота предыдущим диском. В настоящей Энигме каждый диск имел специальную выемку, которая в определенной позиции подцепляла следующий ротор и сдвигала его на одну позицию.Расположение выемки для каждого из роторов можно было регулировать с помощью специальных внешних колец. Начальное положение колец не влияло на коммутацию роторов и на результат шифрования отдельно взятой буквы, поэтому кольца не учитываются при расчете пространства ключей Энигмы.
Итак, базовая модель Энигмы имела 3 различных ротора, пронумерованных римскими цифрами I, II, III и реализующих следующие подстановки:
Entry = ABCDEFGHIJKLMNOPQRSTUVWXYZ
I = EKMFLGDQVZNTOWYHXUSPAIBRCJ
II = AJDKSIRUXBLHWTMCQGZNPYFVOE
III = BDFHJLCPRTXVZNYEIWGAKMUSQO
При шифровании роторы можно было располагать в любой последовательности, что для трех роторов дает 6 разных комбинаций.
Помимо этого каждый ротор мог быть установлен в одной из 26 возможных стартовых позиций. Т.е. начальное положение роторов имеет всего
6*26 3 =105456 комбинаций.
Количество всех возможных соединений на коммутационной панели вычисляется по формуле n! /((n-2m)! m! 2 m), где n - количество букв алфавита, m - количество соединенных пар.
Для 26 буква английского алфавита и 10 пар это составляет 150738274937250=2 47 различных комбинаций.
Таким образом базовая версия Энигмы с тремя роторами имела солидное даже по современным меркам пространство ключей:
150738274937250*105456=15,896,255,521,782,636,000≈2 64 .
Такое огромное число вариантов внушало обманчивое чувство неуязвимости.
Криптоанализ Энигмы
Большое пространство ключей обеспечивает шифру Энигмы достаточно серьезный уровень стойкости к атакам по известному шифртексту.Полный перебор 2 64 вариантов даже на современных компьютерах дело не простое.
Однако все меняется если применить атаку с известным открытым текстом. Для такого случая существует весьма хитроумный метод, позволяющих пренебречь настройками коммутационной панели в процессе поиска ключевой комбинации, что сводит пространство ключей Энигмы всего к 105456 комбинациям и делает весь шифр фатально уязвимым.
Метод эксплуатирует наличие в паре открытый-закрытый текст так называемых «циклов». Чтобы объяснить понятие «цикл», рассмотрим следующее открытое сообщение P и соответствующий ему криптотекст C, зашифрованный Энигмой.
P = WETTERVORHERSAGEBISKAYA
C = RWIVTYRESXBFOGKUHQBAISE
Запишем каждый символ из пары в виде таблицы:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| w | e | t | t | e | r | v | o | r | h | e | r | s | a | g | e | b | i | s | k | a | y | a |
| r | w | i | v | t | y | r | e | s | x | b | f | o | g | k | u | h | q | b | a | i | s | e |
Обратите внимание на подстановки, реализуемые энигмой в 14, 15 и 20 позициях. На 14 шаге буква A шифруется в G. Последняя, в свою очередь, шифруется в K на 15 шаге. И затем буква K зашифровывается в A на 20 шаге, закольцовывая тем самым цепочку A-G-K-A. Такие закольцованные цепочки называются циклами. Наличие циклов позволяет разделить задачу взлома Энигмы на две простые составные части: 1) поиск стартового положения роторов и 2) поиск соединений коммутационной панели при известных установках роторов.
Мы знаем, что при шифровании в Энигме происходит несколько преобразований. Сперва сигнал проходит через коммутационную панель. Результат преобразования на коммутационной панели поступает в роторы. После чего сигнал попадает на рефлектор и возвращается через роторы на коммутационную панель, где выполняется последняя подстановка. Все эти операции можно представить математической формулой:
E i = S -1 R -1 TRS, где
S и S -1 , - преобразование на коммутационной панели на входе и выходе соответственно;
R и R -1 - преобразование в роторах на входе и выходе;
T - преобразование на рефлекторе.
Опустив коммутационную панель выразим внутреннее преобразование Энигмы через P i:
P i = R -1 TR
Теперь шифрование можно записать как:
E i = S -1 P i S
Используя формулу перепишем подстановки из примера в 14, 15 и 20 позициях.
S -1 P 14 S(A) = G или что одно и тоже P 14 S(A) = S(G).
P 15 S(G) = S(K)
P 20 S(K) = S(A)
Заменив в последнем выражении S(K) получим:
P 20 P 15 P 14 S(A) = S(A) (1), где S(A) - буква, соединенная с A на коммутационной панели.
Теперь атака сводится к тривиальному перебору всех возможных установок ротора. Для каждой комбинации роторов необходимо проверить выполнение равенства (1). Если равенство выполняется для буквы S, это означает что найдена правильная конфигурация роторов и что буква A соединена на коммутационной панели с буквой S. Поиск остальных пар сводится к по буквенной расшифровке криптотекста и сопоставлению результата с известным открытым текстом.
Следует отметить, что с вероятностью 1/26 равенство может выполняться и при неправильной установке роторов, поэтому для повышения надежности алгоритма желательно использовать несколько «циклов».
Еще один важный момент связан с тем, что атакующему может быть известна только часть зашифрованного сообщения. И в таком случае, прежде всего ему потребуется найти местоположение известного текста в полученной криптограмме. В решении этой задачи очень сильно помогает знание того факта, что Энигма никогда не шифрует букву саму в себя. Т.е. для нахождения правильного смещения нужно найти такую позицию в криптотексте при которой ни одна из букв закрытого текста не дублируется буквой открытого сообщения.
P.S.
Очень медленную, но вполне рабочую реализацию атаки на Python можно посмотреть наAll specialists unanimously agreed that a reading is impossible.
Admiral Kurt Fricke, Chief of Naval War Command
Энигма - роторная шифровальная машина, использовавшаяся нацистской Германией в годы Второй мировой войны. Благодаря влиянию, оказанному на ход войны, взлом Энигмы стал, возможно, самым ярким моментом в многовековой истории криптоанализа. В этом топике я бы хотел рассказать о методе взлома, использовавшимся в Блетчли-парк, а так же описать устройство самой машины.
Роторные машины
Впервые шифровальные роторные машины начали использоваться в начале 20 века. Основным компонентом таких устройств является диск (он же ротор) с 26 электрическими контактами на обоих сторонах диска. Каждый контакт соответствовал букве английского алфавита. Соединение контактов левой и правой сторон реализовывало шифр простой замены. При вращении диска контакты смещались, изменяя тем самым подстановку для каждой буквы. Один диск обеспечивал 26 различных подстановок. Это означает, что при шифровании одного и того же символа, получаемая в результате последовательность начинает повторяться через 26 шагов.Для увеличения периода последовательности можно использовать несколько роторов, соединенных последовательно. При совершении полного оборота одного из дисков, следующий диск сдвигается на одну позицию. Это увеличивает длину последовательности до 26 n , где n - количество соединенных последовательно роторов.
В качестве примера рассмотрим следующее изображение упрощенной роторной машины:
Приведенная машина состоит из клавиатуры (для ввода символа), трех дисков, индикатора (для отображения криптотекста) и реализует шифрование 4 символов: A, B, C, D. В начальной позиции первый диск реализует подстановку: A-C; B-A; C-B; D-D. Подстановки второго и третьего дисков равны A-B; B-C; C-A; D-D и A-A; B-C; C-B; D-D соответственно.
При нажатии буквы B на клавиатуре замыкается электрическая цепь, зависящая от текущего положения роторов, и на индикаторе загорается лампочка. В приведенном выше примере буква B будет зашифрована в C. После чего первый ротор сдвинется на одну позицию и настройки машины приобретут следующий вид:
Энигма
Энигма является наиболее популярным представителем мира шифровальных роторных машин. Она использовалась германскими войсками во время второй мировой войны и считалась практически не взламываемой.Процедура шифрования Энигмы реализована как в приведенном выше примере за исключением некоторых дополнительных штрихов.
Во-первых, число роторов в разных версиях Энигмы могло отличаться. Наиболее распространенной была Энигма с тремя роторами, но использовался так же вариант с четырьмя дисками.
Во-вторых, процесс расшифровки демонстрационной роторной машины, описанной выше, отличается от процесса шифрования. Каждый раз для расшифровки придется менять левый и правый ротор местами, что может быть не совсем удобным. Для решения этой проблемы в Энигме был добавлен еще один диск, который назывался рефлектор. В рефлекторе все контакты были соединены попарно, реализуя тем самым повторное прохождение сигнала через роторы, но уже по другому маршруту. В отличие от остальных роторов рефлектор всегда находился в фиксированном положении и не вращался.
Добавим рефлектор, реализующий замену (A-B; C-D) к нашей демонстрационной шифровальной машине. При нажатии на клавишу B сигнал проходит через роторы и поступает в рефлектор через контакт C. Здесь сигнал «отражается» и возвращается обратно, проходя через роторы в обратном порядке и по другому пути. В результате чего буква B на выходе преобразуется в D.
Обратите внимание, что если нажать клавишу D, то сигнал пойдет по той же самой цепи, преобразовывая D в B. Таким образом наличие рефлектора делало процессы шифрования и дешифрования идентичными.
Еще одно свойство Энигмы, связанное с рефлектором, заключается в невозможности шифрования какой-либо буквы в саму себя. Это свойство сыграло очень важную роль при взломе Энигмы.
Получившееся устройство уже очень похоже на настоящую Энигму. С одной незначительной оговоркой. Стойкость подобной машины упирается в секретность внутренней коммутации роторов. Если устройство роторов будет раскрыто, то взлом сводится к подбору их начальных позиций.
Так как каждый ротор может находится в одной из 26 позиций, для трех роторов получаем 26 3 =17476 вариантов. При этом сами роторы тоже могут располагаться в произвольном порядке, что увеличивает сложность в 3! раз. Т.е. пространство ключей такой машины составит 6*17576=105456. Этого явно не достаточно для того, чтобы обеспечить высокий уровень безопасности. Поэтому Энигма было оснащена еще одним дополнительным инструментом: коммутационной панелью
. Соединяя на коммутационной панели буквы попарно можно было добавить еще один дополнительный шаг к шифрованию.
К примеру, предположим что на коммутационной панели буква B соединена с буквой A. Теперь при нажатии на A сперва происходит подстановка A-B, и на вход первого ротора подается буква B.
Аналогичным образом происходит расшифровка сообщения. При нажатии клавиши D роторы и рефлектор производят преобразование D-D-D-D-C-B-A-B. После чего коммутационная панель преобразует B в A.
Анализ стойкости Энигмы
Реальная Энигма отличалась от описанной демонстрационной машиной только в одном. А именно в устройстве роторов. В нашем примере ротор изменяет свое положение только при совершении полного оборота предыдущим диском. В настоящей Энигме каждый диск имел специальную выемку, которая в определенной позиции подцепляла следующий ротор и сдвигала его на одну позицию.Расположение выемки для каждого из роторов можно было регулировать с помощью специальных внешних колец. Начальное положение колец не влияло на коммутацию роторов и на результат шифрования отдельно взятой буквы, поэтому кольца не учитываются при расчете пространства ключей Энигмы.
Итак, базовая модель Энигмы имела 3 различных ротора, пронумерованных римскими цифрами I, II, III и реализующих следующие подстановки:
Entry = ABCDEFGHIJKLMNOPQRSTUVWXYZ
I = EKMFLGDQVZNTOWYHXUSPAIBRCJ
II = AJDKSIRUXBLHWTMCQGZNPYFVOE
III = BDFHJLCPRTXVZNYEIWGAKMUSQO
При шифровании роторы можно было располагать в любой последовательности, что для трех роторов дает 6 разных комбинаций.
Помимо этого каждый ротор мог быть установлен в одной из 26 возможных стартовых позиций. Т.е. начальное положение роторов имеет всего
6*26 3 =105456 комбинаций.
Количество всех возможных соединений на коммутационной панели вычисляется по формуле n! /((n-2m)! m! 2 m), где n - количество букв алфавита, m - количество соединенных пар.
Для 26 буква английского алфавита и 10 пар это составляет 150738274937250=2 47 различных комбинаций.
Таким образом базовая версия Энигмы с тремя роторами имела солидное даже по современным меркам пространство ключей:
150738274937250*105456=15,896,255,521,782,636,000≈2 64 .
Такое огромное число вариантов внушало обманчивое чувство неуязвимости.
Криптоанализ Энигмы
Большое пространство ключей обеспечивает шифру Энигмы достаточно серьезный уровень стойкости к атакам по известному шифртексту.Полный перебор 2 64 вариантов даже на современных компьютерах дело не простое.
Однако все меняется если применить атаку с известным открытым текстом. Для такого случая существует весьма хитроумный метод, позволяющих пренебречь настройками коммутационной панели в процессе поиска ключевой комбинации, что сводит пространство ключей Энигмы всего к 105456 комбинациям и делает весь шифр фатально уязвимым.
Метод эксплуатирует наличие в паре открытый-закрытый текст так называемых «циклов». Чтобы объяснить понятие «цикл», рассмотрим следующее открытое сообщение P и соответствующий ему криптотекст C, зашифрованный Энигмой.
P = WETTERVORHERSAGEBISKAYA
C = RWIVTYRESXBFOGKUHQBAISE
Запишем каждый символ из пары в виде таблицы:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| w | e | t | t | e | r | v | o | r | h | e | r | s | a | g | e | b | i | s | k | a | y | a |
| r | w | i | v | t | y | r | e | s | x | b | f | o | g | k | u | h | q | b | a | i | s | e |
Обратите внимание на подстановки, реализуемые энигмой в 14, 15 и 20 позициях. На 14 шаге буква A шифруется в G. Последняя, в свою очередь, шифруется в K на 15 шаге. И затем буква K зашифровывается в A на 20 шаге, закольцовывая тем самым цепочку A-G-K-A. Такие закольцованные цепочки называются циклами. Наличие циклов позволяет разделить задачу взлома Энигмы на две простые составные части: 1) поиск стартового положения роторов и 2) поиск соединений коммутационной панели при известных установках роторов.
Мы знаем, что при шифровании в Энигме происходит несколько преобразований. Сперва сигнал проходит через коммутационную панель. Результат преобразования на коммутационной панели поступает в роторы. После чего сигнал попадает на рефлектор и возвращается через роторы на коммутационную панель, где выполняется последняя подстановка. Все эти операции можно представить математической формулой:
E i = S -1 R -1 TRS, где
S и S -1 , - преобразование на коммутационной панели на входе и выходе соответственно;
R и R -1 - преобразование в роторах на входе и выходе;
T - преобразование на рефлекторе.
Опустив коммутационную панель выразим внутреннее преобразование Энигмы через P i:
P i = R -1 TR
Теперь шифрование можно записать как:
E i = S -1 P i S
Используя формулу перепишем подстановки из примера в 14, 15 и 20 позициях.
S -1 P 14 S(A) = G или что одно и тоже P 14 S(A) = S(G).
P 15 S(G) = S(K)
P 20 S(K) = S(A)
Заменив в последнем выражении S(K) получим:
P 20 P 15 P 14 S(A) = S(A) (1), где S(A) - буква, соединенная с A на коммутационной панели.
Теперь атака сводится к тривиальному перебору всех возможных установок ротора. Для каждой комбинации роторов необходимо проверить выполнение равенства (1). Если равенство выполняется для буквы S, это означает что найдена правильная конфигурация роторов и что буква A соединена на коммутационной панели с буквой S. Поиск остальных пар сводится к по буквенной расшифровке криптотекста и сопоставлению результата с известным открытым текстом.
Следует отметить, что с вероятностью 1/26 равенство может выполняться и при неправильной установке роторов, поэтому для повышения надежности алгоритма желательно использовать несколько «циклов».
Еще один важный момент связан с тем, что атакующему может быть известна только часть зашифрованного сообщения. И в таком случае, прежде всего ему потребуется найти местоположение известного текста в полученной криптограмме. В решении этой задачи очень сильно помогает знание того факта, что Энигма никогда не шифрует букву саму в себя. Т.е. для нахождения правильного смещения нужно найти такую позицию в криптотексте при которой ни одна из букв закрытого текста не дублируется буквой открытого сообщения.
P.S.
Очень медленную, но вполне рабочую реализацию атаки на Python можно посмотреть наНемецкая шифровальная машинка была названа "Загадкой" не для красного словца. Вокруг истории ее захвата и расшифровки радиоперехватов ходят легенды, и во многом этому способствует кинематограф. Мифы и правда о немецком шифраторе - в нашем материале.
Перехвату противником сообщений, как известно, можно противопоставить только их надежную защиту или шифрование. История шифрования уходит корнями в глубь веков — один из самых известных шифров называется шифром Цезаря. Потом предпринимались попытки механизации процесса шифрования и дешифрования: до нас дошел диск Альберти, созданный в 60-х годах XV века Леоном Баттиста Альберти, автором "Трактата о шифрах" — одной из первых книг об искусстве шифровки и дешифровки.
Машинка Enigma, использовавшаяся Германией в годы Второй мировой войны, была не уникальна. Но от аналогичных устройств, взятых на вооружение другими странами, она отличалась относительной простотой и массовостью использования: применить ее можно было практически везде — и в полевых условиях, и на подводной лодке. История Enigma берет начало в 1917 году — тогда голландец Хьюго Коч получил на нее патент. Работа ее заключалась в замене одних букв другими за счёт вращающихся валиков.
Историю декодирования машины Enigma мы знаем в основном по голливудским блокбастерам о подводных лодках. Однако фильмы эти, по мнению историков, имеют мало общего с реальностью.
Например, в картине 2000 года U-571 рассказывается о секретном задании американских моряков захватить шифровальную машинку Enigma, находящуюся на борту немецкой субмарины U-571. Действие разворачивается в 1942 году в Северной Атлантике. Несмотря на то, что фильм отличается зрелищностью, история, рассказанная в нем, совершенно не отвечает историческим фактам. Подводная лодка U-571 действительно состояла на вооружении нацистской Германии, но была потоплена в 1944 году, а машинку Enigma американцам удалось захватить лишь в самом конце войны, и серьезной роли в приближении Победы это не сыграло. К слову, в конце фильма создатели сообщают исторически верные факты о захвате шифратора, однако появились они по настоянию консультанта картины, англичанина по происхождению. С другой стороны режиссер фильма Джонатан Мостов заявил, что его лента "представляет собой художественное произведение".
Европейские же фильмы стараются соблюсти историческую точность, однако доля художественного вымысла присутствует и в них. В фильме Майкла Аптеда "Энигма", вышедшего в 2001 году, рассказывается история математика Тома Джерико, которому предстоит всего за четыре дня разгадать обновленный код немецкой шифровальной машинки. Конечно, в реальной жизни на расшифровку кодов ушло гораздо больше времени. Сначала этим занималась криптологическая служба Польши. И группа математиков — Мариан Реевский, Генрих Зыгальский и Ежи Рожицкий, — изучая вышедшие из употребления немецкие шифры, установили, что так называемый дневной код, который меняли каждый день, состоял из настроек коммутационной панели, порядка установки роторов, положений колец и начальных установок ротора. Случилось это в 1939 году, еще перед захватом Польши нацистской Германией. Также польское "Бюро шифров", созданное специально для "борьбы" с Enigma, имело в своем распоряжении несколько экземпляров работающей машинки, а также электромеханическую машинку Bomba, состоявшую из шести спаренных немецких устройств, которая помогала в работе с кодами. Именно она впоследствии стала прототипом для Bombe — изобретения Алана Тьюринга.
Свои наработки польская сторона сумела передать британским спецслужбам, которые и организовали дальнейшую работу по взлому "загадки". Кстати, впервые британцы заинтересовали Enigma еще в середине 20-х годов, однако, быстро отказались от идеи расшифровать код, видимо, посчитав, что сделать это невозможно. Однако с началом Второй мировой войны ситуация изменилась: во многом благодаря загадочной машинке Германия контролировала половину Атлантики, топила европейские конвои с продуктами и боеприпасами. В этих условиях Великобритании и другим странам антигитлеровской коалиции обязательно нужно было проникнуть в загадку Enigma.
Сэр Элистер Деннисон, начальник Государственной школы кодов и шифров, которая располагалась в огромном замке Блетчли-парк в 50 милях от Лондона, задумал и провел секретную операцию Ultra, обратившись к талантливым выпускникам Кембриджа и Оксфорда, среди которых был и известный криптограф и математик Алан Тьюринг. Работе Тьюринга над взломом кодов машинки Enigma посвящен вышедший в 2014 году фильм "Игра в имитацию". Еще в 1936 году Тьюринг разработал абстрактную вычислительную "машину Тьюринга", которая может считаться моделью компьютера — устройства, способного решить любую задачу, представленную в виде программы — последовательности действий. В школе кодов и шифров он возглавлял группу Hut 8, ответственную за криптоанализ сообщений ВМФ Германии и разработал некоторое количество методов взлома немецкого шифратора. Помимо группы Тьюринга, в Блетчли-парке трудились 12 тысяч сотрудников. Именно благодаря их упорному труду коды Enigma поддались расшифровке, но взломать все шифры так и не удалось. Например, шифр "Тритон" успешно действовал около года, и даже когда "парни из Блетчли" раскрыли его, это не принесло желаемого результата, так как с момента перехвата шифровки до передачи информации британских морякам проходило слишком много времени.
Все дело в том, что по распоряжению Уинстона Черчилля все материалы расшифровки поступали только начальникам разведслужб и сэру Стюарту Мензису, возглавлявшему МИ-6. Такие меры предосторожности были предприняты, чтобы немцы не догадались о раскрытии шифров. В то же время и эти меры не всегда срабатывали, тогда немцы меняли варианты настройки Enigma, после чего работа по расшифровке начиналась заново.
В "Игре в имитацию" затронута и тема взаимоотношений британских и советских криптографов. Официальный Лондон действительно был не уверен в компетенции специалистов из Советского Союза, однако по личному распоряжению Уинстона Черчилля 24 июля 1941 года в Москву стали передавать материалы с грифом Ultra. Правда, для исключения возможности раскрытия не только источника информации, но и того, что в Москве узнают о существовании Блетчли-парка, все материалы маскировались под агентурные данные. Однако в СССР узнали о работе над дешифровкой Enigma еще в 1939 году, а спустя три года на службу в Государственную школу кодов и шифров поступил советский шпион Джон Кэрнкросс, который регулярно отправлял в Москву всю необходимую информацию.
Многие задаются вопросами, почему же СССР не расшифровал радиоперехваты немецкой "Загадки", хотя советские войска захватили два таких устройства еще в 1941 году, а в Сталинградской битве в распоряжении Москвы оказалось еще три аппарата. По мнению историков, сказалось отсутствие в СССР современной на тот момент электронной техники.
К слову, специальный отдел ВЧК, занимающийся шифровкой и дешифровкой, был созван в СССР 5 мая 1921 года. На счету сотрудников отдела было много не очень, по понятным причинам - отдел работал на разведку и контрразведку, — афишируемых побед. Например, раскрытие уже в двадцатых годах дипломатических кодов ряда стран. Был создан и свой шифр — знаменитый "русский код", который, как говорят, расшифровать не удалось никому.
История электрической роторной шифровальной машины «Энигма» начинается в 1917 году с патента , полученного голландцем Хьюго Кочем. В следующем году патент был перекуплен Артуром Шербиусом , начавшим коммерческую деятельность с продажи экземпляров машины как частным лицам, так и немецким армии и флоту . До середины 1920-х годов продажи шли плохо, в частности, из-за высокой цены .
В июне 1924 года британская криптографическая служба (Room 40) заинтересовалась устройством машины. С этой целью была закуплена партия машин у германской компании Chiffrier-maschinen AG, производившей «Энигму». Одним из условий сделки была регистрация патента в британском патентном бюро, благодаря чему криптографическая служба получила доступ к описанию криптографической схемы .
Польский этап
Первые перехваты сообщений, зашифрованных при помощи «Энигмы», относятся к 1926 году. Однако прочитать их долгое время не могли. В январе 1929 года коробка с коммерческим вариантом «Энигмы» случайно попала на варшавскую таможню. Германия попросила вернуть коробку, после чего её содержимым заинтересовались поляки. По поручению польского «Бюро шифров» машина была изучена специалистами фирмы «AVA», в том числе её руководителем криптоаналитиком Антонием Пальтхом, после чего коробку отправили в германское посольство. Изучение машины не позволило дешифровать сообщения, к тому же германские военные использовали свой, усиленный вариант «Энигмы» .
В 1928-29 годах в Польше были организованы первые математические курсы по криптографии. Слушателями были два десятка студентов-математиков со знанием немецкого языка. Трое из слушателей - Мариан Реевский , Генрих Зыгальский и Ежи Рожицкий - поступили на службу в «Бюро шифров» . Впоследствии именно они получат первые результаты по вскрытию кода «Энигмы» .
В 1931 году сотрудник шифрбюро министерства обороны Германии Ганс-Тило Шмидт , ставший уже агентом «Аше», начал передавать французской разведке вышедшие из употребления коды, которые, согласно служебным обязанностям, ему требовалось уничтожать, а также передал инструкцию по использованию военного варианта «Энигмы». Среди причин, побудивших Ганс-Тило сделать это, были и материальное вознаграждение, и обида на родную страну, не оценившую его успехи во время Первой мировой войны , и зависть к армейской карьере брата Рудольфа Шмидта . Первыми двумя документами стали «Gebrauchsanweisung für die Chiffriermaschine Enigma» и «Schlüsselanleitung für die Chiffriermaschine Enigma» . Французская и английская разведки, однако, не проявили интереса к полученным данным - возможно, считалось, что вскрыть шифр «Энигмы» невозможно. Полковник французской разведки Гюстав Бертран передал материалы польскому «Бюро шифров» и продолжал передавать им дальнейшую информацию от агента до осени 1939 года .
- настроек коммутационной панели; (нем. Steckerverbindungen )
- порядка установки роторов; (нем. Walzenlage )
- положений колец; (нем. Ringstellung )
- начальных установок роторов. (нем. Kenngruppen )
Однако оператор не должен был использовать дневной ключ для шифрования сообщений. Вместо этого оператор придумывал новый ключ из трёх букв (нем. Spruchschlüssel ) и дважды шифровал его с использованием дневного ключа. После чего настройки роторов менялись в соответствии с придуманным ключом и производилось шифрование сообщения .
Усилия Мариана сосредоточились на анализе уязвимости протокола обмена сообщениями, а именно - на повторении ключа сообщения. Из ежедневных сообщений выбирались первые шесть букв и на их основе составлялась таблица соответствия (примеры взяты из книги Сингха ):
| Сообщение 1 | L | O | K | R | G | M | … | |
| Сообщение 2 | M | V | T | X | Z | E | … | |
| Сообщение 3 | J | K | T | M | P | E | … | |
| Сообщение 4 | D | V | Y | P | Z | X | … |
| 1-я буква | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| 4-я буква | P | M | R | X |
Если сообщений было достаточно, то таблица заполнялась полностью.
| 1-я буква | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| 4-я буква | F | Q | H | P | L | W | O | G | B | M | V | R | X | U | Y | C | Z | I | T | N | J | E | A | S | D | K |
Особенность полного варианта таблицы заключалась в том, что пока дневной ключ остаётся без изменений, содержимое таблицы также не меняется. И, с большой степени вероятности, наоборот. Можно было бы составить каталог таблиц… однако их количество равно 26!, что делает эту работу невозможной в обозримое время. Реевский стал пытаться выделить из таблиц некоторые шаблоны или найти некоторые структурные закономерности. И это ему удалось. Он стал рассматривать цепочки букв следующего вида :
| 1-я буква | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| A → F → W → A | ↓ | ↓ | ↓ | |||||||||||||||||||||||
| 4-я буква | F | Q | H | P | L | W | O | G | B | M | V | R | X | U | Y | C | Z | I | T | N | J | E | A | S | D | K |
В примере полной таблицы выше таких цепочек оказалось 4:
- A → F → W → A
- B → Q → Z → K → V → E → L → R → I → B
- C → H → G → O → Y → D → P → C
- J → M → X → S → T → N → U → J
Следующим открытием Мариана стало то, что хотя конкретные буквы зависели от дневной настройки «Энигмы» полностью, количество цепочек и букв в них задавалось только настройками роторов. Так как количество роторов было равно 3 (но они могли стоять в любом порядке), а начальная настройка состояла из трех букв латинского алфавита, то число вариантов было равно 3 ! ∗ 26 3 = 105456 {\displaystyle 3!*26^{3}=105456} . Это было значительно меньше чем 26!, что позволило, используя построенные (или украденные) машины «Энигма» составить каталог, содержащий все возможные цепочки. Данная работа заняла почти год, однако результатом стала возможность читать германскую переписку .
Как отмечает Сингх, именно возможность разделить задачу на две составляющих (настройки роторов и настройки коммутационной панели) позволили Реевскому справиться с данной задачей, а также помощь как математиков «Бюро шифров», так и Шмидта :
После того, как настройки роторов для дневного сообщения были восстановлены, оставалось выяснить настройки коммутационной панели. С криптографической точки зрения это был простой моноалфавитный шифр , дополнительно ограниченный лишь 6 парами замен букв. Текст даже часто не требовалось подвергать частотному криптоанализу, а всего-лишь присмотреться к строкам вроде «alliveinbelrin» (англ. arrive in Berlin с заменой R ↔ L) и другим, которые было легко восстановить «на глаз» .
В 1934 году Германия начала менять конфигурацию положения роторов каждый месяц вместо каждого квартала. В ответ на это Мариан Реевский спроектировал устройство под названием «циклометр», позволяющий быстро воссоздать каталог циклов .
15 декабря 1938 года Германия добавила 4-й и 5-й роторы, а 1 января 1939 года увеличила количество соединений коммутационной панели с 6 до 10. Всё это значительно затруднило криптоанализ «Энигмы» .
PC Bruno
Британский этап
Дальнейшая работа по взлому «Энигмы» проходила в секретном центре британской разведки «Station X», известном впоследствии как Блетчли-парк .
Кадры
Руководителем проекта был назначен ветеран военной разведки Алистер Деннистон . Работу по дешифровке возглавил коллега Деннистона по комнате № 40 , известный лингвист и криптоаналитик Альфред Нокс («Dilly» Knox). За общую организацию работы отвечал профессор-математик Гордон Уэлчман . Деннистон начал набирать штат криптоаналитиков по принципу умственных способностей: лингвистов, математиков, шахматистов, чемпионов по решению кроссвордов , египтологов и даже палеонтологов . В частности, одним из первых был принят известный шахматный мастер Стюарт Милнер-Бэрри (Stuart Milner-Barry). Среди математиков был и молодой профессор логики из Кембриджа - Алан Тьюринг .
Метод
Перехват радиосообщений противника выполняли десятки приемных станций, имевших кодовое название «Y-station». Ежедневно в Блетчли-парк поступали тысячи таких сообщений. Блетчли-парк имел в своем распоряжении точную копию «Энигмы», поэтому расшифровка сообщений сводилась к подбору установки дисков и, для более поздних моделей, - штекерного коммутатора.
Сложность задачи усугублялась тем, что установки роторов менялись ежедневно, поэтому службы дешифровки работали круглосуточно в три смены .
Конструкция «Энигмы» при правильном использовании обеспечивала практически полную секретность . На практике, однако, со стороны немецких пользователей «Энигмы» зачастую допускались небрежные действия, дававшие подсказки британским аналитикам (такие подсказки на сленге английских студентов назывались cribs ). Именно на использовании и систематизации таких погрешностей и был основан метод дешифровки.
Подсказками служили любые часто повторяющиеся тексты, такие как приветствия, цифры (кодировались по произношению: «один», «два» и т. д. ). Все подсказки заносились в картотеку (Index) вместе с контекстом: почерком радиста, местом и временем передачи и т. п.
При отсутствии необходимого количества подсказок, особенно накануне крупных операций, проводились специальные мероприятия по их получению. Этот прием получил кодовое название «садоводство » (англ. gardening ). Например, перед выходом очередного полярного конвоя проводилось демонстративное минирование определённого участка моря. Если противник докладывал результаты разминирования с указанием заранее известных координат, это давало искомую подсказку.
Тьюринг
Одним из основных теоретиков Блетчли-парка был Алан Тьюринг . После изучения польских материалов Тьюринг пришёл к выводу, что использовать прежний подход с полным перебором сообщений уже не получится. Во-первых, это потребует создания более 30 машин польского типа, что во много раз превышало годовой бюджет «Station X», во-вторых, можно было ожидать, что Германия может исправить конструктивный недостаток, на котором основывался польский метод. Поэтому он разработал собственный метод, основанный на переборе последовательностей символов исходного текста.
Вскоре немцы добавили в конструкцию Энигмы коммутирующее устройство, существенно расширив этим количество вариантов кода. Возникшую для англичан задачу решил Гордон Уэлчман , предложив конструкцию «диагональной доски». В результате этой работы в августе 1940 года была построена криптоаналитическая машина Bombe . Со временем в Блетчли-Парке было установлено более 200 машин , что позволило довести темп расшифровки до двух-трёх тысяч сообщений в день .
Хотя Bombe претерпевала некоторые изменения в деталях, её общий вид оставался прежним: шкаф весом около тонны, передняя панель два на три метра и 36 групп роторов на ней, по три в каждой. Использование машины требовало специальных навыков, и сильно зависело от квалификации обслуживающего персонала - девушек-добровольцев из Women’s Royal Naval Service (англ. ) . Впоследствии, когда часть работ была перенесена в США, вместе с технологиями была направлена и часть сотрудниц .
«Живая» информация
Время от времени Германия вносила в машину конструктивные изменения или каким-либо способом усиливала криптографическую защиту. В таких случаях криптоаналитики из Блетчли-парка оказывались бессильными, и для дальнейшей работы срочно требовалось найти описание изменений или хотя бы новые экземпляры инструкций и машин «Энигма» .
Секретность
«Это моя курочка-ряба, которая несет золотые яйца, но никогда не кудахчет.»
Уинстон Черчилль о Блетчли-парке
Английское правительство делало все возможное для того, чтобы скрыть успехи в расшифровке немецких шифров как от противника, так и от руководства СССР. С этой целью все действия, основанные на данных программы «Ультра» должны были сопровождаться операциями прикрытия, маскирующими истинный источник информации . Так, для передачи сведений «Ультра» в СССР использовалась швейцарская организация Lucy, располагавшая по легенде источником в верхах немецкого руководства. Информацию, полученную от Lucy, передавал в СССР резидент советской разведки в Швейцарии Шандор Радо .
Для маскировки «Ультра» применялись фиктивные разведывательные полеты, радиоигра и т. п. мероприятия.
О существовании программы «Ультра» было известно строго ограниченному кругу лиц, число которых составляло порядка десяти человек. Необходимые сведения передавались по назначению сетью подразделений разведки, прикомандированных к штабам командующих армии и флота. Источник сведений при этом не раскрывался, что иногда приводило к недооценке британским командованием вполне надёжных сведений «Ультры» и крупным потерям (См. Гибель авианосца «Глориес»).
СССР
В числе полученной Великобританией информации были и сведения о подготовке вторжения в СССР . Несмотря на риск раскрытия источника, сведения были переданы советскому правительству . Однако Сталин не поверил в возможность нападения .
Оценки результатов
Некоторые авторы указывают, что с современной точки зрения шифр «Энигмы» был не очень надёжным . Однако в своё время его абсолютная надежность не вызывала никаких сомнений у немецких специалистов: до самого конца войны немецкое командование искало причины утечек секретной информации где угодно, но не в раскрытии «Энигмы». Именно поэтому успех британских дешифровщиков стал особенно ценным вкладом в дело победы над нацизмом.
После войны
См. также
Примечания
- Случались и ошибки: среди приглашенных в проект оказался биолог капитан-лейтенант Джеффри Танди - специалист по криптогамам
- Макс Ньюман , Том Флауэрс и другие специалисты попали в Блетчли-парк позднее в связи с работой над шифром «Танни ».
- Шифром «Энигмы» пользовались не только армия, авиация и флот, но и военная разведка (Abwehr), железная дорога и другие службы. Все они применяли собственные установки роторов.
- Важным недостатком конструкции была невозможность кодирования буквы той же самой буквой. Эта особенность «Энигмы» была широко использована при дешифровке
- Тюринг подметил, что цифра «один» (нем. Eins ) встречается в 90 % сообщений. На этой основе был построен особый метод дешифровки - «eins-алгоритм». В качестве crib использовалось даже приветствие Heil Hitler и грубые ругательства, что особенно забавляло многочисленный женский персонал Блетчли-парка
- Польская машина называлась «бомба» (польск. Bomba kryptologiczna - Криптологическая бомба). По-английски бомба - bomb . Её название, по одной из версий, происходит от названия десерта из мороженого Bombe glacée («One theory was that bomba was named after the ice cream, bombe glacee, which was being eaten when the machine was invented.» // Enigma: The Battle for the Code, By Hugh Sebag-Montefiore, 2002, ISBN 978-0-471-43721-5).
- Изготовлением Bombe занималась компания «British Tabulating Machines» (англ. ) ; проект машины сделал главный конструктор компании Гарольд Кин (англ. Harold Keen ).
- Машины и обслуживающий персонал размещались вне территории Блетчли-парка в окружающих поселках.
- Версия отказа от защиты Ковентри ради сохранения секретности Ultra, не соответствует действительности и основана исключительно на воспоминаниях Ф. У. Винтерботтама, - офицера RAF не имевшего доступа к подобной информации. Версия Винтерботтама неоднократно опровергалась другими мемуаристами и историками.
- СССР имел некоторые сведения о программе Ultra от своего агента в Блетчли-парке - Джона Кернкросса , одного из членов Кембриджской пятерки . Англичане не подозревали о роли Кернкросса до 1951 г.
- Ф. Уинтерботем пишет, что в дальнейшем, из соображений секретности, англичане информацией не делились. Так, по мнению Уинтерботема, о Курской операции вермахта в СССР узнали из других источников. Нужно учитывать, однако, что книга Уинтерботема вышла до снятия грифа секретности с британских архивов о дешифровке кода «Лоренц» (1975), а сам он, будучи во время войны офицером ВВС, доступа к секретным сведениям об «Энигме» не имел. Архивные же материалы однозначно свидетельствуют о передаче в Москву детального плана
Про немецкую шифровальную машину «Энигма» слышали, наверное, все. Не в последнюю очередь благодаря тому, что ее историю любят писатели и сценаристы, а ко взлому ее шифра причастен отец современного компьютера Алан Тьюринг.
Во время войны он, как и многие другие математики (а также лингвисты, египтологи, шахматисты и даже составители кроссвордов), работал в так называемой Правительственной школе кодов и шифров, расположившейся в имении Блетчли-парк в Англии и являвшейся операционным и интеллектуальным центром работы по перехвату и расшифровке коммуникаций противника.
Шифровальная машина «Энигма»
В двух словах история выглядит примерно так: «Энигма» была самой совершенной на тот момент шифровальной машиной, которая позволяла защищать коммуникации флота и армии нацистской Германии таким образом, что взлом представлялся неразрешимой задачей. Однако польским и британским криптоаналитикам удалось найти способ расшифровывать сообщения «Энигмы» , что дало коалиции существенное преимущество в войне, по мнению Черчилля и Эйзенхауэра - решающее.
Подробно о том, как работала «Энигма», можно , а в этом ролике можно даже посмотреть, как она работает:
В самом общем виде схема выглядит примерно следующим образом: когда оператор, набирая сообщение, нажимал клавишу с буквой на клавиатуре, сигнал проходил по электрической цепи, образуемой несколькими роторами с контактами, и на панели с буквами загоралась уже другая буква, которую и нужно было включить в зашифрованное сообщение. Роторы поворачивались после каждого ввода каждого знака, и в следующий раз та же буква кодировалась уже другой.
Создание криптоаналитической машины «Бомба», которая и позволила поставить взлом сообщений «Энигмы» на поток, стало результатом не только научной и аналитической работы, но и ошибок немецкой стороны
Создание криптоаналитической машины «Бомба», которая и позволила поставить взлом сообщений «Энигмы» на поток, стало результатом сочетания не только колоссальной научной и аналитической работы, но и ошибок немецкой стороны в работе с «Энигмой», захвата различных экземпляров машины и шифроблокнотов, а также спецопераций, позволявших криптоаналитикам работать с сообщениями, исходный текст которых содержал заведомо известные слова.
Чем поучительна история «Энигмы» для нас сегодня? Сама по себе машина с точки зрения современных представлений о защите информации практического интереса уже не представляет, однако многие из уроков истории «Энигмы» актуальны и сегодня:
1. Не стоит полагаться на собственное технологическое превосходство. У немецкой стороны были все основания считать «Энигму» абсолютно надежной, но союзники создали свою машину, которая обладала достаточной «мощностью», чтобы за короткое время перебирать возможные варианты настроек «Энигмы» в поисках правильного и расшифровывать сообщения. Это был технологический скачок, который трудно было предсказать. Сегодня мы довольно точно знаем, как называется «Бомба» для всей современной криптографии: .
2. Иногда сложно предположить, что именно окажется «слабым звеном» в хорошо продуманной схеме защиты информации. Невозможность совпадения буквы в исходном сообщении и его зашифрованном варианте может показаться несущественной деталью или даже правильным решением, однако именно это помогло наладить машинную отбраковку неприменимых вариантов ключа - надо было просто отбросить все варианты, дававшие хотя бы одно совпадение буквы в исходной и зашифрованной версиях.
3. Никогда не надо лениться усложнять ключ. Для большинства пользователей этот совет в первую очередь . В свое время добавление лишнего ротора к военно-морской модификации «Энигмы» на полгода парализовало работу криптоаналитиков, и начать расшифровку сообщений усовершенствованной машины удалось только после захвата ее экземпляра с потопленной подлодки. Как вы можете легко убедиться с помощью нашего сервиса проверки пароля , всего один дополнительный знак может увеличить время подбора вашего пароля на порядок.
4. Человеческий фактор играет огромную роль даже в высокотехнологичных системах. Неизвестно, удалось бы взломать «Энигму», если бы не различные мелкие ошибки и послабления, которые позволяли себе ее операторы. К человеческому фактору, по-видимому, надо отнести и упорство, с которым немецкое командование искало иные объяснения неожиданной прозорливости союзников, вместо того чтобы допустить мысль о компрометации «Энигмы».
5. Информационное превосходство - обоюдоострое оружие. Чуть ли не самой сложной задачей для командования союзников стало использование данных, полученных из расшифровки сообщений «Энигмы», таким образом, чтобы не раскрыть противнику сам факт доступа к зашифрованным сообщениям. Иногда это решалось с помощью специальных операций по созданию альтернативных объяснений успеха (пролет самолета разведчика перед нападением на конвой, слив информации о якобы имевшемся ценном источнике агентурных данных), иногда приходилось просто отказываться от каких-то шагов (пришлось допустить бомбардировку Ковентри немецкой авиацией, как если бы о ее подготовке ничего не было известно).
Мы совершенствуем наши технологии, наращиваем вычислительную мощность день ото дня, но базовые принципы работы с информацией и ее защиты меняются гораздо медленнее, и прошлое по-прежнему несет в себе много полезных уроков.
5 по-прежнему актуальных уроков, которые можно извлечь из взлома «Энигмы» во время Второй мировой
