id: Гость   вход   регистрация
текущее время 15:30 28/03/2024
Владелец: unknown редакция от 14/07/2009 13:06 (автор: unknown) Печать
Категории: криптография, криптоанализ, алгоритмы, шифрование с открытым ключом, атаки, полный перебор
https://www.pgpru.com/Новости/2009/КластерИзPlaystation-3Взламывает112-битныеЭллиптическиеКривые
создать
просмотр
редакции
ссылки

14.07 // Кластер из Playstation-3 взламывает 112-битные эллиптические кривые


Лаборатория криптологических алгоритмов Федеральной политехнической школы Лозанны (Швейцария) представила новый рекорд в решении проблемы дискретного логарифма на эллиптических кривых (ECDLP) путём нахождения его решения в 112-битном конечном поле. Предыдущий рекорд был выполнен для 109-битного простого поля и датировался октябрём 2002 года. Новые вычисления были произведены с использованием кластера из игровых консолей Playstation 3.

Что было сделано


112-битное простое число задано в виде p = (2128 – 3) / (11 * 6949 ), пусть E – эллиптическая кривая над конечным полем Fp из p элементов, заданных уравнением Вейерштрасса y2 = x3 + ax + b, где значения


a = 4451685225093714772084598273548424
b = 2061118396808653202902996166388514.


Точка P в группе точек E(Fp) из E над Fp с координатами (x,y):
(188281465057972534892223778713752,3419875491033170827167861896082688) имеет порядок простого числа
4451685225093714776491891542548933.


Данная эллиптическая кривая стандартизирована в fileстандарте эффективной криптографии (SEC), SEC2: Рекомендованные параметры входных значений области определения эллиптических кривых в качестве кривой secp112r1 и в спецификации беспроводной связи fileWireless Transport Layer Security Specification в качестве кривой номер 6.


Дискретный логарифм был решён в отношении P для точки


Q = (1415926535897932384626433832795028, 3846759606494706724286139623885544)


в E(Fp) и было найдено что Q = 312521636014772477161767351856699 * P. Отмечается, что координата x из Q была выбрана как [(pi-3)*1034].

Как это было достигнуто


Вычисления начались 13 января 2009 года и закончились 8 июля 2009. Они запускались и прекращались, периодически прерываясь другими криптоаналитическими проектами, такими как этот или этот или приглашением поиграть на консолях в ходе демонстрационных мероприятий. Кластер состоял из более чем двухсот игровых консолей PlayStation 3 (PS3). Если бы вычисления проводились непрерывно на последней версии кода, это вычисление заняло бы три с половиной месяца. В общем было выполнено 8.5 * 1016 сложений в группе точек на эллиптической кривой, что можно приблизительно перевести в 1018 сложений и умножений по модулю 112-битных целых чисел. На PS3 это эквивалентно затратам на поиск примерно четырнадцати 56-битовых ключей DES.


Насколько можно судить, данное вычисление является новым рекордом для ECDLP над простыми полями. Это побило предыдущий рекорд по кривой над 109-битным простым полем, который отмечен в 2002 году и потребовал 549 дней вычислений свыше 10000 участников из более чем 250 комманд, потративших время, эквивалентное полному году вычислений на 4000-5000 ПК (см. здесь и здесь )

Некоторые детали


Был использован простой распараллеливаемый метод ро-Полларда со свойством 24-битного различителя. Были собраны свыше четверти миллиарда отмеченых точек перед тем, как были найдены коллизии. Это довольно близко к тому, что ожидалось на основании парадокса дней рождения с обыкновенной вероятностью успеха 50%. Отмеченные точки были сохранены в виде формата несжатого простого текста для облегчения нахождения коллизий с помощью простых unix-комманд. Под эти цели потребовалось 0.6 терабайт дискового пространства.


Полные детали вычислений будут описаны в последующей публикации. Частичный интерес представляет новый метод 128-битного "грубого сокращения", который комбинирует избыточное представление классов вычета по модулю 112-битного простого числа p с быстрым 128-битным усечением. Это может в итоге привести к некоректному результату, но это может случится с такой низкой вероятностью, что такого ни разу не произошло в ходе вычислений. Если бы ошибка произошла, это привело бы к появлению некорректной отмеченой точки, которая была бы затем выявлена. Грубое сокращение позволило создать branch-free код, который следовательно оказался очень эффективным на PS3 4-way SIMD SPU. Эта техника также хорошо применима к другим специально представленным простым числам, таким как 2255-19 как было предложено в связи с этим профессором Дэниэлом Бернштейном.
Не использовалось т.н. negation map, поскольку это требует ветвлений и как следствие такой код был бы медленнее в окружении SIMD.


На каждом SPU четыре потока обрабатывались в SIMD-режиме, два из которых состояли из четырёх кортежей, которые обрабатывались конвейером, чтобы избежать всех задержек, связанных с процессором и 50 из этих пар по четыре кортежа запускались одновременно, чтобы получить преимущество в одновременности обратных преобразований Монтгомери. С шестью SPU на SP3, одна PS3 таким образом обрабатывала 2400 потоков параллельно, что в масштабах всего кластера давало более чем четверти миллионов паралелльных выполнений потоков.

Почему это важно


Вычисления такого рода могут повысить нашу уверенность в стойкости криптографии на эллиптических кривых (ECC). Для лучшего понимания насколько сложно может быть решение предположительно трудных математических проблем, лежащих в основе ECC, мы пытаемся решить ECDLP для параметров, которые сравнительно малы, по сравнению с теми, которые используются в ECC. Полученное в результате время выполнения комбинируется с известными методами экстраполяции, дающими значения оценок сложности, основанных на том какие "безопасные" параметры могут быть выбраны для оценок обезопасности исполнения систем ECC.


Вскоре будет отменён стандарт ECC, допускающий использование 160-битовых полей простых чисел. Решение ECDLP в таких полях в целом, как считается, требует в 16 миллионов раз больше времени, чем в 112-битовых полях. Время выполнения, которое наблюдалось в 112-битном случае, даже для 160-битного стандарта ECC, который предполагается к завершению действия в конце 2010 года, подразумевает, что ни для каких обычных пользователей это не должно служить предметом особенного беспокойства по поводу безопасности 160-битного ECC в течении следующего десятилетия.

Криптоаналитический потенциал кластера PS3


В предыдущих работах было показано, что тот же самый PS3 кластер может быть удачно использован для совершенно разных криптоаналитических задач, таких как нахождение коллизий в криптографических хэш-функциях. Это уже обширно освещалось в интернете и криптографической литературе. См. http://www.win.tue.nl/hashclash/ и другие ссылки для более детальной информации. Другая работа, включающая криптоанализ симметричных алгоритмов (таких как поиск симметричных ключей) находится в стадии подготовки.


Данное выполнение ECDLP значительно отличается и показывает, что кластер PS3 также хорошо годится для задач в области асимметричной криптографии. Это обычно включает модулярную арифметику, которая может, например, быть использована к ECDLP (как в этом случае) и к методу эллиптических кривых (ECM) для факторизации целых чисел.


Авторы работы выражают благодарность за помощь швейцарского национального научного фонда и EPFL DIT.

Авторы работы


Joppe W. Bos(1) и Marcelo E. Kaihara(1)
с участием Thorsten Kleinjung(1), Arjen K. Lenstra(1,2) и Peter L. Montgomery(3)


(1) EPFL IC LACAL, CH-1015 Lausanne, Switzerland
(2) Alcatel-Lucent Bell Laboratories, Murray Hill, NJ, USA
(3) Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA


Источник: EPFL Laboratory for cryptologic algorithms