криптография с параметризацией на эллиптической кривой

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

1. Способ проверки устройства (10) с помощью контроллера (11) на основе пароля ( ), содержащий следующие этапы, выполненные в устройстве или контроллере:

/1/ на основе случайного числа r ₁ определяют точку P(X,Y) на эллиптической кривой в конечном поле F_q, где q - целое число, а кривая задается уравнением:



/2/ получают первый и второй параметры k и k , такие, что

P(X,Y)=F(k,k ),

где F - сюръективная функция F_qxF _q в F_q;

/3/ получают первый и второй параметры в зашифрованном виде посредством шифрования в виде функции, зависящей от пароля; и

/4/ передают упомянутые первый и второй параметры контроллеру;

при этом функция F такова, что независимо от входных элементов z и z из F_q, F(z,z ) является точкой на эллиптической кривой и входные элементы не удовлетворяют уравнению (1).

2. Способ проверки по п.1, в котором функция F имеет вид:

F(k,k )=f(k )+f_a,b(k),

где f_a,b - обратимая функция, основанная на коэффициентах a и b эллиптической кривой, на вход которой подают входной параметр и на выходе получают точку на эллиптической кривой;

f - функция генерации точки на эллиптической кривой, зависящая от параметра;

причем на этапе /2/ параметры k и k получают в ходе следующих этапов:

случайно генерируют значение параметра k ;

вычисляют значение f (k );

определяют значение параметра k из следующего выражения:

.

3. Способ проверки по п.2, в котором функция f имеет вид:

f (k )=k .G,

где G - генератор множества точек на эллиптической кривой; а

значение параметра k определяют из следующего выражения:

.

4. Способ проверки по п.2, в котором функция f имеет вид:

f (k )=f_a,b(k ),

а значение параметра k определяют из следующего выражения:

5. Способ проверки по любому из пп.1-4, в котором функция F содержит по меньшей мере одну обратимую функцию f _a,b, полученную с помощью многочленов X₁(k), X₂(k), X₃(k) и U(k), которые удовлетворяют равенству Скальба:

f(X₁(k)).f(X₂ (k)).f(X₃(k))=U(k)²,

где f - многочлен, который определяет эллиптическую кривую E_a,b.

6. Способ проверки по п.5, в котором функция f_a,b сопоставляет паре параметров (x, y) в параметр u в F_q, где q равен 2 mod 3, так что:

х=( ²-b-u⁶/27)^1/3+u² /3

и

y=u.x+ ,

где ,

и f_a,b(0)=0.

7. Способ проверки по п.1, дополнительно включающий следующие этапы:

получают сообщение, содержащее первый и второй параметры, зашифрованные с помощью пароля;

расшифровывают первый и второй параметры и получают параметры р и р ; и

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

K=r₁.F(p,p ),

где r₁ - указанное случайное число, использованное на этапе /1/.

8. Электронное устройство в системе проверки с помощью пароля, содержащее:

блок (41) определения, выполненный с возможностью определения точки P(X,Y) на эллиптической кривой в конечном поле F_q, где q - целое число, на основе случайного числа r₁ , причем эллиптическая кривая удовлетворяет уравнению:



блок (42) получения, выполненный с возможностью получения первого и второго параметров k и k , таких, что

P=F(k,k ),

где F - сюръективная функция F_qxF _q в F_q;

блок (43) шифрования, выполненный с возможностью получения первого и второго параметров в зашифрованном виде посредством шифрования в виде функции от пароля; и

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

при этом функция F такова, что независимо от входных элементов z и z из F_q, F(z,z ) является точкой на эллиптической кривой, а входные элементы не удовлетворяют уравнению (1).

9. Электронное устройство по п.8, содержащее средство для осуществления способа проверки по п.1.

10. Система проверки с помощью пароля, содержащая по меньшей мере одно первое электронное устройство по п.8 или 9 в качестве контроллера, и второе электронное устройство по п.8 или 9 в качестве проверяемого устройства.

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

