Стандарты безопасности применяющие RSA

Другой прогноз относительно будущего целочисленной факторизации предлагает Ривест (R. Rivest). В основе прогноза — оценка инвестиций для производства специального факторизующего компьютера.

Отметим, что участники проекта RSA-129 без значительных усилий получили доступ к 0,03% вычислительных ресурсов Internet По их собственным оценкам, в проекте могло быть задействовано около 3% вычислительных ресурсов сети.

Помимо сети Internet существует ряд локальных организаций (фирм, корпораций, консорциумов), обладающих достаточными вычислительными ресурсами. Например, компания SiliconGraphics имеет около 5000 сотрудников и 10 000 рабочих станций с общей производительностью 105 mips — в десять раз больше производительности проекта RSA-129. Воспользовавшись алгоритмом ОЧР, компания, в частности, может легко факторизовать число 160D (512-битный RSA-модуль) в течение одного года.

Известно, что вычислительные ресурсы рабочих станций Internet могут использоваться незаметно для их владельцев. Недавно в результате несанкционированного использования вычислительных ресурсов общей производительностью 400 MY был факторизован 384-битный RSA-модуль.

Обратимся к прогнозу роста производительности. Закон Мура утверждает, что производительность компьютеров удваивается каждые 18 месяцев. Таким образом, за 10 лет она возрастет приблизительно в 100 раз и в 2004 г. составила 103 mips, а в 2014 — 104 - 105 mips.

В настоящее время в мире существует около 1010 - 1011 компьютеров. Прогноз основан на оценке роста населения, которое в 2014 г. составило около 1010 человек. Предполагается, что на каждого человека в 2014 году приходиться около 10 компьютеров — это вполне реально с учетом большого числа встроенных микропроцессоров (smart card, бытовое оборудование и т.д.). (Отметим, что в проекте RSA-129 использовались две факс-машины.) Не приходится сомневаться и в том, что практически все компьютеры будут связаны в единую сеть. Однако вопрос о доле компьютеров, доступных для решения задач факторизации, остается открытым.

Рассмотрим два сценария:

• Открытый проект — широко объявленная атака на известную криптосистему. Вполне очевидно, что при этом может быть задействовано не менее 0,1% мирового вычислительного ресурса в течение одного года. (Напомним о 3% вычислительных ресурсов Internet-проекта RSA-129.) Принимая во внимание фактор роста сети, суммарная производительность в 2004 г. составила 2 х 109 MY и 1011 - 1013 MY в 2014 г.

• Скрытая атака, предпринятая локальной группой участников, университетом или корпорацией. Организаторы атаки могли бы получить в свое распоряжение 105 компьютеров в 2004 г. и 1010 - 1011 в 2014-м. Таким образом, суммарная производительность составила в 2004 г. 108 MY , в 2014 г. 1010 - 1011.

Изменение доступных вычислительных ресуров: 

 

Год	Скрытая атака	Открытый проект
2004	108 MY	2 x 109 MY
2014	1010 – 1011 MY	1011 – 1013 MY

 

 

Эффективность факторизации по алгоритму ОЧР (в MY): 

 

Разрядность в битах	512	768	1024	1280	1536	2048
Производительность	3 х 104	2 х 108	3 х1011	1014	3 х 1016	3 х 1020

 

 

Известные алгоритмы факторизации можно разделить на два типа:

1.      алгоритмы, время работы которых зависит от разрядности простых делителей, и

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

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

Самым быстрым алгоритмом факторизации первого типа считается метод эллиптических кривых. Асимптотическая оценка времени работы этого алгоритма ехр(O((ln(р))1/2 • (lnln(p))1/2)). Основной практический недостаток — вычислительная трудоемкость базовых операций. Наибольшее число, факторизованное этим методом, имело 145 двоичных разрядов. Маловероятно, что в ближайшем будущем при помощи этого алгоритма будет выполнена факторизация 512-битного модуля RSA. Алгоритмы второго типа существенно быстрее. Наилучшим считается алгоритм ОЧР. Асимптотическая оценка времени работы ОЧР ехр(O((ln(n))1/3 • (ln ln (n))2/3)). Алгоритм позволяет факторизовать      512-битный модуль при производительности от 10 000 до 15 000 MY. Отметим, что алгоритмы факторизации второго типа применялись во всех успешных атаках на криптосистему RSA. Таким образом, логично предположить, что тенденция сохранится в будущем.

