Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Шнайер - Прикладная криптография.doc
Скачиваний:
13
Добавлен:
01.05.2025
Размер:
10 Мб
Скачать
☆

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

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

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

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

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

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

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