Математика/5. Математическое моделирование

Виноградова Т. А.

УМВД России по Калининградской области

Генерация эллиптических и гиперэллиптических кривых

на основе СМ-метода Дойринга

В настоящее время продолжает расти спрос на методы надёжной защиты передаваемых данных. Один из подходов к созданию процедур генерации, обмена, хранения ключей состоит в использовании проблемы факторизации больших целых чисел. Другой способ основан на проблеме дискретного логарифма (DL), состоящей в том, что в некоторых группах при относительно легком осуществлении операции возведения в степень (нахождения b = aⁿ, aG, n), обратная операция логарифмирования (отыскания числа n = log_a(b)) достаточно трудоемка. В случае конечной абелевой группы требуется, чтобы её порядок был простым либо произведением простого числа на небольшое целое.

В качестве требуемой группы можно взять множество точек абелева многообразия над конечным полем (это конечная абелева группа, сложение в которой задается посредством рациональных функций). Если группа (_q) абелева многообразия является подходящей для DL-систем, также называется подходящим. Подходящим абелево многообразие будет в случае, когда оно является многообразием Якоби (якобианом) J_C некоторой кривой С. Тогда группа J_C(_q) совпадает с группой классов _q -рациональных дивизоров кривой и сложение на J_C(_q) задается посредством сложения в группе классов дивизоров.

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

В 1986 году Эткин (A. O. L. Atkin) предложил алгоритм нахождения конечной группы, подходящей для криптографии, взяв за основу метод комплексного умножения Дойринга (M.Deuring). СМ-метод Дойринга позволяет построить гиперэллиптическую кривую рода g 2 c заданным порядком якобиана. Группа точек эллиптической кривой (кривой рода 1) совпадает с её якобианом, так что достаточно отыскать кривую с заданным порядком группы [6].

Идея алгоритма состоит в следующем: выбирается мнимое квадратичное числовое поле K и целое число w Î , такое, что = p для некоторого подходящего простого p. В этом случае w соответствует эндоморфизму Фробениуса p_р эллиптической кривой Е с комплексным умножением и кольцом эндоморфизмов . При подстановке x = 1 в характеристический многочлен эндоморфизма Фробениуса f_p(x) = (x – w)(x – ) получаем число _р-рациональных точек кривой Е. Для построения соответствующей кривой Е над _р сначала вычисляются инварианты j₁,…j_h группы классов поля K. Они и являются j-инвариантами сопряженных над K эллиптических кривых Е_j / K(j). Согласно теории комплексного умножения, инварианты являются целыми алгебраическими числами, и числовое поле K(j) представляет собой гильбертово поле классов, так что коэффициенты классового полинома H(x) = целые, и редуцированные инварианты j_(р), однозначно определяющие кривую Е_j(р) / _р, будут корнями классового полинома H_р(x) = H(x) mod p_. Путем возведения точки Р Î Е_j(р)( _р) в степеньN_p = f_p(1) определяется нужная кривая. Заметим, что идеалы р (в ) и p (в ) выбираются так, чтобы в гильбертовом поле классов H_K можно было найти идеал P | р и p был бы тотально расщеплен (это можно сделать, поскольку группа классов конечна, а из теоремы Чеботарёва следует бесконечность множества тотально расщепленных простых p). По теореме Дойринга, для каждой эллиптической кривой над H_K с комплексным умножением и кольцом эндоморфизмов выполняется End(E mod P) @ , так что редуцированная кривая также обладает комплексным умножением.

Естественным образом возникает вопрос построения подходящего для DL-систем якобиана кривой рода 2, поскольку для таких кривых проблема дискретного логарифма представляется весьма сложной. Этот случай представляет существенную сложность, поскольку якобиан уже нельзя отождествить с группой точек. Якобиан кривой рода 2 является группой классов дивизоров степени нуль Pic_C⁰, с другой стороны, это главно поляризованное абелево многообразие J_C размерности 2. Кроме того, он обладает структурой аналитического многообразия, являясь комплексным тором C²/L. Другими словами, имеет место изоморфизм J_C Pic_C⁰C²/L. Кольцо эндоморфизмов якобиана является максимальным порядком в СМ-поле степени 4 над полем рациональных чисел (мнимом квадратичном расширении тотально действительного числового поля).