Настоящее изобретение касается шифрования сообщений на основе использования точек на эллиптической кривой, а более конкретно, упомянутого использования в области алгоритмов типа ЕКЕ (обмен зашифрованными ключами).

Способы аутентификации с помощью пароля основаны на использовании алгоритма типа ЕКЕ. Этот тип алгоритмов показан на фиг.1.

Устройство D10 хочет пройти аутентификацию на основе пароля у контроллера C11. Каждый из этих объектов знает пароль . Более того, предположим, что общедоступными параметрами является эллиптическая кривая E_a,b и генератор G множества точек на эллиптической кривой. Эллиптическая кривая удовлетворяет следующему уравнению:

На этапе 12 устройство D10 генерирует случайное число r₁. Далее оно передает это случайное число в форме точки на эллиптической кривой контроллеру 11. Для этого оно определяет некоторое передаваемое значение V, удовлетворяющее выражению:

V=r₁.G.

Далее этот результат зашифровывается с помощью пароля в виде E (r₁.G), при этом E - функция шифрования с паролем.

Далее устройство посылает сообщение 13 контроллеру, содержащее значение E (r₁.G).

При получении сообщения 13 контроллер 11 в свою очередь на этапе 14 генерирует случайное число r₂. Далее он преобразует это число в форму точки на эллиптической кривой и передает устройству 10 сообщение 15, содержащее результат:

E (r₂.G).

После этого обмена случайными числами r₁ и r₂ в зашифрованной форме устройство 10 на этапе 16 восстанавливает случайное число r₂, сгенерированное контроллером, что делается посредством дешифрования с использованием функции D расшифрования с паролем; информация, содержащаяся в сообщении 15:

r₂.G=D E (r₂.G),

а контроллер 11 на этапе 17 восстанавливает случайное число r₁, сгенерированное устройством 10, что делается посредством дешифрования информации, содержащейся в сообщении 13:

r₁.G=D E (r₁.G).

Таким образом, после защищенного обмена сообщениями каждый объект может вычислить общий ключ K:

K=r₁.r₂.G.

Алгоритм этого типа предназначен для обмена значениями в виде, зашифрованном с помощью пароля или ключа, полученного по паролю. Тем не менее, надо заметить, что в соответствии с классическим представлением эллиптической кривой, удовлетворяющей уравнению (1) в конечном поле F_q, описанный со ссылкой на фиг.1 обмен сообщениями позволяет потенциальному нарушителю получить информацию, касающуюся пароля . Фактически описанный выше обмен случайными числами в зашифрованной форме с помощью сообщений 13 и 15 дает лишнюю информации, которая может позволить взломать секретность пароля. Более конкретно, при каждом перехвате нарушитель может проверять пароль на предмет расшифровывания информации, которой обмениваются в сообщениях 13 и 15. Далее для него возможны два случая. В первом случае расшифрованная информация соответствует точке на кривой и соответственно пароль правильный. Во втором случае расшифрованная информация не соответствует точке на эллиптической кривой и соответственно пароль не найден. Путем увеличения количества перехватов и отдельных паролей таким образом возможно найти пароль, принадлежащий конечному множеству элементов.

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

Согласно первому аспекту настоящего изобретения предложен способ проверки устройства с помощью контроллера на основе пароля;

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

/1/ на основе случайного числа r₁ определяют точку P(X,Y) на эллиптической кривой в конечном поле F_q , при этом q - целое число и кривая задается уравнением:

/2/ получают первый и второй параметры k и k , такие, что

P=F(k,k ),

где F - сюръективная функция F_q xF_q в F_q;

/3/ получают первый и второй параметры в зашифрованном виде посредством шифрования в виде функции, зависящей от пароля; и

/4/ передают упомянутые первый и второй параметры контроллеру;

при этом функция F такова, что независимо от входных элементов z и z из F_q, F(z,z ) является точкой на эллиптической кривой и входные элементы не удовлетворяют уравнению (1).

Благодаря таким конструкциям возможно избежать описанных выше атак, характерных для существующего уровня техники. Фактически при этих условиях больше невозможно проверять пароль путем определения, соответствует ли полученный результат некоторой точке (X,Y) на эллиптической кривой E_a,b, так как на выходе функция F всегда дает точку на эллиптической кривой, независимо от входных параметров, хотя входные параметры не удовлетворяют классическому выражению эллиптической кривой. Следовательно, предусматривается другое представление точки на эллиптической кривой, с использованием этой сюръективной функции F, чтобы не давать никакой информации потенциальному нарушителю, которая могла быть позволить ему установить используемый пароль.

Чтобы определить упомянутую функцию F, позволяющую представить точку P(X,Y) на эллиптической кривой в соответствии с некоторой параметризацией, отличной от уравнения (1), возможно использовать в качестве основы обратимую функцию f_a,b, обратная функция которой позволяет восстановить точку на кривой, соответствующей двум параметрам, которые не удовлетворяют уравнению (1), по входному параметру.

Функция F может быть записана в следующем виде:

F(k,k )=f(k )+f_a,b(k),

где f_a,b - обратимая функция, основанная на коэффициентах а и b эллиптической кривой, на вход которой подают входной параметр и на выходе получают точку эллиптической кривой;

при этом f - функция генерации точки на эллиптической кривой, зависящая от параметра; и

на этапе /2/ параметры k и k получают в ходе следующих этапов:

- случайно генерируют значение параметра k ;

- вычисляют значение f (k );

- определяют значение параметра k из следующего выражения:

.

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

В частности, функция f может быть записана следующим образом:

f (k )=k .G,

где G - генератор множества точек на эллиптической кривой; а

значение параметра k определяют из следующего выражения:

.

В таких условиях функцию F можно записать так:

F(k,k )=f_a,b(k)+k .G,

В качестве альтернативы функцию f можно записать следующим образом:

f (k )=f_a,b(k )

и

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

.

В таких условиях функцию F можно записать так:

F(k,k )=f_a,b(k)+f_a,b(k ).

Таким образом, в общем для параметризации точки P(X,Y) на кривой в соответствии с настоящим изобретением первый этап предполагает получение точки на кривой для некоторого значения параметра k . Далее определяют точку на кривой, которая соответствует вычитанию из представляемой точки Р(Х,Y) точки, полученной на первом этапе. Далее получают другую точку на эллиптической кривой. После этого функцию, обратную к функции f_a,b, применяют к этой точке и получают значение параметра k. Таким образом, точку Р представляют в виде пары параметров k и k , которые не удовлетворяют уравнению (1).

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

,

где L является целым числом, значение которого сравнительно мало по сравнению с количеством точек на эллиптической кривой (1).

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

Таким образом, применение функции F к первому и второму параметрам может соответствовать применению по меньшей мере к одному из двух параметров функции f_a,b , такой, что

где L является целым числом, значение которого сравнительно мало по сравнению с количеством точек на эллиптической кривой (1).

Другими словами, рассматриваемая здесь функция f_a,b содержит прообраз, соответствующий множеству точек Р на эллиптической кривой Е_a,b и ограниченный достаточно небольшим максимальным значением по сравнению с количеством точек на эллиптической кривой. Фактически, если бы это было не так, то было бы возможно обратить функцию f_a,b просто произвольно выбирая число. В этом контексте можно рассматривать, например, что L меньше произведения 1/2⁸⁰ и количества точек на кривой.

Благодаря использованию обратимой функции, удовлетворяющей условиям (4), легко получить функцию F для представления точки на кривой с помощью параметров k и k , которые не позволяют реализовывать описанную выше атаку на пароль, использованный для шифрования этих параметров.

В одном варианте осуществления настоящего изобретения функция f_a,b устанавливает соответствие пары параметров (x, y) параметру и так что х является единственным решением следующего уравнения:

а y удовлетворяет:

y=u.x+Q(u, a,b).

Это уравнение (5), полученное заменой у в уравнении (1) на элемент ux+Q(u,a,b). Элемент ux+Q(u,a,b) является рациональной дробью, зависящей от переменных и a, и b.

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

х³+aх+b-(ux+Q(u, a,b))².

Для q=2 mod 3 можно записать

(u, a, b)=-3R(u, а, b)²,

где R - рациональная дробь.

Фактически для q=2 mod 3, -3 не является квадратом и, следовательно, -3R(u,a,b) ² никогда не является квадратом многочлена.

Так как уравнение (5) только допускает наличие единственного корня, то следующий элемент является многочленом степени 1:

gcd(x³+ax+b-(ux+Q(u,a,b)) ²,X^P-X),

где gcd - наибольший общий делитель.

Корень этого многочлена, обозначаемый как X_P, является абсциссой точки на эллиптической кривой. Наконец, точка с абсциссой X_P и ординатой u.X_P+Q(u,a,b) является точкой на кривой.

В одном примере в качестве рациональной дроби Q(u,a,b) можно рассмотреть следующую дробь:

В одном варианте осуществления изобретения целесообразно следующим образом определить функцию f_a,b в F_q, где q равна 2 mod 3. Она сопоставляет паре параметров (x, y) параметр u так, что

х=( ²-b-u⁶/27)^1/3+u² /3

и

y=u.x+ ,

где

и где f_a,b(0)=0.

Такая функция обратима. Таким образом, для P(X,Y) на эллиптической кривой прообраз точки для функции f_a,b представляет собой решение следующего уравнения:

u⁴ -6u²х+6uy-3a=0.

Итак, степенное уравнение такого типа может быть легко обращено.

Более того, множество прообразов точек Р для этой функции f _a,b ограничено L, которое мало по сравнению с количеством точек на эллиптической кривой.

Таким образом, эта функция удовлетворяет определенным ранее характеристикам.

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

Заметим, что многочлены, удовлетворяющие равенству Скальба, определены в документе «Рациональные точки на определенных гиперэллиптических кривых над конечными полями» («Rational points on certain hyperelliptic curves over finite fields»), автор Масие Улас (Macie Ulas), 11 июня 2007 года. Эти функции являются обратимыми. Фактически заданные многочлены X₁(k), X₂ (k), X₃(k) и U(k) удовлетворяют равенству Скальба, если удовлетворяют уравнению:

f(X₁(k)).f(X ₂(k)).f(X₃(k))=U(k)²,

где f - многочлен, который определяет эллиптическую кривую E _a,b.

Более конкретно f удовлетворяет уравнению:

f(x)=y²,

где x и y являются элементами , а пара (x, y) представляет собой точку на E_a,b .

f_a,b(k) определяют как точку P=(X _i(k), f(X_i(k))^1/2), где i такое, что f(X_i(k)) является квадратом в F_q. Таким образом, чтобы обратить функцию f_a,b, при заданной точке P=(X,Y), вычисляют решения k_s трех степенных уравнений:

X₁(k_s)-X=0

X₂(k_s)-X=0

X₃(k_s)-X=0.

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

В случае, когда F(k,k ) записана как:

F(k,k )=f_a,b(k)+f_a,b(k ).

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

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

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

Через D обозначим множество точек на эллиптической кривой E _a,b, у которых существует точно i прообразов для функции f_a,b. В описанном ниже примере определено пять множеств: D₁, D₂, D₃, D₄ и D₅.

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

Для t от 0 до T-1, где T - целое число:

- генерируют точку P_t с помощью функции GEN;

- если P_t является элементом D₀, то переходят на начало;

- если P_t является элементом D_i, то

- выбирают случайное число b, находящееся между 0 и 1 и удовлетворяющее равенству:

Pr(b=0)= _i,

- если b равно 1, то переходят на этап (1);

- в ином случае

- случайно выбирают элемент и из множества ;

- возвращают u.

Заметим, что для получения вероятности успеха, равной 1-1/2^k , достаточно, чтобы T равнялось многочлену, вычисленному в точке k степени 1, другими словами, чтобы T было кратно k.

Более того, могут быть применены следующие этапы:

- получают сообщение, содержащее первый и второй параметры, зашифрованные с помощью пароля;

- расшифровывают первый и второй параметры и получают параметры р и р ; и

- вычисляют общее секретное значение K с помощью контроллера и в соответствии со следующим выражением:

K=r₁.F(p,p ),

где r₁ - случайное число, используемое на этапе /1/.

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

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

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

Другие аспекты, цели и достоинства изобретения будут ясны после прочтения описания одного из вариантов осуществления изобретения. Изобретение будет лучше понятно из следующих фигур:

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

фиг.2 - вид, на котором показаны основные этапы способа проверки, который соответствует одному варианту осуществления настоящего изобретения;

фиг.3 - вид, на котором показана реализация способа проверки, реализуемого между устройством и контроллером в соответствии с одним вариантом осуществления настоящего изобретения; и

фиг.4 - вид, на котором показано устройство и контроллер в соответствии с одним вариантом осуществления настоящего изобретения.

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

На этапе 21 точку P=(X,Y) на эллиптической кривой в конечном поле F _q, где q - целое число, определяют на основе случайного числа r₁. Далее на этапе 22 так получают первый и второй параметры k и k , что

P=F(k,k ),

где F - сюръективная функция из F _qxF_q в F_q.

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

На этапе 23 первый и второй параметры зашифровывают с помощью пароля и, таким образом, получают их зашифрованный вид E (k, k ).

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

Функция F такова, что независимо от элементов z и z из F_q, F(z,z ) является точкой на эллиптической кривой и элементы z и z не удовлетворяют уравнению (1).

На фиг.3 показан обмен сообщениями между проверяемым устройством 10 и контроллером 11 в соответствии с одним вариантом осуществления настоящего изобретения.

Проверяемое устройство D10 сначала на этапе 31 генерирует случайное число r₁ . Если мощность множества точек на эллиптической кривой является целым числом N, то число r₁ может быть случайным числом из следующего множества значений: [0, N-1].

Далее, с учетом этого случайного числа с использованием генератора G генерируют точку P=(X,Y) на эллиптической кривой E_a,b . Упомянутый генератор обладает следующим свойством: для любой точки Р на эллиптической кривой существует значение h, такое, что:

P=h.G.

Таким образом, точку P₁ получают следующим образом:

P ₁=r₁.G.

Далее на этапе 33 определяют значения параметров k₁ и с целью представления точки P₁ в соответствии с параметрами, отличающимися от координат X и Y, которые со своей стороны удовлетворяют выражению (2).

Для определения этих параметров k₁ и сначала для параметра могут сгенерировать случайное число. Далее точка P _k1 на эллиптической кривой соответствует этому случайному числу или благодаря применению функции f_a,b, которая сопоставляет координаты х, y точки на кривой параметру, или благодаря использованию генератора G точек на эллиптической кривой.

Далее получают значение параметра k₁ путем применения обратного преобразования для функции f_a,b к точке, соответствующей вычитанию в группе точек на эллиптической кривой: P(X,Y)-P_k1.

Параметры k ₁ и представляют точку P(X,Y). Далее полученные ранее первый и второй параметры шифруют с помощью функции шифрования E , основанной на пароле , что делают с целью их передачи контроллеру с помощью сообщения 34.

Симметричным образом на этапе 35 контроллер генерирует случайное число r₂. Далее на этапе 36 он преобразует это число в точку Р₂ на эллиптической кривой. Затем, как описано ранее на этапе 33, на этапе 37 контроллер получает соответствующие значения первого и второго параметров k₁ и . Далее он шифрует эти значения до их передачи проверяемому устройству 10 с помощью сообщения 38.

Следовательно, проверяемое устройство 10 имеет в своем распоряжении случайное число r₁, числа k₂ и и функцию F.

Таким образом, на этапе 39 оно восстанавливает точку P₂:

