Запуск шифра с ключом

В классической криптографии шифр с бегущим ключом — это тип многоалфавитной замены шифра , в котором текст, обычно из книги, используется для обеспечения очень длинного потока ключей . Самое раннее описание такого шифра было дано в 1892 году французским математиком Артуром Жозефом Германом (более известным как основатель Éditions Hermann ). Обычно книга, которая будет использоваться, согласовывалась заранее, а используемый отрывок выбирался случайным образом для каждого сообщения и тайно указывался где-то в сообщении.

Пример

Ключевым используемым текстом является «Язык программирования C» (издание 1978 года), а прямая таблица — это таблица. Открытый текст: «Беги немедленно».

Страница 63, строка 1 выбрана в качестве бегущей клавиши:

ошибки могут возникнуть в нескольких местах. На этикетке есть...

Затем рабочий ключ записывается под открытым текстом:

Открытый текст	ж	л	и	и	а	т	тот	н	с	и
Бегущий ключ	И	Р	Р	ТО	Р	С	С	А	Н	ТО
Зашифрованный текст	Дж	С	V	С	Р	л	вопрос	Н	П	С

Затем сообщение отправляется как «JCVSR LQNPS». Однако, в отличие от шифра Виженера , если сообщение расширено, ключ не повторяется; сам ключевой текст (текст из языка программирования C ) используется в качестве ключа и может быть расширен на любую произвольную длину. Если сообщение расширено, например: «Беги немедленно. Нас обнаружили», то бегущая клавиша продолжается, как и раньше:

Открытый текст	ж	л	и	и	а	т	тот	н	с	и	В	и	а	р	и	д	я	с	с	тот	v	и	р	и	д
Бегущий ключ	И	Р	Р	ТО	Р	С	С	А	Н	ТО	С	С	В	Р	я	Н	С	И	V	И	Р	А	л	П	л
Зашифрованный текст	Дж	С	V	С	Р	л	вопрос	Н	П	С	И	Г	В	я	М	вопрос	А	В	Х	С	М	И	С	Т	ТО

Чтобы определить, где найти работающий ключ, впоследствии добавляется поддельный блок из пяти символов зашифрованного текста, три из которых обозначают номер страницы, а два - номер строки, используя A = 0, B = 1 и т. Д. Для кодирования цифр. Такой блок называется индикаторным блоком . Блок индикатора будет вставлен предпоследним в каждое сообщение. (Возможны многие другие схемы сокрытия блоков индикаторов.) Таким образом, страница 63, строка 1 кодируется как «AGDAB» (06301).

В результате получается последнее сообщение «JCVSR LQNPS YGUIM QAWXS AGDAB MECTO».

Варианты

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

Перестановка генерирует рабочие ключи

Можно использовать более компактный рабочий ключ, если комбинаторно генерировать текст, используя несколько указателей начала (или правил комбинирования). Например, вместо того, чтобы начинать с одного места (один указатель), можно использовать несколько указателей начала и объединить потоки с помощью xor, чтобы сформировать новый рабочий ключ; аналогичным образом можно использовать правила пропуска. Затем происходит обмен серией указателей на книгу текущих ключей и/или серией правил для генерации нового перестановочного рабочего ключа из исходного текста ключа. (Ими можно обмениваться посредством шифрования с открытым ключом или лично. Их также можно часто менять без изменения текущей книги ключей.)

Зашифрованный текст выглядит как открытый текст

Традиционный зашифрованный текст сильно отличается от открытого текста. Чтобы решить эту проблему, в одном варианте в качестве зашифрованного текста выводятся слова «открытого текста» вместо букв «открытого текста». Это делается путем создания «алфавита» слов (на практике каждому выходному символу зашифрованного текста может соответствовать несколько слов). Результатом является зашифрованный текст, который выглядит как длинная последовательность слов открытого текста (процесс может быть вложенным). Теоретически это ничем не отличается от использования в качестве вывода стандартных символов зашифрованного текста. Однако зашифрованный текст, похожий на открытый текст, может привести к тому, что «человек в курсе» попытается ошибочно интерпретировать его как декодированный открытый текст.

