Solitaire: криптографический алгоритм с картами

Криптографический алгоритм

Криптографический алгоритм Solitaire был разработан Брюсом Шнайером (Bruce Schneier) по просьбе Нила Стивенсона (Neal Stephenson) для использования в его романе «Криптономикон» (Cryptonomicon). В романе полевые агенты используют его для безопасного общения без необходимости полагаться на электронику или носить с собой компрометирующие инструменты. Алгоритм был разработан как ручная криптосистема, которую можно вычислять с помощью обычной колоды игральных карт. В «Криптономиконе» этот алгоритм первоначально назывался Pontifex, чтобы скрыть тот факт, что он использует игральные карты.

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

Шифрование и расшифрование

Этот алгоритм использует стандартную колоду из 52 карт четырёх мастей и двух различимых джокеров, называемых джокером A и джокером B. Для простоты в этом примере используются только две масти: трефы и бубны. Каждой карте присваивается числовое значение: трефы нумеруются от 1 до 13 (туз через короля), а бубны — от 14 до 26 аналогичным образом. Джокерам присваиваются значения 27 и 28. Таким образом, валет треф имеет значение 11, а двойка бубен — 15. (В полной колоде карт масти оцениваются в порядке бриджа: трефы, бубны, черви, пики, с картами, пронумерованными от 1 до 52, и джокерами, пронумерованными 53 и 54.)

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

Алгоритм генерирует поток ключей — последовательность значений, которые объединяются с сообщением для его шифрования и расшифрования. Каждое значение потока ключей используется для шифрования одного символа сообщения, поэтому поток ключей должен быть по крайней мере такой же длины, как сообщение. Если поток ключей длиннее сообщения, сообщение может быть дополнено дополнительным повторяющимся символом, что лишает злоумышленника знания точной длины сообщения.

Для шифрования сообщения:

• Удалите всю пунктуацию и пробелы, оставив только 26 букв A–Z.
• Преобразуйте каждую букву в её естественное числовое значение: A = 1, B = 2, …, Z = 26.
• Сгенерируйте одно значение потока ключей для каждой буквы в сообщении, используя алгоритм потока ключей ниже.
• Добавьте каждое значение потока ключей к соответствующему числу открытого текста, вычитая 26, если результирующее значение больше 26. (В математике это называется модульной арифметикой.)
• Преобразуйте полученные числа обратно в буквы. Эта последовательность букв является шифротекстом.

Для расшифрования шифротекста:

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

Алгоритм потока ключей

Этот алгоритм генерирует значения потока ключей путём перемещения карт в колоде. Алгоритм потока ключей является детерминированным, поэтому значения потока ключей зависят только от начального порядка колоды. Колода рассматривается как циклический массив, что означает, что если карте когда-либо потребуется продвинуться ниже нижней карты в колоде, она просто вернётся в начало (другими словами, первая карта следует за последней картой).

Например, возьмите эту начальную колоду:

• 1 4 7 10 13 16 19 22 25 B 3 6 9 12 15 18 21 24 A 2 5 8 11 14 17 20 23 26

Выполните эти шаги для генерирования одного символа потока ключей.

• Найдите джокер A и переместите его на одну позицию вниз в колоде. Если он последняя карта, он становится второй картой. Он не может стать первой картой. Колода теперь выглядит так:

• 1 4 7 10 13 16 19 22 25 B 3 6 9 12 15 18 21 24 2 A 5 8 11 14 17 20 23 26

• Найдите джокер B и переместите его на две позиции вниз в колоде. Обратите внимание, что если он вторая с конца карта, он становится второй картой, обернувшись. Если он последняя карта, он становится третьей картой. Он не может стать первой картой.

• 1 4 7 10 13 16 19 22 25 3 6 B 9 12 15 18 21 24 2 A 5 8 11 14 17 20 23 26

• Выполните «тройной разрез»: разделите колоду на три секции, разделённые джокерами, и поменяйте местами верхнюю и нижнюю секции. Сами джокеры и карты между ними остаются нетронутыми.

• 5 8 11 14 17 20 23 26 B 9 12 15 18 21 24 2 A 1 4 7 10 13 16 19 22 25 3 6

• Выполните «разрез подсчёта»: посмотрите на значение карты в нижней части колоды. Если карта — джокер, возьмите его значение равным 27 (53 при использовании полной колоды). Удалите это количество карт с верхней части колоды и вставьте их прямо над последней картой в колоде.

• 23 26 B 9 12 15 18 21 24 2 A 1 4 7 10 13 16 19 22 25 3 5 8 11 14 17 20 6

• Теперь посмотрите на значение верхней карты. Опять же, любой джокер считается 27 (53 при использовании полной колоды). Отсчитайте это количество позиций ниже этой карты и возьмите значение этой карты как следующее значение в потоке ключей. Если карта, на которую вы отсчитали, — джокер, игнорируйте её и повторите алгоритм потока ключей. В этом примере верхняя карта — 23, поэтому 24-я карта, которая равна 11, определяет значение потока ключей. (Обратите внимание, что в этом шаге карты не меняют позиции; этот шаг просто определяет значение потока ключей).

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

В 1999 году Пол Кроули (Paul Crowley) обнаружил, что в потоке ключей существует смещение в сторону повторяющихся символов, которые встречаются примерно каждые 1/22,5 символа вместо ожидаемых 1/26. В результате Solitaire утекает информацию со скоростью примерно 0,0005 бит на символ. Хотя его безопасность может быть адекватной для очень коротких сообщений, в целом Solitaire считается небезопасным.

Кроули также заметил, что в некоторых случаях существуют две различные конфигурации колоды, которые приводят к одной и той же конфигурации после выполнения алгоритма потока ключей. Например, когда джокер A находится либо в нижней части колоды, либо в верхней части колоды, он становится второй картой после шага 1. Это означает, что алгоритм не всегда обратим, как первоначально утверждал Шнайер.

В 2019 году Дэниел Шиу (Daniel Shiu) предложил модификации алгоритма, которые повысили бы его безопасность за счёт усложнения ручной реализации для пользователя.