Алгоритм Шуфа (Glikjnmb Orsg)

Перейти к навигации Перейти к поиску

Алгоритм Шуфа — эффективный алгоритм[1] подсчёта числа точек на эллиптической кривой над конечным полем. Алгоритм имеет приложения в эллиптической криптографии, где важно знать число точек, чтобы судить о трудности решения задачи дискретного логарифмирования на группе точек на эллиптической кривой.

Алгоритм опубликовал в 1985 Рене Шуф[англ.] и это был теоретический прорыв, поскольку это был первый детерминированный алгоритм полиномиального времени для подсчёта точек на эллиптической кривой[англ.]. До алгоритма Шуфа подходы к подсчёту точек на эллиптических кривых, каким был бесхитростный алгоритм малых и больших шагов, были по большей части трудоёмкими и требовали экспоненционального времени работы.

Данная статья объясняет подход Шуфа, делая упор на математические идеи, лежащие в основе алгоритма.

Пусть  — эллиптическая кривая, определённая над конечным полем , где для простого и целого . Над полем с характеристикой эллиптическая кривая может быть задана (коротко) уравнением Вейерштрасса

с . Множество точек, определённых над , состоит из решений , удовлетворяющих уравнению кривой, и бесконечно удалённой точки . Если использовать групповой закон на эллиптических кривых на этом множестве, можно видеть, что это множество образует абелеву группу, в которой действует как нулевой элемент. Чтобы посчитать точки на эллиптической кривой, мы подсчитываем мощность множества . В подходе Шуфа для подсчёта мощности используется теорема Хассе об эллиптических кривых вместе с китайской теоремой об остатках и многочленами деления[англ.].

Теорема Хассе

[править | править код]

Теорема Хассе утверждает, что если является эллиптической кривой над конечным полем , то удовлетворяет неравенству

Этот сильный результат, полученный Хассе в 1934, упрощает нашу задачу путём сужения к конечному (хотя и большому) множеству возможностей. Если определить как и использовать этот результат, мы получим, что вычисление мощности по модулю , где , достаточно для вычисления , а потому и для получения . Хотя нет эффективного пути вычисления прямо для чисел общего вида, можно вычислить для малого простого числа довольно эффективно. Мы выбираем в качестве множества различных простых чисел, таких, что . Если задано для всех , китайская теорема об остатках позволяет вычислить .

Чтобы вычислить для простого , мы используем теорию эндоморфизма Фробениуса и многочлены деления[англ.]. Заметим, что рассмотрение простых чисел не приводит к проблемам, поскольку мы всегда можем выбрать большее простое число, чтобы обеспечить, чтобы произведение было достаточно велико. В любом случае алгоритм Шуфа наиболее часто используется для случая , поскольку имеются более эффективные, так называемые -адичные алгоритмы, для полей с малой характеристикой.

Эндоморфизм Фробениуса

[править | править код]

Если задана эллиптическая кривая , определённая над , мы рассматриваем точки на над , алгебраическим замыканием[англ.] поля . То есть мы разрешаем точкам иметь координаты в . Эндоморфизм Фробениуса над расширяет эллиптическую кривую отображением .

Это отображение тождественно на и можно расширить его точкой на бесконечности , что делает его морфизмом группы из на себя.

Эндоморфизм Фробениуса удовлетворяет квадратному уравнению, связанному с мощностью по следующей теореме:

Теорема: Эндоморфизм Фробениуса, заданный отображением , удовлетворяет характеристическому уравнению

, где

Тогда для всех имеем , где + означает сложение эллиптической кривой, а и означают скалярное произведение точки на и точки на [2].

Можно попытаться в символьном виде вычислить эти точки , и как функции на координатном кольце[англ.] на кривой , а затем искать значение , которое удовлетворяет уравнению. Однако степени получаются очень большими и такой подход практического значения не имеет.

Идея Шуфа заключалась в выполнении таких вычислений, ограничиваясь точками порядка для различных малых простых чисел . Фиксируя нечётное простое число мы переходим к решению задачи определения , определённого как , для заданного простого . Если точка находится в подгруппе -кручения , то , где является единственным целым числом, таким, что и . Заметим, что и что для любого целого мы имеем . Таким образом, имеет тот же порядок, что и . Тогда для , принадлежащего , мы имеем также , если . Следовательно, мы свели нашу задачу к решению уравнения

