WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

А. Г. Ростовцев Логарифмирование через поднятие Задачи вычисления логарифма в группе точек эллиптической кривой и в муль типликативной группе конечного поля положены в основу безопасности многих крип

тосистем, например, стандартов цифровой подписи РФ и США. Для логарифмирования на эллиптической кривой, обладающей группой простого порядка r, наилучшим счита ется алгоритм Полларда со сложностью O r. Для логарифмирования в конечном ( ) поле Fp наилучшим считается алгоритм решета числового поля со сложностью exp ln p ln ln p 2 c3 для c < 2. Предлагается подход к вычислению логарифмов, O ( ) основанный на использовании эллиптической кривой над числовым полем, обладаю щей достаточно большим рангом. Показано, что задача логарифмирования в конечном поле и на эллиптической кривой сводится к поднятию точки кривой в числовое поле.

1. Теоретические основы Эллиптическая кривая E(K): y2 = x3 + Ax + B,(1) заданная над числовым полем K = Q( D1, D2,..., Dm ), может быть при ведена по модулю p, если Di Fp (вместо различных Di, конечно, можно использовать одно алгебраической число). Целостное кольцо целых эле ментов поля K обладает однозначным разложением на простые идеалы.

Координаты каждой конечной точки кривой E(K) могут быть приведены к паре дробей с целыми рациональными знаменателями. Редукция кривой E(K) по модулю p определена и задает отображение : E(K) E(Fp). (2) Обратно, кривая E(Fp): y2 x3 + Ax + B (mod p)(3) может быть вложена в кривую E(K). Отображение точки Q E(Fp) в точку Q E(K) назовем поднятием точки Q из поля Fp в поле K, при этом срав нение (3) превращается равенство (1). Сумме точек E(K) соответствует сумма точек E(Fp) (обратное утверждение неверно). Поэтому задача вы числения векторного индекса на кривой E(K) соответствует задаче вычис ления индекса на кривой E(Fp) относительно гомоморфных образов обра зующих кривой E(K).

Кривая (3) допускает изоморфизмы x xu2, y yu3, A Au4, B Bu6. Таким образом, вместо одиночной кривой (3) можно рассматри «Проблемы информационной безопасности. Компьютерные системы», СПб., 2000. № 2. С. 49– вать семейство изоморфных кривых, каждая из которых может быть вло жена в соответствующую кривую E(K).

Нас будет интересовать случай бесконечной группы E(K). Отобра жение (2) определяется ядром. Пусть #E(Fp) = r — большое простое число.

Если бесконечная группа E(K) циклична с образующей P1, то Ker() = nrP1, где n Z, а точке P = kP1 на кривой E(Fp) будет соответствовать множест во точек kP1 + nrP1 на кривой E(K).

Предположим, что бесконечная группа E(K) без кручения имеет две образующих P1 и P2, и на кривой E(Fp) выполняется равенство (P2) = = s(P1). Ядро гомоморфизма включает в себя целочисленные линейные комбинации образующих, кратные r. Кроме того, в ядро входят комбина ции образующих, гомоморфный образ которых дает бесконечно удален ную точку, например, sP1 – P2, (2s (mod r))P1 – 2P2 и т. п. Тогда Ker() = n1rP1 + n2rP2 + (ms (mod r))P1 – mP2, где n1, n2 Z, m Z/pZ.

Обобщим предыдущее рассуждение на случай k образующих P1,..., Pk. Пусть на кривой E(Fp) выполняются равенства (Pk) = s1(P1) = s2(P2) = =... = sk–1(Pk–1). Тогда k k -1 k - Ker() = nrP + (ms (mod r))Pi - m (mod r) Pk, i i i i i i =1 i =1 i = где ni Z, mi Z/pZ.

Каноническая высота точки P E(Q) определяется [1] как предел h(mP) h(P) = lim,(4) m m где h(R) — длина координаты x точки R в битах, h(P) R. В соответствии с (4) длина координат точек mR растет пропорционально квадрату от m или пропорционально экспоненте от квадрата длины m. Имеет место ра h(P) венство h(P) = +. Аналогично определяется и каноническая вы O(1) сота на эллиптической кривой E(K) над конечным расширением K поля Q.

При этом имеют место равенства h( P + Q) + h( P - Q) = 2h( P) + 2h(Q) h(mP) = m2h(P).(5) Равенство (5) устанавливает связь задачи логарифмирования на эллипти ческой кривой и задачи логарифмирования в конечно порожденной под группе группы R* ненулевых вещественных чисел.

Каждая точка бесконечного порядка эллиптической кривой E(K) од нозначно определяется канонической высотой. Если P — точка кручения, то h(P) = 0. По теореме Морделла — Вейля ранг кривой E(K) конечен.

Индекс ind(R) каждой точки R E(K) может быть представлен как вектор, число координат которого равно рангу кривой. Если P1,..., Pk — образую k щие групп E(K) бесконечных порядков и R = Pi, индексы точек Pi n i i= образуют базис k-мерного Z-модуля. Поэтому индексы точек бесконечного порядка кривой E(K) образуют целочисленную решетку.

