id: Гость   вход   регистрация
текущее время 16:01 28/03/2024
создать
просмотр
редакции
ссылки

Это старая редакция страницы Библиотека / Статьи / Стойкость R S A 1024 за 12/09/2009 02:28.


К вопросу о безопасности 1024-битной версии RSA и 160-битной криптографии на эллиптически кривых


Оригинальная версия статьи 2.1, 1 сентября 2009 года, перевод с сокращениями.
© Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, Peter L. Montgomery — (EPFL IC LACAL, Station 14, CH-1015 Лозанна, Швейцария; Лаборатория Alcatel-Lucent Bell; Microsoft Research, One Microsoft Way, Рэдмонд WA 98052, США)
Перевод © 2009 unknown


Предварительные комментарии переводчика к статье


Принятый Агентством Национальной Безопасности (АНБ) набор криптографических алгоритмов в США называется "NSA Suite B" (шифр AES, хэш функции SHA и асимметричная криптография на эллиптических кривых), в отличие от набора секретных алгоритмов "NSA Suite A", не предназначенных для гражданского использования. На АНБ возложена ответственность по защите государственных коммуникаций и обеспечению инфобезопасности США в том числе и посредством криптографии, для этой цели оно обращается к гражданскому криптосообществу, которое предлагает алгоритмы из которых формируют криптостандарты в Национальном Институте Стандартов и Технологий (НИСТ), эти стандарты могут включаться в набор "NSA Suite B". Кроме того НИСТ выпускает собственные более подробные рекомендации.


Упоминаемые в статье 80-битный и 128-битный уровни безопасности со слов авторов точно не определены, но обычно в контексте статьи подразумевают соответствующее количество шагов в атаке взлома как симметричных так и асимметричных алгоритмов (при этом для симметричных шифров эти уровни безопасности по определению совпадают с длиной ключа самого алгоритма, для хэшей — с половиной длины значения выхода функции, для асимметричных алгоритмов — со скоростью проведения атаки на лежащую в их основе вычислительно трудную задачу и соотвественно всегда меньше длины асимметричного ключа, при этом такая атака всё равно называется атакой грубой силой, хотя и не является для асимметричных алгоритмов простым перебором).


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


Краткое содержание


Ожидаемая необходимость новых криптографических стандартов от НИСТ (Национального Института Стандартов и Технологий США) означает выведение из использования 1024-битного RSA и 160-битной криптографии на эллиптических кривых (ECC) в конце 2010 года. Данные описания комментируют уязвимости этих систем к попыткам атак со стороны открытого сообщества и имеют своей целью оценить риск их неизбежного использования после 2010 года пока не будет завершена миграция на новые стандарты. Мы пришли к заключению что для 1024-битного RSA риск невелик по крайней мере до 2014 года, а также 160-битная ECC над полем простого числа может быть безопасно использована значительно дольше — при текущем состоянии дел в криптоанализе мы будем удивлены, если усилия открытого сообщества поставят под угрозу 160-битную ECC над полем простого числа до 2020 года. Наша оценка основана на последних практических данных попыток широкомасштабной целочисленной факторизации и вычисления дискретного логарифма в эллиптических кривых.

1. Введение


В феврале 2005 года Агентство Национальной Безопасности (АНБ) убеждало в том, что "Продолжающийся быстрый рост информационных технологий в 21 веке диктует необходимость принятия гибкой и адаптируемой криптографической стратегии для защиты информации, относящейся к национальной безопасности", анонсированной в Криптографических протоколах Suite B. По схожим мотивам Национальный Институт Стандартов и Технологий США (НИСТ) предоставил руководство по использованию алгоритмов для адекватной защиты чувствительной информации и планов на будущее по возможным изменениям в использовании криптографии в части первой специальных публикаций 800-57. Эти инициативы затрагивают большое количество коммерческих поставщиков и предпринимателей по всему миру, а не только в США, которые в большей или меньшей степени вынуждены им следовать.


