Группа криптографов из Лаборатории исследований в области компьютерных наук и прикладного программирования в университете Лотарингии (Франция) и Парижской лаборатории информатики смогли решить один из аспектов фундаментальной проблемы дискретного логарифмирования, то есть одной из главных алгоритмических проблем теории чисел, на которой основаны многие современные криптографические системы.
Дискретное логарифмирование — задача обращения функции g^x в некоторой конечной мультипликативной группе G.
Исследователи предложили новый криптоалгоритм, который ставит под сомнение безопасность одного из варианта вышеупомянутой проблемы, которая пристально изучалась с 1976 года. Таким образом, новая схема дискредитирует несколько криптографических систем, ранее считавшихся относительно надёжными. Хотя работа носит теоретический характер, но последствия могут быть довольно серьёзными, особенно в области использования криптографических систем в смарт-картах, RFID-чипах и т.д.
Представленный алгоритм решает проблемы дискретного логарифмирования гораздо лучше, чем предыдущие алгоритмы. При увеличении размера чисел вычислительные ресурсы, потребляемые программой, увеличиваются не так быстро, как у предыдущих алгоритмов. Соответственно, с его помощью можно подбирать числа большего размера за меньшее время.
Научная работа опубликована в журнале “Advances in cryptology”, а результаты исследования оглашены на конференции Eurocrypt 2014, которая прошла в Копенгагене 11-15 мая 2014 года.
В ближайшем будущем исследователи должны оптимизировать алгоритм и разработать прикладную программу для демонстрации дискретного логарифмирования на невиданной скорости.
