А. И. Кочубинский Институт кибернетики нану




Скачать 324.09 Kb.
НазваниеА. И. Кочубинский Институт кибернетики нану
страница1/2
Дата публикации26.02.2013
Размер324.09 Kb.
ТипДокументы
uchebilka.ru > Математика > Документы
  1   2

Эллиптические кривые в криптографии


А.И.Кочубинский

Институт кибернетики НАНУ

Резюме В статье обсуждаются причины, побудившие использовать группы точек эллиптических кривых над конечным полем в криптографических целях, описываются свойства этих объектов, способы их построения и использование эллиптических кривых над конечным полем для построения надежных и эффективных криптографических алгоритмов.
Изобретение в середине семидесятых годов концепции несимметричных криптографических алгоритмов [1] и создание первых криптографических алгоритмов этого типа, пригодных к практическому использованию (протокола Диффи-Хеллмана [1] и алгоритма RSA [2]) фактически произвело переворот в практической и теоретической криптографии и позволило решать сложнейшие задачи идентификации, аутентификации, управления ключами и ряд других элегантным и достаточно простым образом. Одновременно это событие повлекло быструю алгебраизацию криптографии, вовлечение в криптографическую теорию и практику все новых алгебраических объектов. В этой статье рассказывается о криптографических применениях старого математического объекта  эллиптических кривых над конечным полем. Следует сразу сказать, что даже простая реализация новых криптографических алгоритмов требует достаточно серьезной математической подготовки. Если для реализации традиционных криптографических алгоритмов с общедоступными ключами фактически достаточно уметь выполнять деление целых чисел с остатком, то для применения новых алгоритмов надо не только уметь выполнять операции в соответствующих алгебраических структурах, но и решать другие задачи, например, находить корни уравнений над конечными полями или выполнять операции над алгебраическими числами.

Напомним, что протокол Диффи-Хеллмана служит для установления общего ключа двумя участниками информационного обмена и заключается в следующем. Два участника A и B информационного обмена выбирают общее простое конечное поле GF(p), где p  большое простое число, условливаются об общем порождающем элементе g мультипликативной группы этого поля, а затем каждый из участников выбирает свой секретный ключ (соответственно xA и xB), вычисляет открытый ключ (соответственно, вычисления выполняются в поле GF(p), т.е. по модулю простого числа p) и обмениваются открытыми ключами. После этого общий ключ K вычисляется очень просто:

.

Потенциальный перехватчик для определения ключа должен решить одно из уравнений относительно соответственно xA или xB. Задача решения уравнения вида называется задачей дискретного логарифмирования и относится к числу сложнейших вычислительных задач. Таким образом, криптографическая стойкость протокола Диффи-Хеллмана основана на невозможности за разумное время решить задачу дискретного логарифмирования в простом конечном поле при достаточно большом простом числе p. В 1985г. Т.Эльгамаль [3] предложил алгоритм вычисления и проверки цифровой подписи, стойкость которого тоже основана на сложности дискретного логарифмирования в простом конечном поле. В дальнейшем был предложен целый ряд криптографических алгоритмов (например, [4, 5]) для решения задач контроля целостности документов (цифровая подпись), идентификации, шифрования и т.д., стойкость которых определяются сложностью решения этой задачи. Иногда такие алгоритмы называются криптографическими алгоритмами экспоненциального типа. Широко известный алгоритм RSA относится к другому классу криптографических алгоритмов. В этом алгоритме базовым алгебраическим объектом является группа обратимых элементов кольца Zn, где n  целое число, являющееся произведением двух больших простых чисел Обратимыми элементами (единицами) кольца Zn являются целые числа, взаимно простые с числом n, поэтому порядок группы равен числу целых чисел, не превышающих числа n и взаимно простых с ним, т.е. равно значению функции Эйлера по определению этой функции. В данном случае . В алгоритме RSA числа p и q считаются секретными, кроме того, выбирается секретный ключ (ключ шифрования), в качестве открытого ключа (ключа расшифрования) берется обратный к секретному ключу элемент . Тогда для шифрования отрытого текста m и расшифрования криптограммы c используются уравнения , вычисления выполняются в группе , т.е. по модулю составного числа n. Секретный ключ легко вычислить по открытому ключу, если известно значение , но вычисление этого значения эквивалентно разложению числа n на простые множители. Разложение большого целого числа на простые множители (задача факторизации)  вторая классическая сложная задача теории чисел. Таким образом, стойкость криптографического алгоритма RSA основана на сложности решения задачи факторизации.