Алгоритм ОЧР удобен для практической реализации, максимальный выигрыш наблюдается при факторизации чисел порядка 115D и более. Прогноз производительности, необходимой для факторизации чисел различной разрядности по алгоритму ОЧР, построен исходя из прецедента факторизации числа 130D при производительности 500 MY.

Данные позволяют заключить, что 1280-битный RSA-модуль гарантирует адекватный уровень практической криптостойкости в течение ближайших 20 лет. К прогнозу, основанному на предположении о превосходстве алгоритма ОЧР, необходимо относиться осторожно — не исключена возможность появления более эффективных методов целочисленной факторизации.

Отметим, что факторизация 512-битного модуля реальна уже сегодня. Не нужно открывать новые алгоритмы факторизации, нет необходимости в увеличении числа компьютеров или в более производительных компьютерах — достаточно найти нужное количество участников и воспользоваться свободным временем их рабочих станций для факторизации. Например, лишь компьютеры компании Silicon Graphics могут факторизовать 512-битный модуль за полгода при условии, что будут свободны две трети рабочего времени.             

Для факторизации чисел Ферма (Fn =  + 1) разработан алгоритм специального числового решета (СЧР). Рекорд факторизации по алгоритму СЧР — число 162D при производительности 200 MY.

Прогноз производительности, необходимой для факторизации чисел различной разрядности по алгоритму СЧР:

 

 

 Таблица 2.

Разрядность в битах	768	1024	1280	1536	2048
Производительность	105	3 х 107	3 х 109	2 х 1011	4 х 1014

 

 

При сохранении тенденции (число F7 факторизовано в 1970 г., F8 в 1980 и F9 в 1990) логично предположить, что в 2000 г. будет факторизовано число  F10 = 21024 + 1.

Возможно ли появление универсальных методов целочисленной факторизации, столь же эффективных, как алгоритм СЧР для чисел Ферма? Специалисты в области вычислительной теории чисел полагают, что возможно. Прогресс в целочисленной факторизации имеет устойчивый характер. Считалось, например, что методы линейной алгебры, играющие ключевую роль в большинстве алгоритмов факторизации и плохо поддающиеся распараллеливанию, ограничат применение распределенных вычислений. Однако факт разработки новых алгоритмов опроверг сложившееся мнение.

Для факторизации числа 129D по сравнению с факторизацией числа 45D по методу непрерывных дробей в 1970 г. понадобилось бы в 6 х 1011 раз больше производительности и в 5 х 106 раз больше — при использовании быстрого алгоритма.

Таким образом, развитие алгоритмической базы сравнимо (по логарифмической шкале) с ростом производительности компьютеров. При условии сохранения отмеченной тенденции в 2004 г. скрытая атака позволит факторизовать 1024-битные числа (современные алгоритмы позволяют факторизовать 768-битные числа). В 2014 г. разрядность факторизуемых чисел возрастет до 1500 бит и более.

Основная причина стремительного роста разрядности надежного модуля заключается в субэкспоненциальной оценке времени работы современных алгоритмов факторизации. Для сравнения; трудоемкость силовой атаки на симметричную криптосистему, например DES, определяется объемом ключевого пространства (2n — в худшем случае и 2n-1 — в среднем, при n-разрядном ключе).

 

 

ГЛАВА 4 РАЗНОВИДНОСТИ RSA

4.1 Разбалансированная RSA

Тенденция к увеличению размера модуля криптосистемы RSA вполне обоснована — атака на основе факторизации представляет реальную угрозу. Тем более, когда речь идет о хранении долговременных секретов (например, долговременных долговых обязательств, закладных и т.д.). Однако с увеличением разрядности модуля сложность вычислений возрастает кубически. Таким образом, выбор разрядности модуля представляет собой компромисс между вычислительной эффективностью и криптостойкостью.

Как было отмечено в предыдущем параграфе, трудоемкость современных алгоритмов факторизации (например, ОЧР) не зависит от разрядности делителей модуля: для нахождения простого делителя из одной и из пятидесяти десятичных цифр требуется одинаковое время. Поскольку основные достижения в области факторизации получены в результате применения алгоритма ОЧР или аналогичных ему, можно предположить, что эта тенденция сохранится и впредь.