Грубо говоря, "Suite B" принимает 128-битный и более высокие уровни безопасности, прекращая поддержку широко распространённого сегодня 80-битного уровня. Это также предписывает точный набор технологий, которые должны быть использованы. Документ НИСТа "SP 800-57" допускает больше гибкости в технологиях и устанавливает 112-битный уровень безопасности в качестве низшего уровня безопасности с 2011 года. Любая миграция к другим технологиям, к новому уровню безопасности или к тому и другому будет логистическим кошмаром и будет иметь потенциал для существенных брешей в безопасности независимо от уровней криптографической безопасности. Тем не менее, миграция к уровню безопасности, превышающему 80 бит не только обязательна, это также без вопросов сама по себе хорошая идея. Эта миграция должна однако быть управляема с крайней осторожностью и слишком торопливого принятия новых стандартов следует избегать, даже для самого АНБ это потребует многих лет для исполнения. НИСТ отмечает в своих комментариях, что мы получили урок того, что это не так легко сделать. Таким образом хотя и "Suite B" и "SP 800-57" являются прекрасными инициативами, выполнение которых рекомендовано к 2010 году, важным вопросом является то, сколько времени потребуется компаниям и другим исполнителям стандарта перед тем как обоснованно согласиться на полное выполнение обоих стандартов в порядке максимально возможных ожиданий безопасности и экономии затрат. К последнему вопросу мы и обратимся в данной статье. Это не стоит подробно рассматривать как поддержку старого 80-битного уровня безопасности, но стоит отметить определённые реалистичные риски полной миграции к более высоким уровням безопасности до даты 2010 года.


Инициативы АНБ и НИСТ затрагивают всех трёх столпов современной криптографии: блочные шифры, криптографические хэш-функции и криптографию с открытым ключом. Для блочных шифров "Suite B" требует использования стандарта AES, который разрабатывался для обеспечения 128-битного или более высокого уровня безопасности. Если даже есть сомнения по поводу того в какой модели противник может достигнуть уровня безопасности, подразумеваемого AES, существует соглашение, что одинарный DES (классический стандарт шифрования данных) не может быть больше использован даже для приложений малого риска. "SP 800-57" также допускает ограниченное использование тройного DES с тройным ключом. В данном описании далее не затрагивается тема блочных шифров или миграции на AES. Также это не касается хэш-функций. Но хорошо бы напомнить читателю, что ситуация в отношении криптографических хэш-функций расстраивает. В первую очередь сомнение по поводу уровня безопасности, обеспечиваемого текущим стандартом со 160-битной хэш-функцией SHA-1, предусмотренной для обеспечения 80-битной безопасности. Были представлены убедительные аргументы, что уровень безопасности SHA-1 немного ниже: в данный момент нельзя сказать насколько это значимо. Если коллизии с подобранным префиксом, представленные для MD5, могут работать против SHA-1, атаки могут быть достижимы таким образом, что это окажет негативное воздействие на безопасность интернета в целом. SHA-256, как предусмотрено в "Suite B", может рассматриваться как улучшение в обычном использовании SHA-1. Однако, определённые сходства между SHA-1 и SHA-256 и непредсказуемый на данный момент исход конкурса НИСТ на новую хэщ-функцию, делает неясной ситуацию в отношении хэшей.


Здесь мы сконцентрируемся на третьем столпе, упомянутом выше — миграции от 80-битного уровня безопасности для криптографии с открытым ключом. АНБ ограничивает использование криптографии с открытым ключом в "Suite B" только криптографией на эллиптических кривых (ECC). Согласие будет вызовом для приложений, пока ещё не использующих ECC, поскольку выполнение ECC нетривиально по множеству причин — поскольку это включает математические структуры, которые значительно труднее к пониманию и выполнению, чем те, которые вовлечены в RSA, но также поскольку должны быть приняты различные системные решения более высокого уровня, последствия которых не всегда очевидны для того чтобы придти к согласию даже среди специалистов. Наконец, даже при полном понимании математики и решении, какого типа эллиптические кривые использовать, всё ещё остаётся вызовом определение наилучших вычислительных преимуществ на определённых платформах.