где и лежат в интервале .

Вычисления по простому модулю

[править | править код]

Многочлен деления[англ.] с номером l — это такой многочлен, что его корни являются в точности x координатами точек порядка l. Тогда ограничение вычисления на точки l-кручения означает вычисление этих выражений как функций координатного кольца E и модуля l-го многочлена деления. То есть мы работаем в . Это, в частности, означает, что степень X и Y, определяемых через не превышают 1 по переменной y и по переменной x.

Скалярное произведение может быть осуществлено методом удвоить-и-сложить, либо с помощью -го многочлена деления. Второй подход даёт:

,

где  — n-й многочлен деления. Заметим, что является функцией только от x, обозначим эту функцию через .

Мы должны разбить задачу на два случая: случай, в котором , и случай, в котором .

Случай 1:

[править | править код]

Используя формулу сложения для группы , мы получим:

Заметим, что это вычисление невозможно, если предположение о неравенстве не выполняется.

Мы теперь можем сузить выбор координаты x для до двух возможностей, а именно — положительного и отрицательного случаев. Используя координату y, определяем, который из двух случаев имеет место.

Сначала мы покажем, что X является функцией только от x. Рассмотрим . Поскольку чётно, заменив на , мы переписываем выражение как

и имеем

Теперь, если для , то для верно равенство

для всех точек P l-кручения.

Как было упомянуто ранее, используя Y и , мы можем теперь определить, какое из двух значений ( или ) работает. Это даёт значение . Алгоритм Шуфа запоминает значения в переменной для каждого рассматриваемого простого l.

Случай 2:

[править | править код]

Предположим, что . Поскольку l является нечётным простым числом, невозможно, чтобы , а следовательно, . Из характеристического уравнения следует, что , а следовательно, что . Из этого следует, что q является квадратом по модулю l. Пусть . Вычислим в и проверим, выполняется ли . Если так, то является , в зависимости от координаты y.

Если q окажется не равным квадрату по модулю l или если равенство не выполняется для некоторого w и , наше предположение, что неверно, так что . Характеристическое уравнение даёт .

Дополнительный случай

[править | править код]

Если вспомнить, наши начальные соглашения не рассматривают случая . Поскольку мы предположили, что q нечётно, и, в частности, тогда и только тогда, когда имеет элемент порядка 2. По определению сложения в группе любой элемент порядка 2 должен иметь вид . Таким образом тогда и только тогда, когда многочлен имеет корень в , тогда и только тогда, когда НОД.

    Ввод:
        1. Эллиптическая кривая .
        2. Целое число q для конечного поля  с .
    Вывод:
        Число точек E над .
    Выбираем множество нечётных простых чисел S, не содержащее p, такое, что  
    Примем , если НОД, иначе принимаем .
    Вычисляем многочлен деления . 
    Все вычисления в цикле ниже осуществляются в кольце 
    Для  выполняем:
        Пусть  — единственное целое  такое, что  и .
        Вычисляем ,  и .   
        Если   то
            Вычисляем .
            для  выполняем:
                если  то
                    если  то
                        ;
                    иначе
                        .
        иначе если q является квадратом по модулю l  то 
            вычисляем w с 
             вычисляем 
            если   то
                
            иначе если  то
                
            иначе
                
        иначе
            
    Используем китайскую теорему об остатках для вычисления t по модулю N из уравнения , где .
    Выводим .

Большинство вычислений заключаются в вычислении и , для каждого простого числа , то есть вычислении , , , для каждого простого числа . Вычисления включают возведение в степень в кольце и требуют умножений. Поскольку степень равна , каждый элемент в кольце является многочленом степени . По теореме о распределении простых чисел имеется около простых чисел размера , что даёт для значение , и мы получаем . Таким образом, каждое умножение в кольце требует умножений в , что, в свою очередь, требует, битовых операций. В общей сложности число битовых операций для каждого простого числа равно . Если принять, что это вычисление требуется провести для каждого из простых чисел, полная сложность алгоритма Шуфа становится . Использование быстрых операций с многочленами и целочисленной арифметики сокращает это время до .

