Дискретное логарифмирование запись являются лучшими результатами , достигнутые до настоящего времени в решении дискретного логарифма проблемы, что является задачей нахождения решения х к уравнению г х = ч даны элементов г и ч конечной циклической группы G . Трудность этой проблемы является основой для обеспечения нескольких криптографических систем, в том числе Диффи-Хеллмана соглашения ключа, шифрования ElGamal , в схеме подписи ElGamal , тем алгоритм цифровой подписи , и эллиптической кривой криптографиианалоги этих. Обычный выбор для G, используемый в этих алгоритмах, включает мультипликативную группу целых чисел по модулю p , мультипликативную группу конечного поля и группу точек на эллиптической кривой над конечным полем .
Целые числа по модулю p
- 2 декабря 2019 года Фабрис Будо, Пьер Годри, Аврора Гильевич, Надя Хенингер , Эммануэль Томе и Пол Циммерманн объявили о вычислении дискретного логарифма по модулю 240-значного (795-битного) простого числа RSA-240 + 49204 (первое безопасное простое число). выше RSA-240). Это вычисление было выполнено одновременно с факторизацией RSA-240 с использованием алгоритма сита числового поля и программного обеспечения CADO-NFS с открытым исходным кодом. Для вычисления дискретного логарифма потребовалось приблизительно 3100 ядерно-лет при использовании процессоров Intel Xeon Gold 6130 в качестве эталона (2,1 ГГц). Исследователи подсчитали, что улучшения в алгоритмах и программном обеспечении сделали эти вычисления в три раза быстрее, чем можно было бы ожидать от предыдущих записей после учета улучшений в оборудовании. [1] [2]
Предыдущие записи для целых чисел по модулю p включают:
- 16 июня 2016 года Торстен Кляйнджунг, Клаус Дием, Арьен К. Ленстра , Кристин Приплата и Колин Штальке объявили о вычислении дискретного логарифма по модулю 232-значного (768-битного) безопасного простого числа с использованием сита числового поля. Вычисления были начаты в феврале 2015 года и заняли примерно 6600 ядерно-лет в масштабировании до Intel Xeon E5-2660 с тактовой частотой 2,2 ГГц. [3]
- 18 июня 2005 года Антуан Жу и Рейнальд Лерсье объявили о вычислении дискретного логарифма по модулю 130-значного (431-битного) сильного простого числа за три недели с использованием 16-процессорного компьютера HP AlphaServer GS1280 с частотой 1,15 ГГц и алгоритма сита числового поля. . [4]
- 5 февраля 2007 года это было заменено объявлением Торстена Кляйнджунга о вычислении дискретного логарифма по модулю 160-значного (530-битного) безопасного простого числа , снова с использованием сита числового поля. Большая часть вычислений выполнялась в режиме простоя на различных ПК и в кластере параллельных вычислений. [5]
- 11 июня 2014 года Сирил Бувье, Пьеррик Годри, Лоран Имбер, Хамза Джельели и Эммануэль Томе объявили о вычислении дискретного логарифма по модулю 180-значного (596-битного) безопасного простого числа с использованием алгоритма сита числового поля. [6]
Также следует отметить, что в июле 2016 года Джошуа Фрид, Пьеррик Годри, Надя Хенингер, Эммануэль Том опубликовали свое вычисление дискретного логарифма для 1024-битного простого числа. [7] Они сгенерировали простое число, восприимчивое к решету специального числового поля, используя специальный алгоритм для сравнительно небольшой подгруппы (160 битов). Хотя это небольшая подгруппа, это был стандартизированный размер подгруппы, используемый с 1024-битным алгоритмом цифровой подписи (DSA).
Конечные поля
Текущий рекорд (по состоянию на июль 2019 г.[Обновить]) в конечном поле характеристики 2 было объявлено Робертом Грейнджером, Торстеном Кляйнджунгом, Арьеном Ленстрой, Бенджамином Весоловски и Йенсом Замбрегелем 10 июля 2019 г. [8] Эта команда смогла вычислить дискретные логарифмы в GF (2 30750 ), используя 25 481 219 часы работы ядра на кластерах на базе архитектуры Intel Xeon. Это вычисление было первым крупномасштабным примером, использующим этап исключения квазиполиномиального алгоритма. [9]
Предыдущие рекорды в конечном поле характеристики 2 были объявлены:
- Роберт Грейнджер, Торстен Кляйнджунг и Йенс Цумбрегель, 31 января 2014 г. Эта команда смогла вычислить дискретные логарифмы в GF (2 9234 ), затратив около 400 000 ядерных часов. Новые возможности этого вычисления включают модифицированный метод получения логарифмов элементов второй степени и систематически оптимизированную стратегию спуска. [10]
- Антуан Жу, 21 мая 2013 года. Его команда смогла вычислить дискретные логарифмы в полевых условиях с 2 6168 = (2 257 ) 24 элементами, используя менее 550 процессорных часов. Это вычисление было выполнено с использованием того же алгоритма расчета индекса, что и в недавнем вычислении в поле с 2 4080 элементами. [11]
- Роберт Грейнджер, Фарук Гелоглу, Гэри Макгуайр и Йенс Зумбрегель, 11 апреля 2013 г. Новое вычисление касалось поля с 2 6120 элементами и заняло 749,5 ядерных часов.
- Антуан Жу, 22 марта 2013 г. При этом использовался тот же алгоритм [12] для малых характеристических полей, что и в предыдущем вычислении для поля с 2 1778 элементами. Новое вычисление касалось поля с 2 4080 элементами, представленного как расширение степени 255 поля с 2 16 элементами. Вычисление заняло менее 14100 часов работы ядра. [13]
- Роберт Грейнджер, Фарук Гелоглу, Гэри Макгуайр и Йенс Замбрегель, 19 февраля 2013 года. Они использовали новый вариант сита поля функции основного поля среднего размера для двоичных полей, чтобы вычислить дискретный логарифм в поле из 2 элементов 1971 года . Чтобы использовать базовое поле среднего размера, они представили поле как расширение поля из 2 27 элементов на 73 градуса . Вычисление заняло 3132 ядерных часа в кластере SGI Altix ICE 8200EX с использованием шестиядерных процессоров Intel (Westmere) Xeon E5650. [14]
- Antoine Joux, 11 февраля 2013 г. Он использовал новый алгоритм для малых характеристических полей. Вычисление касалось поля из 2 1778 элементов, представленного как расширение поля с 2 14 элементами в степени 127 . Вычисление заняло менее 220 часов работы ядра. [15]
Текущий рекорд (по состоянию на 2014 г.[Обновить]) в конечном поле характеристики 2 простой степени было объявлено Торстеном Кляйнджунгом 17 октября 2014 года. Вычисление проводилось в поле из 2 1279 элементов и, по сути, следовало пути, намеченному дляв [16] с двумя основными исключениями: вычисление линейной алгебры и фаза спуска. Общее время работы составило менее четырех основных лет. [17] Предыдущий рекорд в конечном поле характеристики 2 простой степени был объявлен группой CARAMEL 6 апреля 2013 года. Они использовали решето функционального поля для вычисления дискретного логарифма в поле из 2 809 элементов. [18]
Текущий рекорд (по состоянию на июль 2016 г.[Обновить]) для поля характеристики 3 было объявлено Гора Адж, Исааком Каналес-Мартинесом, Нарели Крус-Кортесом, Альфредом Менезесом, Томасом Оливейрой, Франсиско Родригес-Энрикес и Луисом Ривера-Замаррипа 18 июля 2016 года. 4841-битное конечное поле с 3 6 · 509 элементами и было выполнено на нескольких компьютерах в CINVESTAV и Университете Ватерлоо . В общей сложности на вычисления было затрачено около 200 основных лет вычислительного времени. [19]
Объявлены предыдущие рекорды в конечном поле характеристики 3:
- в полной версии статьи Жу и Пьеро Asiacrypt 2014 г. (декабрь 2014 г.). [20] DLP решается в поле GF (3 5 · 479 ), которое является 3796-битным полем. В этой работе не использовались какие-либо «особые» аспекты поля, такие как свойства Куммера или твист-Куммера. Суммарные вычисления заняли менее 8600 процессорных часов.
- Гора Адж, Альфред Менезес, Томас Оливейра и Франсиско Родригес-Энрикес 26 февраля 2014 г., обновив предыдущее объявление от 27 января 2014 г. Вычисление решает DLP в 1551-битном поле GF (3 6 · 163 ), занимая 1201 ЦП часы. [21] [22]
- в 2012 году совместной командой Fujitsu, NICT и Университета Кюсю, которая вычислила дискретный логарифм в поле из 3 6 · 97 элементов и размером 923 бита [23], используя вариант сита функционального поля и превзойдя предыдущий запись в поле 3 6 · 71 элемента и размером 676 бит с большим отрывом. [24]
Среди полей с характеристикой «среднего» размера заметные вычисления по состоянию на 2005 г. включали те, что в поле из 65537 25 элементов (401 бит) было объявлено 24 октября 2005 г., а в поле из 370801 30 элементов (556 бит) было объявлено 9 ноября 2005 г. . [25] Текущий рекорд (по состоянию на 2013 год) для конечного поля «умеренной» характеристики был объявлен 6 января 2013 года. Команда использовала новую вариацию решета функционального поля для среднего простого случая, чтобы вычислить дискретный логарифм в поле из 33341353 57 элементов (1425-битное конечное поле). [26] [27] Тот же метод был использован несколькими неделями ранее для вычисления дискретного логарифма в поле из 33553771 47 элементов (конечное поле размером 1175 бит). [27] [28]
25 июня 2014 года Разван Барбулеску, Пьерк Годри, Аврора Гильевич и Франсуа Морен объявили о новом вычислении дискретного логарифма в конечном поле, порядок которого состоит из 160 цифр и является расширением степени 2 для простого поля. [29] Используемый алгоритм представлял собой решето числового поля (NFS) с различными модификациями. Общее время вычислений было эквивалентно 68 дням на одном ядре ЦП (просеивание) и 30 часам на графическом процессоре (линейная алгебра).
Эллиптические кривые
Certicom Corp. выпустила серию задач по криптографии с эллиптическими кривыми. Уровень I включает поля размером 109 и 131 бит. Уровень II включает размеры 163, 191, 239, 359 бит. Все задачи уровня II в настоящее время считаются вычислительно невыполнимыми. [30]
Были выполнены следующие проблемы Уровня I: [31]
- ECC2K-108, включающий дискретный логарифм на кривой Коблица над полем из 2 108 элементов. Премия была вручена 4 апреля 2000 года группе из около 1300 человек, которую представлял Роберт Харли. Они использовали параллельный метод Полларда-ро с ускорением.
- ECC2-109, включающий дискретное логарифмирование кривой над полем из 2 109 элементов. Премия была вручена 8 апреля 2004 года группе из около 2600 человек, которую представлял Крис Монико. Они также использовали вариант распараллеленного метода Полларда-ро , который занял 17 месяцев календарного времени.
- ECCp-109, включающий дискретный логарифм кривой по модулю 109-битного простого числа. Премия была вручена 15 апреля 2002 года группе из 10308 человек, которую представлял Крис Монико. И снова они использовали вариант распараллеленного метода Полларда-ро , на который ушло 549 дней календарного времени.
По состоянию на 2019 год ни одна из 131-битных (или более крупных) задач не была решена.[Обновить].
В июле 2009 года Йоппе В. Бос, Марсело Э. Кайхара, Торстен Кляйнджунг, Арьен К. Ленстра и Питер Л. Монтгомери объявили, что они выполнили вычисление дискретного логарифма на эллиптической кривой (известной как secp112r1 [32] ) по модулю a. 112-битное простое число. Расчет проводился на кластере из более чем 200 игровых консолей PlayStation 3 в течение примерно 6 месяцев. Они использовали распространенную распараллеленную версию метода Полларда-ро . [33]
В апреле 2014 года Эрих Венгер и Пол Вольфгер из Технологического университета Граца решили дискретный логарифм 113-битной кривой Коблица за 24 дня экстраполяции с использованием 18-ядерного кластера ПЛИС Virtex-6 . [34] В январе 2015 года те же исследователи решили дискретный логарифм эллиптической кривой, определенной над 113-битным двоичным полем. Среднее время работы составляет около 82 дней с использованием 10-ядерного кластера ПЛИС Kintex-7 . [35]
2 декабря 2016 года Даниэль Дж. Бернштейн , Сюзанна Энгельс , Таня Ланге , Рубен Нидерхаген , Кристоф Паар , Петер Швабе и Ральф Циммерманн объявили о решении общей задачи дискретного логарифмирования 117,35-битной эллиптической кривой на двоичной кривой с использованием оптимизированной Реализация на ПЛИС параллельной версии алгоритма ро Полларда . Атака продолжалась около шести месяцев на 64–576 ПЛИС параллельно. [36]
23 августа 2017 года Такуя Кусака, Шо Джойчи, Кен Икута, доктор Аль-Амин Хандакер, Ясуюки Ногами, Сатоши Уэхара, Нариёши Ямаи и Сильвен Дукесн объявили, что они решили задачу дискретного логарифмирования для 114-битной пары. дружественная кривая Баррето-Нерига (BN) [37], использующая свойство особого секстического скручивания кривой BN для эффективного выполнения случайного блуждания по методу ро Полларда. В реализации использовалось 2000 ядер ЦП, и на решение проблемы ушло около 6 месяцев. [38]
16 июня 2020 года Александр Зеневич (zielar) и Жан Люк Понс ( JeanLucPons ) объявили о решении задачи дискретного логарифма 114-битной интервальной эллиптической кривой на кривой secp256k1 путем решения 114-битного закрытого ключа в программе Bitcoin Puzzle Transactions Challenge. Чтобы установить новый рекорд, они использовали собственное программное обеспечение [39] на базе Pollard Kangaroo на 256-кратном процессоре NVIDIA Tesla V100 GPU, и это заняло у них 13 дней. Двумя неделями ранее - они использовали то же количество видеокарт, чтобы решить 109-битный интервал ECDLP всего за 3 дня.
Рекомендации
- ^ Эммануэль Thomé, «795-битный факторинг и дискретные логарифмы,» 2 декабря 2019.
- ^ F. Boudot и др., «Сравнение сложности факторизации и дискретного логарифма: 240-значный эксперимент», 10 июня 2020 г.
- ^ Торстен Kleinjung, «Дискретные логарифмы в GF ( р ) - 768 бит,» 16 июня 2016 года.
- ↑ Антуан Жу, «Дискретные логарифмы в GF ( p ) - 130 цифр», 18 июня 2005 г.
- ^ Торстен Kleinjung, «Дискретные логарифмы в GF ( р ) - 160 цифр» 5 февраля 2007 года.
- ^ Сирил Бувье, Пьеррик Годри, Лоран Имбер, Хамза Джелжели и Эммануэль Томе, «Дискретные логарифмы в GF ( p ) - 180 цифр»
- ^ Джошуа Фрид, Пьеррик Годри, Надя Хенингер, Эммануэль Том, «Вычисление дискретного логарифма килобитных скрытых snfs» , весна IACR, июль 2016 г.
- ^ Йенс Зумбрагель, «Дискретные логарифмы в GF (2 ^ 30750)», 10 июля 2019 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;62ab27f0.1907 .
- ^ Р. Грейнджер, Т. Кляйнджунг, Дж. Зумбрагель. О задаче дискретного логарифмирования в конечных полях фиксированной характеристики. Пер. Амер. Математика. Soc. 370, нет. 5 (2018), стр. 3129-3145.
- ^ Йенс Зумбрагель, «Дискретные логарифмы в GF (2 ^ 9234)», 31 января 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401 .
- ^ Антуан Жу, «Дискретные логарифмы в GF (2 6168 ) [= GF ((2 257 ) 24 )]», 21 мая 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2 = ind1305 & L = NMBRTHRY & F = & S = & P = 3034 .
- ^ Антуан Жу. Новый алгоритм расчета индекса со сложностью $ L (1/4 + o (1)) $ в очень маленькой характеристике, 2013 г., http://eprint.iacr.org/2013/095
- ^ Антуан Жу, «Дискретные логарифмы в GF (2 4080 )», 22 марта 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1303&L=NMBRTHRY&F=&S=&P=13682 .
- ^ Фарук Гологлу и др., О решетке функционального поля и влиянии более высоких вероятностей расщепления: применение к дискретным логарифмам в, 2013 г., http://eprint.iacr.org/2013/074 .
- ^ Антуан Жу, «Дискретные логарифмы в GF (2 1778 )», 11 февраля 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=2317 .
- ^ Грейнджер, Роберт, Торстен Kleinjung и Jens Zumbrägel. «Нарушение« 128-битных безопасных »суперсингулярных двоичных кривых (или как решить дискретные логарифмы в а также ). » arXiv: 1402.3668 [cs, Math], 15 февраля 2014 г. https://arxiv.org/abs/1402.3668 .
- ^ Торстен Kleinjung, 2014 17 октября, "Дискретные логарифмы в GF (2 ^ 1279)", https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;256db68e.1410 .
- ^ Группа КАРАМЕЛЬ: Разван Barbulescu и Кирилла Бувье и Жереми DeTrey и Pierrick Годри и Хамза Jeljeli и Эммануэль Thomé и Марион Videau и Пол Циммерман, «Дискретное логарифмирование в GF (2 809 ) с FFS», 6 апреля 2013, HTTP: / /eprint.iacr.org/2013/197 .
- ^ Франсиско Родригес-Энрикес, 18 июля 2016 г., «Дискретные логарифмы в GF (3 ^ {6 * 509})», https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;65bedfc8. 1607 .
- ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 11 декабря 2014 года . Проверено 11 декабря 2014 .CS1 maint: заархивированная копия как заголовок ( ссылка )
- ↑ Франсиско Родригес-Энрикес, «Объявление», 27 января 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;763a9e76.1401 .
- ^ Гора Адж, Альфред Менезес, Томас Оливейра и Франсиско Родригес-Энрикес, «Вычисление дискретных логарифмов в F_ {3 ^ {6 * 137}} и F_ {3 ^ {6 * 163}} с использованием Magma», 26 февраля 2014 г., http : //eprint.iacr.org/2014/057 .
- ^ Университет Кюсю, NICT и Fujitsu Laboratories достигли мирового рекорда по криптоанализу криптографии следующего поколения, 2012 г., http://www.nict.go.jp/en/press/2012/06/PDF-att/20120618en.pdf .
- ^ Такуя Хаяси и др., Решение 676-битной задачи дискретного логарифма в GF (3 6 n ), 2010 г., http://eprint.iacr.org/2010/090 .
- ^ А. Дюран, «Новые рекорды в вычислениях над большими числами», Информационный бюллетень по безопасности, январь 2005 г., http://eric-diehl.com/letter/Newsletter1_Final.pdf. Архивировано 10 июля2011 г. на Wayback Machine .
- ^ Антуан Жу, «Дискретные логарифмы в 1425-битном конечном поле», 6 января 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1301&L=NMBRTHRY&F=&S=&P=2214 .
- ^ a b Более быстрое вычисление индекса для среднего простого случая. Приложение к 1175-битным и 1425-битным конечным полям, Eprint Archive, http://eprint.iacr.org/2012/720
- ^ Антуан Жу, «Дискретные логарифмы в 1175-битном конечном поле», 24 декабря 2012 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1212&L=NMBRTHRY&F=&S=&P=13902 .
- ^ Разван Барбулеску, «Дискретные логарифмы в GF (p ^ 2) --- 160 цифр», 24 июня 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;2ddabd4c. 1406 .
- ^ Certicom Corp., «Certicom ECC Challenge», https://www.certicom.com/content/certicom/en/the-certicom-ecc-challenge.html.
- ^ Certicom Research, Certicom ECC Challenge (Certicom Research, 10 ноября 2009 г.), «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 22 октября 2015 года . Проверено 30 декабря 2010 .CS1 maint: заархивированная копия как заголовок ( ссылка ) .
- ^ Certicom Research, "SEC 2: Рекомендуемые параметры домена эллиптической кривой" https://www.secg.org/SEC2-Ver-1.0.pdf
- ^ Джоппе В. Бос и Марсело Э. Кайхара, «Вычисления PlayStation 3 преодолевают барьер 2 ^ 60: решено 112-битное простое ECDLP», Лаборатория криптологических алгоритмов EPFL - LACAL, http://lacal.epfl.ch/112bit_prime
- ^ Эрих Венгер и Пол Вольфгер, «Решение дискретного логарифма 113-битной кривой Коблица с помощью кластера FPGA» http://eprint.iacr.org/2014/368
- ^ Эрих Венгер и Пол Вольфгер, «Сложнее, лучше, быстрее, сильнее - вычисления дискретного логарифма эллиптической кривой на ПЛИС» http://eprint.iacr.org/2015/143/
- ^ Рубен Нидерхаген, «117,35-битный ECDLP на двоичной кривой», https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;628a3b51.1612 [ мертвая ссылка ]
- ^ «114-битный ECDLP на кривой BN был решен» . Проверено 3 мая 2018 .
- ^ Кусака, Такуя; Джойчи, Шо; Икута, Кен; Хандакер, штат Мэриленд Аль-Амин; Ногами, Ясуюки; Уэхара, Сатоши; Ямаи, Нариёси; Duquesne, Сильвен (2018). «Решение 114-битного ECDLP для кривой Баррето-Нерига» (PDF) . Информационная безопасность и криптология - ICISC 2017 . Springer. С. 231–244. DOI : 10.1007 / 978-3-319-78556-1_13 .
- ^ Понс, Жан-Люк; Зеневич, Александр. «Кенгуру Полларда для SECPK1» .
Внешние ссылки
- Вычисления дискретных логарифмов, отсортированных по дате