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

Криптографический алгоритм «Пасьянс» («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^71. Ещё лучше, что, не считая джокеров, в колоде 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. Затем переходим к буквам.

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

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

Инициализация колоды

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

• Используйте одинаково перетасованные колоды. Случайный ключ является лучшим. То есть тому, кто шифрует, надо перетасовать колоду, а затем сложить карты в другой колоде таким же образом. Большинство людей не очень хорошие «тасовщики», так что надёжней будет перетасовать колоду несколько раз. Затем одна колода остаётся у шифрующего, а вторая отдаётся адресату. И обе стороны должны иметь дополнительный набор карт в том же порядке, иначе, если будет совершена ошибка, то сообщение никогда не будет расшифровано. При этом необходимо помнить, что пока такая колода существует, ключ находится в опасности.
• Можно использовать какой-либо пароль, чтобы упорядочить колоду. В этом случае сам «Пасьянс» будет использоваться для создания начального состояния колоды. Вначале отправитель и получатель выбирают фразу для инициализации колоды, затем начиная с колоды, в которой все карты расположены по возрастанию. Выполняйте те же операции, что и при шифровании, но вместо пятого шага, сделайте ещё один срез (то есть повторите четвёртый шаг), но вместо значения последней карты в колоде используйте первую букву в выбранной фразе, а точнее соответствующее ей число. Повторив все шаги для каждой буквы, получаем инициализированную колоду. Помимо этого, можно располагать джокеров в колоде согласно последним двум символам фразы. То есть, например, если предпоследняя буква во фразе «F» (6), то помещаем первого джокера после шестой карты. Если последняя «S» (19), то второго джокера помещаем после 19-й карты.

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

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

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

Локализация

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

Недостатки

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

Примечания

Помимо этого стоит придерживаться следующих правил:

• Для любого криптографического алгоритма с обратной связью по выходу главное правило — никогда не использовать один и тот же ключ для шифрования двух различных сообщений. Допустим, вы имеете два зашифрованных текста A + K и B + K, тогда «вычитая» один из другого имеем: (A + K) − (B + K) = A − B. То есть получаем текст, составленный из двух сообщений без использования ключа, такой текст взломать гораздо проще.
• Шифруйте короткие сообщения. Этот алгоритм создан именно для сообщений такого типа: несколько тысяч символов — это максимум. Используйте сокращения, аббревиатуры и сленг для уменьшения объёма. Если вам надо зашифровать повесть состоящую из 100 000 слов, то лучше использовать компьютерный алгоритм.
• Как и все алгоритмы с обратной связью по выходу, «Пасьянс» имеет один весомый недостаток: невозможность восстановления после ошибки. Если вы шифруете сообщение и делаете ошибку на одном из шагов, то всё, что будет зашифровано далее — неверно. Так что при шифровании сообщения желательно зашифровать повторно, для того, чтобы убедиться, что всё верно.
• Для максимальной секретности необходимо стараться делать как можно больше в уме, не оставляя никаких записей. Если же что-то было записано, то наилучший вариант — сжечь это.
• «Пасьянс» можно использовать и на компьютере. Обычно только одна сторона находится в положении, когда нет возможности использовать его.

Литература

1. Schneier, Bruce Solitaire  (неопр.) (May 1999). Дата обращения: 7 декабря 2012. Архивировано 17 января 2013 года.
2. Crowley, Paul Problems with Bruce Schneier's "Solitaire"  (неопр.). Дата обращения: 7 декабря 2012. Архивировано 17 января 2013 года.
3. Крипто-шифр «Пасьянс»  (неопр.). Дата обращения: 7 декабря 2012. Архивировано 17 января 2013 года.