Если в "Suite B" принята 256-битная ECC, как асимметричная система наименьшего уровня стойкости, НИСТ "SP 800-57" допускает 224-битную ECC, и в значительно большей степени, продолжение использования RSA, но с 2048-битным модулем. Оценки уровня безопасности, которому соответствует 2048-битный RSA-модуль варьируются. Для подразумеваемого 112-битного уровня безопасности, 2048-битный RSA можно считать удовлетворительным, в зависимости на то, как смотреть на безопасность, обеспечиваемую 1024-битным RSA (см. ниже). Уровень безопасности любых других стандартизированных систем не является однако темой данной статьи — на самом деле мы даже не пытаемся в точности определить, что означает "уровень безопасности". Вместо этого мы рассматриваем короткий срок, но тем не менее перед многими исполнителями стандартов встанут важные вопросы, даже в то время, пока будут действовать текущие стандарты на 1024-битный RSA м 160-битную ECC, которые должны использоваться с должной ответственностью: должны ли бизнес-организации в самом деле принять новые стандартоы к 2010 году или для них допустим плавный переход? Для RSA этот вопрос, который включает важные практические опасения того, что цифровые сертификаты, основанные на 1024-битном RSA должны выйти из употребления, что рассмотрено во второй части, для ECC — в третьей. Для ECC мы ограничиваем себя эллиптическими кривыми над полями простых чисел, также поскольку это находится в фокусе рекоммендаций АНБ: повсюду в данной работе ECC относится к ECC над полями простых чисел.


В вопросе данного рода мы должны сказать кое-что о модели противника. В течении этого описания мы ограничиваем своё внимание работами, которые были или могут быть выполнены в открытом исследовательском сообществе. Активность такого рода стремиться сделать публично доступными потенциальные уязвимости, которые вызывают нежелательные помехи для пользователей уязвимых систем. Потенциальная уязвимость к усиленно финансируемым попыткам может иметь место и за закрытыми дверями, такими как в правительственных лабораториях, что воспринимается иначе. Как будет аргументировано в дальнейшем, такие системы тут же уже становятся уязвимыми к верно определённым массированым попыткам атак, но тем не менее их текущее использование обычно не рассматривается как "ненадёжное". Следовательно, когда мы говорим, что система может "быть использована надёжно", мы подразумеваем, что считается маловероятным, что академическое, открытое сообщество способно провести успешную атаку. Очевидно, что это не означает формального определения и оставляет нерассмотренными многие проблемы (такие как время и уровень финансирования). Тем не менее, вопреки неясностям, мы усиленно верим, что работы такого рода полезны для сообщества пользователей криптографии. Мы представляем актуальное состояние дел и комбинируя его с разработками прошлого предлагаем свой взгляд на то, что может и не может произойти в ближайшем будущем. Более важно то, что хотя читатель может выработать понимание усилий, затрачиваемых на взлом RSA или ECC для выбранных актуальных параметров и может составить собственные заключения.


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

2. Безопасность 1024-битного RSA


Со времени представления криптосистемы RSA эффективность атаки грубой силой значительно возросла, что серьёзно повлияло на выбор величины RSA модулей. Самый эффективный метод, который был опубликован, решето числового поля (NFS), уже имеет более чем 20-летний возраст. Его разработка, влияние и свойства, относящиеся к безопасности 1024-битных RSA-модулей рассмотрены в этом разделе. Со времени 1989 года в целочисленной факторизации не произошло ничего значительного, за исключением кажущегося бесконечным потока относительно небольших улучшений. Все эти улучшения, в частности когда они комбинированы, влияют на эффективность NFS, но никакое из них не представляет значительной новой идеи или прорыва: исследования способов факторизации расстраивают или успокаивают своим застоем. Примечательным исключением является факторизация на квантовом компьютере, также далёкая от практического выполнения и полиномиально-временное доказательство простоты.


