множители любые числа того же размера. Разумно предположить, что решето общего поля чисел может быть оптимизировано, чтобы достичь такой же скорости [1190], возможно, что NSA уже знает, как это сделать. В 2-й показано количество mips-лет, требуемое для разложения чисел различной длины при помощи решета спец и-ального поля чисел [1190].

Табл. 7-5.

Разложение на множители с помощью решета специального поля чисел

В 1991 году участники семинара Европейского института безопасности систем ( European Institute for System Security) согласились, что 1024-битовых модулей будет достаточно для длительного хранения секретов до 2002 года [150]. Однако, они предупреждали: "Хотя участники этого семинара являются лучшими специалистами в соответствующих областях, это заявление (по поводу срока безопасности) должно быть воспринято с осторожностью." Это хороший совет.

Умный криптограф сверхконсервативен при выборе длин открытых ключей . Чтобы понять, насколько длинный ключ вам нужен, вам придется оценить нужную безопасность и время жизни ключа, не забывая о текущем состоянии искусства разлагать на множители . Чтобы получить тот же уровень безопасности, который давало 512-битовое число в начале восьмидесятых, сегодня вам понадобится 1024-битовое число. Если же вы хотите, чтобы ваши ключи оставались безопасными в ближайшие 20 лет, 1024-битовое число, по видимому, слишком коротко.

Даже если ваши конкретные секреты не стоят усилий, нужных для разложения вашего модуля, вы можете оказаться в опасности. Представьте себе автоматическую банковскую систему, использующую для безопасности RSA. Мэллори может предстать перед судом и заявить: "Читали ли вы в газете за 1994 год, что RSA-129 был взломан, и что 512-битовые числа могут быть разложены на множители любой организацией, которая может потратить несколько миллионов долларов и подождать несколько месяцев ? Мой банк использует для безопасн ости 512-битовые числа и, между прочим, эти семь изъятий сделаны не мной." Даже если Мэллори лжет, судья, вероятно, может потребовать, чтобы банк это доказал .

Почему не использовать 10000-битовые ключи ? Конечно, можно, но чем длиннее ваши ключи, тем больше стоимость вычислений. Вам нужен ключ, который был бы достаточно длинным для обеспечения безопасности, но достаточно коротким, чтобы его можно было использовать .

Ранее в этом разделе я называл предсказания глупостью . Теперь я сам попытаюсь предсказать кое-что. В 1-й приведены мои рекомендации по выбору длин открытых ключей в зависимости от того, какой срок безопасн ости ключа вам нужен. Для каждого года приведены три длины ключа, одна для частного лица, одна для крупной корпорации и одна для правительства большого государства .

Вот некоторые соображения из [66]:

Мы считаем, что сможем получить доступ к 100 тысячам компьютеров без сверхчеловеческих усилий и неэтичных де й-ствий. То есть, мы не собираемся выпускать в Internet "червя" или разрабатывать вирус, который бы предоставил бы нам в ы-числительные ресурсы. Во многих организациях многие тысячи машин подключены к сети . Доступ к их возможностям потребует искусной дипломатии, но не является невозможным. Приняв среднюю производительность машины равной 5 mips и время работы 1 год, вполне возможно осуществить проект, который требует полмиллиона mips-лет.

Проект разложения на множители 129-разрядного числа без значительных усилий смог задействовать 0.03 процента оценочной полной вычислительной мощности Internet [1190]. Разумно предположить, что хорошо разрекламированный проект получит на год 2 процента всемирной вычислительной мощности .

Предположим, что увлеченный криптоаналитик сможет получить в свое распоряжение 10000 mips-лет, большая корпорация - 107 mips-лет, а правительство большой страны - 109 mips-лет. Предположим также, что вычислительная мощь будет возрастать на порядок каждые пять лет. И , наконец, предположим также, что ус-

пехи в математике разложения на множители позволят нам раскладывать любые числа со скоростью, сравн и-мой с той, которую обеспечивает решето специального поля чисел. (Это пока невозможно, но прорыв может случиться в любой момент.) 1st рекомендует для различных лет использовать с целью обеспечения безопасн ости различные длины ключей.

Табл. 7-6.

Рекомендованные длины открытых ключей в (битах)

Не забывайте учитывать значимость ключа. Открытые ключи часто используются для длительной обеспеч е-ния безопасности важной информации: главный ключ банка для системы электронных наличных, ключ, и с-пользуемый правительством для подтверждения паспортов, ключ цифровой подписи государственного нотари уса. Возможно, не стоит тратить месяцы машинного времени на вскрытие какого-то личного ключа, но если м о-жете с помощью добытого ключа напечатать собственные деньги, то идея становится весьма захватывающей . Длина 1024-битовогой ключа достаточна для подписи чего-нибудь, что будет проверено в течение недели, мес я-ца, даже нескольких лет. Но вы же не хотите, представ перед судом лет 20 спустя с подписанным электронным образом документом, смотреть, как противоположная сторона показывает, как подделать документы, используя эту же подпись .

Предсказывать более далекое будущее еще глупее. Кто может знать, каких успехов к 2020 году достигнет вычислительная техника, сетевые вычисления и математика? Однако, если окинуть взглядом всю картину, можно заметить, что в каждом следующем десятилетии мы получаем возможность разлагать на множители вдвое более длинные числа, чем в предыдущем . Это позволяет построить 0-й.