Рассмотрим обобщение алгоритма Эткина на случай рода g = 2 [7]. Алгоритм имеет следующую структуру:

1. Нахождение классов изоморфных абелевых многообразий. Кольцо эндоморфизмов якобиана является порядком в СМ-поле K степени 2g = 4 над . Аналитическое представление зависит от комплексного представления кольца эндоморфизмов, поэтому в рассмотрение вводятся СМ-типы (если
j_i, 1 i 2g – различные вложения K в , и никакие два из них не являются сопряженными, то набор (K, Ф) = (K, {j₁,…,j_g}) представляет собой СМ-тип). Для абелева многообразия , обладающего свойством End_K() Ä @ K, существует СМ-тип (K, Ф) = (K, {j₁,…,j_g}).

1.1. Подбираются натуральное свободное от квадратов d Î , такое, что число классов поля K₀ = () равно 1 (тогда идеалы в имеют целый базис по отношению к и становится возможным задать матрицы периодов главно поляризованных абелевых многообразий с комплексным умножением на .), и a = a + b, свободное от квадратов и такое, что a ± b > 0. Поле K = K₀(i) является СМ-полем степени 4. Чтобы многообразие Якоби было простым, K / не должно быть расширением Галуа поля с группой Галуа /2 ´ /2. Выбирая пару различных несопряженных вложений j₁, j₂ поля K в , получаем СМ-тип (K, Ф) = (K, { j₁, j₂ }). Полагаем Ф(А) = {(j₁(a), j₂(a))^t, a Î А} (А – идеал). ²/Ф(А) – абелево многообразие с комплексным умножением на .

1.2. С помощью системы компьютерной алгебры осуществляется вычисление фундаментальной единицы e₀ поля K₀. Затем определяются классы идеалов кольца , содержащие идеал А и такие, что  = a , а j₁(α), j₂(α) действительны и положительны. Для них выбирается полная система представителей ; А_j = + τ_j,Im(τ_j) > 0, N(e₀) < 0, N(t_j) тотально положительна. Находятся представители всех классов изоморфных главно поляризованных абелевых многообразий над с кольцом эндоморфизмов СМ-типа (K, Ф), относящихся к идеалам А_i, и для них определяются матрицы периодов W_i Î H₂, связанные с кривыми С_i посредством решеток , соответствующих идеалам А_i из . Здесь H₂ = {z Î , z = z^t, Im z > 0} –– верхняя полуплоскость Зигеля.

2. Нахождение классовых полиномов. С помощью матриц периодов W_i вычисляются тета-константы (посредством 10-ти четных тета-констант, соответствующих матрицам периодов, можно получить полную систему инвариантов кривых рода 2, выражающихся через коэффициенты уравнения кривой). Алгебраическая система уравнений будет задаваться инвариантами Игусы (J.I.Igusa), которые выражаются в рациональных функциях через тета-константы. Эти инварианты порождают неразветвленное поле классов над двойственным полем K^*, относящимся к полю K, и являются целыми алгебраическими числами. Корни редуцированного многочлена будут соответственно инвариантами редуцированной кривой. Решая систему уравнений для каждой из кривых С_i, найдём многочлены H_K,k(X).

2.1. Вычисление тета-констант. В терминах матрицы периодов W для рода 2 они определяются следующим образом:

q (z, W) =exp(πi(n + d)^tΩ(n + d) + 2(n+d)^t(z + e));

d, e Î (/2)^g, z = 0.

