Обзор методов вскрытия криптосистемы RSA

В целях развития математических методов факторизации корпорация RSA Data Security, Inc. объявила открытый конкурс на факторизацию RSA-модулей и учредила специальную денежную премию. В 1996 г. число RSA-130 (130D) было факторизовано при помощи алго­ритма обобщенного числового решета (ОЧР). За счет применения алгоритма ОЧР эффек­тивность факторизации RSA-130 возросла на порядок по сравнению с факторизацией числа RSA-129. Проект RSA-130 был коллективным.

К моменту факторизации RSA-130 четыре из объявленных ранее модулей были факторизованы при помощи алгоритма КР . Таким образом, возможность успешной атаки на криптосистемуRSA с 512-битным моду­лем (» 160D) подтверждается результатами:

В настоящее время рекомендуемая минимальная длина RSA-модуля — 768 бит (w 230D). Исходя из оценки трудо­емкости проекта RSA-130, производительность компьютера для эффективной факторизации числа 230D должна быть не меньше 108 MY.

В феврале 1999 г. методом ОЧР был факторизован модуль RSA-140. Данный проект, также как и RSA-130.

Суммарная производительность проекта RSA-140 достигла 2000MY, а объем оператив­ной памяти (на одной рабочей станции) при реализации ключевого этапа алгоритма ОЧР составил 800 Мбайт.

Данные о трудоемкости проекта RSA-140 позволяют построить прогноз относительно ко­личества ресурсов, необходимых для факторизации модулей с разрядностью 512, 768, 1024 бит:

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

Отметим, что для эффективной факторизации RSA-129 по алгоритму ОЧР потребуется 1000 MY вместо 5000 MY при факторизации по алгоритму КР.

Существенный скачок в производительности компьютеров в период между 1984 и 1994 го­дами обусловлен интенсивным развитием компьютерных сетей и, как следствие, практиче­ской реализацией метода распределенных вычислений. Идея использования свободного вре­мени рабочих станций сети для факторизации принадлежит Силверману        (В. Silverman). (К сожалению, более ранняя попытка Шреппеля (R. Schroeppel) использовать сетевые ресурсы для факторизации восьмого числа Ферма F8 = 2256 + 1 не привлекла внимания специали­стов.) Дальнейшее развитие идея распределенных вычислений получила в исследованиях Ленстры (A. Lenstra) и Мэнэсса (М. Manasse). В проекте RSA-129 было задействовано около 1600 рабочих станций в течение восьми месяцев. В отличие от традиционного подхода, когда для эффективной силовой атаки необходимо построить специальный компьютер, атака на основе идеи распределенных вычислений не требует значительных инвестиций и технических ресурсов.

Другой прогноз относительно будущего целочисленной факторизации предлагает Ривест (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.

В настоящее время в мире существует около 108 компьютеров, в 2004 году их будет не менее 2 х 109, в 2014 г — 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.

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

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

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

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.

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