Записи дискретного логарифма - Discrete logarithm records

Записи дискретного логарифма являются лучшими результатами, достигнутыми на сегодняшний день в решении дискретный логарифм проблема, которая является проблемой поиска решений Икс к уравнению граммИкс = час данные элементы грамм и час конечного циклическая группа  грамм. Сложность этой проблемы - основа безопасности нескольких криптографический системы, в том числе Диффи – Хеллмана ключевое соглашение, Шифрование Эль-Гамаля, то Схема подписи Эль-Гамаля, то Алгоритм цифровой подписи, а криптография на основе эллиптических кривых аналоги этих. Общие варианты для грамм используемые в этих алгоритмах включают мультипликативную группу целых чисел по модулюп, мультипликативная группа конечное поле, а группа точек на эллиптическая кривая через конечное поле.

Целые числа по модулю п

  • 2 декабря 2019 года Фабрис Будо, Пьер Годри, Аврора Гильевич, Надя Хенингер, Эммануэль Томе и Пауль Циммерманн объявила о вычислении дискретного логарифма по модулю 240-значного (795 бит) простого RSA-240 + 49204 (первый безопасный прайм выше RSA-240). Это вычисление было выполнено одновременно с факторизацией RSA-240 с использованием алгоритма сита числового поля и программного обеспечения CADO-NFS с открытым исходным кодом. Для вычисления дискретного логарифма потребовалось примерно 3100 ядерно-лет при использовании процессоров Intel Xeon Gold 6130 в качестве эталона (2,1 ГГц). Исследователи подсчитали, что улучшения в алгоритмах и программном обеспечении сделали эти вычисления в три раза быстрее, чем можно было бы ожидать от предыдущих записей после учета улучшений в оборудовании. [1][2]

Предыдущие записи для целых чисел по модулю п включают:

  • 16 июня 2016 года Торстен Кляйнджунг, Клаус Дием, Арьен К. Ленстра, Кристина Приплата и Колин Штальке объявили о вычислении дискретного логарифма по модулю 232-значного (768-разрядного) безопасный прайм, используя решето числового поля. Вычисления были начаты в феврале 2015 года и заняли примерно 6600 ядерно-лет в масштабировании до Intel Xeon E5-2660 с частотой 2,2 ГГц.[3]
  • 18 июня 2005 г. Антуан Жу и Рейнальд Лерсье объявили о вычислении дискретного логарифма по модулю 130-значного (431-битного) сильный прайм за три недели при использовании 16-процессорного HP 1,15 ГГц AlphaServer GS1280 компьютер и числовое поле сито алгоритм.[4]
  • 5 февраля 2007 года это было заменено объявлением Торстена Кляйнджунга о вычислении дискретного логарифма по модулю 160-значного (530-разрядного) безопасный прайм, снова используя решето числового поля. Большая часть вычислений была выполнена в режиме простоя на различных ПК и в кластере параллельных вычислений.[5]
  • 11 июня 2014 года Сирил Бувье, Пьеррик Годри, Лоран Имбер, Хамза Джельели и Эммануэль Томе объявили о вычислении дискретного логарифма по модулю 180-значного (596-битного) безопасного простого числа с использованием алгоритма сита числового поля.[6]

Также следует отметить, что в июле 2016 года Джошуа Фрид, Пьеррик Годри, Надя Хенингер, Эммануэль Том опубликовали свое вычисление дискретного логарифма на 1024-битном простом числе.[7] Они сгенерировали простое число, восприимчивое к решето специального числового поля, используя специальный алгоритм для сравнительно небольшой подгруппы (160 бит). Хотя это небольшая подгруппа, это был стандартизированный размер подгруппы, который использовался с 1024-битным алгоритмом цифровой подписи (DSA).

Конечные поля

Текущий рекорд (по состоянию на июль 2019 г.) в конечном поле характеристики 2 было объявлено Робертом Грейнджером, Торстеном Кляйнджунгом, Арьеном Ленстра, Бенджамином Весоловски и Йенсом Цумбрегелем 10 июля 2019 года.[8] Эта команда смогла вычислить дискретные логарифмы в GF (230750) с использованием 25 481 219 часов ядра в кластерах на базе архитектуры Intel Xeon. Это вычисление было первым крупномасштабным примером, использующим этап исключения квазиполиномиального алгоритма.[9]