Оригинальная версия NFS, которая сейчас называется как специальный метод решета числового поля (SNFS) была специально изобретена для полной факторизации девятого числа Ферма, F9 = 2(29) + 1 и успешно справилась с этим в 1990 году. SNFS критически полагается на характерную, специфическую форму чисел, которыми он может оперировать, такими как F9 и в частности не может быть использован для факторизации модулей RSA. Потребовалось немного больше лет пока SNFS был обобщён до несколько более медленного метода, известного сейчас как NFS, который может оперировать с модулями RSA. Первый публичный анонс NFS-факторизации 512-битного модуля RSA был в 1999 году.


Последний рекорд SNFS факторизации был на такого рода "специальном" числе 21039 – 1, найденном в 2007 году. Попытки факторизовать с помощью NFS 768-битный RSA модуль всё ещё в процессе и ожидаются к завершению в 2010 году. Возможно появление нового NFS рекорда, который побьёт текущий рекорд факторизации 663-бит, RSA модуль из 200 цифр RSA-200 на более чем 100 битов. Ожидается, что 768-битная факторизация, когда будет завершена, потребует примерно от 10 до 15 раз больше ресурсов, чем требовалось для 21039 – 1. Эта оценка основана на текущих практических находках, а не на теоретических оценках или догадках: и то и другое недостоверно при переходе от SNFS к NFS. Экстраполяция 768-битного NFS до 1024-битного NFS (как требуется для 1024-битного RSA-модуля) может быть сделана с использованием эвристической асимптотической оценки времени выполнения NFS. Используя это в стиле o(1)-приближений, можно найти, что 1024-битные RSA-модули примерно в 1200 раз сложнее для взлома, чем 768-битные. Мы можем округлить это в меньшую сторону к одной тысяче, основываясь на аргументах, что есть практическая непрерывность во времени выполнения для "маленьких" номеров, которая не имеет адекватного отражения в асимптотическом времени исполнения если опустить o(1). Числа из 768-битов относительно близки к нижнему концу диапазона, где оптимальны числовые поля расширений степени 6, несмотря на то, что 1024-битные номера достаточно близки к середине того же самого диапазона. Из этого следует, что o(1)-приближение в качестве оценки для 768-бит плохо соотносится с действительным временем выполнения, в то время как для 1024-битов это ожидается значительно более близким. Таким образом можно ожидать, что 1200 — это слишком пессимистично и 1000 значительно ближе к реальности. Более того, комбинируя числа, можно оценить, что 1024-битный модуль RSA потребует ресурсов по крайней мере от 10 до 15 раз больше, чем уже выполненная попытка SNFS для 21039 – 1.


Можно спорить, что есть некая натяжка в оценочной экстраполяции факторизации NFS от 768 до 1024 бит. Но это поддерживается похожими вычислениями и сравнительно большей экстраполяцией от 512 до 768 бит: "o(1)-приближение" в экстраполяции теоретического времени выполнения подсказывает, что 768-битный модуль RSA примерно в шесть тысяч раз сложнее взломать, чем 512-битный, несмотря на то что эмпирические свидетельства, основанные на лучших попытках с использованием текущего программного и аппаратного обеспечения, дают сведения о средней цифре между 4 и 8 тысячами.


Далее мы оценим ресурсы, необходимые для работы с 1024-битными RSA-модулями, подразумевая грубую фамильярность в отношении главных шагов (S)NFS факторизации. Это следует за дискуссией о том, что безопасность 1024-битных модулей RSA лежит в близком, а не очень далёком будущем.


Полиномиальный выбор. Результат этого шага (необходимого только для NFS, но не для SNFS) значительно влияет на время, затрачиваемое на последние шаги, но объём вычислений, который здесь затрачивается мал по отношению к остальным: примерно от 3% до 5% суммарных вычислений. Он полностью распараллеливается. Здесь всё ещё есть место для улучшения текущих методов.


