Вечная битва создания и уничтожения кодов: 80 лет машине Enigma | Кофе и теоремы | Наука

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

Первыми появились шифры моноалфавитная замена. Его работа очень проста: каждая буква исходного сообщения заменяется другим символом, чтобы получить зашифрованное сообщение. Например, все «e» заменены на «g». Проблема этой системы в том, что частота букв исходного текста передается в зашифрованный текст. Таким образом, если в зашифрованном сообщении много «g» и «q», они, вероятно, соответствуют «e» и «a», наиболее часто встречающимся буквам в тексте на испанском языке. С этой идеей, развитой в технике частотного анализа, мы могли начать взламывать код. история Золотой жукЭдгара Аллана По, история переплетается с подробным объяснением этого метода.

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

Хотя машина «Энигма» выполняет тот же тип многоалфавитного шифрования, это был большой шаг вперед по сравнению с классическими методами. Он имеет три ротора, которые устанавливают связь между клавиатурой и световой панелью. При нажатии клавиши загорается буква, которой она зашифрована, и конфигурация роторов изменяется, так что для следующей буквы используется другое правило. Детали внутреннего механизма означают, что используется огромное количество различных правил, из-за чего взломать код крайне сложно: это возможно только в том случае, если известна начальная конфигурация машины. Небольшие системные проблемы вместе с математическими и вычислительными достижениями нескольких лет работы и некоторой долей удачи, наконец, позволили расшифровать Энигму.

Одним из таких недостатков была необходимость заранее распространять информацию о конфигурации машин, рискуя ее перехватом. Таким образом, сложность безопасного обмена ключами была следующей проблемой, которую необходимо было решить, чтобы сделать системы более надежными. Ответ пришел только в 70-е годы прошлого века, с протоколом Диффи-Хеллман.

Предположим, Антонио и Беатрис хотят зашифровать свои сообщения, для чего им нужно будет согласовать секретный ключ. Этот протокол устраняет необходимость личной встречи для этого. Лежащий в основе математический процесс часто объясняют так, как если бы это была смесь разных красок. Оба агента выбирают обычно используемый цвет, который не нужно держать в секрете. И каждый тоже тайно выбирает цвет, известный только ему самому. Смешивая свои цвета с обычной краской, они получают два новых разных цвета, которые и будут информацией, которую они посылают.

Если кто-то перехватит информацию, ему будет трудно узнать ваши секретные цвета: даже если они знают «общедоступный» цвет, разделение смеси для определения цветов, из которых она состоит, — очень дорогой процесс. Однако, получив его, они могут снова добавить свой секретный цвет, получив таким образом смесь из тех же трех цветов, которая и будет их общим секретом. Чтобы перехватчик получил такой же окончательный микс, ему пришлось бы отделить один из отправленных миксов и добавить полученный частный цвет к другому. Поскольку это невозможно из-за слишком высокой стоимости, протокол является безопасным.

На самом деле этот процесс осуществляется не красками, а математикой. Его безопасность основана на быстрой операции вычисления на компьютере, возведении в степень в модульная арифметика, но очень сложно отменить, зная только результат. В то время как обычное возведение в степень следует четкой схеме, возведение в степень в модульной арифметике очень трудно предсказать и, следовательно, отменить. Это известно как проблема дискретного логарифмирования.

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

Лаура Кастилья, испанский у Хавьер Пенафиел Томас является научным сотрудником Мадридского университета Комплутенсе и Высшего совета по научным исследованиям соответственно, а также членом Институт математических наук

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

Редакция и согласование: Агат А. Руль Г. Лонгория (ICMAT).

Вы можете следить МАТЕРИА в Фейсбук, Твиттер е Инстаграмукажите здесь, чтобы получить наш еженедельный информационный бюллетень.