Пасьянс (шифр)

Криптографический алгоритм «Пасьянс» был разработан Брюсом Шнайером по просьбе Нила Стивенсона для использования в его романе «Криптономикон» , в котором полевые агенты используют его для безопасного общения без необходимости полагаться на электронику или носить с собой компрометирующие инструменты. ^[1] Он был разработан как ручная криптосистема , рассчитываемая с помощью обычной колоды игральных карт . В «Криптономиконе » этот алгоритм изначально назывался Pontifex, чтобы скрыть тот факт, что в нем задействованы игральные карты.

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

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

В этом алгоритме используется стандартная колода карт, содержащая 52 одномастные карты и два отличающихся друг от друга джокера, называемые джокером А и джокером Б. Для простоты в этом примере будут использоваться только две масти: трефовая и бубновая. Каждой карте присвоено числовое значение: трефы будут пронумерованы от 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 Б 3 6 9 12 15 18 21 24 А 2 5 8 11 14 17 20 23 26

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

Найдите джокера А и переместите его вниз по колоде на одно место. Если это последняя карта, она становится второй картой. У нее нет возможности стать первой картой. Колода теперь выглядит так:
- 1 4 7 10 13 16 19 22 25 Б 3 6 9 12 15 18 21 24 2 А 5 8 11 14 17 20 23 26
Найдите джокера B и переместите его вниз по колоде на два места. Обратите внимание: если это предпоследняя карта, она становится второй картой при заворачивании. Если это последняя карта, она становится третьей картой. У нее нет возможности стать первой картой.
- 1 4 7 10 13 16 19 22 25 3 6 Б 9 12 15 18 21 24 2 А 5 8 11 14 17 20 23 26
Выполните «тройной разрез»: разделите колоду на три части, разделенные джокерами, и поменяйте местами верхнюю и нижнюю часть. Сами джокеры и карты между ними остаются нетронутыми.
- 5 8 11 14 17 20 23 26 Б 9 12 15 18 21 24 2 А 1 4 7 10 13 16 19 22 25 3 6
Выполните «подсчет»: обратите внимание на значение карты внизу колоды. Если карта представляет собой любой из джокеров, примите ее значение равным 27 (53 при использовании полной колоды). Удалите указанное количество карт сверху колоды и вставьте их чуть выше последней карты колоды.
- 23 26 Б 9 12 15 18 21 24 2 А 1 4 7 10 13 16 19 22 25 3 5 8 11 14 17 20 6
Теперь посмотрите на значение верхней карты. Опять же, любой джокер считается за 27 (53 при использовании полной колоды). Подсчитайте это количество мест ниже этой карты и примите значение этой карты в качестве следующего значения в ключевом потоке. Если карта, на которую рассчитывается, является джокером, проигнорируйте ее и повторите алгоритм ключевого потока. В этом примере верхняя карта — 23, поэтому 24-я карта, равная 11, определяет значение ключевого потока. (Обратите внимание, что на этом этапе никакие карты не меняются местами; этот шаг просто определяет значение ключевого потока).

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

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

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

В 2019 году Дэниел Шиу предложил модификации алгоритма, которые повысят его безопасность за счет того, что пользователю будет сложнее реализовать его вручную. ^[3]

Ссылки

^ Шнайер, Брюс (май 1999 г.). «Пасьянс» . Проверено 2 июля 2006 г.
^ Jump up to: ^а ^б Кроули, Пол. «Проблемы с «Пасьянсом» Брюса Шнайера » . Проверено 26 марта 2018 г.
^ Jump up to: ^а ^б Шиу, Дэниел (13 сентября 2019 г.). «Анализ пасьянса». arXiv : 1909.06300 [ cs.CR ].

Внешние ссылки

Описание пасьянса Шнайера

[1] Шнайер, Брюс (май 1999 г.). «Пасьянс» . Проверено 2 июля 2006 г.

[ciphergoth-2] Jump up to: ^а ^б Кроули, Пол. «Проблемы с «Пасьянсом» Брюса Шнайера » . Проверено 26 марта 2018 г.

[shiu-3] Jump up to: ^а ^б Шиу, Дэниел (13 сентября 2019 г.). «Анализ пасьянса». arXiv : 1909.06300 [ cs.CR ].

[1]

[2]

[3]