Сложный советский шифр "ВИК": Рукописный код холодной войны

Введение

Комплексная советская шифровка, используемая карандашом и бумагой. Шифр VIC был карандашной и бумажной шифровкой, использовавшейся советским шпионом Рейно Хяйхяненом, с позывным "VICTOR". Если бы этому шифру дали современное техническое название, он был бы известен как "разбиение на части с моноалфавитной подстановкой, усиленное модифицированной двойной транспозицией". Однако, по общей классификации, он относится к нигилистическому семейству шифров. Считается, что это был самый сложный шифр, работающий вручную, из когда-либо обнаруженных. Первоначальный анализ, проведенный Агентством национальной безопасности США (NSA) в 1953 году, не позволил однозначно заключить, что это ручной шифр, но его обнаружение внутри пустой монеты номиналом 5 центов (позже известной как дело "пустой монеты") указывало на возможность его дешифровки карандашом и бумагой. Шифр VIC оставался не взломанным до тех пор, пока не стало доступно больше информации о его структуре. Хотя он, безусловно, не так сложен и надежен, как современные компьютерные потоковые или блочные шифры, на практике сообщения, зашифрованные им, противостояли всем попыткам криптоанализа, по крайней мере, со стороны NSA, с момента его обнаружения в 1953 году до дезертирства Хяйхянена в 1957 году.

Революционный скачок

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

История

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

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 phrase "a sin to err" (dropping the second "r"). The standard English straddling checkerboard has 28 character slots and in this cipher the extra two 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 actually 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. However, despite the theoretical perfection of the one time pad, in practice they were broken, while VIC was not. The one time cipher could however only be broken when cipher pages were re used, due to logistic problems, and therefore was no longer truly one time.

Подробная механика

Примечание: в этом разделе отслеживаются вычисления со ссылками на [строку X] или подобные. Это сделано для соответствия обозначениям, указанным в описании архивных материалов ЦРУ.

Вывод ключа сообщения

[Строка Q]: Первые 'a' цифр (где 'a' – первое значение, полученное в результате сложения последних различных цифр в [строке P] с личным номером), извлеченные из [строк K, L, M, N, P] при транспонировании через [строку J]. Это транспонирование выполняется путем записи столбцов чисел под цифрами в [строке J], начиная со столбца под цифрой ‘1’, затем столбца под цифрой ‘2’ и так далее в числовом порядке, пока не будет записано 'a' цифр (в приведенном ниже примере значение 'a' будет равно 13, поэтому это транспонирование продолжится на 13 цифр). Эти цифры используются в качестве ключа для колоночной транспозиции. [Строка R]: Следующие 'b' цифр (где 'b' – второе значение, полученное в результате сложения последних различных цифр в [строке P] с личным номером), извлеченные (после извлечения 'a' цифр) из [строк K, L, M, N, P] при транспонировании через [строку J]. Это транспонирование выполняется тем же способом, что и [строка Q], но продолжается с предыдущего транспонирования, то есть может начаться посреди столбца под цифрой [строки J], где закончилось предыдущее транспонирование (в приведенном ниже примере [строка R] начинается посреди столбца под цифрой ‘3’ в [строке J]). Полученные цифры используются в качестве ключа для диагональной транспозиции. [Строка S]: Последовательность [строки P], которая используется в качестве ключа для шахматной доски со страдлированием.

Перестановки: колоннарная перестановка

Сообщение шифруется с помощью стандартной столбцовой перестановки, ключ к которой задан в [Линии Q] выше. (Примечание: если длина закодированного сообщения на этом этапе не кратна 5, добавляется дополнительная цифра.)

Затем сообщение подвергается диагональной перестановке, ключ к которой задан в [Линии R] выше. В данном случае термин "диагональная" означает, что для внесения нерегулярности в перестановку использовались треугольные области искажения.

Вставка группы ключей

(Незашифрованная) группа ключей вставляется в группы шифротекста "P" с конца, где "P" – неиспользованная шестая цифра даты.

Секвенирование

Секвенирование в данном контексте — это присвоение порядковых номеров от 1 до 10 элементам входной последовательности (где '0' соответствует 10). Это применяется либо к буквам (в алфавитном порядке), либо к числам (в порядке их числового значения). При равных значениях приоритет отдается элементу, расположенному левее. Например:

БУКВЫ: Слово 'Octopus' секвенируется как '2163475' (т.е. C=1, первая 'O'=2, вторая 'O'=3)
ЧИСЛА: Число '90210' секвенируется как '34215' (в числовом порядке. Ноль при секвенировании имеет значение '10')

Кодирование цифр

Шаг кодирования заменяет каждую цифру в числе (например, [Строка G] в шифре) на цифру из последовательности ключей (например, [Строка E.2]), которая соответствует её позиции в упорядочении от 1 до 10. Следует заметить, что если записать ряд '1234567890' (показан как [Строка F.2]) под [Строкой E.2], то для каждой цифры от 0 до 9 можно найти соответствующую цифру над ней. Просто замените каждую цифру в кодируемом числе на цифру, находящуюся над ней в последовательности ключей. Ключ (Строка E.2) 6 0 1 3 5 8 9 4 2 7 Помощь (Строка F.2) 1 2 3 4 5 6 7 8 9 0

Например, число '90210' будет закодировано следующим образом:
Таким образом, результат будет: '27067'.

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

Шифр является одним из самых надежных шифров, используемых вручную, которые фактически применялись на практике, и в свое время не был взломан АНБ (в плане определения лежащего в его основе алгоритма). Однако с развитием современных вычислительных мощностей и публичным раскрытием алгоритма, он уже не считается надежным шифром. Можно заметить, что основная часть энтропии секретного ключа концентрируется в 10-значном числе [Строка H]. Это 10-значное число обеспечивает примерно 34 бита энтропии, а в сочетании с последней цифрой даты (необходимой для определения KeyGroup) дает около 38 бит энтропии, определяющей стойкость ключа сообщения. 38 бит уязвимы для атаки полным перебором менее чем за сутки на современных компьютерах.