решета специального поля чисел и скорость технического прогресса 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 литров каждая ".

Квантовые вычисления

А теперь еще большая фантастика. В основе квантовых вычислений используется двойственная природа м а-терии (и волна, и частица). Фотон может одновременно находиться в большом количестве состояний. Классич е-ским примером является то, что фотон ведет себя как волна, встречая частично прозрачное зеркало. Он одн о-временно и отражается и проходит через зеркало подобно тому, как морская волна, ударяясь о волнолом с н е-большим отверстием в нем, одновременно отразится от стены и пройдет сквозь нее . Однако, при измерении фотон ведет себя подобно частице, и только одно состояние может быть обнаружено .

В [1443] Питер Шор (Peter Shor) очертил принципы построения машины для разложения на множители, о снованной на законах квантовой механики . В отличие от обычного компьютера, который можно представить как машину, имеющее в каждый момент времени единственное фиксированное состояние, квантовый компьютер обладает внутренней волновой функцией, являющейся суперпозицией комбинаций возможных основных с о-стояний. Вычисления преобразуют волновую функцию, меняя весь набор состояний единым действием . Таким образом, квантовый компьютер имеет преимущество над классическим конечным автоматом : он использует квантовые свойства для числа разложения на множители за полиномиальное время, теоретически позволяя взломать криптосистемы, основанные на разложении на множители или задаче дискретного логарифма .