Предыдущие рекорды в конечном поле характеристики 2 были объявлены:

  • Роберт Грейнджер, Торстен Кляйнджунг и Йенс Цумбрегель, 31 января 2014 г. Эта команда смогла вычислить дискретные логарифмы в GF (29234) с использованием около 400000 часов работы ядра. Новые возможности этого вычисления включают модифицированный метод получения логарифмов элементов второй степени и систематически оптимизированную стратегию спуска.[10]
  • Антуан Жу, 21 мая 2013 года. Его команда смогла вычислить дискретные логарифмы в полевых условиях с 26168 = (2257)24 элементы, использующие менее 550 процессорных часов. Это вычисление было выполнено с использованием того же алгоритма расчета индекса, что и в недавнем вычислении в поле с 24080 элементы.[11]
  • Роберт Грейнджер, Фарук Гелоглу, Гэри Макгуайр и Йенс Замбрегель, 11 апреля 2013 г. Новое вычисление касалось поля с 26120 элементов и занял 749,5 сердечных часов.
  • Антуан Жу, 22 марта 2013 г. Используется тот же алгоритм. [12] для малых характеристических полей, как в предыдущем вычислении в поле с 21778 элементы. Новое вычисление касалось поля с 24080 элементы, представленные как расширение поля со степенью 255 с 216 элементы. Вычисление заняло менее 14100 часов работы ядра.[13]
  • Роберт Грейнджер, Фарук Гелоглу, Гэри Макгуайр и Йенс Зумбрегель, 19 февраля 2013 г. Они использовали новый вариант базового поля среднего размера. сито функционального поля, для двоичных полей, чтобы вычислить дискретный логарифм в поле 21971 элементы. Чтобы использовать базовое поле среднего размера, они представили поле как расширение поля 227 элементы. Вычисление заняло 3132 ядерных часа в кластере SGI Altix ICE 8200EX с использованием шестиядерных процессоров Intel (Westmere) Xeon E5650.[14]
  • Antoine Joux, 11 февраля 2013 г. Он использовал новый алгоритм для небольших характеристических полей. Вычисление касалось поля 21778 элементов, представленных как расширение поля со степенью 127 с 214 элементы. Расчет занял менее 220 часов работы ядра.[15]

Текущий рекорд (по состоянию на 2014 г.) в конечном поле характеристики 2 простой степени было объявлено Торстеном Кляйнджунгом 17 октября 2014 г. Расчет производился в поле 21279 элементов и следовали по пути, намеченному для в[16] с двумя основными исключениями: вычисление линейной алгебры и фаза спуска. Общее время работы составило менее четырех основных лет.[17] Предыдущий рекорд в конечном поле характеристики 2 простой степени был объявлен группой КАРАМЕЛ 6 апреля 2013 г. Они использовали сито функционального поля для вычисления дискретного логарифма в поле 2809 элементы.[18]

Текущий рекорд (по состоянию на июль 2016 г.) для поля характеристики 3 было объявлено Гора Адж, Исааком Каналес-Мартинесом, Нарели Крус-Кортесом, Альфредом Менезесом, Томасом Оливейрой, Франсиско Родригес-Энрикесом и Луисом Ривера-Замаррипа 18 июля 2016 года. 4841-битное конечное поле с 36 · 509 элементов и выполнялась на нескольких компьютерах в CINVESTAV и Университет Ватерлоо. В общей сложности на вычисления было затрачено около 200 основных лет вычислительного времени.[19]

Объявлены предыдущие рекорды в конечном поле характеристики 3:

  • в полной версии статьи Жу и Пьеро Asiacrypt 2014 г. (декабрь 2014 г.).[20] ДЛП решается в поле GF (35 · 479), который представляет собой 3796-битное поле. В этой работе не использовались какие-либо «особые» аспекты поля, такие как свойства Куммера или твист-Куммера. Суммарные вычисления заняли менее 8600 процессорных часов.
  • Гора Адж, Альфред Менезес, Томас Оливейра и Франсиско Родригес-Энрикес, 26 февраля 2014 г., обновив предыдущее объявление от 27 января 2014 г. Вычисления решают DLP в 1551-битном поле GF (36 · 163), что занимает 1201 час работы процессора.[21][22]
  • в 2012 году совместной командой Fujitsu, NICT и Университета Кюсю, которая вычислила дискретный логарифм в области 36 · 97 элементов и размером 923 бита,[23] используя вариант сито функционального поля и побив предыдущий рекорд в области 36 · 71 элементов и размером 676 бит с большим отрывом.[24]

