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

Сингх Саймон

Это очень напоминает дешифрование сообщения, зашифрованного шифром Виженера с использованием ключа, состоящего из нескольких слов, что было показано в главе 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-кода, а эти двоичные цифры могут рассматриваться как десятичное число. После этого М зашифровывается, образуя шифртекст С, по формуле:

С= M^e(mod N)

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

(6) Чтобы зашифровать это сообщение, Боб начинает разыскивать открытый ключ Алисы и находит, что N= 187, а е = 7. Это дает ему формулу шифрования, необходимую, чтобы зашифровывать сообщения для Алисы. При М= 88 формула имеет вид:

С = 88⁷ (mod 187)

(7) Вычислить ее на калькуляторе непросто, поскольку дисплей не способен справиться с такими огромными числами. В модулярной арифметике есть, однако, способ вычисления экпоненциальных функций. Мы знаем, что, поскольку 7 = 4 + 2+ 1, то:

88⁷ (mod 187) = [88⁴ (mod 187) х 88² (mod 187) х 88¹] (mod 187)] (mod 187) 88¹ = 88 = 88 (mod 187)

88² = 7744 = 77 (mod 187)

88⁴ = 59969536 = 132 (mod 187)

88⁷ = 88¹ х 88² х 88⁴ = 88 х 77 х 132 = 894432 = 11 (mod 187)

Теперь Боб отправляет Алисе зашифрованный текст: С = 11.

(8) Мы знаем, что экпоненциальные функции в модулярной арифметике являются односторонними функциями, поэтому двигаться в обратном направлении и восстановить из С = 11 исходное сообщение М исключительно сложно. Так что Ева дешифровать сообщение не сможет.

(9) Алиса, однако, способна расшифровать его, поскольку у нее есть определенная специальная информация: ей известны значения р и q. Она вычисляет особое число d — ключ для расшифровывания, иначе известный как ее секретный ключ. Число d рассчитывается по следующей формуле:

е х d = 1 (mod (р- 1) $х (q — 1))

7 х d (mod 16 $x 10)