Текущее положение дел

2. Текущее положение дел

2.1. Какова максимальная длина ключа длясимметричных криптосистем, которая

поддается программному взлому методомполного перебора?

Известно, что два ключа по 56 бит были подобраны полным перебором на обычных

компьютерах типа PC. Специализированная машина (построенная EFF) помогла

длявторого ключа, выполнив приблизительно треть общего объема вычислений.

Ключи были для алгоритма DES. Качественный ПК или рабочая станция могут

перебирать с максимальной скоростью нескольких миллионов ключей в секунду.

Еслипринять среднюю скорость один миллион ключей в секунду на машину, то легко

видеть, что для подбора ключа 10000 машин должны в среднем затратить 42 дня.

Полный перебор ключа длиной 64 бита для RC5 (для которого сложность полного

перебора несколько выше, чем для DES) в настоящее время продолжается, и

будетдлиться, по крайней мере, еще нескольких лет. Напоминаем, что подбор ключа

размером 64 бита, является в 256 раз более трудоемким, чем подбор ключа длиной

56 бит.

2.2. То же, с использованием специальнойаппаратуры?

Американская группа EFF, инвестировала 250000$ в создание специализированной

машины под названием "Deep crack" ("глубокий взлом"),которая в состоянии

перебрать все ключи алгоритма DES приблизительно за три дня. В ней использованы

специализированные процессоры, которые невозможноприменить для целей, отличных

от взлома DES (в частности, они ничего "не знают" о RC5).

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

более 20 лет, и можно предположить, что, вероятно, машине EFF

предшествовалидругие прототипы, разрабатываемые секретными службами. В любом

случае, скоро уже 15 лет периодически упоминаются принципы построения такой

машины.

2.3. А для несимметричных криптосистем?

В принципе, существуют две математические задачи, используемые в асимметричных

шифрах: факторизация и дискретное логарифмирование. RSAиспользует первую, DSS

вторую. Другие упоминаемые задачи (вариации двух предыдущих, использование

эллиптических кривых, задача об укладке ранца,минимизация сети (задача

коммивояжера), обратное распознавание (permuted perceptrons problem - см.

примечания) относительно редко используются в настоящеевремя.

Рекорд факторизации датируется 22-ым августа 1999: число размером 155 десятичных

цифр (512 бит) было факторизовано за шесть месяцев вычислений напарке

приблизительно из 600 машин, некоторые из которых могут быть квалифицированны

как "быки" (в частности Cray с 2 ГБ памяти).Примененные алгоритмы гораздо более

сложны, чем полный перебор, и требуют большого количества оперативной памяти с

хорошей скоростью доступа.

Дискретное логарифмирование менее исследовано, на его взлом осуществлено меньше

инвестиций, чем на факторизацию. Рекорд - порядка 95 десятичных цифр.

2.4. Что относительно "кофейника"Шамира?

Представленный на Eurocrypt'99 в Праге (в начале мая 1999), этот аппарат

ускоряет физическими средствами исследование гладких чисел (то есть

полученныхпроизведением только маленьких простых чисел), которые получают обычно

методом решета. Эти числа являются основой нескольких алгоритмов факторизации и

решенийзадачи дискретного логарифмирования.

Сам аппарат еще не построен, описаны только его принципы. Существуют технические

проблемы для реализации прототипа (Arjen Lenstra высказал некоторыевозражения, с

которыми Adi Shamir согласился).

По общему мнению, этот метод позволил бы факторизовать число приблизительно в

600 бит, со средствами, которые позволили установить рекорд в 465 бит (вфеврале

1999), если все проблемы с реализацией будут решены. Отмечено, что решето заняло

приблизительно 60% времени для рекорда в 512 бит.

Все же шоу было очень увлекательным. Phil Zimmerman, автор PGP, заметил, что

очень доволен тем, что исследователи интересуются, как обстоят дела в

этихпроблемах, так как это увеличивает степень доверия к такого рода системам.

3. То, что будет возможным в будущем

3.1. Что такое закон Мура?

Закон Мура (Moore) является оценкой развития вычислительной техники во времени.

В базовом варианте он гласит, что для заданной стоимости (в широкомсмысле,

включая энергопотребление, производство оборудования, износ, стоимость хранения,

и т.д.) вычислительная мощность увеличивается в 8 раз каждые 3 года.Говоря более

точно, можно сказать, что через каждые три года, технологические достижения

позволяют разместить в 4 раза больше логических элементов вмикросхеме заданной

стоимости, одновременно ускоряя ее быстродействие в 2 раза.

Этот закон замечательно подтверждался в течение последних 15 лет. Следует

отметить, что центральные микропроцессоры компьютеров общего назначения

неполностью следуют этому закону, потому что они не могут так же быстро

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

такжепотому, что вычисления, которые эти процессоры обычно производят, имеют

дополнительные ограничения, делающие бесполезным использование слишком

большихрегистров).

Это касается, таким образом, систем, описываемых в терминах логических

элементов, специализированных на конкретном алгоритме. Таким образом, это посути

ASIC (Application Specific Integrated Circuit - специализированные микросхемы) и

FPGA (Field Programmable Gate Arrays - программируемые логическиеинтегральные

схемы); то есть перепрограммируемые цепи, выполняющие те же задачи, что и ASIC,

но вдвое более дорогие при заданной мощности, однакоявляющиеся многоцелевыми).