По полям с характеристикой «умеренного» размера заметные вычисления по состоянию на 2005 г. включали в себя поле 6553725 элементы (401 бит), объявленные 24 октября 2005 г., и в поле 37080130 элементы (556 бит) анонсированы 9 ноября 2005 г.[25] Текущий рекорд (по состоянию на 2013 год) для конечного поля «умеренной» характеристики был объявлен 6 января 2013 года. Команда использовала новую вариацию сито функционального поля для среднего простого случая, чтобы вычислить дискретный логарифм в поле 3334135357 элементы (1425-битное конечное поле).[26][27] Тот же метод был использован несколькими неделями ранее для вычисления дискретного логарифма в поле 3355377147 элементы (конечное поле размером 1175 бит).[27][28]

25 июня 2014 года Разван Барбулеску, Пьерк Годри, Аврора Гильевич и Франсуа Морен объявили о новом вычислении дискретного логарифма в конечном поле, порядок которого состоит из 160 цифр и является расширением степени 2 для простого поля.[29] Используемый алгоритм представлял собой решето числового поля (NFS) с различными модификациями. Общее время вычислений было эквивалентно 68 дням на одном ядре CPU (просеивание) и 30 часам на GPU (линейная алгебра).

Эллиптические кривые

Certicom Corp. выпустила серию задач по криптографии с эллиптическими кривыми. Уровень I включает поля размером 109 и 131 бит. Уровень II включает размеры 163, 191, 239, 359 бит. В настоящее время считается, что все задачи уровня II вычислительно невыполнимы.[30]

Решенные задачи Уровня I:[31]

  • ECC2K-108, включающий дискретный логарифм на Кривая Коблица над полем из 2108 элементы. Премия была вручена 4 апреля 2000 года группе из около 1300 человек, которую представлял Роберт Харли. Они использовали распараллеленный Метод Полларда ро с ускорением.
  • ECC2-109, включающий дискретный логарифм на кривой над полем 2109 элементы. Премия была вручена 8 апреля 2004 года группе из около 2600 человек, которую представлял Крис Монико. Они также использовали версию распараллеленного Метод Полларда ро, что занимает 17 месяцев календарного времени.
  • ECCp-109, включающий дискретный логарифм кривой по модулю 109-разрядного простого числа. Премия была вручена 15 апреля 2002 года группе из 10308 человек, которую представлял Крис Монико. И снова они использовали версию распараллеленного Метод Полларда ро, что занимает 549 дней календарного времени.

По состоянию на 2019 год ни одна из 131-битных (или больших) задач не была решена..

В июле 2009 г. Йоппе В. Бос, Марсело Э. Кайхара, Торстен Кляйнджунг, Арьен К. Ленстра и Питер Л. Монтгомери объявили, что они выполнили вычисление дискретного логарифма на эллиптической кривой (известной как secp112r1[32]) по модулю 112-битного простого числа. Расчет проводился на кластере из более чем 200 человек. PlayStation 3 игровых приставок около 6 месяцев. Они использовали общую распараллеленную версию Метод Полларда ро.[33]

В апреле 2014 г. Эрих Венгер и Пол Вольфгер из Технологический университет Граца решил дискретный логарифм 113-битной кривой Коблица за 24 дня, используя 18-ядерный Виртекс-6 FPGA кластер.[34] В январе 2015 года те же исследователи решили дискретный логарифм эллиптической кривой, определенной над 113-битным двоичным полем. Среднее время работы составляет около 82 дней при использовании 10-ядерного Кинтекс-7 FPGA кластер.[35]

2 декабря 2016 г. Дэниел Дж. Бернштейн, Сюзанна Энгельс, Таня Ланге, Рубен Нидерхаген, Кристоф Паар, Питер Швабе, и Ральф Циммерманн объявила о решении общей задачи дискретного логарифмирования 117,35-битной эллиптической кривой на двоичной кривой с использованием оптимизированной реализации параллельной версии ПЛИС Алгоритм ро Полларда. Атака длилась около шести месяцев параллельно на 64–576 ПЛИС.[36]

23 августа 2017 года Такуя Кусака, Шо Джойчи, Кен Икута, доктор Аль-Амин Хандакер, Ясуюки Ногами, Сатоши Уэхара, Нариёши Ямаи и Сильвен Дукесн объявили, что они решили задачу дискретного логарифмирования для 114-битной пары дружественная кривая Баррето-Нерига (BN),[37] использование особого свойства секстического скручивания кривой BN для эффективного выполнения случайного блуждания по методу ро Полларда. В реализации использовалось 2000 ядер ЦП, и на решение проблемы ушло около 6 месяцев.[38]

