Термодинамические ограничения

Одним из следствий закона второго термодинамики является то, что для представления информации нео б-ходимо некоторое количество энергии. Запись одиночного бита, изменяющая состояние системы, требует кол и-чества энергии не меньше чем кТ; где Т - абсолютная температура системы и к- постоянная Больцмана. (Не волнуйтесь, урок физики уже почти закончен.)

Приняв, что к= 1.38*10-¹⁶ эрг/К, и что температура окружающей вселенной 3.2К, идеальный компьютер, ра­ботая при 3.2К, потреблял бы 4.4* 10"¹⁶ эрга всякий раз, когда он устанавливает или сбрасывает бит. Работа компьютера при температуре более низкой, чем температура космического пространства, потребовала бы д о-полнительных расходов энергии для отвода тепла.

Далее, энергия, излучаемая нашим Солнцем за год, составляет около 1.21*10⁴¹ эргов. Это достаточно для выполнения 2*10⁵⁶ перемен бита в нашем идеальном компьютере, а этого, в свою очередь, хватит для того, чт о-бы 187-битовый счетчик пробежал все свои значения. Если мы построим вокруг Солнца сферу Дайсона и пер е-хватим без всяких потерь всю его энергию за 32 года, мы сможем получить компьютер для вычисления 2 ^ш чисел. Конечно, энергии для проведения каких-нибудь полезных вычислений с этим счетчиком уже не

останется.

Но это только одна жалкая звезда. При взрыве типичной сверхновой выделяется около 10⁵¹ эргов. (В сто раз больше энергии выделяется в виде нейтрино, но пусть они пока летают .) Если всю эту энергию удастся бросить на одну вычислительную оргию, то все свои значения сможет принять 219-битовый счетчик.

Эти числа не имеют ничего общего с самой аппаратурой, они просто показывают максимальные значения, обусловленные термодинамикой. Кроме того, эти числа наглядно демонстрируют, что вскрытие грубой силой 256-битового ключа будет невозможно, пока компьютеры построены из обычной материи и располагаются в обычном пространстве.

7.2 Длина открытого ключа

Однонаправленные функции обсуждались в разделе 2.3. Однонаправленной функцией является умножение двух больших простых чисел, получить произведение, перемножив числа, нетрудно, но нелегко разложить пр о-изведение на множители и получить два больших простых числа (см. раздел 11.3). Криптография с открытыми ключами использует эту идею для создания однонаправленной функции с люком . На самом деле, это ложь, не доказано, что разложение на множители является тяжелой проблемой (см. раздел 11.4). Насколько сегодня из­вестно, это похоже на правду. И даже если это так, никто не может доказать, что трудные проблемы действи­тельно трудны. Все считают, что разложение на множители является трудной задачей, но это никогда не было доказано математически.

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

В любом случае, доминирующие сегодня алгоритмы шифрования с открытым ключом основаны на трудн о-сти разложения на множители больших чисел, которые являются произведением двух больших простых чисел. (Другие алгоритмы основаны на так называемой Дискретной проблемой логарифма, но пока предположим, что к ней применимы те же рассуждения.) Эти алгоритмы также восприимчивы к вскрытию грубой силой, но по разному. Взлом этих алгоритмов состоит не из перебора всех возможных ключей, а из попыток разложения больших чисел на множители (или взятия дискретных логарифмов в очень большом конечной области - точно такая же проблема). Если число слишком мало, вы никак не защищены. Если число достаточно велико, то вы надежно защищены против всей вычислительной мощи мира, если она будет биться над этой задачей с насто я-щего времени до тех пор, пока Солнце не станет сверхновой - таково сегодняшнее понимание математики этой проблемы. В разделе 11.3 разложение на множители рассматривается математически подробно, а здесь я огр а-ничусь оценкой времени разложения на множители чисел различной длины.

Разлагать большие числа на множители нелегко, но, к несчастью для проектировщиков алгоритмов, этот процесс становится все легче. Что еще хуже, он становится легче ч большей скоростью, чем предсказывалось математиками. В 1976 году Ричард Гай (Richard Guy) писал: "Я был бы немало удивлен, если бы кто-нибудь научился разлагать на множители произвольные числа порядка 10 ⁸⁰ в течение данного столетия" [680]. В 1977 году Рон Ривест (Ron Rivest) заявил, что разложение на множители 125-разрядного числа потребует 40 квад­риллионов лет [599]. В 1994 году было разложено на множители 129-разрядное число [66]. Если из этого и можно сделать какие-то выводы, то только то, что предсказывать глупо .

В 4-й приведены результаты разложения на множители за последнюю дюжину лет . Самым быстрым алго­ритмом разложения на множители является квадратичное решето (см. раздел 11.3).

Эти числа сильно пугают. Сегодня 512-битовые числа уже используются в операционных системах. Разл о-жение их на множители, и полная компрометация, таким образом, системы защиты, вполне реально. Червь в Internet мог бы сделать это в течение уикенда.

Табл. 7-3. Разложение на множителя с помощью "квадратичного решета"

Вычислительная мощь обычно измеряется в mips-годах: годовая работа компьютера, выполняющего милли­он операций в секунду (one-million-instraction-per-second, mips), или около 3*10¹³ операций. Принято, что ма­шина с производительностью 1 mips-год эквивалентна VAX 11/780 компании DEC. To есть, mips-год - это год работы компьютера VAX 11/780 или эквивалентного. (100 МГц Pentium - это машина в 50 mips, a Intel Paragon из 1800 узлов - примерно 50000 mips.)

В 1983 году разложение на множители 71-разрядного числа требовало 0.1 mips-года, в 1994 году разложение на множители 129-разрядного числа потребовало 5000 mips-лет. Такой взлет вычислительной мощности обу­словлен, в основном, введением распределенных вычислений, использующих время простоя сети рабочих ста н-ций. Этот подход был предложен Бобом Силверманом (Bob Silverman) и полностью разработан Аржаном Лен-строй (Arjen Lenstra) и Марком Манассом (Mark Manasse). В 1983 году разложение на множители использовало 9.5 часов процессорного времени на единственном компьютере Cray X-MP, в 1994 году разложение на множи­тели заняло 5000 mips-лет и использовало время простоя 1600 компьютеров во всем мире в течение приблизи­тельно восьми месяцев. Современные методы разложения на множители позволяют использовать подобные распределенные вычисления.

Картина даже продолжает ухудшаться. Новый алгоритм разложения на множители - решето общего поля ч и-сел - заменил квадратичное решето. В 1989 году математики сказали бы вам, что решето общего поля чисел никогда не будет иметь практического значения. В 1992 году они сообщили бы, что оно реализуемо, но дает выигрыш по сравнению с квадратичным решетом только для чисел со 130-150 десятичными разрядами и бол ь-ших. Сегодня известно, что этот новый алгоритм быстрее, чем квадратичное решето, для чисел значительно меньших, чем 116-разрядные [472, 635]. Решето общего поля чисел может разложить на множители 512-битовое число в 10 раз быстрее, чем квадратичное решето . На 1800-узловом компьютере Intel Paragon выполне­ние этого алгоритма заняло бы меньше года. В 3rd показано количество mips-лет, которое требуется для разло­жения чисел различных размеров при использовании современных реализаций решета общего поля чисел [1190].