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

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

Стивенсону был необходим алгоритм шифрования, который бы позволил агентам — персонажам его книги «Криптономикон» - обмениваться секретной информацией, не вызывая подозрений. «Пасьянс» идеально удовлетворял этим требованиям, поскольку позволял агентам шифровать сообщения без использования электроники или каких-либо компрометирующих устройств. В книге алгоритм назывался «Понтифик», чтобы скрыть тот факт, что для шифрования используются карты.

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

Основная идея этого алгоритма в том, что он генерирует так называемые «гаммы» чисел от 1 до 26. Для шифрования необходимо генерировать количество «гамм» равное количеству букв в тексте. Затем добавить их по модулю 26 к каждой из букв текста. К примеру, рассмотрим процесс шифрования первого сообщения из книги «Криптономикон» «DO NOT USE PC»:

1) Разделяем сообщения на группы по пять символов (это к шифрованию отношения не имеет, просто так принято), для дополнения последней группы при необходимости используем X. В нашем случае получаем:

• «DONOT USEPC»

2) Используем «Пасьянс» для генерации десяти гамм (детали ниже), допустим они:

• «KDWUP ONOWT»

3) Переводим буквы из сообщения в цифры: A=1, B=2 и т. д., получаем:

• 4 15 14 15 20 21 19 5 16 3

4) Подобным же образом переводим «гаммы»:

• 11 4 23 21 16 15 14 15 23 20

5) Складываем сообщение и «гаммы» по модулю 26:

• 15 19 11 10 10 10 7 20 13 23

6) Переводим полученную сумму обратно в буквы:

• «OSKJJ JGTMW»

При наличии достаточно большой практики можно попробовать сразу производить «сложение» букв, что значительно ускорит процесс шифрования.

Основная идея расшифрования заключается в том, что адресат генерирует такие же «гаммы» и вычитает их из шифротекста.

1) Разделяем шифротекст на группы из пяти символов:

• «OSKJJ JGTMW»

2) Используем колоду карт для генерации «гамм». Если получатель использует тот же ключ, что и адресант, то «гаммы» будут одинаковыми:

• «KDWUP ONOWT»

3) Переводим шифротекст из букв в числа:

• 15 19 11 10 10 10 7 20 13 23

4) Аналогично поступаем с «гаммами»:

• 11 4 23 21 16 15 14 15 23 20

5) Вычитаем гаммы из шифротекста по модулю 26:

• 4 15 14 15 20 21 19 5 16 3

6) Переводим полученную сумму обратно в буквы:

• «DONOT USEPC»

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

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

«Пасьянс» генерирует «гаммы» при помощи колоды карт. Карточная колода состоит из 54 карт, что дает нам количество перестановок равное 54!, что приблизительно равно 2,3·10⁷¹. Ещё лучше, что, не считая джокеров, в колоде 52 карты, а в алфавите 26 букв. Для шифрования нужна колода с 54 картами, причём джокеры должны как-то отличаться друг от друга. Условно обозначим одного из джокеров А, а другого В. Для «инициализации» колоды необходимо расположить карты в определённом порядке, это и будет ключ. Затем надо взять карты рубашкой вниз, теперь можно генерировать «гаммы».

1) Находим джокера А, перемещаем его на одну карту вниз, то есть меняем местами с картой под ним.

2) Находим джокера В, перемещаем его на две карты вниз. Таким образом, если карты были расположены в таком порядке перед первым шагом:

• A 7 2 B 9 4 1,

то после второго шага:

• 7 A 2 9 4 B 1.

Если же имеем вначале, например,

• 3 A B 8 9 6,

то в конце получим

• 3 A 8 B 9 6.

3) Выполняем «тройной разрез», то есть меняем карты над первым джокером с картами под вторым джокером. То есть, если колода будет выглядеть так:

• 2 4 6 B 5 8 7 1 A 3 9,

то после этого шага она перейдёт в:

• 3 9 B 5 8 7 1 A 2 4 6.

Как видно, здесь «первый» и «второй» относятся к порядку, в котором джокеры встречаются в колоде. Главное — запомнить, что сами джокеры и карты между ними никак не двигаются и не меняются во время этого шага. И если колода будет выглядеть перед этим шагом следующим образом:

А … В,

то после 3-го шага ничего не изменится.

4) Смотрим на нижнюю карту в колоде, ставим ей в соответствие число от 1 до 53.

Делаем это следующим образом: если масть карты — трефы, то это значение, соответствующее показанному на карте; если это бубны, то значение плюс 13; если червы, то значение плюс 26; пики — значение плюс 39. Любой джокер — 53. Теперь отсчитываем это же число карт, начиная с первой, и помещаем их между нижней картой и остатком колоды.

Если колода изначально выглядела следующим образом:

• 7 … cards .. 4 5 … cards … 8 9,

то после этого шага она перейдет в:

• 5 … cards … 8 7 … cards … 4 9

Причина, по которой последняя карта остаётся на месте — необходимость сделать этот шаг обратимым. Если нижним в колоде был джокер, то она остаётся неизменной после этого шага.

5) Находим карту, с помощью которой будет создаваться «гамма». Для этого сопоставляем верхней карте число от 1 до 53 как в четвёртом шаге. Отсчитываем это количество карт. Записываем карту, которая лежит под той, до которой досчитали, на бумаге, оставляя её в колоде (если попадаем на джокера, то начинаем снова с первого шага). Это и есть интересующая нас карта. Заметим, что на этом шаге не меняется порядок карт в колоде.

6) Переводим карту из пятого шага в число. Это проделывается так же, как и в четвёртом шаге с одним исключением. Поскольку в алфавите 26 букв, то трефы и червы нумеруем от 1 до 13, а пики и бубны — от 14 до 26. Затем переходим к буквам.

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

В общем и целом не обязательно придерживаться правил нумерации карт, приведенных здесь, главное, чтобы оба человека придерживались одной схемы.

Несмотря на то, что в исходной статье автора алгоритма указывается, что он обратим, ситуация, когда джокер оказывается внизу колоды и затем перемещается наверх при инициации колоды, делает процесс необратимым. Здесь стоит отметить, что необратимые генераторы псевдослучайных чисел имеют более короткие периоды и имеют склонность к повторению. Действительно, при использовании алгоритма «Пасьянс» возможна генерация числа от 1 до 26, то есть каждое из них должно выходить с вероятностью 1/26, однако в реальности эта вероятность больше — 1/22,5.^[2]

Можно придумать и русскую версию данного шифра, например, выбросив из алфавита букву «ё», получим 32 символа плюс 2 карты аналога джокеров, итого — 34. Это позволяет использовать обычную колоду в 36 карт без, скажем, пары шестерок. Огромный минус такого использования — понижение стойкости ключа. Этот вариант, вероятно, оптимальный, потому что в случае оставления 52 карт и проведения вычислений аналогичных вычислениям в оригинальном варианте, но по модулю 32, получаем возможность частотного анализа. Другой вариант — придумать преобразование исходного текста, написанного с использованием всех 33 букв русского алфавита в текст, содержащий только какие-то 26 букв.^[3]

Одним из недостатков является то, что шифрование и дешифрование занимает долгое время. Но в сравнении с другими подобными шифрами это время является приемлемым. Например, реальный шифр, который использовался советскими шпионами, описанный Дэвидом Канном, занимает для шифрования достаточно большого сообщения столько же времени, как и «Пасьянс»: приблизительно один вечер.