Автоключевой шифр (также известный как автоклавный шифр ) — это шифр , который включает сообщение ( открытый текст ) в ключ . Ключ генерируется из сообщения каким-то автоматизированным способом, иногда путем выбора определенных букв из текста или, что встречается чаще, путем добавления короткого праймерного ключа в начало сообщения.
Существует две формы шифра автоключа: шифры ключ-автоключ и текст-автоключ . Шифр ключ-автоключ использует предыдущие элементы потока ключей для определения следующего элемента в потоке ключей. Шифр текст-автоключ использует текст предыдущего сообщения для определения следующего элемента в потоке ключей.
Этот шифр был изобретен в 1586 году Блезом де Виженером с обратной таблицей из десяти алфавитов. Версия Виженера использовала согласованную букву алфавита в качестве праймера, создавая ключ, записывая эту букву, а затем остальную часть сообщения. [1]
Более популярные автоключи используют tabula recta , квадрат с 26 копиями алфавита, первая строка начинается с «A», следующая строка начинается с «B» и т. д. Вместо одной буквы используется короткое согласованное ключевое слово, а ключ генерируется путем записи праймера, а затем остальной части сообщения, как в версии Виженера. Для шифрования открытого текста находятся строка с первой буквой сообщения и столбец с первой буквой ключа. Буква, в которой пересекаются строка и столбец, является буквой зашифрованного текста.
Шифр автоключа, используемый членами Американской ассоциации криптограмм , начинается с относительно короткого ключевого слова, праймера , и добавляет к нему сообщение. Например, если ключевое слово QUEENLYи сообщение attack at dawn, то ключ будет QUEENLYATTACKATDAWN. [2]
Открытый текст: атака на рассветеКлюч: QUEENLYATTACKATDAWNШифрованный текст: QNXEPVYTWTWP
Таким образом, зашифрованное сообщение будет иметь вид «QNXEPVYTWTWP».
Чтобы расшифровать сообщение, получатель должен был начать с записи согласованного ключевого слова.
QNXEPVYTWTWPКОРОЛЕВСКИЙ
Затем берется первая буква ключа, Q, и эта строка находится в tabula recta. Этот столбец для первой буквы шифртекста просматривается, также Q в этом случае, и извлекается буква наверху, A. Теперь эта буква добавляется в конец ключа:
QNXEPVYTWTWPКОРОЛЕВСКИЙ А а
Затем, поскольку следующая буква в ключе — U, а следующая буква в зашифрованном тексте — N, просматривается строка U, чтобы найти N и получить T:
QNXEPVYTWTWPКОРОЛЕВСКИЙ AT в
Это продолжается до тех пор, пока не будет восстановлен весь ключ, после чего можно будет удалить праймер с самого начала.
При использовании шифра с автоключом Виженера единственная ошибка в шифровании делает остальную часть сообщения непонятной. [3]
Шифры Autokey несколько более безопасны, чем полиалфавитные шифры, которые используют фиксированные ключи, поскольку ключ не повторяется в пределах одного сообщения. Поэтому такие методы, как проверка Касиски или анализ индекса совпадений , не будут работать с шифротекстом, в отличие от аналогичных шифров, которые используют один повторяющийся ключ. [3]
Однако решающим недостатком системы является то, что открытый текст является частью ключа. Это означает, что ключ, скорее всего, будет содержать общие слова в разных местах. Ключ можно атаковать, используя словарь общих слов, биграмм , триграмм и т. д., и пытаясь расшифровать сообщение, перемещая это слово через ключ, пока не появится потенциально читаемый текст.
Рассмотрим пример сообщения, meet at the fountainзашифрованного с помощью ключевого слова primer KILT: [4] Для начала автоключ будет создан путем помещения primer в начало сообщения:
открытый текст: meetatthefountainпраймер: KILTавтоключ: KILTMEETATTHEFOUN
Затем сообщение шифруется с использованием ключа и алфавитов подстановки, в данном случае это tabula recta:
открытый текст: meetatthefountainключ: KILTMEETATTHEFOUNЗашифрованный текст: WMPMMXXAEYHBRYOCA
Атакующий получает только зашифрованный текст и может атаковать текст, выбрав слово, которое, скорее всего, появится в открытом тексте. В этом примере атакующий выбирает слово theкак потенциальную часть исходного сообщения, а затем пытается расшифровать его, помещая THEв каждое возможное место в ключе:
зашифрованный текст: WMP MMX XAE YHB RYO CAключ: THE THE THE THE THE ..открытый текст: dfl tft eta fax yrk ..Зашифрованный текст: W MPM MXX AEY HBR YOC Aключ: . THE THE THE THE .открытый текст: . tii tqt hxu oun fhy.Зашифрованный текст: WM PMM XXA EYH BRY OCAключ: .. THE THE THE THE THE THEоткрытый текст: .. wfi eqw lrd iku vvw
В каждом случае полученный открытый текст выглядит почти случайным, поскольку ключ не выровнен для большей части зашифрованного текста. Однако, изучая результаты, можно предположить, что места расположения ключа были выровнены должным образом. В этих случаях полученный расшифрованный текст потенциально является частью слова. В этом примере крайне маловероятно, что это dflначало исходного открытого текста, и поэтому крайне маловероятно, что первые три буквы ключа являются THE. Изучая результаты, можно увидеть ряд фрагментов, которые, возможно, являются словами, а другие можно исключить. Затем фрагменты открытого текста можно отсортировать в порядке их вероятности:
маловероятно ←——————————————————→ многообещающийeqw dfl tqt ... ... ... ... этот факс или факс
Правильный фрагмент открытого текста также появится в ключе, сдвинутом вправо на длину ключевого слова. Аналогично, угаданная часть ключа ( THE) также появится в открытом тексте, сдвинутом влево. Таким образом, угадывая длину ключевых слов (вероятно, от 3 до 12), можно раскрыть больше открытого текста и ключа.
Попытка сделать это с помощью oun, возможно, после потери некоторого времени с другими, приводит к следующему:
сдвиг на 4:Зашифрованный текст: WMPMMXXAEYHBRYOCAключ: ......ETA.THE.OUNоткрытый текст: ......the.oun.ain
сдвиг на 5:Зашифрованный текст: WMPMMXXAEYHBRYOCAключ: .....EQW..THE..OUоткрытый текст: .....the..oun..og
сдвиг на 6:Зашифрованный текст: WMPMMXXAEYHBRYOCAключ: ....TQT...THE...Oоткрытый текст: ....the...oun...m
Можно увидеть, что сдвиг на 4 выглядит хорошо (оба других имеют маловероятные Q), поэтому раскрытый текст ETAможно сдвинуть обратно на 4 в открытый текст:
Зашифрованный текст: WMPMMXXAEYHBRYOCAключ: ..LTM.ETA.THE.OUNоткрытый текст: ..eta.the.oun.ain
Сейчас можно работать со многим. Ключевое слово, вероятно, состоит из 4 символов ( ..LT), и часть сообщения видна:
м.эта.те.оун.айн
Поскольку догадки открытого текста влияют на ключевые 4 символа слева, дается обратная связь по правильным и неправильным догадкам. Пробелы можно быстро заполнить:
встреча у фонтана
Простота криптоанализа обусловлена обратной связью от связи между открытым текстом и ключом. Угадывание трех символов открывает еще шесть символов (по три с каждой стороны), которые затем открывают дополнительные символы, создавая каскадный эффект. Это позволяет быстро исключить неверные угадывания.