В настоящее время стойкость практически всех несимметричных криптографических алгоритмов основана на сложности решения одной из двух только что описанных задач. Попытки использовать в криптографических целях другие вычислительно сложные математические задачи (например, задачу о рюкзаке или задачу декодирования линейных кодов общего вида) пока к успеху не привели. Широкое практическое использование несимметричных криптографических систем экспоненциального и факторизационного типа привлекло внимание исследователей к созданию новых способов решения двух фундаментальных задач теории чисел, задачи дискретного логарифмирования и задачи факторизации. В результате были созданы достаточно мощные алгоритмы решения этих задачи, имеющие субэкспоненциальную сложность. Поясним, что сложность решения задачи, задаваемой входной последовательностью длиной t битов, определяется как число битовых операций , которые необходимо выполнить для получения решения. Если функция представляет собой многочлен, то такая задача имеет полиномиальную сложность и считается простой. В качестве примеров таких задач можно привести задачу возведения целого числа в степень по модулю целого числа, задачу вычисления наибольшего общего делителя двух целых чисел или задачу доказательства простоты целого числа. Если функция имеет вид , где -постоянная, то говорят, что задача имеет экспоненциальную сложность. Такие задачи считаются очень сложными и представляют наибольший интерес для криптографии, использующей несимметричные алгоритмы. В теории сложности рассматриваются функции , имеющие промежуточную скорость роста. Эти функции зависят от трех параметров и имеют вид , где . При v=0 получаем полиномиальную сложность, при v=1 имеем экспоненциальную сложность. Если же 0p и n, т.е. или . Поэтому применительно к задачам дискретного логарифмирования и факторизации экспоненциальная сложность имеет порядок роста или , а субэкспоненциальная сложность для задачи дискретного логарифмирования имеет порядок . Для задачи факторизации верна эта же формула с заменой p на n. Очевидно, что чем меньше v, тем проще в вычислительном значении задаче и, значит, практически она может быть решена для бóльших значений p и n. На данный момент самым мощным методом решения рассматриваемых задач является метод решета в полях алгебраических чисел (NFS), предложенный Дж.Поллардом [6] для задачи факторизации и перенесенный затем на задачу дискретного логарифмирования [7]. Этот метод позволяет довести значение параметра v до 1/3. О мощи этого метода говорит выполненное в августе 1999г. разложение на простые множители целого числа размером в 512 бит. Известно, что числа такого размера широко применялись на практике и до недавнего времени считались совершенно безопасными. Важно подчеркнуть, что этот алгоритм существенно использует свойства целых чисел, а именно, тот факт, что случайное целое число с достаточно большой вероятностью можно разложить на простые множители небольшого размера. Аналогичным свойством обладают и целые алгебраические числа, где существует богатый набор целых простых алгебраических чисел, имеющих небольшую норму, а также кольцо многочленов над конечным полем, где достаточно много неприводимых многочленов небольшой степени.

Наличие таких алгоритмов заставило использовать в практических криптографических системах ключи все большего размера. В настоящее время для достижения приемлемой стойкости порядка 1024 элементарных операций приходится использовать ключи размером не менее 1024 бит. При сохранении нынешних тенденций развития вычислительной техники и алгоритмической теории ключи такого размера будут безопасными до 2005г., затем длину ключа придется увеличить до 1500 бит и более. Увеличение размера ключа приводит к существенному уменьшению быстродействия несимметричных криптографических систем, которое и так не очень велико. Особенно остро эта задача стоит при реализации таких криптографических преобразований на микропроцессорах, используемых в смарт-картах. По поводу последних заметим, что сами операции с целыми числами достаточно сложно реализовать аппаратно. По этой причине пытались строить алгоритмы экспоненциального типа в конечных полях характеристики 2, поскольку операции в этих полях  это операции над многочленами с коэффициентами 0 и 1 , которые достаточно просто реализовать в аппаратном виде, однако мощный алгоритм решения задачи дискретного логарифмирования в таких полях (с тем же значением v=1/3) был разработан Д.Копперсмитом еще в 1984г. [9] и от этой идеи пришлось отказаться. Поэтому начались поиски альтернативных решений. С математической точки зрения ситуация достаточно проста. Как видно из приведенного выше описания алгоритма Диффи-Хеллмана и алгоритма RSA, эти алгоритмы дословно переносятся на произвольные конечные абелевы группы Gm порядка m. Это верно и для остальных несимметричных криптографических алгоритмов. Существует два варианта использования таких групп.

1. Если порядок группы m вычислить сложно (т.е. сложность такого вычисления по крайней мере субэкспоненциальна), то мы получаем RSA-подобные алгоритмы, в частности, собственно алгоритм RSA работает в группе Gm =, причем . Как сказано выше, вычисление значения функции Эйлера эквивалентно факторизации числа n.

2. Возьмем в Gm циклическую подгруппу , порожденную некоторым элементом .Если порядок этой циклической подгруппы легко вычисляется (этот порядок является делителем числа m) , но решение уравнения , относительно x, 1< x<n, имеет экспоненциальную сложность, то в этой циклической подгруппе можно строить криптографические системы экспоненциального типа. В этом случае будем считать, что группа Gm и есть циклическая группа порядка m.

Вопрос заключается в выборе группы Gm. В произвольной циклической группе Gm задачу дискретного логарифмирования можно решить за операций, например, с помощью метода Шэнкса. Это метод заключается в составлении двух список размером t= каждый. Первый список состоит из пар и отсортирован по второй компоненте. Второй список состоит из пар вида и тоже отсортирован по второй компоненте. Такая упорядоченность списков позволяет легко найти две пары с равными вторыми компонентами, т.е. и с . Тогда по модулю m. Поэтому группа должна допускать только алгоритмы решения задачи дискретного логарифмирования, порядок сложности которых не меньше , и не допускать алгоритмов субэкспоненциальной сложности. Аналогичные требования предъявляются к RSA-подобным криптографическим алгоритмам. Второе принципиально важное условие  групповая операция должна быть простой в реализации. Третье условие построение групп должно быть не очень сложным и их должно быть достаточно много для того, чтобы построение самих групп и вычисление их параметров не превратилось в сложную задачу. Групп, пригодных для создания RSA-подобных систем, до сих пор не найдено. Что касается криптографических алгоритмов экспоненциального типа, то здесь вспомнили о давно известном математическом объекте  группе точек эллиптической кривой, определенной над конечным полем. Эти группы обладают замечательными свойствами:

  1. порядок этих групп вычисляется достаточно просто; Р.Схоф [11] доказал, что сложность вычисления порядка группы точек эллиптической кривой имеет полиномиальную сложность, этот результат чисто теоретический, но впоследствии были построены достаточно эффективные практические алгоритмы построения эллиптических кривых и вычисления их порядка;

  2. отсутствуют субэкспоненциальные алгоритмы решения задачи дискретного логарифмирования в циклических подгруппах этих групп; на эллиптических кривых нет аналогов простых чисел или неприводимых многочленов; как мы видели, именно наличие таких элементов играет ключевую роль в построении субэкспоненциальных алгоритмов; это свойство позволяет на практике использовать ключи сравнительно небольшого размера, например, для обеспечения стойкости порядка 1024 достаточно взять ключ размером всего 160 бит, а ключ размером 320 бит эквивалентен по стойкости ключу обычного алгоритма длиной около 5600 бит. Это позволяет реализовывать очень стойкие и в то же время достаточно быстрые криптографические алгоритмы даже на смарт-картах.

  3. групповая операция достаточно проста; правда, это верно только в отношении эллиптических кривых, определенных над конечным полем характеристики 2, использование поля GF(p) при большом простом целом p никаких преимуществ не дает и поэтому в дальнейшем будем рассматривать только эллиптические кривые над полем GF(2m), которое называется базовым полем;

  4. над каждым конечным полем существует много эллиптических кривых и отвечающих им групп;

  5. существуют простые необходимые и достаточные условия, которые гарантируют хорошие криптографические качества эллиптической кривой.

Впервые криптографические алгоритмы в группах точек эллиптических кривых были предложены независимо друг от друга Н.Коблицем [9] и В.Миллером [10] в 1985г. Первоначально эти алгоритмы казались весьма экзотическими и далекими от практического применения, но в начале девяностых годов был получен ряд теоретических результатов, доказывающих высокую стойкость новых алгоритмов, стала ясной и возможность эффективного выполнения операций в этих группах. В настоящее время эта область криптографии активно развивается и достигла такого уровня, что эллиптические алгоритмы стали включать в проекты криптографических стандартов.

В алгебраической геометрии эллиптическая кривая определяется как гладкая алгебраическая кривая рода 1 вместе с выделенной точкой О на ней. Одна из центральных теорем алгебраической геометрии, теорема Римана-Роха, позволяет доказать, что каждая эллиптическая кривая над конечным полем F=GF(2m) является множеством пар элементов (x,y) основного поля, которые являются решениями несингулярного канонического уравнения Вейерштрасса вида



либо вида



при этом выделенная точка О будет бесконечно удаленной точкой. Второе уравнение определяет суперсингулярную кривую. Первоначально предлагалось использовать в криптографических целях именно такие кривые, поскольку вычисления на них особенно просты, но, как мы увидим ниже, эти кривые не следует использовать в криптографических алгоритмах. Поэтому мы будем рассматривать только несуперсингулярные эллиптические кривые Обозначим такую эллиптическую кривую E=E/F Несингулярность уравнения Вейерштрасса означает, что стоящий в правой части кубический многочлен не имеет кратных корней или, что эквивалентно, дискриминант этого кубического многочлена . В этом случае существует обратный элемент , который называется j-инвариантом эллиптической кривой. Это название связано с тем, что если две кривые изоморфны, то их j-инварианты равны. Обратное верно в алгебраически замкнутых полях. Вообще следует сказать, что алгебраически замкнутое поле  естественная область определения эллиптической кривой Это важно не только в чисто теоретическом плане, но с практической точки зрения. Если кривая определена над конечным полем GF(2m), то алгебраически замкнутое поле, содержащее все точки эллиптической кривой есть объединение всех расширений этого конечного поля, т.е. . Важно помнить, что даже в том случае, когда коэффициенты уравнения, определяющего эллиптическую кривую принадлежат основному полю, она содержит бесконечное число точек, просто алгоритмы строятся на конечной кривой, координаты точек которой принадлежат основному полю. Такая конечная кривая обозначается E(F). Если обозначить через число точек эллиптической кривой, лежащих в поле , то аналог производящей функции вида



называется дзета-функцией эллиптической кривой. Аналогичная функция определена для любых алгебраических многообразий. Одна из центральных теорем алгебраической геометрии, теорема Вейля, утверждает, что такая дзета-функция есть рациональная функция. В случае эллиптической кривой эта теорема принимает следующий вид (этот частный случай был доказан Хассе).

Теорема Дзета-функция эллиптической кривой имеет вид

, (1)

где , а параметр a определяется из соотношения N=q+1-a, N=N1, причем и квадратное уравнение в числителе имеет два сопряженных корня и . Кроме того, .

Эта теорема имеет не только теоретическое, но и большое практическое значение. Именно на основе этой теоремы построены все известные методы вычисления порядка эллиптической кривой над большими полями В частности, из этой теоремы следует очень важное неравенство Хассе, а именно, число точек эллиптической кривой N=N1 удовлетворяет неравенству

.

Для каждого числа из этого диапазона существует эллиптическая кривая, причем имеется 2(q-1) неизоморфных кривых. Таким образом, при фиксированном основном поле существует очень много эллиптических кривых.
С каждой гладкой алгебраической кривой связывается некоторая группа. Особенность эллиптических кривых состоит в том, то элементы связанных с ними групп можно отождествить с точками самих кривых, поэтому можно говорить о группе точек эллиптических кривых. В силу этого мы получаем простое и естественное представление элементов такой группы и интуитивно понятное определение групповой операции. По традиции групповая операция на эллиптических кривых обозначается аддитивно и говорят о сложении точек эллиптической кривой. Нейтральным элементом этой группы служит бесконечно удаленная точка О, т.е. для любой точки P(x,y)E/F с координатами (x,y) выполняется P+O=O+P=P. Обратной к точке P(x,y) явятся точка –P(x,y)=Q(x,x+y), т.е. P+Q=O.

Сумма двух разных точек R(x3,y3)= P(x1,y1)+ Q(x2,y2), PO, QO, P-Q определяется как точка с координатами



Если , то , где



Все эти формулы в том случае, когда эллиптическая кривая определена над полем действительных чисел, допускают простую геометрическую интерпретацию и становятся интуитивно понятными. Для получения суммы двух разных точек проводится секущая через точки P и Q, находится третья точка пересечения секущей с кривой, эта точка отражается относительно оси абсцисс, полученная точка и есть сумма точек P и Q. Сказанное иллюстрирует классический рисунок, приведенный на этой странице. При удвоении точки (вычислении точки 2P) вместо секущей используется касательная, проходящая через точку P. Обратная точка – это точка, симметричная относительно оси абсцисс. Заметим, что бесконечно удаленная точка лежит в направлении положительного направления оси ординат. Выписанные выше формулы сложения точек и удвоения точки представляют собой аналитическое выражение приведенных геометрических соображений. Сумма точек обозначается , эта операция называется скалярным произведением , она аналогична операции возведения в степень в простом конечном поле. Эта операция естественным образом распространяется на все целые числа: если n<0, то nP=(-n)(-P), 0P=O. В последней формуле в левой части стоит целое число 0, а в правой части  нулевой элемент группы точек эллиптической кривой, т.е. бесконечно удаленная точка. Формулы сложения показывают, что координаты суммы двух точек выражаются через координаты слагаемых рационально, поэтому если координаты слагаемых принадлежат основному полю, то и сумма этих точек принадлежит этому же полю. Это свойство и позволяет говорить о конечной группе точек и строить в этой группе криптографические алгоритмы. Эти формулы показывают также, что операция в группе точек эллиптической кривой достаточно проста и эффективность ее выполнения определяется эффективностью вычислений в конечных полях характеристики 2. Выполнение последних намного эффективнее по сравнению с вычислениями в простых полях и, что немаловажно, сравнительно просто реализуются в аппаратном виде. Самая сложная в вычислительном отношении операция в формулах сложения  вычисление обратного элемента. Используя так называемое проективное представление точек эллиптической кривой, можно избавиться от этой операции, правда, за счет некоторого увеличения числа других операций. Вообще говоря, имеется много вариантов выполнения операций в конечных полях и на эллиптических кривых, зависящих от выбора базиса конечного поля и представления точек кривой, что дает возможность выбора, наилучшим образом подходящего в каждом конкретном случае. Операция скалярного умножения выполняется с помощью алгоритмов, вполне аналогичных широко известным алгоритмам возведения в степень, которые обычно применяются при реализации обычных криптографических алгоритмов. Кроме того, есть и специфические алгоритмы вычисления скалярного произведения, применимые к определенным классам кривых, например, использующие разложения целых чисел в группах эндоморфизмов эллиптических кривых.

Для построения криптографических алгоритмов выбираются эллиптические кривые, порядок которых делится на большое простое число u, строится циклическая подгруппа , где ^ P  точка эллиптической кривой, имеющая порядок u (т.е. uP=O). Тогда задача дискретного логарифмирования в группе точек эллиптической кривой заключается в нахождении целого числа n, 1<n<u удовлетворяющего уравнению для данной точки QO. Выше уже говорилось, что для решения этой задачи известны алгоритмы только экспоненциальной сложности.

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

y2 + xy = x3 + x2 + 1

над полем GF(2109), порядок которой равен 324518553658426701487448656461467 (108 бит). Задача была решена за 4 месяца с помощью 9500 компьютеров, использовался описанный выше метод Шэнкса. Выполненного объема вычислений хватило бы на решение 50 задач факторизации 512-битовых чисел. Для решения аналогичной задачи в поле GF(2163) с использованием той же вычислительной техники и точно такого же алгоритма потребовалось бы примерно 40 000 000 лет.

Для использования в криптографических целях групп точек эллиптических кривых надо уметь эти группы строить и, в первую очередь, иметь возможность вычислять порядок эллиптических кривых, т.е. определять число точек, составляющих эти кривые. Задача построения эллиптических кривых решается более сложными методами по сравнению с вычислением параметров криптографических систем в простых конечных полях. В настоящее время известны и практически применяются три способа построения эллиптических кривых и вычисления их порядка. Во всех трех методах ключевую роль играет соотношение (1).Например, если разложить в ряд по степеням T логарифм дзета-функции и сравнить коэффициенты при одинаковых степенях полученного ряда и исходного ряда, определяющего дзета-функцию, то получим соотношение

.

Это соотношение дает возможность по значению вычислить значения для всех . Величины =образуют так называемую последовательность Люкá и для их вычисления используются простые рекуррентные соотношения:



Отсюда следует самый простой способ построения эллиптической кривой и определения ее порядка.

Выберем небольшое конечное поле ^ GF (2l) и в качестве базового конечного поля возьмем расширение этого небольшого поля степени k, т.е. базовое поле имеет вид GF(2m), m=kl для некоторого k. Для каждого допустимого значения w порядка кривой над GF(2l) вычислим величину  порядок некоторой эллиптической кривой над полем ^ GF(2m). Допустимые значения w определяются неравенством Хассе, . Перебор значений w продолжаем до тех пор, пока не найдем такое значение N, которое содержит большой простой делитель. Порядок эллиптической кривой в криптографических применениях должен удовлетворять также дополнительному условию, о котором речь пойдет ниже. Теперь перебором по парам (a,b), , b0 остается найти эллиптическую кривую над малым полем, имеющую выбранный порядок w, число точек кривой над малым полем легко найти полным перебором.

Этот метод настолько прост, что не требуется много места для того, чтобы привести пример построения эллиптической кривой. Возьмем небольшое поле GF(28) и построим эллиптическую кривую над расширением этого небольшого поля степени k=23 т.е. над полем GF(2184). Область перебора в данном случае есть интервал (226,288), при w=230 находим

,



Далее,

,

где



 простое число. Перебором находим, что порядок w=230 над небольшим полем имеет эллиптическая кривая



Разумеется, 2 и 22  не целые числа, а сокращенная запись элементов поля ^ GF(28), например, 2 – это элемент поля (00000010). Следовательно, полученная эллиптическая кривая, если ее рассматривать над полем GF(2184), имеет порядок N, содержащий простой множитель u .

Этот метод позволяет строить эллиптические кривые только в расширениях малых полей, т.е. применим не ко всем полям, но главный его недостаток состоит в том, что он дает небольшое множество эллиптических кривых, Так, для m=168 вообще нет кривых, пригодных для криптографических применений. Однако этот метод вполне пригоден для получения начального набора эллиптических кривых для экспериментальных целей.

Второй метод  метод комплексного умножения, более универсален. В этом методе существенно используется кольцо эндоморфизмов эллиптической кривой. Эндоморфизмом эллиптической кривой называется отображение кривой в себя, сохраняющее точку О. Эндоморфизмом является, например, отображение , т.е. скалярное умножение точки на целое число. Поэтому кольцо целых чисел вкладывается в кольцо эндоморфизмов. Если кольцо эндоморфизмов строго больше кольца целых чисел, говорят, что эллиптическая кривая имеет комплексное умножение. Этот термин восходит к эллиптическим кривым над полем комплексных чисел, где эндоморфизм, отличный от умножения на целое число, действительно является умножением на комплексное число. Все кривые над конечными полями имеют комплексное умножение. Если кривая не суперсингулярна, то кольцо эндоморфизмов изоморфно порядку мнимого квадратичного поля с дискриминантом d<0, определяемым из соотношения

, (2)

где  максимальный квадрат, делящий правую часть этого соотношения. Порядок мнимого квадратичного поля есть множество , где . Примером эндоморфизма, не эквивалентного ни одному из эндоморфизмов [n], является эндоморфизм Фробениуса

.

