Криптографический алгоритм «Пасьянс» («Solitaire») — поточный шифр с обратной связью по выходу, который был разработан Брюсом Шнайером по просьбе писателя Нила Стивенсона.
Стивенсону был необходим алгоритм шифрования, который бы позволил агентам — персонажам его книги «Криптономикон» - обмениваться секретной информацией, не вызывая подозрений. «Пасьянс» идеально удовлетворял этим требованиям, поскольку позволял агентам шифровать сообщения без использования электроники или каких-либо компрометирующих устройств. В книге алгоритм назывался «Понтифик», чтобы скрыть тот факт, что для шифрования используются карты.
«Пасьянс» унаследовал свою надёжность от неотъемлемой хаотичности положения карт при перетасовке колоды. Производя определённые манипуляции с простой колодой карт, человек, шифрующий сообщение, может создать случайную последовательность символов, которые впоследствии объединяются с сообщением. Этот алгоритм может показаться достаточно ненадёжным, но, по словам самого Шнайера, «Пасьянс» может выдержать даже атаку самых сильных военных противников с огромным финансированием, мощными компьютерами и отличными криптоаналитиками и является лучшим в мире криптографическим алгоритмом, реализуемым при помощи «карандаша и бумаги».[1]
Основная идея этого алгоритма в том, что он генерирует так называемые «гаммы» чисел от 1 до 26. Для шифрования необходимо генерировать количество «гамм» равное количеству букв в тексте. Затем добавить их по модулю 26 к каждой из букв текста. К примеру, рассмотрим процесс шифрования первого сообщения из книги «Криптономикон» «DO NOT USE PC»:
1) Разделяем сообщения на группы по пять символов (это к шифрованию отношения не имеет, просто так принято), для дополнения последней группы при необходимости используем X. В нашем случае получаем:
2) Используем «Пасьянс» для генерации десяти гамм (детали ниже), допустим они:
3) Переводим буквы из сообщения в цифры: A=1, B=2 и т. д., получаем:
4) Подобным же образом переводим «гаммы»:
5) Складываем сообщение и «гаммы» по модулю 26:
6) Переводим полученную сумму обратно в буквы:
При наличии достаточно большой практики можно попробовать сразу производить «сложение» букв, что значительно ускорит процесс шифрования.
Основная идея расшифрования заключается в том, что адресат генерирует такие же «гаммы» и вычитает их из шифротекста.
1) Разделяем шифротекст на группы из пяти символов:
2) Используем колоду карт для генерации «гамм». Если получатель использует тот же ключ, что и адресант, то «гаммы» будут одинаковыми:
3) Переводим шифротекст из букв в числа:
4) Аналогично поступаем с «гаммами»:
5) Вычитаем гаммы из шифротекста по модулю 26:
6) Переводим полученную сумму обратно в буквы:
Как видно процесс дешифрования абсолютно аналогичен процессу шифрования. Данный пример достаточно прост, при конвертировании же сообщений большего размера необходимо вначале избавиться от знаков пунктуации.
Перейдем к генерации «гаммы». Это самая важная часть алгоритма, все изложенное выше верно для любого поточного шифра с обратной связью по выходу. Эта же часть относится непосредственно только к «Пасьянсу».
«Пасьянс» генерирует «гаммы» при помощи колоды карт. Карточная колода состоит из 54 карт, что дает нам количество перестановок равное 54!, что приблизительно равно 2,3·1071. Ещё лучше, что, не считая джокеров, в колоде 52 карты, а в алфавите 26 букв. Для шифрования нужна колода с 54 картами, причём джокеры должны как-то отличаться друг от друга. Условно обозначим одного из джокеров А, а другого В. Для «инициализации» колоды необходимо расположить карты в определённом порядке, это и будет ключ. Затем надо взять карты рубашкой вниз, теперь можно генерировать «гаммы».
1) Находим джокера А, перемещаем его на одну карту вниз, то есть меняем местами с картой под ним.
2) Находим джокера В, перемещаем его на две карты вниз. Таким образом, если карты были расположены в таком порядке перед первым шагом:
то после второго шага:
Если же имеем вначале, например,
то в конце получим
3) Выполняем «тройной разрез», то есть меняем карты над первым джокером с картами под вторым джокером. То есть, если колода будет выглядеть так:
то после этого шага она перейдёт в:
Как видно, здесь «первый» и «второй» относятся к порядку, в котором джокеры встречаются в колоде. Главное — запомнить, что сами джокеры и карты между ними никак не двигаются и не меняются во время этого шага. И если колода будет выглядеть перед этим шагом следующим образом:
А … В,
то после 3-го шага ничего не изменится.
4) Смотрим на нижнюю карту в колоде, ставим ей в соответствие число от 1 до 53.
Делаем это следующим образом: если масть карты — трефы, то это значение, соответствующее показанному на карте; если это бубны, то значение плюс 13; если червы, то значение плюс 26; пики — значение плюс 39. Любой джокер — 53. Теперь отсчитываем это же число карт, начиная с первой, и помещаем их между нижней картой и остатком колоды.
Если колода изначально выглядела следующим образом:
то после этого шага она перейдет в:
Причина, по которой последняя карта остаётся на месте — необходимость сделать этот шаг обратимым. Если нижним в колоде был джокер, то она остаётся неизменной после этого шага.
5) Находим карту, с помощью которой будет создаваться «гамма». Для этого сопоставляем верхней карте число от 1 до 53 как в четвёртом шаге. Отсчитываем это количество карт. Записываем карту, которая лежит под той, до которой досчитали, на бумаге, оставляя её в колоде (если попадаем на джокера, то начинаем снова с первого шага). Это и есть интересующая нас карта. Заметим, что на этом шаге не меняется порядок карт в колоде.
6) Переводим карту из пятого шага в число. Это проделывается так же, как и в четвёртом шаге с одним исключением. Поскольку в алфавите 26 букв, то трефы и червы нумеруем от 1 до 13, а пики и бубны — от 14 до 26. Затем переходим к буквам.
Такие шаги необходимо проделать, чтобы зашифровать один символ. Повторяя одни и те же шесть шагов для каждого незашифрованного символа, шифруем весь открытый текст.
В общем и целом не обязательно придерживаться правил нумерации карт, приведенных здесь, главное, чтобы оба человека придерживались одной схемы.
Перед началом шифрования надо подготовить колоду. Пожалуй, это самая важная часть, потому что самый простой способ взломать «Пасьянс» — выяснить, какой ключ используется. Для того, чтобы ключ был на самом деле надёжным, стоит придерживаться следующих методов:
При всём этом не стоит забывать, что в английском языке только 1,4 бита случайности на символ, так что автор алгоритма советует шифровать для подготовки колоды фразы длиной хотя бы не менее 80 символов.
Несмотря на то, что в исходной статье автора алгоритма указывается, что он обратим, ситуация, когда джокер оказывается внизу колоды и затем перемещается наверх при инициации колоды, делает процесс необратимым. Здесь стоит отметить, что необратимые генераторы псевдослучайных чисел имеют более короткие периоды и имеют склонность к повторению. Действительно, при использовании алгоритма «Пасьянс» возможна генерация числа от 1 до 26, то есть каждое из них должно выходить с вероятностью 1/26, однако в реальности эта вероятность больше — 1/22,5.[2]
Можно придумать и русскую версию данного шифра, например, выбросив из алфавита букву «ё», получим 32 символа плюс 2 карты аналога джокеров, итого — 34. Это позволяет использовать обычную колоду в 36 карт без, скажем, пары шестерок. Огромный минус такого использования — понижение стойкости ключа. Этот вариант, вероятно, оптимальный, потому что в случае оставления 52 карт и проведения вычислений аналогичных вычислениям в оригинальном варианте, но по модулю 32, получаем возможность частотного анализа. Другой вариант — придумать преобразование исходного текста, написанного с использованием всех 33 букв русского алфавита в текст, содержащий только какие-то 26 букв.[3]
Одним из недостатков является то, что шифрование и дешифрование занимает долгое время. Но в сравнении с другими подобными шифрами это время является приемлемым. Например, реальный шифр, который использовался советскими шпионами, описанный Дэвидом Канном, занимает для шифрования достаточно большого сообщения столько же времени, как и «Пасьянс»: приблизительно один вечер.
Помимо этого стоит придерживаться следующих правил: