кодирование точек эллиптической кривой

Формула изобретения

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



где а₁, а₂ , а₃, а₄ и а₆ являются элементами множества А элементов,

где А является кольцом Z/qZ целых чисел по модулю q, где q является положительным целым числом, являющимся произведением числа I разных простых чисел, строго превышающих 3, при этом I является целым числом, превышающим или равным 2, или А является конечным полем F _q, где q является показателем степени простого целого числа;

где X и Y являются координатами точек Р и являются элементами множества А, при этом способ содержит этапы, на которых:

a) определяют некоторый параметр (11) в указанном кольце А;

b) получают координаты X и Y точки Р(13) посредством применения к указанному параметру некоторой функции f(12);

при этом функция Эйлера для А удовлетворяет уравнению:

(А)mod3=1,

причем указанная функция f(12) является обратимой и детерминистической функцией, выраженной рациональной дробью в а₁, а₂, а ₃, а₄ и а₆ и в указанном параметре во множестве А и достигающей, по меньшей мере, числа d/4^I точек Р при I, равном 1 для конечного поля F_q;

c) указанную точку Р используют для применения в криптографии для шифрования, или хеширования, или подписи, или аутентификации, или идентификации.

2. Способ выполнения вычисления по п.1, в котором множество А отличается от , при этом уравнение (1) можно записать в виде:

Y²=X³+аХ+b, при а=а₂ и b=а₆;

при этом детерминистическая функция дает координаты точки эллиптической кривой согласно следующим соответствующим уравнениям:



и



где u является параметром, определенным на этапе а), а

3. Способ выполнения вычисления по п.1, в котором q удовлетворяет формуле:

q=2ⁿ,

где n является нечетным целым числом,

при этом уравнение (1) записывают в виде:

Y²+XY=Х³ +аХ²+b, при а=а₂, b=а₆ ;

при этом детерминистическая функция дает координаты точки эллиптической кривой согласно следующим соответствующим уравнениям:



Y=uX+w²

где u является параметром, определенным на этапе а), а

w=a+u² +u.

4. Способ выполнения вычисления по п.1, в котором на этапе а) параметр u получают посредством применения функции хеширования h.

5. Способ выполнения вычисления по п.4, в котором функция хеширования является однонаправленной функцией.

6. Способ выполнения вычисления по п.1, в котором на этапе а) параметр u получают посредством применения первой функции хеширования h и второй функции хеширования h , при этом указанное криптографическое вычисление содержит применение следующей функции:

f(h)+h .G,

где f является детерминистической функцией, а

G является генератором группы точек эллиптической кривой.

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

8. Способ шифрования данных, характеризующийся тем, что указанное шифрование основано на тождестве Боне-Франклина на эллиптической кривой, допускающем операцию связывания; где тождество является числовым значением, идентифицирующим информационный объект,

при этом способ содержит этапы, на которых:

a) получают точку посредством применения к тождеству способа выполнения криптографического вычисления по п.6;

b) получают шифрованные данные, комбинируя указанную точку, произвольный параметр и данные.

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



где a₁, а₂ , а₃, а₄ и а₆ являются элементами множества А элементов,

где А является кольцом Z/qZ целых чисел по модулю q, где q является положительным целым числом, являющимся произведением числа I разных простых чисел, строго превышающих 3, при этом I является целым числом, превышающим или равным 2, или А является конечным полем F _q, где q является показателем степени простого целого числа;

где X и Y являются координатами точек Р и являются элементами множества А, при этом способ содержит этапы, на которых:

a) определяют точку Р с координатами X и Y на эллиптической кривой;

b) получают параметр посредством применения некоторой функции fi к точке Р; при этом функция Эйлера множества А отвечает следующему уравнению:

(А)mod3=1,

причем указанная функция fi является обратной функцией обратимой и детерминистической функции, выраженной рациональной дробью в a₁, а₂ , а₃, а₄ и а₆ и в указанном параметре во множестве А и достигающей, по меньшей мере, числа d/4^I точек Р при I, равном 1 для конечного поля F_q;

c) указанную точку Р используют для применения в криптографии для шифрования, или хеширования, или подписи, или аутентификации, или идентификации.

