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

⇐ ПредыдущаяСтр 4 из 5Следующая ⇒

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

С= 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)

7 x d = 1 (mod 160)

d = 23

(Вычислить значение d не просто, но с помощью метода, известного как алгоритм Евклида, Алиса сможет быстро и без труда найти d.)

(10) Чтобы расшифровать сообщение, Алиса просто воспользуется следующей формулой:

М= С^d(mod 187)

М= 11²³ (mod 187)

M = [11¹(mod 187) х 11²(mod 187) х 11⁴(m od 187) х 11¹⁶(mod 187)] (mod 187)

M = 11 х 121 х 55 х 154 (mod 187)

М = 88 = Х в виде ASCII-кода

Ривест, Шамир и АДлеман создали специальную одностороннюю функцию — функцию, которая может быть обращена только тем человеком, который имеет доступ х сугубо конфиденциальной информации, то есть к значениям чисел р и q. Каждая функция может быть индивидуализирована путем выбора р и q, которые перемножаются для получения N. Эта функция позволяет всем зашифровывать сообщения для конкретного лица, используя для этого полученное им число N, но только тот, кому предназначено это сообщение, сможет расшифровать его, поскольку только он знает р и q, следовательно, только он знает ключ для расшифровывания d.

⇐ Предыдущая 1 2 345 Следующая ⇒