Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Больше невозможно с полной ответственностью делать такие заявления . Является ли приемлемым этот продолжающийся риск? Использование алгоритма с 64-битовым ключом вместо 56-битового ключа делает это вскрытие в 256 раз сложнее. А 40-битовый ключ делает картину просто безрадостной . Сеть из 400 компьютеров с производитель- ностью 32000 шифрований в секунду может за день выполнить вскрытие грубым взломом 40-битового ключа . (В 1992 году алгоритмы RC2 и RC4 было разрешено экспортировать с 40- битовым ключом - см. раздел 13.8.) 128-битовый ключ делает нелепой даже мысль о вскрытии грубым взломом . По оценке промышленных экс- пертов к 1996 году в мире будет использоваться 200 миллионов компьютеров . Эта оценка включает все - лт ги- гантского мэйнфрейма Cray до блокнотных компьютеров. Даже если все эти компьютеры будут брошены на вскрытие грубой силой, и каждый из них будет выполнять миллион шифрований в секунду, время раскрытия ключа все равно будет в миллион раз больше времени существования вселенной . Нейронные сети Нейронные сети не слишком пригодны для криптоанализа, в первую очередь из-за формы пространства р е- шений. Лучше всего нейронные сети работают с проблемами, имеющими непрерывное множество решений, одни из которых лучше других. Это позволяет нейронным сетям обучаться, предлагая все лучшее и лучшие р е- шения. Отсутствие непрерывности в алгоритме почти не оставляет места обучению : вы либо раскроете ключ, либо нет. (По крайней мере, это верно при использовании любого хорошего алгоритма .) Нейронные сети хоро- шо работают в структурированных средах, где обучение возможно, но не в высокоэнтропийном, кажущемся случайным мире криптографии. Вирусы Самая большая трудность в получении миллионов компьютеров для вскрытия грубым взломом - это убедить миллионы компьютерных владельцев принять участие во вскрытии. Вы могли бы вежливо попросить, но это требует много времени, и они могут сказать нет. Вы могли бы пробовать силой ворваться в их компьютеры, но это потребует еще больше времени и может закончиться вашим арестом. Вы могли бы также использовать ко м- пьютерный вирус, чтобы распространить программу взлома среди как можно большего количества компьют е- ров. Эта особенно коварная идея впервые появилась в [1593]. Взломщик пишет и выпускает на волю компьюте р- ный вирус. Этот вирус не переформатирует жесткий диск, не удаляет файлы, но во время простоя компьютера он работает на криптоаналитической проблемой грубого взлома. Различные исследования показали, что комп ь- ютер простаивает от 70 до 90 процентов времени, так что у вируса не будет проблем с временем для решения этой задачи. Если он нетребователен и в других отношениях, то его работа даже не будет заметна. В конце концов, одна из машина наткнется на правильный ключ. В этот момент имеются два варианта пр о- должения. Во первых, вирус мог бы породить другой вирус. Он не делал бы ничего, кроме самовоспроизведения и удаления всех найденных копий вскрывающего вируса, но содержал бы информацию о правильном ключе. Этот новый вирус просто распространялся бы среди компьютеров, пока не добрался бы до компьютера челов е- ка, который написал первоначальный вирус. Другим, трусливым подходом бал бы вывод на экран следующего сообщения : В этом компьютере есть серьезная ошибка. Пожалуйста позвоните 1-8001234567 и продиктуйте оператору следующее 64- битовое число: xxxx xxxx xxxx xxxx Первому, кто сообщит об этой ошибке будет выплачено вознаграждение 100 долларов. Насколько эффективно такое вскрытие? Пусть типичный зараженный компьютер проверяет тысячу ключей в секунду. Эта скорость намного меньше потенциальных возможностей компьютера, ведь мы полагаем, что он иногда будет делать и другие вещи. Предположим также, что типичный вирус инфицирует 10 миллионов машин. Этот вирус может вскрыть 56-битовый ключ за 83 дня, а 64 битовый - за 58 лет. Вам возможно при- шлось бы подкупить разработчиков антивирусного программного обеспечения, но это уже ваши проблемы . Лю- бое увеличение скорости компьютеров или распространения вируса, конечно, сделало бы это нападение более эффективным. Китайская лотерея Китайская Лотерея - эклектический, но возможный способ создания громадной параллельной машины для криптоанализа [1278]. Вообразите, что микросхема, вскрывающая алгоритм грубой силой со скоростью милл и- он проверок в секунду, встроена в каждый проданный радиоприемник и телевизор. Каждая микросхема запр о- граммирована для автоматической проверки различного набора ключей после получения пары открытый текст/шифротекст по эфиру. Каждый раз когда китайское правительство хочет раскрыть ключ, оно передает исходные данные по радио. Все радиоприемники и телевизоры в стране начинают пыхтеть. В конечном счете, правильный ключ появляется на чьем-нибудь дисплее. Китайское правительство платит приз тому человеку - это гарантирует, что результат будет сообщен быстро и правильно, и также способствует рыночному успеху р а- диоприемников и телевизоров с микросхемами вскрытия. Если у каждого человека в Китае, будь то мужчина, женщина или ребенок, есть радиоприемник или телев и- зор, то правильное значение 56-битового ключа появится через 61 секунду. Если радиоприемник или телевизор есть только у каждого десятого китайца(что близко к действительности), то правильный ключ появится через 10 минут. Правильный 64-битовый ключ будет раскрыт через 4.3 часа (43 часа, если радиоприемник или телевизор есть только у каждого десятого китайца). Чтобы сделать такое вскрытие возможным на практике, необходимо сделать ряд модификаций. Во первых, проще, чтобы каждая микросхема проверяла случайные, а не уникальные ключи . Это сделает вскрытие на 39% медленнее, что не очень важно для чисел такого масштаба . Затем, Китайская коммунистическая партия должна принять решение, что каждый должен включать свой приемник или телевизор в определенное время, чтобы гарантировать работу всех приемных устройств во время передачи пары открытый текст/шифротекст . Наконец, каждому должно быть приказано позвонить в Центр - или как он там называется - когда ключ появляется у него на экране и зачитать строку чисел, появившуюся на экране . Эффективность Китайской лотереи для различных стран и различных длин ключа показана в 5-й. Ясно, что Китай оказался бы в лучшем положении, если бы у каждого китайца - мужчины, женщины или ребенка - бал свой приемник или телевизор. В Соединенных штатах живет меньше людей, но гораздо больше аппаратуры . Штат Вайоминг самостоятельно сможет взломать 56-битовый ключ меньше, чем за день. Табл. 7-2. Оценки среднего времени вскрытия грубой силой при китайской лотерее (Все данные взяты из World Almanac and Book of Facts за 1995 год.) Страна Население Количество телевизо- ров/радиоприемников Время 56 бит взлома 64 бита Китай 1190431000 257000000 280 секунд 20 часов США 260714000 739000000 97 секунд 6.9 часа Ирак 19890000 4730000 4.2 часа 44 дня Израиль 5051000 3640000 5.5 часа 58 дней Вайоминг 470000 1330000 15 часов 160 дней Виннемукка, Невада 6100 17300 48 дней 34 года Биотехнология Если возможно создание биомикросхем, то было бы глупо не попытаться использовать их в инструмента криптоанализа вскрытием грубой. Рассмотрим гипотетическое животное, называемое "DESозавром" [1278]. Оно состоит из биологических клеток, умеющих проверять возможные ключи . Пары "открытый текст/шифротекст" поступают в клетки по некоторому оптическому каналу (видите ли, все эти клетки прозрач- ны). Решения доставляются к органам речи DESозавра с помощью специальных клеток, путешествующих по кровеносной системе животного. Типичный динозавр состоит из 10 14 клеток (без бактерий). Если каждая из них выполняет миллион шифр о- ваний в секунду (неплохой результат), вскрытие 56-битового ключа займет семь десятитысячных секунды . Вскрытие 64-битового ключа потребует меньше, чем две десятых секунды . Вскрытие 8-битового ключа все же продлится 10 11 лет. Другой биологический подход состоит в использовании генетически проектируемых криптоаналитических морских водорослей, которые умеют выполнять вскрытие криптографических алгоритмов грубой силой [1278]. Такие организмы, покрыв большую область, позволили бы создать распределенную машину с большим колич е- ством процессоров. Пара "открытый текст/шифротекст" могла бы передаваться по радио через спутник. Обн а- ружение результата организмом могло бы стимулировать близлежащие ячейки изменить цвет, сообщая решение обратно на спутник. Предположим, что типичная клетка морской водоросли - это кубик со стороной 10 микрон (возможно, это оценка сверху, следовательно 10 15 клеток заполнят кубический метр. Выплесните их в океан, покрывая 200 квадратных миль (518 квадратных километров) на глубину один метр (это ваши проблемы, как осуществить это - я подаю только идею), и у вас будет 10 23 водорослей (более чем сотней миллиарда галлонов), плавающих в океане. (Для сравнения, из танкера Valdez вытекло 10 миллионов галлонов нефти.) Если каждая из них может проверять миллион ключей в секунду, то для 128-битового алгоритма они раскроют ключ в только спустя 100 лет. (Возникшее при этом цветение морских водорослей - это ваша проблема.) Крупные достижения в быстр о- действии морских водорослей, их диаметр или даже размеры пятна в океане могут заметно уменьшить эти зн а- чения. Даже не спрашивайте меня о нанотехнологии. Термодинамические ограничения Одним из следствий закона второго термодинамики является то, что для представления информации нео б- ходимо некоторое количество энергии. Запись одиночного бита, изменяющая состояние системы, требует кол и- чества энергии не меньше чем kT; где Т - абсолютная температура системы и k - постоянная Больцмана. (Не волнуйтесь, урок физики уже почти закончен.) Приняв, что k = l.38*10 -16 эрг/K, и что температура окружающей вселенной 3.2K, идеальный компьютер, ра- ботая при 3.2K, потреблял бы 4.4*10 -16 эрга всякий раз, когда он устанавливает или сбрасывает бит . Работа компьютера при температуре более низкой, чем температура космического пространства, потребовала бы д о- полнительных расходов энергии для отвода тепла. Далее, энергия, излучаемая нашим Солнцем за год, составляет около 1.21*10 41 эргов. Это достаточно для выполнения 2*10 56 перемен бита в нашем идеальном компьютере, а этого, в свою очередь, хватит для того, чт о- бы 187-битовый счетчик пробежал все свои значения . Если мы построим вокруг Солнца сферу Дайсона и пер е- хватим без всяких потерь всю его энергию за 32 года, мы сможем получить компьютер для вычисления 2 192 чисел. Конечно, энергии для проведения каких-нибудь полезных вычислений с этим счетчиком уже не останется. Но это только одна жалкая звезда. При взрыве типичной сверхновой выделяется около 10 51 эргов. (В сто раз больше энергии выделяется в виде нейтрино, но пусть они пока летают .) Если всю эту энергию удастся бросить на одну вычислительную оргию, то все свои значения сможет принять 219-битовый счетчик. Эти числа не имеют ничего общего с самой аппаратурой, они просто показывают максимальные значения, обусловленные термодинамикой. Кроме того, эти числа наглядно демонстрируют, что вскрытие грубой силой 256-битового ключа будет невозможно, пока компьютеры построены из обычной материи и располагаются в обычном пространстве. 7.2 Длина открытого ключа Однонаправленные функции обсуждались в разделе 2.3. Однонаправленной функцией является умножение двух больших простых чисел, получить произведение, перемножив числа, нетрудно, но нелегко разложить пр о- изведение на множители и получить два больших простых числа (см. раздел 11.3). Криптография с открытыми ключами использует эту идею для создания однонаправленной функции с люком . На самом деле, это ложь, не доказано, что разложение на множители является тяжелой проблемой (см. раздел 11.4). Насколько сегодня из- вестно, это похоже на правду. И даже если это так, никто не может доказать, что трудные проблемы действ и- тельно трудны. Все считают, что разложение на множители является трудной задачей, но это никогда не было доказано математически. На этом стоит остановиться поподробнее. Легко представить, что лет через 50 мы соберемся вместе, вспом и- ная старое доброе время, когда все люди считали, что разложение на множители было трудным и лежало в о с- нове криптографии, а различные компании делали из этого деньги. Легко вообразить, что будущие достижения в теории чисел упростят разложение на множители или достижения теории сложности сделают разложение на множители тривиальным. Нет причин верить в это - и большинство людей, знающих достаточно, чтобы иметь собственное мнение, скажет вам, что подобное развитие событий является маловероятным - но нет и причин верить, что такого прорыва не случится. В любом случае, доминирующие сегодня алгоритмы шифрования с открытым ключом основаны на трудн о- сти разложения на множители больших чисел, которые являются произведением двух больших простых чисел. (Другие алгоритмы основаны на так называемой Дискретной проблемой логарифма, но пока предположим, что к ней применимы те же рассуждения.) Эти алгоритмы также восприимчивы к вскрытию грубой силой, но по разному. Взлом этих алгоритмов состоит не из перебора всех возможных ключей, а из попыток разложения больших чисел на множители (или взятия дискретных логарифмов в очень большом конечной области - точно такая же проблема). Если число слишком мало, вы никак не защищены. Если число достаточно велико, то вы надежно защищены против всей вычислительной мощи мира, если она будет биться над этой задачей с насто я- щего времени до тех пор, пока Солнце не станет сверхновой - таково сегодняшнее понимание математики этой проблемы. В разделе 11.3 разложение на множители рассматривается математически подробно, а здесь я огр а- ничусь оценкой времени разложения на множители чисел различной длины. Разлагать большие числа на множители нелегко, но, к несчастью для проектировщиков алгоритмов, этот процесс становится все легче. Что еще хуже, он становится легче ч большей скоростью, чем предсказывалось математиками. В 1976 году Ричард Гай (Richard Guy) писал: "Я был бы немало удивлен, если бы кто-нибудь научился разлагать на множители произвольные числа порядка 10 80 в течение данного столетия" [680]. В 1977 году Рон Ривест (Ron Rivest) заявил, что разложение на множители 125-разрядного числа потребует 40 ква д- риллионов лет [599]. В 1994 году было разложено на множители 129-разрядное число [66]. Если из этого и можно сделать какие-то выводы, то только то, что предсказывать глупо . В 4-й приведены результаты разложения на множители за последнюю дюжину лет . Самым быстрым алго- ритмом разложения на множители является квадратичное решето (см. раздел 11.3). Эти числа сильно пугают. Сегодня 512-битовые числа уже используются в операционных системах. Разл о- жение их на множители, и полная компрометация, таким образом, системы защиты, вполне реально. Червь в Internet мог бы сделать это в течение уикенда. Табл. 7-3. Разложение на множителя с помощью "квадратичного решета" Год Число десятичных разря- дов в разложенном числе Во сколько раз сложнее разложить на множители 512-битовое число 1983 71 >20 миллионов 1985 80 >2 миллионов 1988 90 250000 1989 100 30000 1993 120 500 1994 129 100 Вычислительная мощь обычно измеряется в mips-годах: годовая работа компьютера, выполняющего милл и- он операций в секунду (one-million-instruction-per-second, mips), или около 3*10 13 операций. Принято, что ма- шина с производительностью 1 mips-год эквивалентна VAX 11/780 компании DEC. То есть, mips-год - это год работы компьютера VAX 11/780 или эквивалентного. (100 МГц Pentium - это машина в 50 mips, а 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]. Табл. 7-4. Разложение на множители с помощью решета общего поля чисел Количество бит Сколько mips-лет нужно для разложе- ния 512 30000 768 2*10 8 1024 3*10 11 1280 1*10 14 1536 3*10 16 2048 3*10 20 Кроме того, решето общего поля чисел становится все быстрее и быстрее . Математики изобретают новые трюки, оптимизации, методы, и нет причин считать, что эта тенденция оборвется. Близкий алгоритм, решето специального поля чисел, уже может разлагать на множители числа определенной специализированной формы - обычно не используемые в криптографии - гораздо быстрее, чем решето общего поля чисел может разложить на множители любые числа того же размера . Разумно предположить, что решето общего поля чисел может быть оптимизировано, чтобы достичь такой же скорости [1190], возможно, что NSA уже знает, как это сделать. В 2-й показано количество mips-лет, требуемое для разложения чисел различной длины при помощи решета спец и- ального поля чисел [1190]. Табл. 7-5. Разложение на множители с помощью решета специаль- ного поля чисел Количество бит Сколько mips-лет нужно для разложе- ния 512 <200 768 100000 1024 3*10 7 1280 3*10 9 1536 2*10 11 2048 4*10 14 В 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-лет, большая корпорация - 10 7 mips-лет, а правительство большой страны - 10 9 mips-лет. Предположим также, что вычислительная мощь будет возрастать на порядок каждые пять лет . И , наконец, предположим также, что ус- пехи в математике разложения на множители позволят нам раскладывать любые числа со скоростью, сравн и- мой с той, которую обеспечивает решето специального поля чисел . (Это пока невозможно, но прорыв может случиться в любой момент.) 1st рекомендует для различных лет использовать с целью обеспечения безопасн о- сти различные длины ключей. Табл. 7-6. Рекомендованные длины открытых ключей в (битах) Год Частное лицо Корпорация Правительство 1995 768 1280 1536 2000 1024 1280 1536 2005 1280 1536 2048 2010 1280 1536 2048 2015 1536 2048 2048 Не забывайте учитывать значимость ключа. Открытые ключи часто используются для длительной обеспеч е- ния безопасности важной информации: главный ключ банка для системы электронных наличных, ключ, и с- пользуемый правительством для подтверждения паспортов, ключ цифровой подписи государственного нотари у- са. Возможно, не стоит тратить месяцы машинного времени на вскрытие какого-то личного ключа, но если м о- жете с помощью добытого ключа напечатать собственные деньги, то идея становится весьма захватывающей . Длина 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. Долгосрочный прогноз разложения на множители Год Длина ключа (в битах) 1995 1024 2005 2048 2015 4096 2025 8192 2035 16384 2045 32768 Минимальные оценки предполагают бюджет $25000, алгоритм "квадратичное решето " и скорость технич е- ского прогресса 20 процентов в год. Средние оценки предполагают бюджет 25 миллионов долларов, алгоритм "решето общего поля чисел" и скорость технического прогресса 33 процента в год . Максимальные оценки пред- полагают бюджет 25 миллиардов долларов, алгоритм "решето общего поля чисел", работающий со скоростью решета специального поля чисел и скорость технического прогресса 45 процентов в год . Всегда есть вероятность того, что успехи в разложении на множители будут поразительны и для меня, но я попытался учесть этот множитель в своих прогнозах . Но почему мне нужно верить? Я лишь продемонстрировал собственную глупость, занимаясь предсказаниями . Табл. 7-8. Оптимистичные рекомендации Ривеста для длины клю- чей (в битах) Год Минимальная Средняя Максимальная 1990 398 515 1289 1995 405 542 1399 2000 422 572 1512 2005 439 602 1628 2010 455 631 1754 2015 472 661 1884 2020 489 677 2017 Вычисление с помощью ДНК Это похоже на волшебство. В 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- p)) n . Число нужных вентилей, по видимому, растет полином и- ально с ростом длины числа (в битах), поэтому число требуемых попыток будет расти с увеличением длины используемых чисел сверхэкспоненциально - хуже чем при разложении делением ! Поэтому, хотя квантовое разложение на множители вызывает восхищение в академических кругах, малов е- роятно, что оно будет иметь практическое значение в обозримом будущем . Но не говорите потом, что я вас не предупреждал. 7.3 Сравнение длин симметричных и открытых ключей Система взламывается обычно в ее слабейшем месте . Если вы проектируете систему, которая использует и симметричную криптографию, и криптографию с открытыми ключами, то длины ключей для криптографии каждого типа должны выбираться так, чтобы вскрыть любой из компонентов системы было одинаково трудно . Бессмысленно использовать симметричный алгоритм со 128-битовым ключом вместе с алгоритмом с открыт ы- ми ключами, использующим 386-битовый ключ. Точно так же бессмысленно использовать в одной системе симметричный алгоритм с 56-битовым ключом и алгоритм с открытыми ключами, применяющий 1024-битовый ключ. В -2-й перечислены длины модулей открытых ключей, трудность разложения которых на множители сра в- нима со сложностью вскрытием грубой силой сопоставленных длин популярных симметричных ключей . Табл. 7-9. Длины симметричных и открытых ключей с аналогичной ус- тойчивостью к вскрытию грубой силой Длина симметричного ключа (в битах) Длина открытого ключа (в битах) 56 384 64 512 80 768 112 1792 128 2304 Из этой таблица можно сделать вывод, что если вы достаточно беспокоитесь о своей безопасности, чтобы выбрать симметричный алгоритм со 112-битовым ключом, вам следует выбрать длину модуля в вашем алг о- ритме с открытыми ключами порядка 1792 бит. Однако, в общем случае следует выбирать длину открытого ключа более безопасную, чем длина вашего симметричного ключа . Открытые ключи обычно используются дольше и применяются для защиты большего количества информации . 7.4 Вскрытие в день рождения против однонаправленных хэш-функций Существует два способа вскрытия однонаправленных хэш-функций грубой силой . Первый наиболее очеви- ден: дано значение хэш-функции сообщения, Н(M), врагу хотелось бы суметь создать другой документ, М', та- кой, что Н(M')=Н(M). Второй способ более тонок: врагу хотелось бы найти два случайных сообщения , M и М', таких, что Н(M')=Н(M). Такой способ называется столкновением и является более простым, чем первый, сп о- собом вскрытия. Парадокс дня рождения является стандартной статистической проблемой. Сколько человек должно собрат ь- ся в одной комнате, чтобы с вероятностью 1/2 хотя бы у кого-нибудь из них был бы общий с вами день рожд е- ния? Ответ - 183. Хорошо, а сколько людей должно собраться, чтобы с вероятностью 1/2 хотя бы у двоих из них был бы общий день рождения? Ответ удивителен - 23. 23 человека, находящихся в комнате, образуют 253 ра з- личных пары. Найти кого-нибудь с тем же днем рождения - аналогия с первым способом вскрытия, найти двух человек с произвольным одинаковым днем рождения - аналогия со вторым способом . Второй способ широко известен как вскрытие в день рождения. Предположим, что однонаправленная хэш-функция безопасна, и лучшим способом ее вскрытия является вскрытие грубой силой. Результатом функции является m-битовое число. Поиск сообщения, хэш-значение кото- рого совпадает с заданным, в среднем потребовал бы хэширования 2 m случайных сообщений. А для обнаруже- ния двух сообщений с одинаковым хэш-значением потребуется только 2 m/2 случайных сообщений. Компьютеру, который хэширует миллион сообщений в секунду, потребовалось бы 600000 лет, чтобы найти второе сообщение с тем же 64-битовым хэш-значением. Тот же компьютер сможет найти пару сообщений с общим хэш-значением примерно за час Это значит, что, если вы опасаетесь вскрытия в день рождения, вы должны выбирать длину хэш-значения в два раза длиннее, чем вам потребовалось бы в противном случае . Например, если вы хотите уменьшить вероят- ность взлома вашей системы до 1 шанса из 2 80 , используйте 160-битовую однонаправленную хэш-функцию . |