---

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

Алгоритм Solitaire (пасьянс) изобретён Брюсом Шнайером специально по запросу Нила Стивенсона для его книги "Криптономикон". Его вопросом было изобретение возможности обмена зашифрованными сообщениями в тяжелейших условиях, когда невозможно пользоваться какими-либо подручными средствами в виде электроники или других компрометирующих устройств, не вызывая подозрений.

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

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

Использоваться должна полная колода карт: 4 масти по 13 карт каждой и два различимых джокера. Интересный и очень полезный факт 2 * 13 = 26: столько же, сколько и букв в латинском алфавите.

Всего колода (ключ) может иметь ((4 * 13) + 2)! = 54! ~ 2.31 * 10^71 значений.

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

1. Уберите все знаки пунктуации. Их можно заменить буквенными эквивалентами. Все буквы переведите в один регистр.
2. Переведите буквы в их численное представление: A=1, B=2, ..., Z=26
3. Сгенерируйте последовательность псевдослучайных чисел по алгоритму Solitaire. Длина должна быть равна длине открытого текста.
4. Поочерёдно сложите каждое числовое представление буквы открытого текста с этой случайной последовательностью по модулю 26.
5. Преобразуйте получившиеся числа в буквенное представление: получите шифротекст.
6. Для дешифрования необходимо проделать всё то же самое, только вместо сложения, использовать вычитание случайной последовательности из шифротекста.

Пример

Мы хотим зашифровать сообщение DO NOT USE PC. В криптографии любят разбивать сообщения на группы по пять символов:

DONOT USEPC

Преобразуем в численный вид:

4 15 14 15 20    21 19 5 16 3

Используйте Solitaire для генерирования ключевой последовательности (случайной последовательности, зависящей от ключа). Предположим что мы получили:

KDWUP ONOWT

Преобразуем в численный вид:

11 4 23 21 16    15 14 15 23 20