Например, эллиптическая кривая E: y2 = x3 + 17 имеет над Q ранг 2.

Образующие групп бесконечного порядка равны P1 = (2, 5) и P2 = (–2, 3), индекс точки бесконечного порядка является двумерным вектором. Точки 1466 56857 94 R1 =,- и R2 =, 169 2197 25 равны R1 = 3P1 – 2P2, R2 = 2P1 – 3P2, их индексы равны ind(R1) = (3, –2), ind(R2) = (2, –3). При переходе к расширению K = Q( -3) кольцо целых 1 + - имеет вид Z[], =, кривая обладает комплексным умножением на число, задаваемое парой функций (x, y) (2x, –y). Поскольку число не является рациональным, то к паре образующих присоединяются (по край ней мере) еще две точки (–22, 3) и (22, 5). Используя сравнения по моду лям различных простых чисел p ± 1 (mod 6), можно показать, что точки (2, 5), (–2, 3), (–22, 3) и (22, 5) кривой E(K) линейно независимы над Z.

По определению канонической высоты выполняется равенство h(P) = h(- P). Поэтому если P и Q — образующие групп бесконечного по рядка, то h(P + Q) = h( P - Q) = h(P) + h(Q).

Следовательно, канонические высоты точек бесконечного порядка эллиптической кривой E(K) образуют решетку, базис которой состоит из канонических высот образующих групп бесконечного порядка.

Пусть H = (hij) — квадратная матрица размера k k (k — ранг кривой E(K)), где h(Pi + Pj ) - h(Pi ) - h(Pj ) hij = и P1,..., Pk — образующие циклических групп бесконечных порядков. То гда имеет место равенство h(n1P1 + n2 P2 +...+nk Pk ) = nHnT,(6) где n = (n1,..., nk) — векторный индекс точки P = n1P1 +... + nkPk. Выраже ние (6) устанавливает связь между канонической высотой произвольной точки кривой E(K), и ее индексом.

2. Использование поля характеристики Задача поднятия точки требует указания всех двоичных разрядов ко ординат точки E(K). В соответствии с (4) длина координат точки пропор циональна квадрату показателя (или экспоненте от квадрата длины пока зателя). Отсюда следует, что для k = 1 задача поднятия является сложной хотя бы потому, что перечисление всех разрядов координат требует экс поненциального времени (даже без учета сложности собственно вычисле ний). Однако, если ранг k кривой E(K) достаточно велик, то на ней суще ствует значительное количество точек с малой высотой. Ранг эллиптиче ской кривой с комплексным умножением может быть вычислен как крат ность нуля функции LE/K(s), где s = 1 в предположении, что верна гипотеза Берча и Свиннертона-Дайера [1].

Определим вес w = w(P) точки P E(K) на точечной решетке как сумму абсолютных значений координат векторного индекса. Если ind(P) = = (n1,..., nk), то w(P) = |n1| +... + |nk|. Число точек Nw с весом ровно w в со ответствии с известным результатом из комбинаторики равно k(k + 1)...(k + w - 1) k + w - 1.(7) Nw = = w w!

Если k = O(w), то число точек с весом не более w можно оценить числом точек с весом w.

Оценим сложность нахождения индекса точки P E(K), k P = Pi,если ранг кривой E(K) равен k и вес точки P не превышает w.

n i i = Из (6) следует, что h(P) = O(kw2 ). Для нахождения индекса точки P E(K) нужно к точке P прибавлять точки ±Pi до тех пор, пока не будет получена нулевая каноническая высота. После каждого сложения высота должна уменьшаться. Число сложений точек в ходе вычисления индекса точки P равно O(kw). Наиболее трудоемкой арифметической операцией при сло жении точек является умножение. Сложность умножения целых чисел ме тодом Шенхаге — Штрассена равна O(kw2log(kw2)). Пусть поле K является конечным расширением поля Q, полученное присоединением квадратных корней из небольших по абсолютной величине чисел D1,..., Dm, причем все Di являются квадратичными вычетами по модулю p. Координаты точки представляют собой многочлены от 2m переменных. Сложность умноже ния координат равна O(2mkw2log(kw2)). Такую же оценку имеет и слож ность сложения точек. Поэтому сложность нахождения индекса точки P E(K) равна S =O(2mk2w3log(kw2)).

Пусть поле K является конечным расширением поля Q, полученное присоединением квадратных корней из небольших по абсолютной вели чине чисел D1,..., Dm, причем все Di являются квадратичными вычетами по модулю p. Предположим по аналогии с теоремой Мазура [1] для E(Q), что группа кручения эллиптической кривой E(K) может иметь только гаранти рованно малый порядок, меньший чем r. Тогда в силу гомоморфизма (2) группа кручения TorsE(K) состоит из бесконечно удаленной точки, то есть все аффинные точки E(K) имеют бесконечный порядок1. Поэтому жела тельно использовать поле K, задаваемое многочленом небольшой степени.

Общий план решения показательного уравнения P = lQ на кривой E(Fp) может иметь следующий вид.