С другой стороны, техника разложения на множители может достичь предела своих возможностей задолго до 2045. Хотя я думаю, что это маловероятно.

Не все согласятся с моими рекомендациями. NSA установило для своего Стандарта цифровой подписи (Digital Signature Standard, см. раздел 20.1) длину ключей от 512 до 1024 бит - намного меньше, чем я рекомендую для длительной безопасности. У Pretty Good Privacy ("Вполне надежный секрет", см. раздел 24.12) максимальная длина ключа RSA составляет 2047 бит. Аржан Ленстра, лучший в мире раскладыватель на множители, в течение последних 10 лет отказывается делать предсказания [949]. В -1-й приведены рекомендации Рона Ри-веста для длины ключей, которые сделаны в 1990 году и кажутся мне слишком оптимистичными [1323]. Хотя его анализ на бумаге выглядит хорошо, в недавней истории можно найти примеры регулярно происходящих сюрпризов. Чтобы предохранить себя от последствия этих сюрпризов, есть смысл выбирать ключи с запасом .

Табл. 7-7.

Долгосрочный прогноз разложения

Минимальные оценки предполагают бюджет $25000, алгоритм "квадратичное решето " и скорость технич е-ского прогресса 20 процентов в год . Средние оценки предполагают бюджет 25 миллионов долларов, алгоритм "решето общего поля чисел" и скорость технического прогресса 33 процента в год . Максимальные оценки предполагают бюджет 25 миллиардов долларов, алгоритм "решето общего поля чисел", работающий со скоростью

решета специального поля чисел и скорость технического прогресса 45 процентов в год .

Всегда есть вероятность того, что успехи в разложении на множители будут поразительны и для меня, но я попытался учесть этот множитель в своих прогнозах. Но почему мне нужно верить? Я лишь продемонстрировал собственную глупость, занимаясь предсказаниями .

Табл. 7-8.

Оптимистичные рекомендации Ривеста для длины ключей (в битах)

Вычисление с помощью ДНК

Это похоже на волшебство. В 1994 году Леонард Эдлман (Leonard M. Adleman) продемонстрировал метод решения задачи NP-полноты (см. раздел 11.2) в биохимической лаборатории, используя молекулы ДНК для представления возможных решений задачи [17]. Задача, решенная Эдлманом, была частным случаем задачи направленного гамильтонова пути : дана карта городов, соединенных однонаправленными дорогами, нужно на й-ти путь из города A в город Z, который проходит через каждый город на карте только один раз . Каждый город был представлен своей случайной цепочкой ДНК с 20 основаниями. С помощью обычных методов молекулярной биологии Эдлман синтезировал 50 пикомолей (30 миллионов миллионов молекул) цепочки ДНК, представляющей каждый город. Каждая дорога была представлена цепочкой ДНК с 20 основаниями, но эти цепочки выбирались не случайным образом: они умело выбирались так, чтобы "начало" цепочки ДНК, представляющей дорогу от города P к городу K ("Дорога PK") стремилась бы соединиться со цепочкой ДНК, представляющей город P, а конец Дороги PK стремился бы соединиться с городом K.

Эдлман синтезировал 50 пикомолей ДНК, представляющих каждую дорогу, смешал их вместе с ДНК гор одами, представляющей города, и добавил фермент лигазу, которая связывает вместе концы молекул ДНК. Правильно подобранная связь между цепочками ДНК для дорог и цепочками ДНК для городов приводит к тому, что лигаза соединяет цепочки ДНК для дорог вместе правильным образом . То есть, "Выход" дороги PK всегда будет соединен со "входом" какой-либо дороги, начинающейся в городе K, но никогда с "выходом" любой дороги или со "входом" дороги, которая начинается не в городе K. После тщательно ограниченного времени реакции лигаза создала большое количество цепочек ДНК, представляющих возможные, но все равно случайные объединения путей карты.

В этом супе из случайных путей Эдлман может найти малейший след - может быть единственной молекулы - ДНК, которая является ответом задачи . Используя обычные методы молекулярной биологии, он удалил все цепочки ДНК, представлявшие слишком короткие или слишком длинные пути . (Число дорог в нужном пути должно равняться числу городов минус один .) Затем он удалил все цепочки ДНК, которые не проходили через город A, затем те, которые шли мимо города B, и так далее. Молекула ДНК, прошедшая через это сито, и пре д-ставляет собой нужную последовательность дорог, являясь решением задачи направленного гамильтонова пути .

По определению частный случай задачи NP-полноты может быть преобразован за полиномиальное время к частному случаю любой другой задачи NP-полноты, и, следовательно, к задаче о направленном гамильтоновом пути. С семидесятых годов криптологи пытались использовать задачи NP-полноты для криптографии с открытыми ключами.

Хотя частный случай, решенный Эдлманом, весьма прост (семь городов на карте, простым наблюдением з а-дача моежт быть решена за несколько минут), это направление только начало развиваться, и не существует н и-каких препятствий для расширения данной методики на более сложные задачи . Таким образом, рассуждения о безопасности криптографических протоколов, основанных на задачах NP-полноты, рассуждения, которые до сих пор начинались словами , "Предположим, что у врага есть миллион процессоров, каждый из которых в ы-полняет миллион проверок каждую секунду", скоро, может быть, будут начинаться словами, "Предположим, у врага есть тысяча ферментных ванн, емкостью по 20000 литров каждая ".