10. Способ уплотнения данных, характеризующийся тем, что предназначенные для уплотнения данные соответствуют парам данных X и Y, соответствующим координатам точек Р эллиптической кривой, удовлетворяющих следующему уравнению:



где a₁, а₂ , а₃, а₄ и а₆ являются элементами множества А элементов,

где А является кольцом Z/qZ целых чисел по модулю q, где q является положительным целым числом, являющимся произведением числа I разных простых чисел, строго превышающих 3, при этом I является целым числом, превышающим или равным 2, или А является конечным полем F _q, где q является показателем степени простого целого числа;

где X и Y являются координатами точек Р и являются элементами множества А, при этом для каждой из указанных пар данных применяют этапы а)-с) способа выполнения криптографического вычисления по п.9, и

указанные пары данных представляют собой параметры, соответственно полученные на этапе b).

11. Электронное устройство для выполнения криптографических вычислений, содержащее средства, предназначенные для применения способа выполнения криптографического вычисления по любому из пп.1-6.

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

Описание изобретения к патенту

Настоящее изобретение касается криптографической обработки сообщений, основанной на использовании точек эллиптической кривой, и, в частности, такой криптографии, которая носит детерминистический характер.

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

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

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

Однако такая обработка является сложной и занимает много времени.

Настоящее изобретение призвано улучшить эту ситуацию.

В качестве первого объекта изобретением предлагается способ выполнения криптографического вычисления в электронном компоненте, содержащий этап получения точек Р на эллиптической кривой, удовлетворяющих следующему уравнению:

где а₁, а₂, а ₃, а₄ и a₆ являются элементами множества А элементов,

где А является кольцом Z/qZ целых чисел по модулю q, где q является положительным целым числом, являющимся произведением числа I разных простых чисел, строго превышающих 3, при этом I является целым числом, превышающим или равным 2, или А является конечным полем F_q, где q является показателем степени простого целого числа;

где Х и Y являются координатами точек Р и являются элементами А,

при этом указанный способ содержит этапы, на которых:

/а/ определяют параметр (11);

/b/ получают координаты Х и Y точки Р (13) посредством применения к этому параметру некоторой функции (12);

при этом функция Эйлера для множества А удовлетворяет формуле:

(А)mod3=1,

причем указанная функция является обратимой и детерминистической функцией, выраженной рациональной дробью в a₁, а₂, а₃, а₄ и а₆ и в указанном параметре в А и достигающей, по меньшей мере, числа d/4^I точек Р при I, равном 1 для конечного поля F_q;

/с/ указанную точку Р используют для применения в криптографии для шифрования, или хеширования, или подписи, или аутентификации, или идентификации.

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

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

Кольцо А может быть кольцом RSA (от "Rivest Shamir Adieman" на английском языке). В этом случае это кольцо можно записать как Z/qZ, где q равно произведению двух простых чисел, при котором вычисление (А) затруднено.

Необходимо отметить, что функция Эйлера на кольце А является функцией, дающей число обратимых элементов в этом кольце А. В случае, когда А является конечным полем F_q, получаем:

(A)=q-1

Подставляя в цикл Z/qZ целых чисел по модулю q, где q является положительным целым числом, являющимся произведением числа I разных простых чисел, строго превышающих 3, при этом I является целым числом, превышающим или равным 2, получаем:

(А)=ppcm(p₁ - 1, р₂ - 1, , p_i - 1)

где ppcm обозначает наименьшее общее кратное, и

р_i являются I простыми числами.

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

Действительно, во множестве А функции возведения в степень 3 и 1/3 являются биективными. Следовательно, их можно записать в виде рациональных дробей и, таким образом, детерминистическую функцию f можно записать в виде рациональных дробей. Во множестве А вычисление показателя степени 1/3 является таким же, как и при вычислении показателя степени (2 (а)+1)/3. Последний является целым числом, так как (А)mod3=1. На множестве А справедливо следующее уравнение:

х ^(A)=1

Из этого уравнения выводят следующее уравнение:

(x³)^{(2 (А)+1)/3}=x^{3(2 (А)+1)/3}=x^{2 (A)+1}=x

Следовательно, можно записать:

x^{(2 (A)+1)/3}=x^1/3

Однако функция f, которая позволяет получить точку Р эллиптической кривой, содержит это возведение в степень 1/3.

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

Кроме того, в случае, когда А соответствует конечному полю F_q, детерминистическая функция f может давать, по меньшей мере, q/4 точек Р эллиптической кривой. В случае, когда А соответствует кольцу Z/qZ целых чисел по модулю q, где q является положительным целым числом, являющимся произведением числа I разных простых чисел, строго превышающих 3, при этом I является целым числом, превышающим или равным 2, детерминистическая функция f может давать по меньшей мере q/4 ^I точек Р эллиптической кривой.

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

В варианте выполнения настоящего изобретения используемая эллиптическая кривая является кривой типа Вейерштрасса или так называемой кривой характеристики р. В данном случае считают, что q отличается от 2ⁿ.

Формулу (1) можно записать:

Y²=X³+аХ+b, при а=а₂ и b=а₆.

Детерминистическая функция дает координаты точки эллиптической кривой согласно следующим соответствующим формулам:

и

где u является параметром, определенным на этапе /а/, и

где =(3а-u⁴)/(6u)

В другом варианте выполнения настоящее изобретение применяют к эллиптическим кривым характеристик 2.

В этом случае q удовлетворяет формуле:

q=2ⁿ;

где n является нечетным целым числом,

и формулу (1) записывают в виде:

Y²+XY=X³ +аХ²+b, при а=а₂ b=а₆; и

детерминистическая функция дает координаты точки эллиптической кривой согласно следующим соответствующим формулам:

Y=uX+w²

где u является параметром, определенным на этапе /а/, и

где w=a+u²+u.

В предпочтительном частном варианте n является нечетным целым простым числом. Действительно, такое n позволяет ограничить определенные атаки.

В этом контексте предпочтительно детерминистическая функция может давать по меньшей мере 2^n-2 точек Р эллиптической кривой.

Предпочтительно эту функцию можно применить к эллиптическим кривым типа Коблитца, то есть для частного случая эллиптических кривых характеристик 2, в котором b равно 1, и а принадлежит к F₂. Действительно, используя эллиптические кривые Коблитца, можно более быстро производить криптографические вычисления.

Можно предусмотреть применение этой детерминистической функции к результату функции хеширования. Так, на этапе /а/ параметр и можно получить посредством применения функции хеширования h.

В варианте выполнения функция хеширования является функцией с одним направлением. Это свойство сохраняется: функция, получаемая из комбинации детерминистической функции и функции хеширования, имеет это свойство однонаправленности.

В данном случае в конечном счете получают функцию на эллиптической кривой, которая имеет единственное направление, такую как функция хеширования. Кроме того, эта функция является устойчивой по отношению к столкновениям.

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

На этапе /а/ параметр u можно получить посредством применения первой функции хеширования h и второй функции хеширования h . Генератор группы точек эллиптической кривой обозначают G. Криптографическое вычисление может содержать применение следующей функции:

f(h)+h .G,

где f является детерминистической функцией, и

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

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

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

Третьим объектом настоящего изобретения является способ шифрования данных, при этом указанное шифрование основано на тождестве Бонеха-Франклина на эллиптической кривой, допускающем операцию сопряжения; где тождество является цифровым значением, идентифицирующим информационный объект,

при этом указанный способ содержит следующие этапы:

/а/ получают точку посредством применения к тождеству способа выполнения криптографического вычисления по п.6;

/b/ получают шифрованные данные, комбинируя указанную точку, произвольный параметр и указанные данные.

В данном случае под термином «комбинировать» следует понимать применение комбинации операций сопряжения, хеширования, операции «исключающее ИЛИ» и скалярного умножения.

Четвертым объектом настоящего изобретения является способ выполнения криптографического вычисления в электронном компоненте, содержащий этап получения точек Р на эллиптической кривой, при этом справедлива следующая формула:

где a₁, а₂, а ₃, а₄ и а₆ являются элементами множества А элементов,

где А является кольцом Z/qZ целых чисел по модулю q, где q является положительным целым числом, являющимся произведением числа I разных простых чисел, строго превышающих 3, при этом I является целым числом, превышающим или равным 2, или А является конечным полем F_q с показателем степени q простого целого числа;

