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

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

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

112-битное простое число задано в виде p = (2¹²⁸ – 3) / (11 * 6949 ), пусть E – эллиптическая кривая над конечным полем F_p из p элементов, заданных уравнением Вейерштрасса y² = x³ + ax + b, где значения

a = 4451685225093714772084598273548424
b = 2061118396808653202902996166388514.

Точка P в группе точек E(F_p) из E над F_p с координатами (x, y):

(188281465057972534892223778713752,3419875491033170827167861896082688)

имеет простой модуль 4451685225093714776491891542548933.

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

Дискретный логарифм был решён в отношении P для точки Q = (1415926535897932384626433832795028, 3846759606494706724286139623885544) в E(F_p) и было найдено что Q = 312521636014772477161767351856699 * P. Отмечается, что координата x из Q была выбрана как [(pi-3)*10³⁴].

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

Вычисления начались 13 января 2009 года и закончились 8 июля 2009. Кластер состоял из более чем двухсот игровых консолей PlayStation 3 (PS3). Если бы вычисления проводились непрерывно на последней версии кода, это вычисление заняло бы три с половиной месяца. В общем было выполнено 8.5 * 10¹⁶ сложений в группе точек на эллиптической кривой, что можно приблизительно перевести в 10¹⁸ сложений и умножений по модулю 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. Эта техника также хорошо применима к другим специально представленным простым числам, таким как 2²⁵⁵-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.

Источники: http://lacal.epfl.ch/page81774.html, http://www.pgpru.com