Сложим их по модулю 26 (если сумма больше 26, то тогда необходимо вычесть 26 из результата (1 + 1 = 2, 26 + 1= 27 - 26 = 1):

15 19 11 10 10    10 7 20 13 23

Преобразуем этот шифротекст в буквенное представление:

OSKJJ JGTM

Это сообщение можно передать собеседнику. Собеседник использует Solitaire для получения ключевой последовательности. Если все правила её генерирования совпадают, то его последовательность тоже получится KDWUP ONOWT.

Ему необходимо преобразовать шифротекст в численное представление и вычесть из него числа ключевой последовательности по модулю 26 (то есть, если первое число больше или равно второму, то добавьте к первому 26 (22 - 21=21, 1 - 22=5)):

4 15 14 15 20    21 19 5 16

Преобразуйте получившуюся последовательность в буквенное представление:

DONOT USEPC

Генерирование случайных чисел

Каждая карта имеет своё собственно число. От 1 (туз) до 13 (король), от 14 до 26, итд. Сначала одна масть, затем другая, итд. Необходимо условиться какой порядок мастей будет идти. Разницы никакой – главное чтобы обе стороны договорились об этом. Шнайер предлагает правила бриджа: трефы (♣), бубны (♦), черви (♥), пики (♠).

Также джокеры необходимо отличать друг от друга. Условимся и назовём одного джокера как A, а другого как B.

Для удобства колоду лучше иметь не перемешанную. Сначала туз треф, потом двойка треф,..., король треф, туз бубен,..., король пик, джокер A, джокер B.

Чтобы получить одну букву "вывода" из Solitaire проделайте следующее:

1. Найдите джокера A. Переместите на одну карту вниз. То есть, поменяйте местами с картой под ним. Если он внизу колоды, то поместите его наверх.
2. Найдите джокера B. Переместите на две карты вниз. Если он внизу колоды, то значит его необходимо поместить под первую карту сверху. Колода это зацикленная структура. Если колода до первого пункта была такой:

   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. Сделайте тройной отрез (triple cut). То есть, обменяйте карты над верхним джокером и под нижним.

   Если колода была такая:

   2 4 6 B 5 8 7 1 A 3 9
   

   то станет:

   3 9 B 5 8 7 1 A 2 4 6
   

   Помните, что джокеры и карты между ними места не меняют.

   Если колода была такой:

   B 5 8 7 1 A 3 9
   

   то станет:

   3 9 B 5 8 7 1 A
   

   Если была такой:

   B 5 8 7 1 A
   

   то на этом шаге не изменится.

4. Сделайте отрез с отсчётом (count cut). Посмотрите на нижнюю карту. Преобразуйте в число от 1 до 53. (если ♣, то число показано на карте; если ♦, то значение +13; если джокер, то значение = 53). Отсчитайте от верхней карты такое количество карт и поместите их над последней картой.

   Если колода была такая:

   7...cards...4 5...cards...8 9
   

   а 4 является девятой картой, то колода станет такой:

   5...cards...8 7...cards...4 9
   

   Если нижней картой является джокер, то колода останется неизменной.

5. Найдите выходную карту (output card). Посмотрите на верхнюю карту. Преобразуйте в число то 1 до 53. Отсчитайте столько же карт (верхняя карта является первой). Запишите/запомните карту до которой дошёл счёт.
6. Преобразуйте карту (числовое значение) в буквенное представление. Так как в алфавите 26 букв, то трефы (♣) от 1-13, бубны (♦) от 14-26, черви (♥) от 1-13, пики (♠) от 14-26.

Для получение следующего символа ключевой последовательности просто повторите все шаги.

Начальное состояние колоды

Начальное состояние колоды перед генерирование ключевой последовательности является, по сути, ключом шифрования. Стойкость алгоритма основана полностью на стойкости (качестве) ключа. Алгоритм может быть известен любой полиции, но вся сила заключена в ключе. Как это применимо и к любому другому серьёзному "боевому" алгоритму. Ключевание колоды – самая ответственная часть.

• В идеале лучше иметь две идентичные как можно более случайно перемешанные колоды. Одна идёт отправителю, а другая получателю сообщений. Но полиция может найти колоды – это опасно.
• Использовать сторонний независимый источник и правила перемешивания колоды относительно его. Например газеты или журналы.
• Использовать парольную фразу для ключевания колоды. Просто используйте алгоритм Solitaire, только вместо пятого шага (output card) произведите ещё один отрез с отсчётом (count cut) – то есть ещё один четвёртый шаг повторно, только в качестве числа отсчёта используйте символ из парольной фразы. И так повторяйте для каждого символа парольной фразы.

Пример использования

Первый выходной символ:

• 1 2 3 4 ... 52 A B
  

• 1 2 3 4 ... 52 B A
  

• 1 B 2 3 4 ... 52 A
  

• B 2 3 4 ... 52 A 1
  

• 2 3 4 ... 52 A B 1
  

• пятый шаг производит выходной символ, так как наверху 2, то отсчитайте до 4 – это и есть выход.

Второй выходной символ:

• 2 3 4 ... 49 50 51 52 B A 1
  

• 2 3 4 ... 49 50 51 52 A 1 B
  

• A 1 B 2 3 4 ... 49 50 51 52
  

• 51 A 1 B 2 3 4 ... 49 50 52
  

• Пятый шаг производит выход. Наверху карта 51, отсчёт 51-ой карты даёт карту 49.

Заметки по применению

• Никогда не используйте один и тот же ключ для шифрования двух различных сообщений.
• Шифруйте достаточно короткие сообщения, не более нескольких тысяч символов.
• Как и все потоковые шифры, одна ошибка приводит к сбою всего алгоритма и дешифровать сообщение уже не получится. Желательно всегда дважды зашифровать сообщение, чтобы убедиться в отсутствии ошибок.
• Весь процесс Solitaire может быть обращён. Если вы оставите хотя бы что-то (записи, какую-то часть колоды), то полиция может обратить весь процесс шифрования.
• Пытайтесь всё делать в своей голове, иметь как можно меньше записей. Если полиция врывается, то перемешайте колоду. Если на бумаге вы имеет записи, то лучше всего сжечь их. Папиросная бумага может быть сожжена без пепла.

Next: Обратная связь, Previous: Полезные ссылки, Up: Russian cypherpunks community