где Х и Y являются координатами точек Р и являются элементами А,

при этом указанный способ содержит следующие этапы:

/а/ определяют точку Р с координатами Х и Y на эллиптической кривой;

/b/ получают параметр посредством применения некоторой функции к точке Р; при этом функция Эйлера для множества А удовлетворяет следующему равенству:

(А)mod3=1,

причем указанная функция является обратной функцией детерминистической функции, выраженной рациональной дробью в а₁, а₂, а₃, а₄ и a₆ и в указанном параметре в А и достигающей по меньшей мере числа d/4^I точек Р при I, равном 1 для конечного поля F_q;

/с/ указанную точку Р используют для применения в криптографии для шифрования, или хеширования, или подписи, или аутентификации, или идентификации.

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

Таким образом, пятым объектом настоящего изобретения является способ уплотнения данных, в котором предназначенные для уплотнения данные соответствуют парам данных Х и Y, соответствующим координатам точек Р эллиптической кривой, удовлетворяющей следующему равенству:

где а₁, а₂, a ₃, a₄ и a₆ являются элементами множества А элементов,

где А является кольцом Z/qZ целых чисел по модулю q, где q является положительным целым числом, являющимся произведением числа I разных простых чисел, строго превышающих 3, при этом I является целым числом, превышающим или равным 2, или А является конечным полем F_q с показателем степени q простого целого числа;

где Х и Y являются координатами точек Р и являются элементами множества А,

при этом для каждой из указанных пар данных применяют этапы /а/-/с/ способа выполнения криптографического вычисления согласно четвертому объекту настоящего изобретения,

причем указанные пары данных представлены параметрами, соответственно полученными на этапе /с/.

Шестым объектом настоящего изобретения является электронное устройство, содержащее средства, предназначенные для применения способа выполнения криптографического вычисления согласно первому объекту настоящего изобретения.

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

Восьмым объектом настоящего изобретения является электронная карта, содержащая электронное устройство согласно шестому и седьмому объектам настоящего изобретения.

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

Описание изобретения представлено со ссылками на фиг.1, которая иллюстрирует основные этапы криптографического вычисления согласно варианту выполнения настоящего изобретения.

Любая эллиптическая кривая на множестве А удовлетворяет следующему равенству:

где a₁, а₂, a₃, а₄ и а₆ являются элементами множества А,

и где Х и Y являются элементами множества А.

Если справедливо следующее равенство:

(А)=1mod3, (2)

где является функцией Эйлера, применяемой к множеству А, то функция возведения в степень 3 и функция возведения в степени 1/3 являются функциями, эффективно вычисляемыми за постоянное время при любых значениях, для которых их вычисляют. Это свойство позволяет получить детерминистическим путем точку Р эллиптической кривой в зависимости от некоторого параметра, при этом время вычисления не зависит от указанного параметра, к которому применяют эту детерминистическую функцию f.

В дальнейшем эта функция f будет обозначаться также f_a,b или f _a в зависимости от типа уравнения рассматриваемых эллиптических кривых.

На фиг.1 на этапе 11 показано определение параметра u, являющегося элементом рассматриваемого конечного поля F_q. Затем к этому параметру на этапе 12 применяют детерминистическую функцию f, чтобы в конечном счете детерминистическим образом получить точку Р эллиптической кривой. Все эти этапы осуществляют на кольце А, удовлетворяющем равенству (2).

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

В следующих разделах рассматриваемой эллиптической кривой является кривая Вейерштрасса над полем F _q.

В этом контексте мощность q конечного поля Галуа равна рⁿ при простом числе р, отличном от значений 2 и 3. Уравнение (1) можно записать в виде следующего уравнения Вейерштрасса:

где а и b являются параметрами эллиптической кривой, обозначенной Е_а,b.

В конечном поле А=F_q, содержащем число q элементов, где q удовлетворяет равенству (2), функция f возведения в степень 3 и функция возведения в степень 1/3 являются биекциями, эффективно вычисляемыми за постоянное время при любых значениях, по которым их вычисляют.

В этих условиях координаты Х и Y точки Р эллиптической кривой удовлетворяют следующим соответствующим равенствам:

и

где u является параметром согласно варианту выполнения настоящего изобретения, причем и принадлежит к конечному полю .

Следует отметить, что в конечном поле F_q возведение в степень ((2 (А)+1)/3 соответствует возведению в степень 1/3.

Таким образом, в случае, когда эллиптическая кривая, используемая для криптографического вычисления, является кривой Вейерштрасса, предпочтительно точки Р эллиптической кривой можно получить в зависимости от параметра и по уравнениям (4) и (5) детерминистическим образом при постоянном времени вычисления относительно параметра u.

Действительно, точка Р с координатами, удовлетворяющими равенствам (4) и (5), соответствует единственной точке эллиптической кривой по уравнению (3), так как пересечение прямой по равенству (5) с рассматриваемой эллиптической кривой (3) соответствует следующей системе уравнений:

и

Эту систему уравнений можно записать следующим образом:

Эти последние уравнения можно еще упростить следующим образом:

Таким образом, в конечном итоге эту систему уравнений можно записать:

Поскольку уравнение (10) соответствует уравнению (4), можно сделать вывод, что Р является точкой рассматриваемой эллиптической кривой,

Следовательно, точка Р, координаты Х и Y которой удовлетворяют уравнениям (4) и (5), является точкой эллиптической кривой по уравнению (3).

При этом обозначим:

- f_a,b функцию, которая приводит в соответствие с элементом точку эллиптической кривой (3).

0 не может быть входом f_a,b, в противном случае было бы возможно деление на 0. Тем не менее, поскольку нейтральный элемент группы точек эллиптической кривой нельзя получить посредством f _a,b, определяют, что 0 на f_a,b соответствует нейтральному элементу группы точек.

Функция f _a,b является детерминистической функцией, когда функция возведения в степень 3 или возведения в степень 1/3 является биективной функцией в рассматриваемом конечном поле Галуа. Можно отметить, что применение такой функции f_a,b в этих условиях приблизительно соответствует возведению в степень в конечном поле F_q.

Чтобы декодировать сообщение, которое было закодировано при помощи вычисления, произведенного в варианте выполнения настоящего изобретения, предусматривают определение одного или нескольких значений параметра u, который позволил получить данную точку Р эллиптической кривой.

Для этого в следующих разделах указано, как вычислять функцию, обратную функции f_a,b.

Предположим, что u₁ и u₂ являются двумя элементами , причем каждый из них является решением следующего уравнения:

где а, x и y являются элементами F _q.

b удовлетворяет следующему равенству:

b=y²-x³-ах

При этих условиях справедливо следующее равенство:

Действительно, прежде всего все точки P₁ с координатами (x₁, y₁), Р₂ с координатами (х₂, y₂) и Р с координатами (x, y) являются точками эллиптической кривой Е_a,b.

Кроме того, согласно уравнению (11) точки Р и P₁ находятся на прямой, определяемой следующим уравнением:

Однако, как было указано выше, поскольку q удовлетворяет равенству (2), эллиптическая кривая (3) и прямая (13) пересекаются только в одной точке. Таким образом, точки Р и P₁ соответствуют одной единственной точке.

Применив эти же рассуждения к точкам Р и Р₂ , можно сделать вывод, что точки Р и P₂ тоже соответствуют одной точке эллиптической кривой.

Таким образом, существует параметр u, при котором:

f_a,b (u)=(x,y)

если и только если параметр u является решением уравнения (11).

Таким образом, решение уравнения (11) позволяет определить параметр u, в зависимости от которого получают точку Р эллиптической кривой по следующему уравнению:

f_a,b(u)=P

Уравнение (11) можно решать при помощи обычных алгоритмов, таких как алгоритм Берлекампа [Shoup, Journal of Symbolic Computation Vol.20, p.363-397, 1995]. Благодаря этому уравнению (11) можно легко инвертировать функцию f_a,b, чтобы найти параметр u, который соответствует точке Р эллиптической кривой.

Это свойство позволяет также ограничить достигаемое число точек значением f_a,b. Предположим, что Im(f_a,b ) является совокупностью точек отображения функции f_a,b . Множество отображения Im(f_a,b) имеет мощность, меньшую чем q, поскольку q является кардиналом F_q. Кроме того, уравнение (11) позволяет показать, что для каждой точки отображения существует максимум 4 антецедента. По сути дела, мощность не превышает 4-кратную мощность Im(f_a,b). В результате получают следующее неравенство:

q/4 #Im(f_a,b) q

Можно также получить эвристический результат в отношении мощности Im(f_a,b). Уравнение (11) является уравнением 4-ой степени в конечном поле. В конечном поле F _q существует вероятность 2/5 того, что некоторый полином 4-й степени не имеет корня. Следовательно, можно считать, что 3/5 точек эллиптической кривой входят во множество точек отображения Im(f_a,b) и поэтому их можно использовать в криптографическом вычислении согласно варианту выполнения настоящего изобретения.

В варианте выполнения настоящего изобретения можно использовать эллиптические кривые на кольце Z/qZ, где q является произведением I простых чисел p₁, , p_I. Китайская теорема об остатках, результат модулярной арифметики, рассматривающая решение системы конгруэнтностей, утверждает, что Z/qZ является изоморфным к Z/p₁Z x x Z/p_IZ. Поэтому можно в равной степени исследовать эллиптические кривые на каждом из Z/p_iZ. Однако, поскольку каждое р_i является простым числом, то по сути дела Z/p_iZ является полем, которое можно обозначить F _pi. Кроме того, поскольку каждое р_i строго превышает 3, уравнение эллиптической кривой на F_pi является уравнением типа Вейерштрасса.

Таким образом, поскольку формулы (4) и (5) верны для каждого из F_pi , то они будут также верны и для F_1i x x F_pI=Z/qZ.

Кроме того, для каждого из F_pi

p_i/4 #Im(f_a,b) p_i

Это позволяет доказать, что на Z/qZ

p₁/4 x x p_I/4=q/4^I #Im(f_a,b) p₁ x x p_I=q

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

где а и b являются элементами конечного поля Галуа .

Число n может быть нечетным простым числом, чтобы ограничить возможные атаки.

В данном случае имеем:

2ⁿmod3=2

В данном случае функция возведения в степень 3 и функция возведения в степень 1/3 тоже является биекцией, вычисляемой за постоянное время при любых значениях, к которым ее применяют, на этом конечном поле Галуа.

Обозначим u и w параметры , которые удовлетворяют следующему уравнению:

w=а+u²+u

Точки Р с координатами Х и Y, удовлетворяющие соответственно нижеследующим формулам, находятся на эллиптической кривой (15):

Таким образом, в случае, когда эллиптическая кривая, используемая для применения криптографического вычисления, является кривой характеристики 2, то предпочтительно можно получить точки Р эллиптической кривой в зависимости от параметра u по формулам (16) и (16 ), причем детерминистическим образом.

Действительно, точка Р с координатами, удовлетворяющими формулам (16) и (16 ), соответствует единственной точке эллиптической кривой по уравнению (15), так как пересечение прямой по формуле (16 ) с рассматриваемой эллиптической кривой (15) удовлетворяет следующей системе уравнений:

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

Эти последние уравнения можно еще упростить следующим образом:

Таким образом, в конечном счете эту систему уравнений можно записать:

Поскольку уравнение (19) соответствует уравнению (16), то можно сделать вывод, что Р является точкой рассматриваемой эллиптической кривой.

Следовательно, точка Р, координаты Х и Y которой отвечают уравнениям (16) и (16 ), является точкой эллиптической кривой по уравнению (15).

Как и в случае эллиптически кривых типа Вейерштрасса, в данном случае тоже можно ограничить число точек, включенных в отображение Im(f_a,b) функции f_a. Это множество Im(f_a,b) содержит не более 2ⁿ элементов, так как это является числом элементов исходной совокупности .

Уравнение (16 ) можно записать:

При значении u, которое решает вышеуказанное уравнение, получаем:

f_a(u)=(x,y)

Уравнение (17) является уравнением 4-й степени. Следовательно, это уравнение имеет решение, по меньшей мере, при четырех разных значениях параметра u. Таким образом, мы имеем, по меньшей мере, 2ⁿ/4=2^n-2 точек отображения f_a. Следовательно, во множестве точек отображения Im(f_a) имеется, по меньшей мере, 2^n-2 элементов.

Благодаря отличительным признакам настоящего изобретения получают детерминистическую функцию f, обозначаемую f_a,b или f_a в зависимости от рассматриваемого типа эллиптических кривых, множество отображений которой является множеством точек на эллиптической кривой, причем число этих точек является большим, так как оно, по меньшей мере, равно четверти числа q (мощность рассматриваемого конечного поля) в случае эллиптических кривых типа Вейерштрасса или, по меньшей мере, равно 2^n-2 в случае эллиптических кривых характеристик 2. Эта детерминистическая функция основана на биективной характеристике функции степени 3 (и степени 1/3) в рассматриваемом конечном поле Галуа, к которому ее применяют.

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

Применив функцию f_a,b согласно варианту выполнения настоящего изобретения для последовательности бит из функции хеширования h, получаем следующую функцию хеширования:

Эта функция (18) на эллиптической кривой предпочтительно имеет следующие характеристики:

- она является однонаправленной, если функция хеширования h является однонаправленной; и

- она является стойкой к столкновениям.

Такая функция находит свое применение во многих криптографических вычислениях.

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

Возьмем две произвольные функции хеширования h и h . Функцию хеширования h применим к совокупности {0,1}* в направлении конечного поля f_N, где N является порядком группы используемых точек кривой.

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

Функцию f_a,b согласно варианту выполнения настоящего изобретения используют для определения точки на эллиптической кривой. G, точку-генератор группы используемых точек, то есть точек отображения f_a,b в контексте применения настоящего изобретения, используют для обеспечения равномерного распределения определенных точек.

Предпочтительно настоящее изобретение можно применять для любого типа криптографического вычисления, в котором используют эллиптические кривые. В частности, оно представляет интерес в протоколах аутентификации при помощи пароля, такого как РАСЕ (от "Password Authenticated Connection Establishment" на английском языке). В этом случае оно позволяет повысить эффективность за счет использования функции (18), препятствуя при этом любой атаке, связанной с временем выполнения криптографического вычисления.

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

Действительно, прослушивая такие протоколы, можно определить параметры используемых эллиптических кривых, как описано в документе "Why public elliptic curve parameters are public", который можно найти на интернет-сайте http://www.larc.usp.br/~pbarreto/tales1.html.

Эти параметры позволяют определить гражданство лиц, предъявляющих эти электронные документы.

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

Настоящее изобретение можно также применять в контексте схем шифрования, основанных на идентификации. Примером такой конструкции является схема шифрования Боне-Франклина (Дан Боне и Мэтью К.Франклин, Акты конференции Крипто-2001). Действительно, чтобы обеспечить использование в условиях безопасности, эта схема требует наличия эллиптической кривой, на которой имеется произвольная функция. Настоящее изобретение дает конструкцию, которая на основании классической произвольной функции возвращает произвольную функцию на эллиптическую кривую. Однако эллиптические кривые, которые подходят для шифрования по схеме Боне-Франклина, требуют особой функции: функции связывания точек. Функция связывания является функцией ê, которая берет на входе две точки и возвращает значение на конечное поле. Это связывание представляет особый интерес, так как характеризуется исключительными математическими свойствами. Проверяют следующее уравнение:

ê(cG,dG)=g ^cd

где g является генератором конечного поля назначения;

где c и d являются дискретными логарифмами cG и dG по основанию G; и

где G является генератором группы используемых точек.

Авторы схемы Боне и Франклин предложили для своей схемы только один тип эллиптических кривых. Настоящее изобретение позволяет увеличить число эллиптических кривых, на которых можно применять их схему шифрования. Действительно, благодаря отличительным признакам настоящего изобретения, эту схему шифрования можно применять на всех кривых, где эффективно вычисляется связывание или где соблюдается уравнение (2).

В варианте выполнения настоящего изобретения можно производить уплотнение координат точек. Действительно, настоящее изобретение позволяет отображать координаты Х и Y точки Р при помощи параметра u. Следовательно, параметр u можно использовать для осуществления уплотнения, так как u отображает в этом случае точку P(X,Y) с вдвое меньшим количеством информации.