Статья посвящена криптоанализу часто используемой схемы Диффи--Хеллмэна открытого распределения ключа. Начиная со статьи [1], идея которой ранее была изложена в работах И. Семаева, значительный интерес с точки зрения атакующих криптопротоколы на эллиптических кривых стала приобретать степень расширения, или MOV-степень. В англоязычной литературе этот параметр (далее к) принято называть "embedding degree". Имеется в виду расширение поля коэффициентов эллиптической кривой, в котором содержатся все точки исходного простого порядка р. Случайное значение этого параметра приближается к значению р, что приводит к длине записи элемента соответствующего расширения не многим меньше, чем p·log·p. В стандарте ГОСТ 34.10-2018 этот параметр предлагается брать больше 31, что позволяет использовать данное расширение, поскольку длина записи его элементов не больше k·log·p. В данной статье предложен полиномиальный алгоритм решения распознавательной и обычной задач Диффи--Хеллмэна, эффективный для некоторых таких кривых. Это означает, что схемы открытого распределения ключа, построенные с использованием этих кривых, являются нестойкими. Предлагаемый алгоритм основан на выборе такого спаривания, которое нетривиально определено на всех точках порядка p и может быть представлено в виде рациональной функции относительно небольшой степени. Сведение задачи Диффи--Хеллмэна к такому обращению получено в работе [2]. За основу предлагаемой конструкции взято нередуцированное спаривание Эйта, использованное в работе [19]. Предложены новые механизмы для расширения области определения рассматриваемого спаривания с помощью автоморфизма Фробениуса и сведения обращения по второму аргументу (лежащему в расширении поля коэффициентов кривой) к решению системы линейных уравнений с последующим поиском корней многочленов небольшой степени. Представлены оценки на вероятность разрешимости получаемых уравнений при взятии случайного представителя смежного класса, представляющего значение спаривания.
展开▼