Следовательно, оно вместе с контроллером получает секретный ключ K, не давая никакой информации о пароле, при этом указанный ключ удовлетворяет равенству:

K=r₁.r².G.

Контроллер восстанавливает секретный ключ К симметричным образом на этапе 301.

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

Функция F является сюръективной функцией из F_qxF_q в F_q, такой, что:

и такой, что для любой пары чисел (k,k ) Р является точкой на эллиптической кривой, хотя k и k не удовлетворяют уравнению (1).

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

Такое представление может быть основано на следующей целесообразной характеристике функции f_a,b(U):

,

где L - целое число.

Другими словами, размер множества прообразов этой функции ограничен величиной L, которая мала по сравнению с количеством точек на эллиптической кривой.

Рассматривая следующую функцию f_a,b(u), можно целесообразно определить функцию F, которая соответствует одному варианту осуществления настоящего изобретения и которая сопоставляет паре параметров (х, u.x+v) из параметр и из F_q так, что:

х=( ²-b-u⁶/27)^1/3+u² /3

и

,

при этом полагают f_a,b(0)=0.

Функция F может быть записана следующим образом:

F(k,k )=f_a,b(k)+f_a,b(k )

или

F(k,k )=f_a,b(k)+k .G.

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

f(X₁(k)).f(X ₂(k)).f(X₃(k))=U(k)²,

где X₁(k), X₂(k), X₃(k) и U(k) - многочлены, удовлетворяющие равенству Скальба, как определено, например, в документе «Рациональные точки на определенных гиперэллиптических кривых над конечными полями» («Rational points on certain hyperelliptic curves over finite fields»), автор Масие Улас, 11 июня 2007 года. Здесь через F_a,b (k) обозначаем (X_i(k),f(X_i(k))^1/2 ), где i таково, что f(X_i(k)) является квадратом в F_q.

На фиг.4 показана система проверки, содержащая проверяемое устройство и контроллер в соответствии с одним вариантом настоящего изобретения.

В соответствии с одним вариантом настоящего изобретения такая система проверки содержит по меньшей мере одно электронное устройство, такое как проверяемое устройство 10, и устройство проверки или контроллер 11. Подобное электронное устройство, независимо от того, используется ли оно как проверяемое устройство или как контроллер, может содержать:

- блок 41 определения, предназначенный для определения точки P(X,Y) на эллиптической кривой в конечном поле F_q , где q - целое число, на основе случайного числа r₁ , причем эллиптическая кривая удовлетворяет уравнению:

- блок 42 получения, предназначенный для получения первого и второго параметров k и k так, что

P=F(k,k ),

где F является сюръективной функцией из F_qxF_q в F_q;

- блок 43 шифрования, предназначенный для получения первого и второго параметров в зашифрованном виде посредством шифрования как функции от пароля; и

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

при этом функция F такова, что независимо от входных элементов z и z из F_q, F(z,z ) является точкой на эллиптической кривой и входные элементы не удовлетворяют уравнению (1).

Функция шифрования E с паролем может быть определена различным образом. Входным параметром для нее является битовая строка и выходом является битовая строка. Тем не менее, для обеспечения конфиденциальности пароля необходимо, чтобы возвращаемое значение не давало информации о пароле. Таким образом, можно различать два случая:

- или пароль используют в качестве ключа шифрования в классической функции шифрования;

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

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

Выбрать случайное число r. Далее преобразовать значение v параметра в битовую строку путем следующих вычислений:

v =v+r.q ,

где q соответствует или q или N, при этом q - количество элементов в основной структуре F_q, N - количество точек на эллиптической кривой. Далее возможно представить v в виде битовой строки.

В случае, когда пароль является индексом, v представляет собой зашифрованное с помощью пароля значение v, так как только человек, знающий общедоступные параметры (q или N), может найти значение v.

В случае, когда пароль используют как ключ шифрования в классической функции шифрования, достаточно зашифровать v с использованием функции шифрования E .

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

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

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