Саймон Сингх - Книга шифров .Тайная история шифров и их расшифровки

• Название: Книга шифров .Тайная история шифров и их расшифровки
• Автор: Саймон Сингх
• Издательство: Астрель
• Жанр: Прочая научная литература
• Год: 2007

Саймон Сингх получил степень кандидата наук по физике в Кембриджском университете. Во время работы продюсером на Би-би-си снял удостоенный награды Британской академии кино и телевидения документальный фильм «Великая теорема Ферма» и написал бестселлер под тем же названием.

Шифры используются с тех пор, как люди научились писать. В «Книге шифров» Саймон Сингх посредством волнующих историй о шпионаже, интригах, интеллектуальном блеске и военной хитрости показывает захватывающую историю криптографии.

<<Изложение Сингха сочетает в себе увлекательность и наиболее содержательный анализ из всех, которые я когда-нибудь видел. Как и всегда, он блещет способностью объяснять>>.

<<Гардиан>>

---

Особенность шифра ADFGVX состоит в том, что здесь осуществляется и замена, и перестановка. Зашифровывание начинается с того, что рисуется сетка 6 x 6, и 36 квадратов заполняются 26 буквами и 10 цифрами в произвольном порядке. Каждая строка и столбец сетки задается одной из шести букв: А, О, Р, в, V или X. Расположение элементов в сетке служит в качестве части ключа, поэтому получателю, чтобы расшифровать сообщение, необходимо знать, как они в ней располагаются.

На первом этапе зашифровывания следует взять каждый символ сообщения, определить его положение в сетке и заменить его буквами, которые обозначают строку и столбец. Так, 8 будет заменено на АА, а р — на AD. Ниже, в качестве примера, показано зашифрованное этим способом короткое сообщение:

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

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

В этом виде шифртекст будет затем передан с помощью кода Морзе; получателю, чтобы восстановить первоначальный текст, потребуется выполнить действия, обратные зашифровыванию. Шифртекст состоит всего лишь из шести букв (т. е. А, D, F, G, V, X), так как этими буквами обозначаются строки и столбцы исходной сетки 6 x 6. Люди часто удивляются, почему были выбраны именно эти буквы, а не, скажем, А, В, С, D, Е и F. Все дело в том, что если буквы А, D, F, G, V и X представить в виде точек и тире кода Морзе, то они будут существенно отличаться одна от другой; тем самым выбор этих букв минимизирует опасность появления ошибок во время передачи.

Приложение G Слабости повторного использования одноразового шифрблокнота

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

Мы, вероятно, будем правы, если предположим, что в первом шифртексте где-то есть слово the, и поэтому криптоанализ начинается с допущения, что все сообщение целиком состоит из последовательности слов the. Далее мы полагаем, что искомый одноразовый шифрблокнот преобразует всю эту последовательность слов the в первый шифртекст. Это станет нашим исходным предположением об одноразовом шифрблокноте. Но как же мы сможем узнать, какие части этого одноразового шифрблокнота правильны?

Мы можем применить наше исходное предположение об одноразовом шифрблокноте ко второму шифртексту и посмотреть, имеет ли какой-нибудь смысл получающийся открытый текст. Если нам улыбнется удача, мы сможем распознать несколько фрагментов слов во втором открытом тексте, что укажет нам, что соответствующие части одноразового шифрблокнота верны. А это, в свою очередь, укажет нам, в каких местах первого сообщения должны стоять the.

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

Это очень напоминает дешифрование сообщения, зашифрованного шифром Виженера с использованием ключа, состоящего из нескольких слов, что было показано в главе 3, где ключом являлось CANADABRAZILEGYPTCUBA.

Приложение H Решение кроссворда, опубликованного в «Дейли Телеграф»
Упражнения для заинтересовавшихся читателей

Некоторые самые значительные дешифрования в истории были сделаны непрофессионалами. Так, Георг Гротефенд, положивший начало дешифрованию клинописи, был школьным учителем. Для тех читателей, кого влечет последовать по его стопам, есть несколько письменностей, которые по-прежнему представляют загадку. Линейное письмо А — минойская письменность — успешно противостоит всем попыткам дешифрования, отчасти из-за недостаточности материала. Этрусская письменность не страдает от этой проблемы — для изучения имеется более 10 000 надписей, — но и она также ставит в тупик ученых с мировым именем. Равно непостижимо и иберийское письмо — еще одна доримская письменность.

Самое любопытное древнее европейское письмо обнаружено на единственном фестосском диске, найденном в южной части Крита в 1908 году. На этой круглой табличке, датируемой примерно 1700 годом до н. э., с каждой стороны сделана надпись, идущая в виде спирали. Знаки на диске выполнены не вручную, а оттиснуты с помощью множества печатей; это пример самого древнего в мире использования «пишущей машинки». Удивительно то, что больше никогда ничего похожего не находили, и потому для дешифрования имеется очень ограниченная информация: всего лишь 242 символа, разделенных на 61 группу. Однако отпечатанный на пишущей машинке документ подразумевает массовое производство, так что есть надежда, что археологи в конце концов отыщут склад подобных дисков и прольют свет на эту неподдающуюся письменность.

За пределами Европы одной из самых значительных задач является дешифрование письменности бронзового века протоиндийской цивилизации, которую можно обнаружить на тысячах печатей, начиная с третьего тысячелетия до н. э. На каждой печати изображено какое-либо животное и имеется короткая надпись, но что они означают — до сих пор ставит в тупик всех специалистов. В одном необычном случае надпись обнаружили на большой деревянной доске, и она была выполнена гигантскими буквами 37 см высотой. Это мог быть самый древний в мире рекламный щит. Что, в свою очередь, означает, что грамотность не являлась привилегией исключительно элиты, и возникает вопрос, о чем же говорится в объявлении? Вероятнее всего, что это была часть рекламной кампании по выборам короля, и если бы можно было установить его личность, то этот рекламный щит проложил бы путь к остальной части письменности.

Приложение J Математика RSA

Ниже в несложном виде дается математическое описание принципа шифрования и дешифрования с помощью RSA.

(1) Алиса выбирает два гигантских простых числа р и q. Простые числа должны быть громадными, но мы, для простоты, предположим, что Алиса выбрала числа р = 17, q = 11. Она должна хранить эти числа в секрете.

(2) Алиса перемножает их и получает число N. В нашем случае N = 187. Теперь она выбирает еще одно число — е; в нашем случае она выбрала е = 7.

(е и (р- 1) х (q — 1) должны быть взаимно простыми[39], но это — техническая сторона дела).

(3) Алиса может теперь опубликовать е и N в чем-то сродни телефонному справочнику. Поскольку эти два числа необходимы для зашифровывания, они должны быть доступны всем, кто захочет зашифровать сообщение для Алисы. Вместе эти числа называются открытым ключом. (Это число е может являться частью открытого ключа не только Алисы, но и любого другого человека. Однако у всех остальных должны быть иные значения N, которые зависят от выбора р и q.)

(4) Перед тем как приступить к зашифровыванию сообщения, оно должно быть вначале преобразовано в число М. Например, слово заменяется на двоичные цифры ASCII-кода, а эти двоичные цифры могут рассматриваться как десятичное число. После этого М зашифровывается, образуя шифртекст С, по формуле:

С= Me(mod N)

(5) Представьте, что Боб хочет послать Алисе простой поцелуй — всего лишь букву X. В ASCII-коде она представляется числом 1011000, которое эквивалентно 88 в десятичном виде. Поэтому М — 88.