Просеивание. Просеивание позволяет полное и фактически свободное от необходимости коммуникаций распараллеливание и может быть запущено на любом количестве мест на любом числе независимых процессоров. Оно является и всегда являлось шагом, требующим массу вычислений. Для 21039 – 1 это потребует около двух тысяч лет вычислений на одном ядре 3-ГГц Pentium D, для 768-битного RSA модуля мы должны принять, что потребуется в десять раз больше усилий. Для 1024-битного RSA-модуля время просеивания экстраполируется до числа от двух до четырёх миллионов лет на ядро процессора.
Для 768-битного RSA модуля хорошо работают 2 гигабайта RAM на ядро, половина от этого значения оперативной памяти также ещё может работать, но значительно менее эффективно. Для 1024 бит, 2 гигабайта RAM на ядро подходят близко к этому пределу, но должны работать 32 или 64 гигабайта памяти на многоядерный или многопоточный процессор (или даже на материнскую плату). Эти оценки сделаны на основании актуальных скоростей доступа процессоров и памяти и основаны на факте, что требования памяти растут приближённо в зависимости от корня квадратного от времени просеивания.


Фильтрование. Преобразование просеянных данных в матрицу один из наименее вызывающих шагов факторизации и не требует здесь обсуждения. Для 1024-битных модулей RSA это потребует несколько сотен терабайтов дискового пространства, что является относительно лёгким в управлении в сравнении с предыдущим и последующим шагом.


Матрица. Матрица требует времени и памяти, растущих также быстро, как и для просеивания. Если бы даже все попытки факторизации в отношении времени матрицы были умеренно сравнимы со временем просеивания, это всегда бы было более обременительным из-за сравнительно малой степени, в которой этот шаг допускает распараллеливание. Первый раз этот шаг был распараллелен между множеством мест при факторизации 21039 – 1 на двух множествах кластеров, одном в Японии и одном в Швейцарии. В целом это заняло 35 лет на ядро 3 ГГц Pentium D. Для 1024-битного RSA-модуля хватит от четверти миллиона до миллиона лет на ядро. Для каждого компактно соединённого кластера, участвующего в шаге работы с матрицей, комбинированный объём памяти 10 терабайт будет адекватным значением.


Финальное извлечение корня. Время исполнения этого шага всегда незначительно по сравнению с другими шагами. Нет оснований чтобы это было иначе для 1024-битного модуля.


Мы подчёркиваем, что вышеприведённые цифры основаны не только на экстраполяции данных, но и на анализе экстраполяции данных текущих попыток факторизации 768-битного модуля RSA, для которых было выполнено просеивание. Эти цифры таким образом отражают наиболее аккуратные оценки, опубликованные пока к "реалистичным" попыткам факторизации 1024-битного RSA модуля.


Мы полагаем, что это имеет значение для безопасности 1024-битного RSA — сейчас для следующих пяти лет, и для следующего десятилетия. На этот момент времени атака грубой силой против 1024-битного RSA потребует около двух лет на нескольких миллионах вычислительных ядер со многими десятками гигабайтов памяти на процессор или материнскую плату. Хотя это и существенно, это в принципе уже достижимо: процессоры с достаточным количеством памяти для просеивания существуют и есть кластеры, которые должны иметь комбинированную память, достаточную для матрицы (хотя большинство из них не имеет достаточного количества узлов). Суммарный требуемый бюджет высок, но меньше чем тратится на другие начные устремления.


Тем не менее, для "открытого сообщества" попытки факторизации 1024-битного RSA всё ещё недостижимы. Но как долго это будет продолжаться? Как обычно, как только мы пытаемся предсказать криптоаналитическое будущее, мы изучаем прошлые тенденции и используем их в качестве основы для наших предсказаний. Так, поскольку прорывов в факторизации не наблюдалось в течении нескольких десятилетий и полиномиальное время факторизации на действующих квантовых компьютерах всё ещё отдаляется на множество десятилетий вперёд, обе эти возможности больше не рассматриваются.


