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

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

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

С момента его создания анализ выявил недостатки в шифре. Сейчас это считается небезопасным.

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

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

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

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

Чтобы зашифровать сообщение:

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

Чтобы расшифровать зашифрованный текст:

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

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

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

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

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

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

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

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

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

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

Рекомендации

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

внешняя ссылка