2.2. Вычисление инвариантов Игусы j₁, j₂, j₃ (осуществляется посредством тета-констант, для этого вводятся значения h₄, h₁₀, h₁₂, h₁₆, связанные с модулярными формами подходящего веса.

2.3. Вычисление классовых полиномов (в отличие от случая эллиптических кривых, они имеют не целые, а рациональные коэффициенты):

H_K,1(X) = , H_K,2(X) = , H_K,3(X) = .

2.4. Переход к полиномам (X) с целыми коэффициентами.

3. Определение уравнения кривой. Для определения уравнений кривых по их инвариантам используется метод Местре (J.-F. Mestre), основанный на теории инвариантов бинарных форм. Решая систему уравнений для инвариантов, получаем коэффициенты уравнения кривых и уравнения соответствующих многообразий Якоби. Существует определенное над _p простое главно поляризованное абелево многообразие с кольцом эндоморфизмов и элементом Фробениуса w, являющееся якобианом J_C кривой С рода 2 над _p. При подстановке x = 1 в характеристический многочлен f_p(x) получаем N_p – число _p-рациональных точек якобиана. Так как обладает комплексным умножением на End() = , то можно определить элемент Фробениуса w Î . Если Dim() = 2, то N_p = f_p(1) = (1 – w_i), w_i – сопряженные с w элементы. Система редуцированных по модулю р инвариантов однозначно задаст кривую над _p.

3.1. Выбор простого числа р = (применяется пакет алгоритмической теории чисел либо более эффективный метод подходящих чисел Вейля). Зная w, получаем возможный порядок якобиана.

3.2. Нахождение инвариантов. По построению, классовые полиномы имеют линейные множители по модулю р. Инвариантам кривых над _p, соответствуют корни многочленов (X) mod р. Выбирается тройка чисел (j₁⁽ⁱ⁾, j₂^(j), j₃^(k)) Î _p³, i, j, k Î {1,…, s}, s – число классов изоморфных кривых, и помощью алгоритма Местре проверяется, будет ли она набором инвариантов кривой.

3.3. Заключительный шаг. Записывается аффинное уравнение

y² =(x), deg = 5.

Путем выбора класса дивизоров Î Pic⁰_C и проверки условия [N] = 0
выясняется, имеет ли якобиан кривой одно из возможных четырех значений порядка (N = {N_w = c_w(1) | wÎW}). Если проверка неудачна ни для одного из них, то выбирается новая тройка инвариантов или (в случае неудачи) новое р.

Отметим, что для случая рода 2 за счёт увеличения размерности усложняется процедура вычисления группы классов. Кроме того, для вычисления классового полинома требуются значения тета-констант не одного, а трёх инвариантов для каждого из классов кривых. Классовых полиномов тоже становится 3 вместо одного, и они уже будут иметь не целые, а рациональные коэффициенты. Существенную сложность представляет нахождение простого числа р, а также поиск редуцированных инвариантов (на этом шаге, в наихудшем случае, выполняется проверка всевозможных s³ троек). Более подробно некоторые из шагов алгоритма рассматриваются в [1], [3] ,[4]. Тем не менее, метод Дойринга оказывается гораздо эффективнее случайного выбора кривой.

Литература:

1. Broeker R., Lauter K. Modular Polynomials for Genus 2. [Электронный ресурс]. URL: http://eprint.iacr.org/2008/161 (дата обращения: 10.02.2012).

2. Cohen H., Frey G. Handbook of elliptic and hyperelliptic curve cryptography. Chapman & Hall/CRC, 2006.

3. Freeman D., Lauter K. Computing endomorphism rings of Jacobians of genus 2 curves over finite fields. [Электронный ресурс]. URL: http://www.arxiv.org/abs/math/0701305 (дата обращения: 10.02.2012).

4. Goren E., Lauter K. Class invariants of quartic CM fields // Annales de l'Institut Fourier. 2007. Vol. 57. No. 2. P. 457-480.

5. S. Lang. Complex Multiplication. Springler-Verlag, 1983.

6. Weng A. Elliptische Kurven und komplexe Multiplikation. Vorlesung am FB Mathematik (Manuscript), Universitaet GH Essen, 2001.

7. Weng A. Konstruction kryptographisch geeigneter Kurven mit komplexer Multiplikation. Dissertation, FB 6 Universitaet GH Essen, 2001.