16 июня 2020 года Александр Зеневич (зелар) и Жан Люк Понс (ЖанЛюкПонс ) объявил о решении задачи дискретного логарифмирования 114-битных интервальных эллиптических кривых на кривой secp256k1 путем решения 114-битных закрытых ключей в программе Bitcoin Puzzle Transactions Challenge. Чтобы установить новый рекорд, они использовали собственное программное обеспечение [39] на основе Поллард Кенгуру на 256x NVIDIA Tesla V100 Процессор GPU и на это у них ушло 13 дней. Двумя неделями ранее - они использовали то же количество видеокарт для решения 109-битного интервала ECDLP всего за 3 дня.

Рекомендации

  1. ^ Эммануэль Томе, «795-битное разложение и дискретные логарифмы», 2 декабря 2019.
  2. ^ Ф. Будо и др., «Сравнение сложности факторизации и дискретного логарифма: 240-значный эксперимент», 10 июня 2020 г.
  3. ^ Торстен Кляйнджунг, «Дискретные логарифмы в GF (п) - 768 бит » 16 июня 2016 г.
  4. ^ Антуан Жу, «Дискретные логарифмы в GF (п) - 130 цифр » 18 июня 2005 г.
  5. ^ Торстен Кляйнджунг, «Дискретные логарифмы в GF (п) - 160 цифр » 5 февраля 2007 г.
  6. ^ Сирил Бувье, Пьеррик Годри, Лоран Имбер, Хамза Джелжели и Эммануэль Томе, «Дискретные логарифмы в GF (п) - 180 цифр "
  7. ^ Джошуа Фрид, Пьеррик Годри, Надя Хенингер, Эммануэль Том, «Вычисление дискретного логарифма килобита скрытых snfs», IACR весна, июль 2016 г.
  8. ^ Йенс Зумбрегель, "Дискретные логарифмы в GF (2 ^ 30750)", 10 июля 2019 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;62ab27f0.1907.
  9. ^ Р. Грейнджер, Т. Кляйнджунг, Дж. Зумбрагель. О задаче дискретного логарифмирования в конечных полях фиксированной характеристики. Пер. Амер. Math.Soc. 370, нет. 5 (2018), стр. 3129-3145.
  10. ^ Йенс Зумбрегель, «Дискретные логарифмы в GF (2 ^ 9234)», 31 января 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401.
  11. ^ Антуан Жу, "Дискретные логарифмы в GF (26168) [= GF ((2257)24)] ", 21 мая 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1305&L=NMBRTHRY&F=&S=&P=3034.
  12. ^ Антуан Жу. Новый алгоритм расчета индекса со сложностью $ L (1/4 + o (1)) $ в очень маленькой характеристике, 2013 г., http://eprint.iacr.org/2013/095
  13. ^ Антуан Жу, "Дискретные логарифмы в GF (24080) ", 22 марта 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1303&L=NMBRTHRY&F=&S=&P=13682.
  14. ^ Фарук Гологлу и др., О решетке функционального поля и влиянии более высоких вероятностей расщепления: применение к дискретным логарифмам в , 2013, http://eprint.iacr.org/2013/074.
  15. ^ Антуан Жу, "Дискретные логарифмы в GF (21778) ", 11 февраля 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=2317.
  16. ^ Грейнджер, Роберт, Торстен Кляйнджунг и Йенс Цумбрегель. «Нарушение« 128-битных безопасных »суперсингулярных двоичных кривых (или Как решить дискретные логарифмы в и ). » arXiv: 1402.3668 [cs, Math], 15 февраля 2014 г. https://arxiv.org/abs/1402.3668.
  17. ^ Торстен Кляйнджунг, 17 октября 2014 г., «Дискретные логарифмы в GF (2 ^ 1279)», https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;256db68e.1410.
  18. ^ Группа CARAMEL: Разван Барбулеску, Сирил Бувье, Жереми Детри, Пьеррик Годри, Хамза Джелжели, Эммануэль Томе, Марион Видео и Пол Циммерманн, «Дискретный логарифм в GF (2809) с ФФС », 6 апреля 2013 г., г. http://eprint.iacr.org/2013/197.
  19. ^ Франсиско Родригес-Энрикес, 18 июля 2016 г., «Дискретные логарифмы в GF (3 ^ {6 * 509})», https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;65bedfc8.1607.
  20. ^ «Архивная копия» (PDF). Архивировано из оригинал (PDF) на 2014-12-11. Получено 2014-12-11.CS1 maint: заархивированная копия как заголовок (связь)
  21. ^ Франсиско Родригес-Энрикес, «Объявление», 27 января 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;763a9e76.1401.
  22. ^ Гора Адж, Альфред Менезес, Томас Оливейра и Франсиско Родригес-Энрикес, «Вычисление дискретных логарифмов в F_ {3 ^ {6 * 137}} и F_ {3 ^ {6 * 163}} с использованием Magma», 26 февраля 2014 г., http://eprint.iacr.org/2014/057.
  23. ^ Университет Кюсю, NICT и лаборатории Fujitsu достигли мирового рекорда криптоанализа криптографии следующего поколения, 2012 г., http://www.nict.go.jp/en/press/2012/06/PDF-att/20120618en.pdf.
  24. ^ Такуя Хаяси и др., Решение 676-битной задачи дискретного логарифмирования в GF (36п), 2010, http://eprint.iacr.org/2010/090.
  25. ^ А. Дюран, «Новые рекорды в вычислениях над большими числами», Информационный бюллетень по безопасности, январь 2005 г. http://eric-diehl.com/letter/Newsletter1_Final.pdf В архиве 2011-07-10 на Wayback Machine.
  26. ^ Антуан Жу, «Дискретные логарифмы в 1425-битном конечном поле», 6 января 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1301&L=NMBRTHRY&F=&S=&P=2214.
  27. ^ а б Более быстрое вычисление индекса для случая среднего простого числа. Применение к 1175-битным и 1425-битным конечным полям, Eprint Archive, http://eprint.iacr.org/2012/720
  28. ^ Антуан Жу, «Дискретные логарифмы в 1175-битном конечном поле», 24 декабря 2012 г. https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1212&L=NMBRTHRY&F=&S=&P=13902.
  29. ^ Разван Барбулеску, «Дискретные логарифмы в GF (p ^ 2) --- 160 цифр», 24 июня 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;2ddabd4c.1406.
  30. ^ Certicom Corp., «Проблема Certicom ECC», https://www.certicom.com/content/certicom/en/the-certicom-ecc-challenge.html
  31. ^ Certicom Research, Certicom ECC Challenge (Certicom Research, 10 ноября 2009 г.), «Архивная копия» (PDF). Архивировано из оригинал (PDF) на 2015-10-22. Получено 2010-12-30.CS1 maint: заархивированная копия как заголовок (связь) .
  32. ^ Certicom Research, "SEC 2: Рекомендуемые параметры домена эллиптической кривой" https://www.secg.org/SEC2-Ver-1.0.pdf
  33. ^ Джоппе В. Бос и Марсело Э. Кайхара, «Вычисления PlayStation 3 преодолевают барьер 2 ^ 60: решено 112-битное простое ECDLP», Лаборатория криптологических алгоритмов EPFL - LACAL, http://lacal.epfl.ch/112bit_prime
  34. ^ Эрих Венгер и Пол Вольфгер, «Решение дискретного логарифма 113-битной кривой Коблица с помощью кластера FPGA» http://eprint.iacr.org/2014/368
  35. ^ Эрих Венгер и Пол Вольфгер, «Сложнее, лучше, быстрее, сильнее - вычисления дискретного логарифма эллиптической кривой на ПЛИС» http://eprint.iacr.org/2015/143/
  36. ^ Рубен Нидерхаген, «117,35-битный ECDLP на двоичной кривой», https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;628a3b51.1612[мертвая ссылка ]
  37. ^ «114-битный ECDLP на кривой BN был решен». Получено 2018-05-03.
  38. ^ Кусака, Такуя; Джойчи, Шо; Икута, Кен; Хандакер, штат Мэриленд Аль-Амин; Ногами, Ясуюки; Уэхара, Сатоши; Ямаи, Нариёси; Duquesne, Сильвен (2018). «Решение 114-битного ECDLP для кривой Баррето-Нерига» (PDF). Информационная безопасность и криптология - ICISC 2017. Springer. С. 231–244. Дои:10.1007/978-3-319-78556-1_13.
  39. ^ Понс, Жан-Люк; Зеневич, Александр. "Кенгуру Полларда для SECPK1".

внешняя ссылка