Примером может служить BDA (алгоритм дефлятора Беркгофа). ^{[ нужна ссылка ]}, каждый выходной символ зашифрованного текста имеет по крайней мере одно связанное с ним существительное, глагол, прилагательное и наречие. (Например (по крайней мере) по одному для каждого ASCII символа ). Грамматически правдоподобные предложения генерируются в виде зашифрованного текста. Дешифрование требует преобразования слов обратно в ASCII, а затем расшифровки символов в реальный открытый текст с использованием текущего ключа. Nested-BDA несколько раз прогонит выходные данные через процесс повторного шифрования, создав несколько слоев зашифрованного текста, похожего на открытый текст, каждый из которых потенциально требует участия «человека в цикле», чтобы попытаться интерпретировать его несуществующее семантическое значение.

Шифр Громарка

«Шифр Громарка» (« шифр Гронсфельда со смешанным алфавитом и бегущим ключом») использует бегущий числовой ключ, образованный путем добавления последовательных пар цифр. ^[1]Шифр VIC использует аналогичный генератор Фибоначчи с задержкой .

Безопасность и криптоанализ

Если текущий ключ действительно случайный, никогда не используется повторно и хранится в секрете, результатом является одноразовый блокнот — метод, обеспечивающий полную секретность (не раскрывающий никакой информации об открытом тексте). Однако, если (как обычно) рабочий ключ представляет собой блок текста на естественном языке , безопасность фактически становится довольно плохой, поскольку этот текст будет иметь неслучайные характеристики, которые можно использовать для помощи в криптоанализе: например, Уильям Ф. Фридман предложил во время Первой мировой войны атаковать только зашифрованный текст против наиболее частых букв, закодированных другими наиболее частыми буквами. ^[2] В результате энтропия на символ как открытого текста, так и текущего ключа невелика, и операцию объединения легко инвертировать.

Чтобы взломать шифр, криптоаналитик может пропустить угаданные вероятные открытые тексты вдоль зашифрованного текста, вычитая их из каждой возможной позиции. Когда результатом является фрагмент чего-то понятного, существует высокая вероятность того, что угаданный открытый текст соответствует этой позиции (либо как реальный открытый текст, либо как часть текущего ключа). «Часть чего-то понятного» часто может быть расширена с любого конца, обеспечивая тем самым еще более вероятный открытый текст, который, в свою очередь, может быть расширен и т. д. (более подробное объяснение см. в разделе « Шифрование с автоматическим ключом» ). В конце концов вполне вероятно, что источник работающего ключа будет идентифицирован, и приспособление будет поднято.

Есть несколько способов повысить безопасность. Первый и наиболее очевидный — использовать секретную таблицу смешанного алфавита вместо прямой таблицы . Это действительно сильно усложняет ситуацию, но не является полным решением. Как показывает метод Фридмана, пары открытого текста и символов бегущего ключа с гораздо большей вероятностью будут высокочастотными парами, такими как «EE», а не, скажем, «QQ». Перекос, который это вызывает в распределении выходных частот, сглаживается тем фактом, что вполне возможно, что «EE» и «QQ» соответствуют одному и тому же символу зашифрованного текста, но, тем не менее, распределение не является плоским. Это может позволить криптоаналитику вывести часть таблицы, а затем продолжить действия, как и раньше (но с пробелами, когда в восстановленной таблице отсутствуют разделы).

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

Другая проблема заключается в том, что пространство ключей на удивление мало. Предположим, что существует 100 миллионов ключевых текстов, которые можно было бы использовать, и в среднем каждый из них имеет 11 тысяч возможных стартовых позиций. Для оппонента с огромной коллекцией возможных ключевых текстов это оставляет возможность перебора порядка $2^{40}$ , что по стандартам компьютерной криптографии является относительно легкой целью. (Подход к этой проблеме см. выше, сгенерированные перестановкой работающие ключи).

Путаница

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

См. также

Ссылки

^ Американская ассоциация криптограмм. «ACA и вы». Архивировано 3 апреля 2016 г. в Wayback Machine .2016.
^ «Криптология: шифры бегущего текста – криптоанализ по Фридману» . www.staff.uni-mainz.de . Проверено 10 января 2024 г.

[1] Американская ассоциация криптограмм. «ACA и вы». Архивировано 3 апреля 2016 г. в Wayback Machine .2016.

[2] «Криптология: шифры бегущего текста – криптоанализ по Фридману» . www.staff.uni-mainz.de . Проверено 10 января 2024 г.

[1]

[2]