Шифр Нигилиста: Ручной симметричный шифр и его эволюция

Введение

Ручной симметричный шифр

В истории криптографии шифр нигилистов — это ручной симметричный шифр, первоначально использовавшийся русскими нигилистами в 1880-х годах для организации террористической деятельности против царского режима. Этот термин иногда распространяется на несколько усовершенствованных алгоритмов, которые позднее использовались Первым Главным управлением для связи со своими агентами.

Описание

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

Криптоанализ

Поскольку каждый символ как в открытом тексте, так и в ключе используется в виде целого числа без каких-либо дробных частей, базовый шифр Нигилиста – это, по сути, числовая версия шифра Виженера, где зашифрованными символами являются многозначные числа вместо букв. Следовательно, на него можно атаковать очень похожими методами. Дополнительная слабость заключается в том, что использование обычного сложения (вместо модульного сложения) раскрывает дополнительную информацию. Например, (если предположить квадрат 5 × 5), если число в шифротексте больше 100, то можно с уверенностью утверждать, что и открытый текст, и ключ были взяты из пятой строки таблицы.

Позднейшие варианты или производные

Во время Второй мировой войны несколько советских шпионских групп связывались с Московским центром, используя два шифра, которые по сути являлись эволюционным усовершенствованием базового шифра Нигилиста. Очень сильная версия применялась Максом Клаузеном в сети Ричарда Сорге в Японии и Александром Футом в шпионском кольце «Люси» в Швейцарии. Несколько более слабая версия использовалась сетью «Rote Kapelle». В обеих версиях открытый текст сначала преобразовывался в цифры с помощью шахматной доски с перестановкой, а не квадрата Полибия. Это давало преимущество в незначительной компрессии открытого текста, тем самым увеличивая его однозначность, а также позволяя радиооператорам быстрее завершать передачу и раньше отключаться. Более раннее отключение снижало риск обнаружения оператора радиопеленгаторами противника. Увеличение расстояния однозначности повышало устойчивость к статистическим атакам. Клаузен и Фут писали свои сообщения на английском языке и запомнили 8 наиболее часто встречающихся букв английского языка (для заполнения верхнего ряда шахматной доски) с помощью мнемонической (и слегка зловещей) фразы «a sin to err» (исключив второе «r»). Стандартная английская шахматная доска с перестановкой содержит 28 символов, и в этом шифре они обозначались как «точка» и «сдвиг цифр». Цифры передавались с помощью сдвига цифр, за которым следовали фактические цифры открытого текста в повторяющихся парах, а затем еще один сдвиг. Затем, аналогично базовому шифру Нигилиста, добавлялась цифровая прибавка, называемая «замыканием». Однако каждый раз использовалась другая прибавка, поэтому в конечном итоге потребовалось вставить скрытую «индикаторную группу», чтобы указать, какая прибавка была использована. В отличие от базового шифра Нигилиста, прибавка добавлялась без переноса (поразрядное сложение по модулю 10), что давало более однородный результат, который не раскрывал столько информации. Что еще более важно, прибавка генерировалась не с помощью ключевого слова, а путем случайного выбора строк из альманахов промышленной статистики. Такие книги считались достаточно скучными, чтобы не вызывать подозрений при обыске агента (особенно учитывая, что легенды агентов были связаны с бизнесом), и обладали достаточно высокой плотностью энтропии, чтобы обеспечить надежную прибавку. Конечно, цифры из такой книги не распределены равномерно (наблюдается избыток «0» и «1» (см. закон Бенфорда), и последовательные числа, вероятно, будут несколько похожи), но тем не менее они имеют гораздо более высокую плотность энтропии, чем пароли и тому подобное; во всяком случае, на практике их, по-видимому, никогда не удавалось успешно дешифровать. Более слабая версия генерировала прибавку из текста романа или аналогичной книги (по крайней мере, один член «Rote Kapelle» использовал «Хорошего солдата Швейка»). Этот текст преобразовывался в цифровую прибавку с использованием техники, аналогичной шахматной доске с перестановкой. Окончательным развитием в этом направлении стал шифр VIC, использованный в 1950-х годах Рейно Хяйхяненом. К этому времени большинство советских агентов вместо этого использовали одноразовые шифровальные книжки.

During World War II, several Soviet spy rings communicated to Moscow Centre using two ciphers which are essentially evolutionary improvements on the basic Nihilist cipher. A very strong version was used by Max Clausen in Richard Sorge's network in Japan, and by Alexander Foote in the Lucy spy ring in Switzerland. A slightly weaker version was used by the Rote Kapelle network. In both versions, the plaintext was first converted to digits by use of a straddling checkerboard rather than a Polybius square. This has the advantage of slightly compressing the plaintext, thus raising its unicity distance and also allowing radio operators to complete their transmissions quicker and shut down sooner. Shutting down sooner reduces the risk of the operator being found by enemy radio direction finders. Increasing the unicity distance increases strength against statistical attacks. Clausen and Foote both wrote their plaintext in English, and memorized the 8 most frequent letters of English (to fill the top row of the checkerboard) through the mnemonic (and slightly menacing) phrase "a sin to err" (dropping the second "r"). The standard English straddling checkerboard has 28 characters and in this cipher these became "full stop" and "numbers shift". Numbers were sent by a numbers shift, followed by the actual plaintext digits in repeated pairs, followed by another shift. Then, similarly to the basic Nihilist, a digital additive was added in, which was called "closing". However a different additive was used each time, so finally a concealed "indicator group" had to be inserted to indicate what additive was used. Unlike basic Nihilist, the additive was added by non carrying addition (digit wise addition modulo 10), thus producing a more uniform output which doesn't leak as much information. More importantly, the additive was generated not through a keyword, but by selecting lines at random from almanacs of industrial statistics. Such books were deemed dull enough to not arouse suspicion if an agent was searched (particularly as the agents' cover stories were as businessmen), and to have such high entropy density as to provide a very secure additive. Of course the figures from such a book are not actually uniformly distributed (there is an excess of "0" and "1" (see Benford's Law), and sequential numbers are likely to be somewhat similar), but nevertheless they have much higher entropy density than passphrases and the like; at any rate, in practice they seem never to have been successfully cryptanalysed. The weaker version generated the additive from the text of a novel or similar book (at least one Rote Kapelle member used The Good Soldier Schweik) This text was converted to a digital additive using a technique similar to a straddling checkerboard. The ultimate development along these lines was the VIC cipher, used in the 1950s by Reino Häyhänen. By this time, most Soviet agents were instead using one time pads.