Из сформулированной выше теоремы следует, что эндоморфизм Фробениуса удовлетворяет в кольце эндоморфизмов квадратному уравнению

, (3)

где a взято из соотношения (1) и называется следом эндоморфизма Фробениуса. Из теоремы Хассе следует, что знание следа эндоморфизма Фробениуса эквивалентно знанию порядка эллиптической кривой. Из (2) видно, что , поэтому в порядке квадратичного поля простое число 2 раскладывается на произведение двух главных простых идеалов, (что возможно только при выполнении сравнения ), при этом . Поэтому след эндоморфизма Фробениуса (и порядок кривой) можно найти, если известен один из главных идеалов. Для решения этой задачи есть старый и очень эффективный алгоритм Корнакьи. Этот алгоритм вычисляет порождающий элемент главного идеала по величине , где b  решение сравнения , при этом одновременно определяются величины и . Поэтому порядок кривой равен . Из сказанного ясно, что перебирая допустимые значения дискриминанта и проверяя отвечающие им значения порядка эллиптической кривой можно найти порядок, отвечающий заданным требованиям. Следующий этап  построение эллиптической кривой, имеющей вычисленный порядок. Для этого достаточно вычислить ее j-инвариант. Известно, что j-инвариант является корнем уравнения Гилберта. Поэтому сначала строится этот многочлен. Для этого используется изоморфизм между группой классов эквивалентности идеалов порядка мнимого квадратичного поля и группой приведенных бинарных квадратичных форм дискриминанта d, т.е. бинарных квадратичных форм таких, что НОД(a,b,c)=1 и , a, b, c – целые числа. Число различных значений j-инварианта делит порядок группы . Для небольших значений дискриминанта группу легко найти прямым перебором. По элементам этой группы строится многочлен Гильберта. Коэффициенты этого многочлена  целые числа, но для их вычисления используются комплексные ряды, поэтому для получения правильного ответа вычисления надо проводить с большой точностью, не менее 100 десятичных знаков. Для сокращения объема вычислений обычно применяют другие многочлены, корни которых выражаются известным образом через j-инвариант, что дает возможность затем вычислить собственно j-инвариант. Теперь, наконец, мы имеем возможность вернуться в основное конечное поле. Для этого коэффициенты многочлена Гильберта приводятся по модулю 2 и корни полученного многочлена над полем являются j-инвариантами неизоморфных эллиптических кривых с вычисленным ранее порядком. Любой из этих корней можно использовать для построения эллиптической кривой. По этому описанию можно судить о характере и трудоемкости вычислений. На практике этот метод весьма быстро приводит к результату. Хотя этот метод позволяет строить только эллиптические кривые, которым отвечает небольшой дискриминант, все же набор таких кривых достаточно велик и вполне достаточен для практических нужд. Описание этого метода приводится в [12].

Третий метод построения эллиптических кривых по существу самый логичный, мы выбираем наугад эллиптическую кривую и вычисляем ее порядок до тех пор, пока не найдем кривую с нужными свойствами. Как уже говорилось, Р.Схоф предложил полиномиальный алгоритм определения порядка произвольной эллиптической кривой над простым конечным полем нечетной характеристики. Метод Схофа заключается в рассмотрении соотношения (3) над подгруппах эллиптической кривой, состоящих из точек с l-кручением, т.е. таких точек P, что lP=O, для набора простых чисел l. Заметим, что элементы группы кручения принадлежат расширению основного поля, а не самому этому полю. В этом случае соотношение (3) принимает вид

, (4)

где , . Для небольших значений l значение можно найти простым перебором, при этом для проверки соотношения (4) вместо затруднительных вычислений в расширениях исходного поля можно использовать существенно более простые вычисления в кольце многочленов за счет использования так называемых многочленов деления, которые вычисляются рекуррентно. Если такие значения удается найти для такого набора простых чисел, что их произведение превышает , то величину a (и порядок кривой) легко вычислить с помощью китайской теоремы об остатках. Этот метод не нашел практического применения в силу того, что степени многочленов деления растут очень быстро и поэтому вплоть до недавнего времени этот способ реализовать было невозможно. Однако за последние годы этот алгоритм был перенесен на интересующие нас поля характеристики 2 и был существенно усовершенствован и дополнен в работах [13-15] и др. Суть этих усовершенствований заключается в замене многочленов деления их делителями, имеющими меньшую степень. Очень удачный метод нахождения таких многочленов с помощью вычисления для каждого простого числа особой кривой, изогенной данной, предложен Р.Лерсьером. Сейчас этот алгоритм считается эффективным методом вычисления порядка случайной эллиптической кривой. Основные вычислительные затраты, помимо упомянутых выше операций в кольце целых чисел для проверки соотношения (4), связаны с решением больших систем линейных или квадратных уравнений над конечными полями. В целом можно сказать, что существуют эффективные методы вычисления эллиптических кривых, пригодных для криптографических применений, хотя технически соответствующие алгоритмы сложнее по сравнению с алгоритмами построения криптографических систем над простыми конечными полями.

Стойкость криптографических систем, определенных на эллиптических кривых, определяется сложностью решения задачи дискретного логарифмирования в группе ее точек, т.е. сложностью решения уравнения относительно n, где точки P и Q принадлежат одной циклической подгруппе. Как и в любой конечной абелевой группе, эту задачу можно решить за элементарных операций. Выше уже говорилось, что в этой группе невозможно построить субэкспоненциальные алгоритмы решения этой задачи на тех принципах, использование которых привело к успеху в случае конечных полей. В 1993г. А.Менезес, Т.Окамото и С.Вэнстоун [16] показали, что эта задача сводится к задаче дискретного логарифмирования в некотором расширении исходного конечного поля. т.е. за полиномиальное время можно построить соответствующий изоморфизм.
  1   2

Добавить документ в свой блог или на сайт

Похожие:

А. И. Кочубинский Институт кибернетики нану iconА. И. Кочубинский Институт кибернетики нану
Упомянутые выше стандарты были адаптированы как стандарты Украины соответственно гост 34. 310-95 и гост 34. 311-95 и действуют в...

А. И. Кочубинский Институт кибернетики нану iconБ. Е. Панченко Институт кибернетики им. В. М. Глушкова нану pr
Поведение системы некруговых отверстий в полупространстве со свободной границей

А. И. Кочубинский Институт кибернетики нану iconБ. Е. Панченко Институт кибернетики им. В. М. Глушкова нану
Высокоточное кластерное решение задачи дифракции волн сдвига на системе отверстий в полубесконечной изотропной среде с защемленной...

А. И. Кочубинский Институт кибернетики нану iconП ервое сообщение
Национальная академия наук Украины, Радиоастрономический институт нану, Институт Радиофизики и электроники им. А. Я. Усикова нану,...

А. И. Кочубинский Институт кибернетики нану iconБ. Е. Панченко Институт кибернетики им. В. М. Глушкова нану
Доказана теорема о шунтировании многозначной зависимости, позволяющая не декомпозировать отношение. Делается вывод о возможности...

А. И. Кочубинский Институт кибернетики нану iconД. М. Рябко Физико-технический учебно-научный центр нану, кафедра...
Физико-технический учебно-научный центр нану, кафедра Института кибернетики им. В. М. Глушкова

А. И. Кочубинский Институт кибернетики нану iconБ. Е. Панченко Институт кибернетики им. В. М. Глушкова нану, 03187,...
Доказана лемма о безаномальности особого реляционного отношения и теорема о безаномальности актуальной части реляционного каркаса....

А. И. Кочубинский Институт кибернетики нану iconНациональная академия наук Украины (нану) Институт проблем материаловедения...
Просим сообщить о Вашем участии в Оргкомитет в Киеве до 10 мая и о желании/нежелании получить место в гостинице с указанием ориентировочной...

А. И. Кочубинский Институт кибернетики нану iconБ. Е. Панченко Институт кибернетики им. В. М. Глушкова нан украины,...
Институт кибернетики им. В. М. Глушкова нан украины, 03187, проспект Академика Глушкова, 40

А. И. Кочубинский Институт кибернетики нану iconНациональная академия наук Украины (нану) Институт проблем материаловедения...
Первая конференция была проведена в 2008г и была посвящена 90-летию со дня рождения выдающегося ученого Г. В. Самсонова. С его именем...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<