отметить, что центральные микропроцессоры компьютеров общего назначения
неполностью следуют этому закону, потому что они не могут так же быстро
увеличить размер шины данных (по соображениям обратной совместимости кода, а
такжепотому, что вычисления, которые эти процессоры обычно производят, имеют
дополнительные ограничения, делающие бесполезным использование слишком
большихрегистров).
Это касается, таким образом, систем, описываемых в терминах логических
элементов, специализированных на конкретном алгоритме. Таким образом, это посути
ASIC (Application Specific Integrated Circuit - специализированные микросхемы) и
FPGA (Field Programmable Gate Arrays - программируемые логическиеинтегральные
схемы); то есть перепрограммируемые цепи, выполняющие те же задачи, что и ASIC,
но вдвое более дорогие при заданной мощности, однакоявляющиеся многоцелевыми).
3.2. Какова предполагаемая стоимость полногоперебора с использованием
специализированного оборудования?
Если закон Мура будет продолжать выполняться (и не имеется веских оснований для
обратного, так как он учитывает качественные достижения, а не толькоувеличение
точности обработки кремния), можно достичь машины EFF (четверть миллиона
долларов, для 56 бит за 3 дня) и добавлять 3 бита каждые 3 года (3бита = 2^3 =
8; что дает в 8 раз больше возможных вариантов ключей).
Заметим, что для сохранения закон Мура, качественные достижения должны
происходить достаточно быстро, так как имеются пределы в увеличении
плотностиэлементов на кристалле кремния (замедление вследствие туннельного
эффекта). В ряде разрабатываемых методов предполагается осуществить замену
кремния наарсенид галлия, что позволит достичь более высокой плотности
элементов, замену алюминия медью, которая позволяет работать гораздо более
быстро, построениеоптической логики (оптический элемент переключается
приблизительно в 100 раз быстрее электронного, но его стоимость выше более чем в
100 раз).
Таким образом, можно считать, подобрать полным перебором 128-битный ключ так же
"легко", как сейчас 56-битный, станет возможным через 72 года. Этаоценка
является "наилучшей", в то время как многие исследователи этой тематики
полагают, что закон Мура будет выполняться в лучшем случае ещенесколько лет
(действительно, все качественные изменения, привнесенные за последних 15 лет,
были просто нереализованными, известными с 1975 года, и ихзапас почти исчерпан в
настоящее время).
3.3. А с использованием квантовыхкомпьютеров?
Квантовые компьютеры, реализуемые через суперпозицию состояний одной частицы,
являются более мощной вычислительной моделью, чем машина Тьюринга ипозволяют
осуществить многие операции (среди которых полный перебор ключей такого
"безграничного" алгоритма, как DES) за субэкспоненциальное время.
Квантовые компьютеры очень соблазнительны, но они не существуют. Был построен
двухбитовый квантовый регистр, но имеются достаточно мощныепрепятствия для
построения машины, способной сломать DES (главным образом, инициализация этого
монстра, которая не может быть распараллелена, и занимает,таким образом, 2^n
операций для ключа n битов).
Это не имеет большого значения для другого типа квантовой криптографии, который
служит для "неперехватываемой" передачи данных по оптоволокну(используя принцип
неопределенности Гейзенберга).
4. Различные слухи
4.1. NSA/DST/другие могут ломать ключи до128 бит.
Имеются очень сильные возражения против такого рода высказываний. Среди
классических можно выделить одно, предполагающее наличие процессора
сэнергопотреблением в 10 раз меньше, чем у классических (таким могли бы
располагать секретные службы, имеющие преимущество). Энергетические затраты
наполный перебор 128-битного ключа, если их перевести в тепловую форму,
заставили бы исчезнуть под водой Нидерланды в результате таяния полярных льдов.
Что касается 256-битных ключей, то если предположить, что затраты на анализ
одного ключа равны энергии перехода электрона с одной орбиты атома на другую,то
количества великодушно предоставляемой Солнцем энергии недостаточно для
осуществления такого перебора за разумное время.
Некоторые легко манипулируют количеством битов, легко относя 20 бит на
использование сверхпроводников или оптических элементов, 20 других наприменение
суперэффективных алгоритмов, и 30 последних потому что "это уже немного" (да,
просто помножим на 1 миллиард, это действительно"немного").
Напомню, что число битов экспоненциально. Это означает, что затраты на перебор
каждых n битов пропорциональны 2^n. Чтобы это было легче представить,напомним,
что:
64 бита: 18446744073709551616 возможных ключей
128 бит: 340282366920938463463374607431768211456 возможных ключей
256 бит:
115792089237316195423570985008687907853269984665640564039457584007913129639936
возможных ключей
4.2. NSA/DST/другие обладают квантовымикомпьютерами.
Очень маловероятно. Если это правда, то технологические достижения опережают
всех как минимум лет на 10. Другими словами, они располагали бы тогда
такойпродвинутой технологией, что сама идея дальнейшей борьбы была бы абсурдом.
Некоторые упоминают возможность получения внеземной технологии, либо через Людей
в Черном, либо непосредственно через Phil Zimmerman, их посла на этойпланете.
Как считают другие источники, квантовым компьютером располагала цивилизация
Атлантов (конечно, Атлантида была затоплена именно в результатеперебора ключа
"классическими" методами, см. выше).
Сталкиваясь с проявлениями абсурда и дилетантства в этой области, хочется
посоветовать держаться подальше от подобного рода спекуляций, чтобыневыглядеть
клоуном. Если хочется оценить что в состоянии сделать NSA, надо дать ему 3 года
времени в соответствии с законом Мура и хороший бюджет. Это позволитсделать
задачу с 64 битами решаемой. 80 бит останутся недостижимыми.
4.3. NSA/DST/другие достигли методов криптоанализа,недоступных другим.
NSA (в лице Don Coppersmith) объявил в 1987 году, что знали уже в 1977 о
дифференциальном криптоанализе, обнародованном Бихамом и Шамиром (E. Biham,
A.Shamir) именно в этом 1987 году. Алгоритм DES, разработанный в 1977,
специально защищен от такой атаки.
Тем не менее, уточним, что такая атака требует огромного количества пар
открытый/зашифрованный текст, и, в любом случае, нереальна. Кроме того, DES
небыл защищен против линейного криптоанализа, открытого в 1993 Matsui, что
ограничивает научное превосходство NSA 15 годами. Наконец, этот последний
способкриптоанализа также нереален, т.к. требует 64 ТБ известного открытого
текста, что в несколько десятков миллионов раз превышает объем Библии.
Подобные слухи ходили также про факторизацию, дискретное логарифмирование и
средства от прыщей. Легко можно встретить такие слухи в упоминаниях
омеждународных заговорах злодеев, которые хотят знать все обо всех в этом мире.
В любом случае, с определенного момента, гораздо дешевле установить видеокамеру
в вашем офисе, чем заставлять "молотить" квантовыйкомпьютер. Знаете ли Вы, что
восстановление изображения Вашего монитора возможно с дистанции 100 метров? То
же самое касается и сигналов клавиатуры,когда Вы печатаете. Необходимо иметь
хорошо спроектированную сетку Фарадея, чтобы защищаться от этого. Шифрование
позволяет установить защищенный каналмежду двумя точками, но не защищает сами
точки.
4.4. Я работаю на NSA/DST/других и поэтомупытаюсь убедить общественность, что
128-битное шифрование надежно.
Niark niark niark. Я обманщик, не так ли?
© Автор: Thomas Pornin (thomas.pornin@ens.fr); оригинал:
http://www.dmi.ens.fr/~pornin/faq-cle.html
©Владислав Мяснянкин, перевод на русский язык.
Примечания переводчика.
Пожалуйста, не присылайте мне замечания/комментарии по содержанию документа. Я
только перевел его. Пишите непосредственно автору (на французском или
английском языке) - адрес в заголовке.
EFF - Electronic Frontier Foundation http://www.eff.org/
NSA - National Security Agency http://www.nsa.gov/
DST - Direction de la Sйcuritй du Territoire
http://www.chez.com/icebreaker/dst/
Я не нашел русского термина для "Permuted Perceptrons Problem" и перевел как
"задача обратного распознавания". Если есть более правильный перевод - буду
рад услышать. Что это такое можно посмотреть например на
http://cgi.dmi.ens.fr/cgi-bin/pointche/papers.html?Po95a (на английском).
Если вы найдете неточности в употреблении терминов или предложите более
"благозвучный" вариант их перевода, это будет воспринято с благодарностью.
Неконструктивная критика и флейм пойдут на /dev/null.