Далее, учитывая аппаратное обеспечение специального назначения, просеивание 1024-битных модулей RSA может быть сделано за год за примерно 10000000 долларов США, плюс стоимость одноразовой разработки примерно 20000000 долларов США и сравнимое время и стоимость для матрицы. Хотя фигурирующие здесь цены выглядят обоснованными, возможность масштабной интеграции может быть под вопросом. Но по нашему мнению, скептицизм вокруг этого имеет право на существование. Цифры стоимости не должны интерпретироваться как верхний предел, т.е. "Будьте осторожны, 1024-битный RSA может быть взломан за два года за примерно двадцать миллионов баксов (подразумевая свободную разработку)", но и как нижние пределы, т.е. "Нет причин для особого беспокойства: даже при самы благоприятных обстоятельствах факторизация 1024-битного RSA-модуля всё ещё требует чрезмерных ресурсов". эти оценки таким образом не должны рассматриваться как угрожающие, но как внушающие уверенность поскольку требуемые ресурсы вне пределов досягаемости попыток открытого сообщества, как здесь рассматривалось.


Помимо вышеизложенных моментов, даже если кто-то управляет постройкой аппаратного обеспечения специального назначения, за это время обычное железо превзойдёт его и по скорости и по стоимости — по крайней мере это согласуется со случаями из прошлого. Питер Хафсти предсказывает, что так будет без изменений по крайней мере до 2030 года, с момента которого аппаратное обеспечение специального назначения может быть единственным способом остаться на кривой закона Мура. Это в будущем, которое слишком отдалено от наших целей. Согласно другим однако этот сдвиг к аппартному обеспечению специального назначения не материализуется никогда. Кроме того, если принять во внимание Paolo Ienne данные подсказывают, что разработка железа и стоимость выпуска часто находятся в криптоаналитическом контексте в тенденции быть оптимистичными (т.е. по наименьшему значению).


Возвращаясь обратно к реальности, следующие события имеют отношения к нашему вопросу когда 1024-битный RSA-модуль может пасть:


1988: Первая факторизация сложного целого числа из ста цифр.
1999: Первая факторизация 512-битного модуля RSA.
2010: Ожидаемая первая факторизация 768-битного модуля RSA.
20??: Ожидаемая первая факторизация 1024-битного модуля RSA.


Основываясь на сравнении времени выполнения NFS для трёх последовательных "барьеров сложности" между приведенными четырьмя факторизациями, мы получаем множители около 2000, 6000 и 1000. Последние два числа уже были приведены выше и 6000 был показан как соответствующий эмпирическим данным. Следует отметить, что факторизация числа из ста цифр не была получена методом NFS, а с использованием асимптотически более слабого предшественника "квадратичного решета". Таким образом, в реальности наибольшим препятствием, чем множитель 2000, было преодоление периода 1988-1999 годов, в основном из-за изобретения и разработки NFS, начиная с 1989 года. В любом случае, первые три вышеприведённые выкладки подсказывают, что тысечекратные продвижения в сложности факторизации традиционно преодолевались за десятилетие. Эти размышления могут привести к наивным выводам, что ожидаемая факторизация открытым сообществом 1024-битного RSA произойдёт в 2020 году. Но есть ли причины ожидать, что разработки, имевшие место между 1988 годом и по сегодняшний день будут продолжаться и в последующие десятилетия?


Чтобы разъяснить множитель в более тысячу за десятилетие, в противоположность простому наблюдению удвоения в прошлом — множитель в виде каждой тысячи на каждые десять лет довольно последовательно согласуется с вкладом закона Мура. Другой фактор — множество медленных улучшений в шаге полиномиального выбора и в программах просеивания и работы с матрицей, вероятно совмещёнными с возросшим упорством и терпеливостью исследователей. Тип вычислительной мощности, требуемой для широкомасштабных усилий в NFS будет следовать закону Мура по крайней мере в течении следующих двух или трёх десятилетий. Таким образом, нет причин ожидать что в последующее десятилетие ожидается иной множитель кроме тысячи в сложности факторизации.


Эти разъяснения наблюдаемого прогресса поддерживают уверенность в наивном предсказании, что ожидается первый успех в факторизации 1024-битного модуля RSA открытым сообществом в течении около десяти лет — подразумевая, что добровольцы смогут подготовить запуск серьёзнного конкурса. В следующем параграфе и в заключении этой секции, мы предположим, можем ли мы ожидать факторизации 1024-битного модуля RSA значительно раньше.