Шамир (A. Shamir) предложил новый подход к решению проблемы RSA-модуля. Криптосистема с модулем, построенным методом Шамира, получила название «разбалансированной RSA». В такой криптосистеме — разрядность модуля п = pq увеличена в десять раз (до 5000 бит), а разрядность делителя р в два раза (до 500 бит). Соответственно на делитель q приходится 4500 бит. Название криптосистемы отражает диспропорцию в разрядности делителей п. Такой выбор делителей, по мнению Шамира, учитывает тенденции развития методов целочисленной факторизации и обеспечит адекватную криптостойкость в течение ближайшего десятилетия.

Основная проблема заключается в том, что при таком модуле быстродействие реализации RSA — в 1000 раз ниже: теперь задержка на одну операцию модульного возведения в степень вместо одной секунды (при микропроцессорной реализации и 500-битном модуле) составит 16 минут — что неприемлемо.

При использовании RSA в процедуре установления ключевого синхронизма (метод цифрового конверта) шифруемые сообщения (сеансовые ключи), как правило, не превышают размера модуля р: даже при использовании режима трехкратного DES-шифрования (EDE= Encode Decode Encode) на трех независимых ключах размер сообщения не превышает          168 бит ( проект NISTпо разработке нового стандарта AES предусматривает применение ключей длиной 128, 192, 256 бит).Таким образом, можно предположить, что шифруемый блок открытого текста в числовом отображении находится в интервале [0, р-1]. При этом чрезмерно короткие блоки могут искусственно дополняться при помощи известной техники «набивки».

Широко распространенный способ повышения вычислительной эффективности RSA при шифровании с = m (mod n) заключается в выборе малого е. Однако при заданных делителях выбор е < 10 не обеспечивает приведения по модулю в процессе шифрования, так как длина сообщения т составляет десятую часть от длины модуля п. При e » 20 разрядность me приблизительно в два раза превышает разрядность модуля n, что обеспечивает приведение по модулю в процессе шифрования. Отметим, что при таком е и вычислении me(mod п) методом последовательного возведения в квадрат большинство промежуточных произведений не приводится по модулю и только последняя операция возведения в квадрат является модульной. Таким образом, при 20 < е < 100 быстродействие шифрования при 5000-битном модуле сравнимо с быстродействием дешифрования при 500-битном модуле (менее одной секунды).

Рассмотрим процедуру дешифрования m = (cd (mod п) при условии, что с, п и d — 5000-битные числа. Воспользовавшись Китайской теоремой об остатках, можно эффективно вычислитьm1 = cd(mod p) для 500-битного модуля р. предварительно приведя с по модулю р к d по модулю (p - 1). Однако вычисление m2 = сd(mod q) при 4500-битном модуле q требует в 93 = 729 раз больше операций.

Шамир выдвинул простое рассуждение, из которого следует, что выполнение этих сложных вычислений не является обязательным. Действительно, по определению m1= m (modр). При этом известно, что открытый текст m меньше р и, следовательно, m (mod p) = m. Это, в свою очередь, означает, что m1 = m и приведение m2 по модулю q приведет к тому же самому результату.

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

Рассмотрим последствия увеличения размера памяти с произвольным доступом (RAM) для различных приложений. Для персонального компьютера десятикратное увеличение памяти для хранения ключей не приводит к серьезным последствиям. (Если в памяти компьютера хранится 100 000 ключей по 5000 бит, то необходимый объем памяти для их хранения составит 60 Мбайт.) Однако для интеллектуальных карточек (Smart Card) это не так - их стоимость прямо пропорциональна объему памяти. Кроме того, многие разработчики интеллектуальных карточек уже реализовали специализированный RSA-процессор на базе 512-битного модуля. По этой причине можно ожидать, что их реакция на увеличение размера модуля будет негативной. В ряде практических приложений интеллектуальные карточки используются совместно с мощными персональными компьютерами. Таким образом, открывается возможность выбора технологической базы (персональный компьютер или интеллектуальная карточка) для реализации процедур шифрования/дешифрования. Например, персональный компьютер может генерировать и шифровать первичный сеансовый ключ. Затем шифротекст подается на вход последовательного интерфейса карточки и в темпе приема (по мере поступления бит шифротекста) приводится по модулю р; в ходе вычислений используются 512-битные регистры RSA-процессора. Конечный сеансовый ключ получается путем модульного возведения в степень, также реализуемого 512-битным RSA-процессором интеллектуальной карточки. Преимущество описанного метода заключается в возможности использования вычислительных ресурсов современных интеллектуальных карточек приpar-боте с модулем переменной длины без их замены.