Шифр с бегучим ключом: принципы и современные варианты

Введение

Тип полиалфавитного шифра подстановки

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

Варианты

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

Переключатели

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

Шифрованный текст, который выглядит как обычный текст

Традиционный шифротекст существенно отличается от открытого текста. Для решения этой проблемы один из вариантов выводит слова открытого текста вместо букв открытого текста в качестве шифротекста. Это достигается путем создания "алфавита" слов (на практике несколько слов могут соответствовать каждому символу выходных данных шифротекста). В результате получается шифротекст, который выглядит как длинная последовательность слов открытого текста (процесс может быть вложенным). Теоретически, это ничем не отличается от использования стандартных символов шифротекста в качестве выходных данных. Однако, шифротекст, похожий на открытый текст, может привести к тому, что "человек в контуре" попытается ошибочно интерпретировать его как расшифрованный открытый текст. Примером является BDA (алгоритм дефлятора Беркхоффа), где каждому символу выходных данных шифротекста соответствует как минимум одно существительное, глагол, прилагательное и наречие (например, как минимум по одному для каждого символа ASCII). Генерируются грамматически корректные предложения в качестве выходных данных шифротекста. Расшифровка требует сопоставления слов обратно с ASCII, а затем расшифровки символов в реальный открытый текст с использованием бегущего ключа. Вложенный BDA многократно пропускает выходные данные через процесс повторного шифрования, создавая несколько слоев шифротекста, "похожего на открытый текст", каждый из которых потенциально требует участия "человека в контуре" для попытки интерпретировать его отсутствующий семантический смысл.

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

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

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

Если ключевой ключ действительно случайный, никогда не используется повторно и хранится в секрете, результатом является одноразовый шифр – метод, обеспечивающий абсолютную секретность (не раскрывающий никакой информации об открытом тексте). Однако, если (как обычно) ключевой ключ представляет собой блок текста на естественном языке, безопасность существенно снижается, поскольку этот текст обладает неслучайными характеристиками, которые могут быть использованы в криптоанализе: например, во время Первой мировой войны Уильям Фридман предложил атаку только по шифротексту, направленную на наиболее часто встречающиеся буквы, закодированные другими наиболее часто встречающимися буквами. В результате энтропия на символ как открытого текста, так и ключевого ключа оказывается низкой, а операция объединения легко обратима. Для взлома шифра криптоаналитик может последовательно подставлять предполагаемые вероятные открытые тексты к шифротексту, вычитая их из каждой возможной позиции. Если в результате получается фрагмент осмысленного текста, существует высокая вероятность того, что угаданный открытый текст верен для этой позиции (либо как фактический открытый текст, либо как часть ключевого ключа). Этот "фрагмент осмысленного текста" часто можно расширить с обоих концов, получая еще более вероятный открытый текст, который, в свою очередь, можно расширить и так далее (более подробное объяснение см. в описании шифра автоключа). В конечном итоге, вероятно, будет установлен источник ключевого ключа, и дело будет раскрыто. Существует несколько способов повысить безопасность. Первый и самый очевидный – использовать секретную перемешанную таблицу алфавита вместо таблицы табулы ректа. Это действительно значительно усложняет задачу, но не является полным решением. Как показано на примере метода Фридмана, пары символов открытого текста и ключевого ключа гораздо чаще представляют собой пары высокой частоты, такие как "EE", а не, скажем, "QQ". Смещение, которое это вызывает в распределении частот выходных данных, смягчается тем фактом, что вполне возможно, что "EE" и "QQ" отображаются в один и тот же символ шифротекста, но распределение все равно не является равномерным. Это может позволить криптоаналитику вывести часть таблицы, а затем продолжить работу как и прежде (но с пробелами там, где в реконструированной таблице отсутствуют секции). Другая возможность – использовать ключевой текст с большей энтропией на символ, чем типичный английский язык. С этой целью КГБ рекомендовал агентам использовать такие документы, как альманахи и торговые отчеты, которые часто содержат длинные списки чисел, кажущихся случайными. Еще одна проблема заключается в том, что пространство ключей на удивление мало. Предположим, что существует 100 миллионов ключевых текстов, которые могут быть использованы, и что в среднем каждый из них имеет 11 тысяч возможных начальных позиций. Для противника, располагающего огромной коллекцией возможных ключевых текстов, это позволяет провести перебор с поиском грубой силой порядка , что по стандартам компьютерной криптографии является относительно легкой целью. (См. выше о методах генерации ключей на основе перестановок для подхода к решению этой проблемы).

If the running key is truly random, never reused, and kept secret, the result is a one time pad, a method that provides perfect secrecy (reveals no information about the plaintext). However, if (as usual) the running key is a block of text in a natural language, security actually becomes fairly poor, since that text will have non random characteristics which can be used to aid cryptanalysis: for example, William F. Friedman suggested a ciphertext only attack during WWI against most frequent letters encoded by other most frequent letters. As a result, the entropy per character of both plaintext and running key is low, and the combining operation is easily inverted. To attack the cipher, a cryptanalyst may run guessed probable plaintexts along the ciphertext, subtracting them out from each possible position. When the result is a chunk of something intelligible, there is a high probability that the guessed plain text is correct for that position (as either actual plaintext, or part of the running key). The 'chunk of something intelligible' can then often be extended at either end, thus providing even more probable plaintext, which can in turn be extended, and so on (for more detailed explanation refer to Autokey cipher). Eventually it is likely that the source of the running key will be identified, and the jig is up. There are several ways to improve the security. The first and most obvious is to use a secret mixed alphabet tableau instead of a tabula recta. This does indeed greatly complicate matters but it is not a complete solution. As exploited in Friedman's method, pairs of plaintext and running key characters are far more likely to be high frequency pairs such as 'EE' rather than, say, 'QQ'. The skew this causes to the output frequency distribution is smeared by the fact that it is quite possible that 'EE' and 'QQ' map to the same ciphertext character, but nevertheless the distribution is not flat. This may enable the cryptanalyst to deduce part of the tableau, then proceed as before (but with gaps where there are sections missing from the reconstructed tableau). Another possibility is to use a key text that has more entropy per character than typical English. For this purpose, the KGB advised agents to use documents like almanacs and trade reports, which often contain long lists of random looking numbers. Another problem is that the keyspace is surprisingly small. Suppose that there are 100 million key texts that might plausibly be used, and that on average each has 11 thousand possible starting positions. To an opponent with a massive collection of possible key texts, this leaves possible a brute force search of the order of , which by computer cryptography standards is a relatively easy target. (See permutation generated running keys above for an approach to this problem).

Спутанность

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