Предположим, что попытки факторизации 768-битного модуля RSA завершаться в 2010 году. Множитель в размере сотни, предоставляемый каждым десятилетием законом Мура, подразумевает десятикратный множитель на каждые пять лет. Таким образом, чтобы факторизовать 1024-битный RSA модуль в 2015 (= 2010 +5) комбинированное алгоритмическое улучшение аккумулируется во множитель порядка сотни в течении следующих пяти лет. Такой прогресс будет беспрецедендентным, даже если не ожидается никаких серьёзных прорывов. При заданных вероятностях попытки открытого сообщества факторизовать 1024-битный RSA не закончаться в 2015 году. Это заключение состоит из наблюдений за тем, что текущие попытки 768-битной факторизации уже затянули все ресурсы энтузиастов факторизации из открытого сообщества: фактически невообразимо, чтобы тысячекратно большие усилия были доступны в течении всего лишь пяти лет. Очевидно не очень крепкий аргумент, скорее более интуитивный, основанный на мнении тех, кто десятилетиями был погружён в опыт исследований по целочисленной факторизации.

3 Безопасность 160-бит ECC


Прим. переводчика: перевод данной главы значительно сокращён, так как ECC-алгоритмы пока всё ещё мало используются


Наиболее эффективный метод атаки грубой силой для вычисления дискретного логарифма в группе эллиптической кривой простого числа — это метод ро-Полларда. Мы подразумеваем, что порядок группы и порядок лежащего в её основе поля простого числа имеют тот же размер в битах. Поллард-ро существует во множестве вариаций, некоторые из которых имеют большое, некоторые незначительное влияние. Более важно, что метод позволяет полное распараллеливание на любое число слабо связанных вычислительных элементов, имеющи лишь незначительную связь с центральным сервером. Определив порядок группы как q, каждый процесс метода ро-Полларда потребует памяти на незначительное постоянное число (log2 q)-бит. В связи с этим, и это огромный контраст на основанных на NFS атаках грубой силы против RSA — фактически любой вычислительный элемент может, тем или иным способом, принять участие в атаке на ECC. Кроме того, если вычислительный элемент поддерживает мульти- или гипертрединг или любой другой модный метод распараллеливания или конвейеризации, то он в принципе может получить преимущество в запуске такого большого количество процессов ро-Полларда, насколько позволяет полностью занятое устройство.


Такая чрезвычайно "лёгкая" паралеллизация меняет соответствующую модель угрозы в сравнении с нашими оценками ресурсов, необходимы для атаки на 1024-битный RSA.


Примечание переводчика. Дальнейшая часть статьи, рассматривающая методику взлома ECC не рассматривается, так как она в значительной мере изложена в ранее переведённой статье от авторов этой группы в новостях о кластере на игровых приставках PS3. Авторы рассматривают потенциал и особенности работы оборудования для взлома: десктопы, приставки PS3, графические карты, платы FPGA и ASIC.


Из вышеприведённы фактов мы можем заключить, что говоря с вычислительной точки зрения взлом 160-битного ECC по крайней мере на три порядка труднее, чем RSA и мы всё ещё смотрим на барьер сложности, определяемый множителем одной тысячи к 2020 году, т.е. к году, когда взлом RSA может быть доступен открытому сообществу.


С другой стороны, запуск множества процессов ро-Полларда намного менее обременительно, чем запуск NFS просеивания и шагов работы с матрицей.

4 Заключение


Переход от 80-битного уровня безопасности к одному из более высоких уровней безопасности — это хорошая идея. При этом нет причин для беспокойства в использовании 1024-битного RSA до 2014 года. Например, нет оснований полагать, что сертификаты, основанные на 1024-битном RSA должны быть отозваны ранее 2014 года, когда они сами истекут по сроку давности. Аналогично, нет никаких причин беспокоиться по поводу продолжения использования 160-бит ECC над полями простых чисел в течении следующего десятилетия.


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


Источник: Cryptology ePrint Archive