Улучшения алгоритма Шуфа

[править | править код]

В 1990-х годах Ноам Элкис, а затем А. О. Л. Аткин[англ.] придумали улучшения базового алгоритма Шуфа путём ограничения множества простых чисел до чисел определённого вида. Эти числа стали называться простыми Элкиса и простыми Аткина соответственно. Простое число называется простым Элкиса, если характеристическое равенство разложим над , а простые Аткина — это простые, не являющиеся простыми Элкиса. Аткин показал как комбинировать информацию, полученную из простых Аткина, с информацией, полученной из простых Элкиса, чтобы получить эффективный алгоритм, который получил название «Алгоритм Шуфа — Элкиса — Аткина[англ.]». Первая задача — определить, данное простое является простым Элкиса, или Аткина. Чтобы это получить, используем модулярные многочлены, которые возникают при изучении модулярных форм и интерпретации эллиптических кривых над полем комплексных чисел как решёток. Как только мы определим, какой случай мы имеем, вместо использования многочленов деления[англ.] мы можем работать с многочленами, имеющими меньшие степени по сравнению с многочленами деления: вместо . Для эффективной имплементации используются вероятностные алгоритмы поиска корней, что делает алгоритм алгоритмом Лас-Вегаса, а не детерминированным алгоритмом. При эвристическом предположении, что примерно половина простых чисел, не превосходящих , являются простыми Элкиса, это даёт алгоритм, который эффективнее алгоритма Шуфа, и ожидаемое время работы этого алгоритма равно , если использовать обычную арифметику, и , если использовать быструю арифметику. Следует заметить, что это эвристическое предположение верно для большинства эллиптических кривых, но не известно для общего случая, даже при верности обобщённой гипотезы Римана.

Имплементации

[править | править код]

Некоторые алгоритмы были имплементированы на C++ Майком Скоттом и доступны в исходном коде. Имплементация абсолютно свободная (никаких условий, никаких ограничений), но использует библиотеку MIRACL, которая распространяется под лицензией AGPLv3.

Примечания

[править | править код]
  1. Хотя, в статье ECDSA написано следующее: Алгоритм Скоофа является достаточно неэффективным на практике для значений p, которые действительно представляют интерес, то есть p > 2160.
  2. Точку mP, равную m-кратному сложению точки P в аддитивной группе точек эллиптической кривой, называют скалярным произведением точки на число m, а сами точки mP — скалярными кратными точки (Рыболовлев 2004). В книге Тиборга (ван Тилборг 2006) то же понятие называется скалярным кратным.

Литература

[править | править код]
  • R. Schoof. Elliptic Curves over Finite Fields and the Computation of Square Roots mod p // Math. Comp.. — 1985. — Т. 44, вып. 170. — С. 483–494.
  • R. Schoof. Counting Points on Elliptic Curves over Finite Fields // J. Theor. Nombres Bordeaux. — 1995. — Вып. 7. — С. 219–254.
  • Gregg Musiker. Schoof's Algorithm for Counting Points on . — 2005.
  • V. Müller. Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. — Saarbrücken: Universität des Saarlandes, 1991. — (Master's Thesis).
  • Andreas Enge. Elliptic Curves and their Applications to Cryptography: An Introduction. — Dordrecht: Kluwer Academic Publishers, 1999.
  • Lawrence C. Washington. Elliptic Curves: Number Theory and Cryptography. — New York: Chapman & Hall/CRC, 2003. — Т. 50. — (Discrete Mathematics and its applications). — ISBN 978-1-4200-7146-7.
  • Neal Koblitz. A Course in Number Theory and Cryptography. — Second edition. — Springer-Verlag, 1994. — Т. 114. — (Graduate Texts in Mathematics). — ISBN 0-387-94293-9.
  • Х. К. А. ван Тилборг. Основы криптологии. — Москва: «Мир», 2006. — ISBN 5-03-003639-3 УДК 519.6.
  • Дмитрий Рыболовлев. Использование криптографии на основе эллиптических кривых в обеспечении безопасности WEB. — 2004.