1. Поднять не менее k аффинных точек Ri = aiP + biQ для некоторых ai, bi, из поля Fp в поле K, определив при этом вид поля K. Не все ai и не все bi должны быть нулевыми. Найти образующие P1,..., Pk бесконечных цик лических групп E(K).

2. Найти индексы точек Ri в группе E(K) минимизацией канонической вы соты.

3. Привести каждую из точек Ri и образующие E(K) по модулю p.

4. Методом гауссова исключения выразить логарифм точки P через лога рифм точки Q.

Поднятие на шаге 1 должно обеспечивать минимальный вес точки.

Если мощность множества точек веса не более w близка к r, то с вероятно стью, близкой к 1, каждую точку кривой E(Fp) можно поднять так, что ее вес не будет превышать w.

Найдем вначале сложность шагов 2–4. Заменим в (7) факториалы по формуле Стирлинга и приравняем log Nw и log r в предположении, что k w. Получим log r = log Nw = (k + w) log(k + w) – k log k – w log w 2k log 2.

Теоретически можно было бы в качестве поля K использовать простое трансцен дентное расширение Fp(t) поля Fp, что облегчило бы поднятие точки. Однако в этом случае группа кручения оказалась бы очень богатой, так как она содержала бы все ко нечные группы E(Fq) для q {p2, p3, …}. Поэтому указанный ниже метод логарифми рования оказывается непрактичным.

Тогда log2 r k =.

Для нахождения логарифма l нужно найти O(k) индексов точек Ri, слож ность этой операции (шаг 2) равна O(2mk3w3log(kw2)) = O(2m(log r)6 log log r).

Сложность шага 3 оценивается многочленом степени не более 6 от log r, сложность шага 4 оценивается многочленом степени 3 от log r. Итоговая сложность вычисления логарифма на кривой E(Fp) равна S = O(2m(log r)6 log log r) + O(log r)(S1 + S2) где S1 — сложность поднятия точки из поля Fp в поле K так, чтобы вес поднятой точки был минимален, S2 — сложность нахождения образующих Pi. Если наибольшая из сложностей S1 и S2 полиномиальна (субэкспонен циальна, экспоненциальна), то и задача логарифмирования может быть решена указанным методом с полиномиальной (соответственно субэкспо ненциальной, экспоненциальной) сложностью. Существование эллиптиче ских кривых над Q неограниченно большого ранга, вытекает из гипотезы Таниямы [1].

Таким образом, задача дискретного логарифмирования на эллипти ческой кривой E(Fp) полиномиально сводится к поднятию точки кривой из поля Fp в числовое поле K и к нахождению множества образующих кривой E(K). Поднятие выполняется наиболее просто, если вес поднятой точки будет минимален.

Метод поднятия точки из Fp в K неочевиден. Если определить вес w точки на решетке ранга k образующих бесконечного порядка кривой E(Q) как наибольшее из абсолютных значений координат, то количество точек с весом не более w, равно числу точек k-мерного параллелепипеда с центром в нуле и длиной стороны 2w и составляет k2w. В этом случае можно оста ваться в рамках поля Q. Если задача поднятия точки в поле Q имеет поли номиальную или субэкспоненциальную сложность, то снижение асимпто тической сложности задачи логарифмирования по сравнению с алгорит мом Полларда происходит при ранге не менее 3. Таких кривых достаточно много [2].

Аналогичный подход может быть использован и для логарифмиро вания в мультипликативной группе простого поля. Для решения показа тельного уравнения au b (mod p) выполняется следующая последователь ность действий.

1. Выбирается эллиптическая кривая E(K) вида y2 = x3 + Cx2 + kp, Ck 0, которая в результате редукции по модулю p дает особую кубику.

2. С помощью вычислимого в обе стороны изоморфизма особой кубики и группы Fp* находятся точки кубики, соответствующие элементам a и b.

3. Находится ранг кривой E(K) и ее образующие.

4. Далее задача решается так же, как и для эллиптической кривой.

Ранг эллиптической кривой E(Q) мал и обычно не превышает 14 [2].

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

Например, если длина порядка группы r равна 200 бит, то оптимальное значение ранга и веса составляют около 100. Для этого можно использо вать последовательные квадратичные расширения поля Q, полученные присоединениями квадратных корней и малых Di, являющихся квадратич ными вычетами по модулю p, или использовать кривую E(Q) достаточно большого ранга. Если кривая обладает комплексным умножением, то при соединение к полю Q квадратичного целого, определяющего комплексное умножение, приводит по крайней мере к удвоению ранга.

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

Анализ техники решения диофантовых уравнений [3], в частности, урав нений Пелля, подтверждает перспективность указанного подхода для ре шения задач логарифмирования.

Литература 1. Silverman J. H. The arithmetic of elliptic curves. — GTM, v. 106, Springer-Verlag, 1986.

2. Степанов С. А. Арифметика алгебраических кривых. — М.: Наука, 1991.

3. Zagier D. Large integral points on elliptic curves // Math. Comp., v. 48, 1987, pp. 425–436.




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.