Криптономикон, часть 2 - Страница 183

183

ШИФРОВАНИЕ С ПОМОЩЬЮ «ПАСЬЯНСА»

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

Для примера зашифруем первое сообщение из романа Стивенсона, «DO NOT USE PC»:

1. Разбейте сообщение открытого текста на группы по пять букв. (Ничего такого магического в цифре 5 нет, это просто традиция.) Последнюю группу дополните буквами «X». Тогда если сообщение «DO NOT USE PC», то открытый текст:

DONOT USEPC

2. С помощью «Пасьянса» сгенерируйте десять букв шифрующего потока. (Подробности дальше.) Предположим, это:

KDWUP ONOWT

3. Переведите открытый текст из букв в числа: А = 1, В = 2, и так далее:

4 15 14 15 20 21 19 5 16 3

4. Точно так же переведите в числа ключевой поток:

11 4 23 21 16 15 14 15 23 20

5. Сложите числа открытого текста с числами ключевого потока по модулю 26. (То есть если сумма превышает 26, вычтите из результата 26.) Например, 1 + 1 = 2, 26 + 1 = 27, а 27 — 26 = 1, так что 26 + 1 = 1.

15 19 11 10 10 10 7 20 13 23

6. Переведите числа обратно в буквы.

OSKJJ JGTMW

Когда натренируетесь, сможете складывать буквы в уме, не переводя их в числа. Тут надо просто привыкнуть. Легко запомнить A + A = B; труднее, что T + Q = K.

РАСШИФРОВКА С ПОМОЩЬЮ «ПАСЬЯНСА»

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

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. Например, 22 — 1 = 20, 1 — 22 = 5. (Это легко. Если первое число меньше второго, перед вычитанием прибавьте к нему 26. Тогда 1 — 22 = ? станет 27 — 22 = 5.)

4 15 14 15 20 21 19 5 16 3

6. Переведите числа обратно в буквы.

DONOT USEPC

Расшифрование происходит так же, как зашифрование, только вы вычитаете ключевой поток из шифртекста.

ГЕНЕРАЦИЯ БУКВ КЛЮЧЕВОГО ПОТОКА

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

«Пасьянс» генерирует ключевой поток с помощью колоды карт. Колоду в 54 листа (помните про джокеров) можно представить как 54-элементную перестановку. Существует 54!, или 2, 31 х 10 возможных раскладов колоды. Что еще лучше, в колоде 52 листа (без джокеров), а в латинском алфавите — 26 букв. Мимо такого совпадения грех пройти.

Для «Пасьянса» в колоде должен быть полный набор из 52 карт и двух джокеров. Джокеры должны как-то отличаться. (Обычно так оно и есть. В колоде, на которую я смотрю, когда пишу, на джокерах звезды: на одном большая, на другом маленькая.) Пусть один джокер будет А, другой Б. Обычно графический элемент у джокеров одинаковый, отличается только размер. Назовите больший джокер «Б» от слова «больше». Если вам так проще, напишите на джокерах «А» и «Б», но помните, что, если вас поймают, вам придется объяснять это тайной полиции.

Для инициализации колоды возьмите ее в руку, лицом вверх. Потом разложите карты в начальной последовательности, которая представляет собой ключ. (Про ключ я объясню позже, но это не то же, что ключевой поток.) Теперь мы готовы сгенерировать цепочку букв ключевого потока.

Вот «Пасьянс»:

1. Найдите джокер А. Переложите его на одну карту вниз. (То есть поменяйте местами с картой, которая лежит сразу под ним.) Если джокер — нижняя карта в колоде, положите его под верхнюю карту.

2. Найдите джокер Б. Переложите его на две карты вниз. Если джокер — нижняя карта в колоде, положите его под две верхние карты. Если предпоследняя, положите сразу под верхнюю. (В общем, представьте, что колода — это петля… ну, поняли.)

Важно выполнять эти два шага в указанной последовательности. Есть соблазн облениться и перекладывать джокеры в том порядке, в каком они вам попадутся. Это не страшно, если только они не лежат близко.

Так что если колода до шага 1 выглядела так:

3 А Б 8 9

то после шага 2 она будет выглядеть:

3 А 8 Б 9

Если есть сомнения, помните, что джокер А надо перекладывать первым. И будьте внимательны, когда джокеры внизу колоды.

3. Подснимите колоду. То есть поменяйте карты над первым джокером с картами под вторым джокером. Если колода выглядела так:

2 4 6 Б 4 8 7 1 А 3 9

то после подснимания она будет выглядеть:

3 9 Б 4 8 7 1 А 2 4 6

«Первый» и «второй» джокер относятся к джокерам, которые лежат соответственно ближе и дальше от верха колоды. На этом шаге не важно, какой из них А, какой Б.

Помните, что джокеры и карты между ними не перекладываются; местами меняются нижняя и верхняя стопка. Если в одной из стопок карт нет (джокеры лежат рядом, либо один из них сверху или снизу), считайте эту стопку пустой и перемещайте ее, как полную.

4. Подснимите по счету. Взгляните на нижнюю карту. Превратите ее в число от 1 до 53. (Последовательность мастей, как в бридже: трефы, бубны, червы, пики. Если карта ♣, ее значение соответствует достоинству. Если это ♦, то достоинству плюс 13. Если ♥, достоинству плюс 26. Если ♠, достоинству плюс 39. Один из джокеров — 53.) Отсчитайте от верха колоды это число. (Я обычно считаю от 1 до 13 требуемое число раз: это проще, чем последовательно досчитывать до больших чисел.) Выньте карты ниже той, до которой вы досчитали, оставив последнюю внизу. Если колода выглядела так:

183