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

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

• 1 Целые числа по модулю p
• 2 Конечные поля
• 3 Эллиптические кривые
• 4 Ссылки
• 5 Внешние ссылки

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

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

• 16 июня 2016 года Торстен Кляйнджунг, Клаус Дием, Арьен К. Ленстра, Кристин Приплата и Колин Штальке объявили о вычислении дискретного логарифма по модулю 232-значное (768-битное) безопасное простое число с использованием решета числового поля. Вычисления были начаты в феврале 2015 года и заняли около 6600 ядерных лет в масштабировании до Intel Xeon E5-2660 с частотой 2,2 ГГц.

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

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

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

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

• Робертом Грейнджером, Торстеном Кляйнджунгом и Йенсом. Zumbrägel 31 января 2014 г. Эта команда смогла вычислить дискретные логарифмы в GF (2), затратив около 400 000 часов работы ядра. Новые функции этого вычисления включают модифицированный метод получения логарифмов элементов второй степени и систематически оптимизированную стратегию спуска.
• Антуан Жу, 21 мая 2013 года. Его команда смогла вычислить дискретные логарифмы в полевых условиях с 2 = (2) элементы, использующие менее 550 процессорных часов. Это вычисление было выполнено с использованием того же алгоритма расчета индекса, что и в недавнем вычислении в поле с двумя элементами.
• Роберт Грейнджер, Фарук Гелоглу, Гэри МакГуайр и Йенс Зумбрегель 11 апреля 2013 года. Новое вычисление касалось поле с 2 элементами и заняло 749,5 основных часов.
• Antoine Joux, 22 марта 2013 г. При этом использовался тот же алгоритм для небольших характеристических полей, что и в предыдущем вычислении в поле с 2 элементами. Новое вычисление касается поля с 2 элементами, представленного как расширение степени 255 поля с 2 элементами. Вычисление заняло менее 14100 основных часов.
• Роберт Грейнджер, Фарук Гелоглу, Гэри МакГуайр и Йенс Замбрегель 19 февраля 2013 г. Они использовали новый вариант сита функционального поля среднего размера , для двоичных полей, для вычисления дискретного логарифма в поле из 2 элементов. Чтобы использовать базовое поле среднего размера, они представили поле как расширение поля из 2 элементов на 73 градуса. Вычисление заняло 3132 ядерных часа на кластере SGI Altix ICE 8200EX с использованием шестиядерных процессоров Intel (Westmere) Xeon E5650.
• Антуан Жу 11 февраля 2013 г. При этом использовался новый алгоритм для небольших характерных полей. Вычисление касалось поля из 2 элементов, представленного как расширение поля с 2 элементами степени 127. Расчет занял менее 220 основных часов.

Текущий рекорд (по состоянию на 2014 год) в конечном поле характеристики 2 простой степени был объявлен Торстеном Кляйнджунгом 17 октября 2014 года. Расчет проводился в поле из 2 элементов и, по сути, следовал пути, намеченному для $F\; 2\; 4\; \cdot \; 1223\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{2\; ^\; \{4\; \backslash \; cdot\; 1223\}\}\}$, с двумя основными исключениями в линейной алгебре расчет и фаза спуска. Общее время работы составило менее четырех основных лет. Предыдущий рекорд в конечном поле характеристики 2 простой степени был объявлен группой CARAMEL 6 апреля 2013 г. Они использовали поле функции sieve для вычисления дискретного логарифма в поле из 2 элементов.

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

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

• в полной версии статьи Жу и Пьеро Asiacrypt 2014 г. (Декабрь 2014 г.). DLP решается в поле GF (3), которое является 3796-битным полем. В этой работе не использовались какие-либо «особые» аспекты поля, такие как свойства Куммера или твист-Куммера. Общее вычисление заняло менее 8600 процессорных часов.
• Гора Адж, Альфред Менезес, Томас Оливейра и Франсиско Родригес-Энрикес 26 февраля 2014 года, обновив предыдущее объявление от 27 января 2014 года. Вычисления решают DLP. в 1551-битном поле GF (3), что потребовало 1201 часов ЦП.
• в 2012 году совместной командой Fujitsu, NICT и Университета Кюсю, которая вычислила дискретный логарифм в поле из 3 элементов и размера 923 бита, используя вариацию поля функции sieve и превзойдя предыдущую запись в поле из 3 элементов и размером 676 бит с большим отрывом.

Над полями «среднего» размера характерные, заметные вычисления по состоянию на 2005 год включали те, что в поле из 65537 элементов (401 бит), объявленном 24 октября 2005 года, и в поле из 370801 элемента (556 бит), объявленном 9 ноября 2005 года. Текущий рекорд (по состоянию на 2013 год) для конечное поле "умеренной" характеристики было объявлено 6 января 2013 года. Команда использовала новую вариацию поля функции siev e для среднего простого случая для вычисления дискретного логарифма в поле из 33341353 элементов (1425-битное конечное поле). Тот же метод был использован несколькими неделями ранее для вычисления дискретного логарифма в поле из 33553771 элемента (конечное поле размером 1175 бит).

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

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

Были выполнены следующие задачи уровня I:

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

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

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

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

2 декабря 2016 года Daniel J. Bernstein, Tanja Lange, и объявил о решении общей задачи дискретного логарифмирования 117,35-битной эллиптической кривой на двоичной кривой с использованием оптимизированной реализации на ПЛИС параллельной версии алгоритма ро Полларда. Атака продолжалась около шести месяцев на 64–576 ПЛИС параллельно.

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

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

• Вычисления дискретных логарифмов, отсортированных по дате