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

Операция разложения на множители отнимает очень много времени, но сколько же на самом деле понадобится Еве времени, чтобы найти сомножители числа 408 508 091? Существуют различные способы разложения на множители числа N_B. Хотя одни из них быстрее, а другие — медленнее, но, по сути, во всех них проверяется, делится ли N_B без остатка на каждое из простых чисел. Например, 3 — это простое число, но оно не является множителем числа 408 508 091, так как 408 508 091 нацело на 3 не делится. Поэтому Ева берет следующее простое число — 5. 5 точно так же не является множителем, поэтому Ева переходит к следующему простому числу и так далее. В конце концов, Ева добирается до числа 18 313, 2000-го простого числа, которое является множителем числа 408 508 091. Найдя один из сомножителей, легко найти и другой — 22 307. Если у Евы есть калькулятор и она способна проверять четыре простых числа в минуту, то ей, чтобы отыскать р_B и q_B, потребуется 500 минут, или свыше 8 часов. Другими словами, Ева сможет раскрыть секретный ключ Боба и, тем самым, расшифровать перехваченное сообщение менее, чем за день.

Это не слишком-то высокий уровень стойкости, но Боб мог бы выбрать гораздо большие простые числа и повысить стойкость своего секретного ключа. Например, он мог бы выбрать простые числа, состоящие из 10⁶⁵ цифр (это означает 1 с 65 нулями, или сто тысяч миллионов миллионов миллионов миллионов миллионов миллионов миллионов миллионов миллионов миллионов). В результате величина N будет приблизительно составлять 10⁶⁵ х 10⁶⁵, то есть 10¹³⁰ цифр. Компьютер смог бы перемножить оба простых числа и вычислить N всего лишь за секунду, но если Ева захочет выполнить обратную операцию и определить р и q, на это потребуется не в пример больше времени. Насколько больше, зависит от быстродействия компьютера Евы. По оценке эксперта по безопасности Симеона Гарфинкеля, 100-MHz компьютеру Intel Pentium с 8 MB RAM, чтобы разложить на множители число, состоящее из 10¹³⁰ цифр потребуется около 50 лет. Криптографы проявляют тенденцию к параноидальности и учитывают при определении стойкости своих шифров наихудшие ситуации, как, например, глобальная секретность. Поэтому Гарфинкель рассматривал, что произойдет, если объединить вместе сотню миллионов персональных компьютеров (количество компьютеров, проданных в 1995 году). В результате он получил, что число, состоящее из 10¹³⁰ цифр, может быть разложено на множители примерно за 15 секунд. Так что в настоящее время общепринято, что для обеспечения подлинной стойкости необходимо использовать еще большие простые числа. Для ответственных банковских операций N стремятся сделать как минимум 10³⁰⁸, которое в десять миллионов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов миллиардов раз больше, чем 10¹³⁰. Объединенными усилиями сотне миллионов персональных компьютеров потребуется затратить более тысячи лет, чтобы раскрыть такой шифр. При достаточно больших значениях р и q, RSA является неуязвимой.

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

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

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

Об RSA впервые было объявлено в августе 1977 года, когда Мартин Гарднер написал статью, озаглавленную «Новый вид шифра, для взлома которого потребуются миллионы лет», для колонки «Математические игры» в «Сайентифик Америкен». Объяснив, как происходит шифрование с открытым ключом, Гарднер задал задачу своим читателям. Он напечатал зашифрованное сообщение и дал открытый ключ, который использовал для его зашифровывания:

N = 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541.

Задача заключалась в том, чтобы разложить на сомножители р и q, а затем использовать эти числа, чтобы расшифровать сообщение. Призом были 100 долларов. У Гарднера не было места, чтобы объяснить все подробности алгоритма RSA; вместо этого он попросил читателей написать в лабораторию вычислительной техники Массачусетского технологического института, откуда им пришлют технический меморандум, который был как раз к тому времени подготовлен. Ривест, Шамир и Адлеман были поражены, получив три тысячи запросов. Однако ответили они не сразу, так как были обеспокоены, что открытое распространение их идеи могло бы поставить под угрозу получение патента. Когда же вопросы по выдаче патента были в конце концов разрешены, троица устроила праздничную вечеринку, на которой преподаватели и студенты уплетали пиццу, запивая ее пивом, и одновременно раскладывали по конвертам технические меморандумы для читателей «Сайентифик Америкен».

Что касается задачи Гарднера, то для ее решения потребовалось 17 лет. 26 апреля 1994 года команда из шестисот добровольцев сообщила о том, какие сомножители были у N:

q = 3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577

р = 32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533.

Используя эти значения в качестве секретного ключа, они смогли расшифровать сообщение. Сообщение состояло из ряда чисел, но, преобразованное в буквы, гласило: «Волшебные слова: брезгливая скопа». Задача разложения на множители была распределена между добровольцами, проживающими в Австралии, Англии, США и Венесуэле. Они использовали свободное время своих рабочих станций, больших ЭВМ и суперкомпьютеров; при этом каждый занимался только частью задачи. По сути, чтобы решить задачу Гарднера, компьютеры, разбросанные по всему миру, объединялись в сеть и работали одновременно. Даже принимая во внимание огромную работу, которая велась параллельно, некоторые читатели могут удивиться, что RSA была взломана за такое короткое время, но следует заметить, что в задаче Гарднера использовалось относительно малое значение N; оно составляло порядка 10¹²⁹. Сегодня, чтобы обеспечить безопасность жизненно важной информации, пользователи RSA могут брать гораздо большие значения. Ныне вполне обычное дело зашифровывать сообщение с использованием такого большого N, что всем компьютерам в мире, чтобы взломать шифр, потребуется время, превышающее возраст Вселенной.

Альтернативная история шифрования с открытым ключом

За последние двадцать лет Диффи, Хеллман и Меркль приобрели мировую известность как криптографы, которые придумали способ шифрования с открытым ключом, а Ривесту, Шамиру и Адлеману приписывается слава создания RSA — самой превосходной реализации криптографии с открытым ключом. Однако появившаяся недавно информация означает, что учебники истории необходимо переписать.