[<<<][^^^][>>>]


Пасьянс (шифр 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.

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

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

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

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

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

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

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


[<<<][^^^][>>>]