Нил Стивенсон Криптономикон. Часть 2
ПРИЛОЖЕНИЕ: ПАСЬЯНС ШИФРОВАЛЬНЫЙ АЛГОРИТМ
жүктеу/скачать 2.2 Mb.
|
- Бұл бет үшін навигация:
- ШИФРОВАНИЕ С ПОМОЩЬЮ «ПАСЬЯНСА»
- DONOT USEPC 2. С помощью «Пасьянса» сгенерируйте десять букв шифрующего потока. (Подробности дальше.) Предположим, это: KDWUP ONOWT
- РАСШИФРОВКА С ПОМОЩЬЮ «ПАСЬЯНСА»
- KDWUP ONOWT 3. Переведите шифртекст из букв в цифры: 15 19 11 10 10 10 7 20 13 23
- 3 А Б 8 9 то после шага 2 она будет выглядеть: 3 А 8 Б 9
- 2 4 6 Б 4 8 7 1 А 3 9 то после подснимания она будет выглядеть: 3 9 Б 4 8 7 1 А 2 4 6
- 7… карты… 4 5… карты… 8 9
- СОБЛЮДЕНИЕ ТАЙНЫ КАК УСЛОВИЕ БЕЗОПАСНОСТИ
ПРИЛОЖЕНИЕ:ПАСЬЯНС ШИФРОВАЛЬНЫЙ АЛГОРИТМБрюс Шнайер,автор «Прикладной криптографии»Президент «Каунтерпейн системс»http://www.counterpane.comВ романе Нила Стивенсона «Криптономикон» персонаж по имени Енох Роот описывает персонажу по имени Рэнди Уотерхауз криптосистему под кодовым названием «Понтифик», а после сообщает, что алгоритм реализуется при помощи колоды карт. Дальше герои обмениваются несколькими сообщениями, зашифрованными этим способом. Систему «Пасьянс» (в романе она выступает под кодовым названием «Понтифик», дабы до поры до времени скрыть, что в ней используется карточная колода) я придумал, чтобы агенты на местах могли выходить на связь, не полагаясь на электронику и не имея при себе компрометирующих инструментов. Агент может оказаться в ситуации, где у него просто не будет доступа к компьютеру, или пострадать, если при нем обнаружат средства секретной связи. А колода карт… что может быть безобиднее? Стойкость «Пасьянса» основана на случайности перетасованной колоды. Манипулируя ею, коммуникант способен создать цепочку «случайных» букв, которые потом комбинируются с сообщением. Разумеется, «Пасьянс» можно воспроизвести на компьютере, но создан он для использования вручную. Хоть «Пасьянс» и низкотехнологичен, надежность в него заложена высокотехнологическая. Я создавал его в расчете на самого богатого военного противника, обладающего самыми большими компьютерами и самыми толковыми криптоаналитиками. Конечно, не исключено, что кто то найдет способ взломать «Пасьянс» (ищите обновления на моей веб странице), но алгоритм несомненно лучше, чем все другие способы шифрования с помощью карандаша и бумаги, которые я видел. Правда, это не быстро. Чтобы зашифровать или расшифровать более или менее длинное сообщение, нужен вечер. В книге «Кан о кодах» Дэвид Кан описывает подлинный метод шифрования с помощью карандаша и бумаги, которым пользовался советский шпион. На шифровку с помощью советского алгоритма и с помощью «Пасьянса» требуется примерно равное время.
«Пасьянс» – поточный шифр с обратной связью по выходу. Иногда это называется генератор гаммы. Основная идея в том, что «Пасьянс» генерирует шифрующий поток из чисел от 1 до 26. Для шифрования сгенерируйте столько же букв ключевого потока, сколько содержит открытый текст. Потом суммируйте их по модулю 26, одну за другой, с буквами открытого текста. Для расшифрования сгенерируйте тот же ключевой поток и вычитайте по модулю 26 из шифртекста, чтобы получить открытый текст. Для примера зашифруем первое сообщение из романа Стивенсона, «DO NOT USE PC»:
DONOT USEPC2. С помощью «Пасьянса» сгенерируйте десять букв шифрующего потока. (Подробности дальше.) Предположим, это: KDWUP ONOWT3. Переведите открытый текст из букв в числа: А = 1, В = 2, и так далее: 4 15 14 15 20 21 19 5 16 34. Точно так же переведите в числа ключевой поток: 11 4 23 21 16 15 14 15 23 205. Сложите числа открытого текста с числами ключевого потока по модулю 26. (То есть если сумма превышает 26, вычтите из результата 26.) Например, 1 + 1 = 2, 26 + 1 = 27, а 27 – 26 = 1, так что 26 + 1 = 1. 15 19 11 10 10 10 7 20 13 236. Переведите числа обратно в буквы. OSKJJ JGTMWКогда натренируетесь, сможете складывать буквы в уме, не переводя их в числа. Тут надо просто привыкнуть. Легко запомнить А + А = В; труднее, что Т + Q = К. РАСШИФРОВКА С ПОМОЩЬЮ «ПАСЬЯНСА»Основная идея состоит в том, что получатель генерирует тот же ключевой поток и потом вычитает буквы ключевого потока из букв шифртекста. 1. Возьмите шифртекст и разбейте его на группы из пяти букв. (Он уже должен быть в таком виде.) OSKJJ JGTMW2. С помощью «Пасьянса» сгенерируйте десять букв ключевого потока. Если получатель использует тот же ключ, что и отправитель, буквы должны получиться те же: KDWUP ONOWT3. Переведите шифртекст из букв в цифры: 15 19 11 10 10 10 7 20 13 234. Переведите ключевой поток аналогичным образом: 11 4 23 21 16 15 14 15 23 205. Вычтите числа ключевого потока из чисел шифртекста по модулю 26. Например, 22 – 1 = 20, 1 – 22 = 5. (Это легко. Если первое число меньше второго, перед вычитанием прибавьте к нему 26. Тогда 1 – 22 =? станет 27 – 22 = 5.) 4 15 14 15 20 21 19 5 16 36. Переведите числа обратно в буквы. DONOT USEPCРасшифрование происходит так же, как зашифрование, только вы вычитаете ключевой поток из шифртекста. ГЕНЕРАЦИЯ БУКВ КЛЮЧЕВОГО ПОТОКАЭто суть «Пасьянса». Приведенное выше описание шифрования и расшифрования работает для любого поточного шифра с обратной связью по выходу. Дальше объясняется, как работает «Пасьянс». «Пасьянс» генерирует ключевой поток с помощью колоды карт. Колоду в 54 листа (помните про джокеров) можно представить как 54 элементную перестановку. Существует 54!, или 2, 31 х 1071 возможных раскладов колоды. Что еще лучше, в колоде 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 требуемое число раз: это проще, чем последовательно досчитывать до больших чисел.) Выньте карты ниже той, до которой вы досчитали, оставив последнюю внизу. Если колода выглядела так: 7… карты… 4 5… карты… 8 9и девятой картой была 4, после подснимания она будет выглядеть так: 5… карты… 8 7… карты… 4 9Последняя карта остается на месте, чтобы сделать шаг обратимым. Это важно для математического анализа его безопасности. 5. Найдите карту результат. Посмотрите на верхнюю карту. Переведите ее в число от 1 до 53, как описано выше. Отсчитайте это число карт. (Считайте верхнюю карту номером первым.) Запишите карту после той, до которой вы досчитали, на листке бумаги. Если это джокер, ничего не записывайте и начните снова с шага 1.) Это первая карта результат. Заметьте, что этот шаг не изменяет состояние колоды. 6. Переведите карту в число. Как и прежде, пользуйтесь последовательностью мастей, принятой в бридже, в порядке возрастания: ¦, ¦, ¦ и ¦. То есть от Т¦ до К¦ – от 1 до 13, от Т¦ до К¦ – от 14 до 26, от T¦ до К¦ – от 27 до 39, и от Т¦ до К¦ – от 40 до 52. Вот и весь «Пасьянс». С его помощью вы можете получить столько чисел ключевого потока, сколько потребуется. Знаю, что в разных странах колоды немного разные. В целом не важно, какую последовательность мастей использовать или как переводить карты в цифры. Важно лишь, чтобы отправитель и получатель сговорились о правилах. Если вы не будете выполнять все операции одинаково, вы не сможете общаться. НАСТРОЙКА КОЛОДЫ«Пасьянс» надежен в той мере, в какой надежен его ключ. То есть простейший способ взломать «Пасьянс» – выяснить, каким ключом пользуются коммуниканты. Если у вас нет хорошего ключа, все остальное бесполезно. Вот несколько советов по поводу обмена ключом. 1. Перетасуйте колоду. Случайный ключ – самый лучший. Один из коммуникантов может случайным образом перетасовать колоду и разложить вторую точно таким же способом. Одна должна быть у получателя, вторая – у отправителя. Большинство людей плохо тасуют карты, поэтому перетасуйте колоду не меньше десяти раз. Лучше взять колоду, которой уже играли, чем только что распечатанную. Обязательно нужно иметь запасную колоду, разложенную в том же порядке, иначе, сделав ошибку, вы уже не сможете прочесть сообщение. И помните, что ключ уязвим: тайная полиция может найти колоду и переписать ее порядок. 2. Используйте бриджевые комбинации. Расклады бриджа, которые печатают в газетах или книгах по карточным играм, соответствую 95 битному ключу. Если коммуниканты договорятся, как, исходя из этого, раскладывать колоды и куда помещать джокеры (может быть, после первых двух карт, упомянутых в разборе), это сработает. Учтите: тайная полиция может найти колонку с бриджем в газете, которой вы решили пользоваться, и списать порядок карт. Можно сговориться на чем нибудь вроде «используй колонку бриджа из газеты в твоем родном городе на день зашифровки сообщения» или похожем. Можно использовать список ключевых слов для поиска на веб сайте «Нью Йорк тайме». Поиск даст вам какую нибудь статью; возьмите бриджевую колонку из номера, в котором она напечатана. Если ключевые слова будут найдены или перехвачены, их сочтут паролем. Придумайте какой нибудь свой вариант: помните, что тайная полиция тоже читает книги Нила Стивенсона. 3. Используйте пароль для расклада колоды. В этом методе для первоначального расклада используется алгоритм «Пасьянса». И отправитель, и получатель знают пароль. (Например, «SECRET KEY».) Начните с колоды, разложенной по порядку, самая младшая сверху, последовательность мастей, как в бридже. Проделайте операцию «Пасьянс», но вместо шага 5 выполните еще одно подснимание по счету, основываясь на первой букве пароля (в данном примере 19). (Не забудьте положить верхние карты сразу над нижней картой колоды, как и раньше.) Выполните это по разу на каждую букву. Еще две буквы определят положение джокеров. Помните, впрочем, что уровень случайности на букву в стандартном английском примерно 1, 4 бита. Для безопасности нужен пароль по меньшей мере из 80 букв; я рекомендую не меньше 120. (Уж простите, но более короткий ключ не дает надежного уровня безопасности.)
ПРИМЕРЫВот несколько примеров, чтобы потренироваться с «Пасьянсом»: Пример 1: Начните с неразложенной колоды: Т¦ – К¦, Т¦ – K¦, Т¦ – К¦, Т¦ – К¦, джокер А, джокер Б (можете считать это последовательностью 1–52, А. Б). Тогда первые десять результатов:
4 49 10 (53) 24 8 51 44 6 3353, естественно, пропускается. Я оставил это число только для ясности. Если открытый текст: ААААА АААААто шифртекст: EXKYI ZSGEHПример 2: Используя метод настройки 3 ключ «FOO», получаем первые 15 результатов: 8 19 7 25 20 (53) 9 8 22 32 43 5 26 17 (53) 38 48Если открытый текст состоит из одних «А», то шифртекст будет: ITHZU JIWGR FARMWПример 3: Используя метод настройки 3 и ключ «CRYPTONOMICON», сообщение «SOLITAIRE» зашифровывается как: KIRAK SFJANРазумеется, надо использовать более длинный ключ. Эти примеры приведены только для тренировки. На моем веб сайте есть еще примеры, и вы можете создать свои, используя программу на языке PERL, приведенную в этой книге. СОБЛЮДЕНИЕ ТАЙНЫ КАК УСЛОВИЕ БЕЗОПАСНОСТИ«Пасьянс» рассчитан на то, что враг не сможет взломать его, даже зная алгоритм. Я исходил из допущения, что «Криптономикон» станет бестселлером и купить его можно будет повсюду. Полагаю, АНБ и все остальные изучат алгоритм. Я исхожу из того, что тайным будет только ключ. Вот почему так важно сохранять ключ в тайне. Если у вас в безопасном месте хранится колода карт, нельзя исключать, что враг заподозрит вас в использовании «Пасьянса». Если у вас в тайнике лежит бриджевая колонка из газеты, это несомненно вызовет интерес. Если известно, что некая группа использует этот алгоритм, тайная полиция постарается следить за бриджевыми колонками. «Пасьянс» надежен, даже если враг знает, что вы им пользуетесь, и простая колода карт – все же не такая улика, как шифровальная программа в вашем ноутбуке, однако этот алгоритм не заменяет житейской смекалки.
СОВЕТЫ ПО ИСПОЛЬЗОВАНИЮПервое правило любого поточного шифра с обратной связью по выходу: нельзя использовать один ключ для зашифровки двух разных сообщений. Повторяйте за мной: НИКОГДА НЕ ИСПОЛЬЗУЙ ОДИН КЛЮЧ ДЛЯ ЗАШИФРОВКИ ДВУХ РАЗНЫХ СООБЩЕНИЙ. В противном случае вы разрушаете всю безопасность системы. Вот почему: если у вас есть два потока шифртекста А + К и В + К и вы вычтете один из другого, то получите (А + К) – (В + К)= А + К – В – К = А – В. Это комбинация двух открытых текстов, которую очень легко взломать. Поверьте на слово: вы, может быть, и не восстановите А и В из А – В, но профессиональный криптоаналитик с этим справится. Так что это жизненно важно: никогда не пользоваться одним ключом для зашифровки двух разных сообщений. Пишите короткие сообщения. Алгоритм рассчитан на сообщения небольшой длины – примерно до двух тысяч знаков. Если вы хотите зашифровать роман в сто тысяч слов, воспользуйтесь компьютерным алгоритмом. Используйте в своих сообщениях стенографию, аббревиатуры, сленг. Не треплитесь попусту. Для большей безопасности постарайтесь делать все в уме. Если тайная полиция ломает вашу дверь, просто спокойно перетасуйте колоду. (Не бросайте ее в воздух, вы удивитесь, насколько при этом сохраняется порядок карт.) Не забудьте перетасовать контрольную колоду, если она у вас есть. АНАЛИЗ БЕЗОПАСНОСТИМне много что есть по этому поводу сказать, но вопрос слишком сложный для краткого изложения в книге. См. http://www.counterpane.com, или напишите Counterpane Systems, 1711 North Ave #16, Oak Park, IL 60302. ДАЛЬНЕЙШЕЕ ЧТЕНИЕРекомендую для начала мою книгу «Applied Cryptography» (John Wilcy & Sons, 1996).21 Потом прочтите «The Codebreackers» Дэвида Кана.22 Дальше есть книги по компьютерной и ручной криптографии Можете подписаться на мою бесплатную рассылку на http:/www.counterpane.com/cryptogram.html, или отправив пустое сообщение по адресу, crypto gram subscribe@chaparraltree.com. Это очень увлекательно, успехов! 1 Так в японской армии называют отступление. 2 Храм Ясукуни – синтоистское святилище в Токио, где поклоняются душам погибших воинов; до разгрома Японии находился в ведении ведомства армии и флота. 3 У финнов, разумеется, есть своя, абсолютно самобытная разновидность автоматического оружия. 4 В чем дело? (нем.) 5 Любимый! (нем.) 6 Сектор (нем.). 7 Главная группа (нем.). 8 Управление военной контрразведки (нем.). 9 Подразделений (нем.). 11 Учреждений и служб (нем.). 12 Служба безопасности (нем.). 13 Фраза, сказанная протестантским проповедником Джоном Брэдфордом (1510–1555) при виде преступников, которых вели на казнь, и тут же ставшая хрестоматийной. 14 Проклятые (нем.). 15 см. рис. 16 Эта фраза – пародия на Дугласа Макартура Шафто. 17 …говорю по испански …чуть чуть. (исп. ) 18 Дозволенный к употреблению шариатом и изготовленный в соответствии с требованиями мусульманской религии. 19 Джейкоб Марли – умерший компаньон Скруджа в «Рождественской песне» Диккенса, является ему в цепях из своих пороков и прегрешений. 20 Пачинко – японская игра, наподобие детского бильярда. 21 Брюс Шнайер, «Прикладная криптография, М.. Издательство ТРИУМФ, 2003. 22 Дэвид Кан, «Взломщики кодов», М., Центрполиграф, 2000. жүктеу/скачать 2.2 Mb. Достарыңызбен бөлісу:
|