Общепризнанно, что квантовый компьютер не противоречит фундаментальным законам квантовой механ и-ки. Однако, непохоже, что квантовая машина для разложения на множители будет построена в обозримом б у-дущем ... если вообще будет построена. Одним из главных препятствий является проблема некогерентности , которая является причиной потери отчетливости волновыми огибающими и приводит к сбою компьютера . Из-за некогерентности квантовый компьютер, работающий при 1К, будет сбиваться каждую наносекунду . Кроме того, для построения квантового устройства для разложения на множители потребуется огромное количество вент илей, а это может не дать построить машину. Для проекта Шора нужно совершенное устройство для возведения в степень. Внутренние часы не используются, поэтому для разложения на множители криптографически знач и-мых чисел могут потребоваться миллионы или, возможно, миллиарды индивидуальных вентилей . Если минимальная вероятность отказа каждого из n квантовых вентилей равна p, то среднее количество испытаний, нео б-ходимое для достижения успеха, составит (1/(1- Число нужных вентилей, по видимому, растет полином и-ально с ростом длины числа (в битах), поэтому число требуемых попыток будет расти с увеличением длины используемых чисел сверхэкспоненциально - хуже чем при разложении делением !

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

7.3 Сравнение длин симметричных и открытых ключей

Система взламывается обычно в ее слабейшем месте . Если вы проектируете систему, которая использует и симметричную криптографию, и криптографию с открытыми ключами, то длины ключей для криптографии каждого типа должны выбираться так, чтобы вскрыть любой из компонентов системы было одинаково трудно . Бессмысленно использовать симметричный алгоритм со 128-битовым ключом вместе с алгоритмом с открыт ыми ключами, использующим 386-битовый ключ. Точно так же бессмысленно использовать в одной системе симметричный алгоритм с 56-битовым ключом и алгоритм с открытыми ключами, применяющий 1024-битовый ключ.

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

Табл. 7-9.

Длины симметричных и открытых ключей с аналогичной устойчивостью к вскрытию грубой силой

Из этой таблица можно сделать вывод, что если вы достаточно беспокоитесь о своей безопасности, чтобы выбрать симметричный алгоритм со 112-битовым ключом, вам следует выбрать длину модуля в вашем алгоритме с открытыми ключами порядка 1792 бит. Однако, в общем случае следует выбирать длину открытого ключа более безопасную, чем длина вашего симметричного ключа . Открытые ключи обычно используются дольше и применяются для защиты большего количества информации .

7.4 Вскрытие в день рождения против однонаправленных хэш-функций

Существует два способа вскрытия однонаправленных хэш-функций грубой силой . Первый наиболее очевиден: дано значение хэш-функции сообщения, H(M), врагу хотелось бы суметь создать другой документ, М, такой, что H(M)=H(M). Второй способ более тонок: врагу хотелось бы найти два случайных сообщения, M и М, таких, что H(M)=H(M). Такой способ называется столкновением и является более простым, чем первый, способом вскрытия.

Парадокс дня рождения является стандартной статистической проблемой. Сколько человек должно собрат ь-ся в одной комнате, чтобы с вероятностью 1/2 хотя бы у кого-нибудь из них был бы общий с вами день рожд е-ния? Ответ - 183. Хорошо, а сколько людей должно собраться, чтобы с вероятностью 1/2 хотя бы у двоих из них был бы общий день рождения? Ответ удивителен - 23. 23 человека, находящихся в комнате, образуют 253 различных пары.

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

Предположим, что однонаправленная хэш-функция безопасна, и лучшим способом ее вскрытия является вскрытие грубой силой. Результатом функции является т-битовое число. Поиск сообщения, хэш-значение которого совпадает с заданным, в среднем потребовал бы хэширования 2 m случайных сообщений. А для обнаружения двух сообщений с одинаковым хэш-значением потребуется только 2 m/2 случайных сообщений. Компьютеру, который хэширует миллион сообщений в секунду, потребовалось бы 600000 лет, чтобы найти второе сообщение с тем же 64-битовым хэш-значением. Тот же компьютер сможет найти пару сообщений с общим хэш-значением примерно за час

Это значит, что, если вы опасаетесь вскрытия в день рождения, вы должны выбирать длину хэш-значения в два раза длиннее, чем вам потребовалось бы в противном случае . Например, если вы хотите уменьшить вероятность взлома вашей системы до 1 шанса из 2 80, используйте 160-битовую однонаправленную хэш-функцию .

7.5 Каков должны быть длина ключа?

На этот вопрос нет единого ответа, ответ этот зависит от ситуации . Чтобы понять, какая степень безопасности вам нужна, вы должны задать себе несколько вопросов . Сколько стоит ваша информация? Как долго она должна безопасно храниться? Каковы ресурсы ваших врагов?

Список клиентов может стоить $1000. Финансовая информация при неожиданном разводе могла бы стоить $10000. Реклама и данные маркетинга для большой корпорации могли бы стоить 1 миллион долларов . Главный ключ для системы электронных наличных может стоить миллиарды .

В мире торговли предметами потребления секреты должны только сохраняться в течение нескольких минут. В газетном бизнесе сегодняшние секреты - это завтрашние заголовки. Информация о разработке какого-то пр о-дукта, возможно, должна будет храниться в секрете в течение года или двух Изделия(программы) могла бы была бы должна остаться секретом в течение года или два. Данные переписи США в соответствии с законом должны храниться в секрете в течение 100 лет.

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

В этих терминах даже можно определить требования к безопасности Можно . Например:

Длина ключа должна быть такой, чтобы взломщик, готовый потратить 100 миллионов долларов, мог взломать систему в течение года с вероятностью не более, чем 1/2 32, даже с учетом скорости технического прогресса 30 процентов в год.

В -3-й, частично взятой из [150], приведены оценки требований к безопасности для различной информ ации:

Будущую вычислительную мощь оценить нелегко, но вот разумное эмпирическое правило : эффективность вычислительных средств удваивается каждые 18 месяцев и возрастает на порядок каждые 5 лет . Следовательно, через 50 лет самые быстрые компьютеры будут в 10 миллиардов быстрее, чем сегодня ! Кроме того, не забывайте, что эти числа относятся только к универсальным компьютерам, кто знает, какие специализированные ус тройства для вскрытия криптосистем будут разработаны в следующие 50 лет ?