В XIV веке появились полиалфавитные шифры, которые не удавалось взломать на протяжении целых 4-х веков. Напомню, что в полиалфавитных шифрах каждой букве исходного алфавита может соответствовать столько букв/символов, сколько алфавитов было использовано для шифрования. Казалось бы, что сложного - перебрать все варианты шифровок и получить исходное сообщение, ведь, например, в латинском алфавите всего 26 букв? Дело в том, что даже при одном произвольном алфавите замены длиной n символов количество переборов равно n! = 1 * 2 * ... * (n-1) * n, что применительно к русскому языку равно 33!, а это в свою очередь больше числа с 35-ю нулями! При двух алфавитах замены длиной n и m соответственно количество переборов уже равно n! * m!. Смекаете, сколько вариантов дешифровок существовало для полиалфавитных шифров? Так много, что часть из них невозможно было бы взломать даже на современных компьютерах, что уж говорить про эпоху Возрождения.
Но в XIX веке в игру вступил английский математик Чарльз Бэббидж - один из самых выдающихся научных деятелей того времени. В сферу его интересов входили все отрасли математики и технологий, а еще он придумал первый механический компьютер, названный разностной машиной. Забавно, что предпосылкой к созданию прародителя наших современных ЭВМ стало всего лишь изучение логарифмических таблиц: Бэббидж заметил многочисленные ошибки в вычислениях, обусловленные человеческим фактором, и именно тогда задумался о создании механизма, способного автоматически производить сложные вычисления с большой точностью.
Итак, в первую очередь свое внимание Бэббидж сосредоточил на квадрате Виженера. Заметим, что у этого шифра есть одна особенность: длина выбранного ключевого слова (или алфавита) определяет количество используемых шифроалфавитов. Ключевое слово дает первые буквы каждой строки квадрата Виженера, а далее строки продолжаются остатком алфавита. После этого ключевое слово, повторенное нужное количество раз, пишется под буквами сообщения, которое необходимо зашифровать, и в итоге буква ключевого слова под каждым символом сообщения подсказывает строку в матрице, из которой надо взять зашифрованное сообщение.
Давайте на примерах посмотрим, как же Бэббиджу удалось взломать полиалфавитный шифр.
Соответственно, если ключевое слово ЧАРЛЬЗ, каждая буква исходного сообщения может быть зашифрована шестью разными способами.
Эта особенность стала ключевой зацепкой для Бэббиджа, позволившей ему взломать полиалфавитный шифр.
Замечаете, что слово BY в обоих случаях шифруется одинаково? Так вот, при достаточно длинном сообщении такие закономерности, очевидно, встречаются каждый раз, когда совпадают несколько букв исходного сообщения и позиции букв ключевого слова.
Процедура дешифровки заключается в следующем: вы отмечаете все повторяющиеся символы и записываете, через сколько позиций они повторяются. Это количество позиций кратно количеству букв в ключевом слове, поэтому обладая этой информацией, вы можете найти все делители этих чисел, которые являются кандидатами на длину ключевого слова. В нашем случае повторение символов встречается после 8-ми символов, значит, длина улючевого слова может быть 2, 4 или 8 (а у нас 4, как мы помним).
Каждая буква ключевого слова в квадрате Виженера определяет моноалфавитный шифр, т.е количество моноалфавитов для шифрования равно количеству букв ключевого слова. Соответственно, каждая буква исходного сообщения, зашифрованная кратно количеству символов ключевого слова, шифруется одним алфавитом.
Допустим, у нас в ключевом слове 3 буквы. Тогда первая буква сообщения будет шифроваться первым шифроалфавитом, вторая - вторым, третья - третьим, четвертая - опять первым, т.е. тем же, что и первая буква сообщения, и так далее. Получается, что на самом деле мы имеем дело с тремя отдельными моноалфавитными шифрами, а каждый из них уже легко поддается частотному криптоанализу.
Используемые алфавиты - (X1, X2, X3)
Сообщение - БЭББИДЖ
Алфавиты в сообщении - X1 X2 X3 X1 X2 X3 X1
Бэббидж завершил свои работы, посвященные криптоанализу, примерно в 1854 году, но по какой-то причине решил не публиковать свое открытие - видимо, решил, что в мире недостаточно загадок, над которыми люди ломают голову :) Только недавно его исследования были найдены и стало известно, что именно он стал первым, кто сумел решить головоломку, не поддающуюся математикам более 3-х столетий.
Кстати, знаете ли вы, что первым программистом была женщина, Ада Лавлейс, ученица Чарльза Бэббиджа? Хотели бы узнать историю их дружбы и совместной работы, благодаря которым сегодня вы можете читать этот пост и вообще пользоваться компьютером? Напишите в комментариях👇