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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

f ( X ) = Y 2 ,   ( 1 )

где f(X) - это многочлен f(X)=Х³+аХ+b.

Известно семейство многочленов, которое удовлетворяют равенству Скальба и которое дает возможность определить такую точку на эллиптической кривой, как описано в документе «Construction of Rational Points on Elliptic curves over finite fields» (Построение рациональных точек эллиптических кривых над конечными полями), авторы Эндрю Шаллуе (Andrew Shallue) и Кристиан ван де Вустейне (Christiaan van de Woestijne).

Многочлены X₁(t), X₂(t), X₃(t) и U(t) удовлетворяют равенству Скальба, если они удовлетворяют следующему выражению:

f ( X 1 ( t ) ) . f ( X 2 ( t ) ) . f ( X 3 ( t ) ) = U 2 ( t ) ,   ( 2 )

где f - это функция, которая определяет рассматриваемую эллиптическую кривую, а t - параметр.

Многочлены, которые удовлетворяют равенству Скальба, могут иметь два параметра u и t. В этом случае равенство Скальба записывается следующим образом:

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

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

При выбранных параметрах t и u заметим, что X₁=X₁(t,u), X₂=X₂(t,u), Х₃=X₃(t,u), U=U(t,u), при этом X₁, X₂, Х₃ и U являются элементами F_q. Это выражение (2) означает, что, по меньшей мере, одно из чисел f(X₁), f(X₂) и f(X₃) соответствует квадрату элемента в конечном поле F_q.

Тогда, когда определен квадрат элемента, f(X_i), в поле F_q, мы можем получить точку на эллиптической кривой P ( X i ,   f ( X i ) .

Вычисление f ( X i ) можно осуществить с помощью вычисления возведения в степень, когда характеристика q поля F_q удовлетворяет равенству:

q=3 mod 4.

В этом случае известно, что

f ( X i ) = f ( X i ) ( q + 1 ) / 4 .   ( 3 )

Следовательно, для определения точки на эллиптической кривой (1) необходимо определить, какое число среди трех чисел f(X₁), f(X₂) и f(Х₃) соответствует квадрату элемента в конечном поле F_q. Для этой цели мы можем предусмотреть сначала проверку того, является ли элемент f(X₁) квадратом элемента в конечном поле F_q, далее, если это не так, применить ту же проверку для элемента f(X₂) и, наконец, если это тоже не правильно, аналогично проверить элемент f(Х₃). Тем не менее, при такой процедуре определение точки на эллиптической кривой не всегда занимает одинаковое время, так как это определение выполняется быстрее, если квадратом является первый элемент, по сравнению со случаем, когда только третий элемент является квадратом.

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

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

Для преодоления этого недостатка возможно методично проверять три элемента f(X_i) для всех i от 1 до 3. Таким образом, время определения точки на кривой не будет зависеть от определенной точки.

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

Цель настоящего изобретения состоит в улучшении этой ситуации.

Согласно первому аспекту настоящего изобретения предложен способ выполнения криптографического преобразования в электронном компоненте, включающий в себя этап получения точки P(X,Y), исходя, по меньшей мере, из одного параметра t, на эллиптической кривой, удовлетворяющей выражению:

Y²=f(Х); и

исходя из многочленов X₁(t), X₂(t), X₃(t) и U(t), удовлетворяющих следующему равенству:

f(X₁(t)).f(X₂(t)).f(X₃(t))=U(t)²

в конечном поле F_q, независимо от параметра t, при этом q удовлетворяет равенству q=3 mod 4;

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

/1/ получают значение параметра t;

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

/i/ вычисляют X₁=X₁(t), Х₂=X₂(t), Х₃=X₃(t) и U=U(t);

/ii/ если элемент f(X₁).f(X₂) является квадратом в конечном поле F_q, то проверяют, является ли элемент f(X₃) квадратом в конечном поле F_q, и вычисляют квадратный корень из элемента f(Х₃), абсциссой точки Р является Х₃, а квадратный корень f(Х₃) является ординатой точки Р;

/iii/ иначе проверяют, является ли элемент f(X₁) квадратом в конечном поле F_q, и если является, вычисляют квадратный корень из элемента f(X₁), абсциссой точки Р является X₁, а квадратный корень f(X₁) является ординатой точки Р;

/iv/ иначе вычисляют квадратный корень элемента f(X₂), абсциссой точки Р является Х₂, а квадратный корень из f(X₂) является ординатой точки Р;

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

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

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

- проверка на то, что элемент является квадратом в F_q;

- определение квадратного корня.

Следовательно, невозможно осуществить атаку, основанную на затратах времени.

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

На этапе /2/-/ii/ необходимо решить, является ли элемент R₀:

R₀=f(X₁).f(X₂)

квадратом.

Этот этап может соответствовать проверке, является ли элемент квадратом, при этом применяется дополнительное возведение в степень, или этот этап может быть основан на заранее вычисленном значении, полученном при более ранних вычислениях в случае, когда многочлен, удовлетворяющий равенству Скальба, соответствует элементу, который не может быть квадратом. В последнем случае, который показан в следующих разделах, применение способа предпочтительно требует только одного возведения в степень. Но в наихудшем случае применение способа, соответствующего одному варианту осуществления настоящего изобретения, соответствует двум возведениям в степень, одно - для проверки, является ли R₀ квадратом, и другое возведение в степень - для проверки, является ли некоторый элемент квадратом, применяемой или к f(X₃), или к f(X₁).

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

В одном варианте осуществления настоящего изобретения на этапе /2/-/ii/ выполняют следующие этапы:

- вычисляют такой R₁, что:

R 1 = ( f ( X 1 ) . f ( X 2 ) ) q + 1 4 ,

- если R 1 2 равен f(X₁).f(X₂), то решают, что элемент f(X₁).f(X₂) является квадратом в поле F_q;

На этапе /2/-/iii/ проверяют, является ли элемент f(X₁) квадратом в конечном поле F_q, в соответствии со следующими этапами:

- вычисляют такой R 2 ' , что:

R 2 ' = f ( X 1 ) q − 1 − q + 1 4 ,

- вычисляют такой R 3 ' , что:

R 3 ' = R 2 ' 2 ,

- вычисляют такой R 4 ' , что:

R 4 ' = R 3 ' . f ( X 1 ) .

Если R 4 ' не равен 1, то на этапе /2/-/iv/ квадратный корень f(X₂) получают в соответствии со следующим выражением:

f ( X 2 ) = R 1 . R 2 ' .

Этот вариант осуществления изобретения является общим и может быть легко применен к любому семейству многочленов, которые удовлетворяют равенству Скальба. Заметим, что в случае, когда в равенстве (2) Скальба f(X₂) является квадратом, то есть последний проверяемый элемент из трех элементов в равенстве Скальба, не нужно осуществлять новое возведение в степень типа f ( X 1 ) q − 1 − q + 1 4 . Фактически элемент R 2 ' может быть предпочтительно использован для получения квадратного корня элемента f(X₂). Таким образом, обеспечивается, что самое большее два возведения в степень применяются при выполнении способа в соответствии с одним вариантом осуществления настоящего изобретения.

В одном варианте осуществления настоящего изобретения многочлены, удовлетворяющие равенству Скальба, выражаются в координатах Якоби в X', Y' и Z следующим образом:

X'=X.Z²,

Y'=Y.Z³,

и операции нахождения обратного элемента преобразуются в операции умножения.

Преобразование в координаты Якоби позволяет преобразовать операции нахождение обратного элемента в умножения при надлежащем выборе элемента Z.

В одном варианте осуществления настоящего изобретения многочлены, удовлетворяющие равенству Скальба, выражены в координатах Якоби, в соответствии с чем точка P(X,Y) записывается как P(X',Y',Z), при этом:

X'=X.Z²,

Y'=Y.Z³,

где функция f записана как f_Z(X') и удовлетворяет следующему равенству:

f_Z(X')=X'³+a.X'.Z⁴+b.Z⁶,

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

Y'²=f_Z(X'),

и многочлены, удовлетворяющие равенству Скальба и выраженные в координатах Якоби, представляют собой X 1 ' ( t ) , X 2 ' ( t ) , X 3 ' ( t ) , Z(t) и U'(t) и удовлетворяют равенству Скальба в координатах Якоби:

U ' ( t ) 2 = f Z ( t ) ( X 1 ' ( t ) ) . f Z ( t ) ( X 2 ' ( t ) ) . f Z ( t ) ( X 3 ' ( t ) ) ,

где Z(t) определен таким образом, что операции нахождения обратного элемента преобразованы в операции умножения.

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

В одном варианте осуществления изобретения многочлены, удовлетворяющие равенству Скальба, таковы, что возможно установить значение Х₃(t) для любого возможного t, чтобы f(X₃(t)) никогда не был квадратом элемента в F_q,

при этом на этапе /2/-/ii/ элемент f(X₁).f(X₂) не является квадратом в конечном поле F_q,

при этом на этапе /2/-/iii/ проверяют, является ли элемент f(X₁) квадратом в конечном поле F_q, в соответствии со следующими этапами:

- вычисляют такой R 2 ' , что:

R 2 ' = f ( X 1 ) q − 1 − q + 1 4 ,

- вычисляют такой R 3 ' , что:

R 3 ' = R 2 ' 2 ,

- вычисляют такой R 4 ' , что:

R 4 ' = R 3 ' . f ( X 1 ) ,

при этом, если R 4 ' не равен 1, то на этапе /2/-/iv/ квадратный корень f(X₂) получают в соответствии со следующим выражением:

f ( X 2 ) = R 1 . R 2 ' ,

где R 1 = ( f ( X 1 ) . f ( X 2 ) ) q + 1 4 , причем R₁ получают заранее из следующего выражения:

R 1 = ( f ( X ) . f ( X 2 ) ) q + 1 4 = U . f ( u ) q − 1 − q + 1 4 .

Таким образом, в конкретном случае, возможно дополнительно ограничить количество выполняемых возведений в степень путем использования конкретного семейства многочленов, так что возможно установить значение X₃(t) для любого возможного t, чтобы f(X₃(t)) никогда не был квадратом элемента в F_q. Здесь предпочтительно может быть использовано семейство многочленов Уласа, которое определено в документе «Рациональные точки на определенных гиперэллиптических кривых над конечными полями» («Rational points on certain hyperelliptic curves over finite fields»), автор Масие Улас (Macie Ulas), 11 июня 2007 года.

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

X 1 ( t , u ) = − b a ( 1 + 1 t 4 f ( u ) + t 2 f ( u ) ) ,

X₂(t,u)=t²f(u)X₁(t,u),

X₃(t,u)=u,

U(t,u)=t³f(u)⁴f(X₁(t,u)),

где f(u)=u³+au+b, а и b - такие элементы F_q, что их произведение не равно нулю.

Эти многочлены могут быть предпочтительно использованы при определении множества значений параметра u, при которых f(X₃)=f(u) не является квадратом элемента в F_q.

Таким образом, на этапе /2/-/ii/ элемент f(X₁).f(X₂) не является квадратом в конечном поле F_q, тогда на этапе /2/-/iii/ проверяют, является ли элемент f(X₁) квадратом в конечном поле F_q, в соответствии со следующими этапами:

- вычисляют такой R 2 ' , что:

R 2 ' = f ( X 1 ) q − 1 − q + 1 4 ,

- вычисляют такой R 3 ' , что:

R 3 ' = R 2 ' 2 ,

- вычисляют такой R 4 ' , что:

R 4 ' = R 3 ' . f ( X 1 ) .

Далее, если R 4 ' не равен 1, то на этапе /2/-/iv/ квадратный корень f(X₂) получают в соответствии со следующим выражением:

f ( X 2 ) = R 1 . R 2 ' ,

где R 1 = ( f ( X 1 ) . f ( X 2 ) ) q + 1 4 , причем предпочтительно R₁ получают заранее из следующего выражения:

R 1 = ( f ( X ) . f ( X 2 ) ) q + 1 4 = U . f ( u ) q − 1 − q + 1 4 .

В частности, элемент f ( u ) q − 1 − q + 1 4 может быть вычислен заранее. Это возможно, так как f(u) также вычисляют заранее. Следовательно, в этом конкретном случае многочленов, которые удовлетворяют равенству Скальба, возможно не осуществлять возведение в степень, связанное с вычислением ( f ( X 1 ( t ) ) . f ( X 2 ( t ) ) ) q + 1 4 , во время применения способа, а осуществлять только умножение U ( t ) . ( f ( u ) ) q − 1 − q + 1 4 . Таким образом, применение такого способа соответствует одному возведению в степень, при вычислении R 2 ' = f ( X 1 ) q − 1 − q + 1 4 .

В этом случае эти конкретные многочлены выражают в координатах Якоби, в соответствии с чем точка P(X,Y) записывается как P(X',Y',Z), где:

X'=X.Z²,

Y'=Y.Z³,

при этом функция f записана как f_Z(X') и удовлетворяет следующему равенству:

f_Z(X')=X'³+a.X'Z⁴+b.Z⁶,

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

Y'²=f_Z(Х'),

в котором многочлены, удовлетворяющие равенству Скальба и выраженные в координатах Якоби, представляют собой X 1 ' ( t ) , X 2 ' ( t ) , Z(t) и U'(t) и удовлетворяют равенству Скальба в координатах Якоби:

U ' ( t ) 2 = f Z ( t ) ( X 1 ' ( t ) ) . f Z ( t ) ( X 2 ' ( t ) ) . f   ( X 3 ( t ) )

и где Z(t) определен таким образом, что операции нахождения обратного элемента преобразованы в операции умножения.

На этапе /1/ значение параметра t может быть получено как функция пароля или идентификатора. Таким образом, возможно предусмотреть использование в качестве параметра непосредственно пароля или производной от пароля.

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

/а/ генерируют случайное число;

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

/в/ передают зашифрованное число для проверки целостности.

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

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

Другие аспекты и достоинства изобретения будут ясны после прочтения описания одного из вариантов осуществления изобретения.

Также изобретение будет лучше понятно из следующих фиг.:

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

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

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

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

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

Это преобразование содержит, в конечном поле F_q, где характеристика q равна 3 mod 4, этап получения точки P(X,Y) на эллиптической кривой, удовлетворяющей выражению:

Y²=f(X).

Абсцисса Х точки P(X,Y) соответствует одному из элементов X₁(t), X₂(t) и X₃(t) для полученного значения t, так что

f ( X 1 ( t ) ) . f ( X 2 ( t ) ) . f ( X 3 ( t ) ) = U 2 ( t ) ,   ( 2 )

где X₁(t), X₂(t), Х₃(t) и U(t) - многочлены, удовлетворяющие равенству Скальба в конечном поле F_q.

Более конкретно, многочлены, которые удовлетворяют равенству Скальба и которые определены в документе «Рациональные точки на определенных гиперэллиптических кривых над конечными полями» («Rational points on certain hyperelliptic curves over finite fields»), автор Масие Улас (Macie Ulas), 11 июня 2007 года, представляют собой функции двух параметров u и t. В контексте настоящего изобретения одному из параметров может быть предпочтительно присвоено значение и, следовательно, многочлены, удовлетворяющие равенству Скальба, являются функциями одного параметра t.

Для определения точки на кривой при входных параметрах u и t мы попытаемся определить те числа из X₁=X₁(t,u), Х₂=X₂(t,u), Х₃=Х₃(t,u), которые соответствуют квадрату элемента в конечном поле F_q. Для этой цели предпочтительно предусмотреть применение двух различных вариантов обработки в зависимости от того, является ли элемент f(X₁).f(X₂) квадратом в конечном поле F_q.

На начальном этапе 100 с учетом параметра t вычисляют:

X_i=X_i(t) для i, равного от 1 до 3,

и

U=U(t).

На этапе 11 мы определяем, является ли элемент f(X₁).f(X₂) квадратом элемента. Это решение может быть основано на предыдущих вычислениях или может быть основано на проверке в ходе применения этого способа. Если элемент f(X₁).f(X₂) является квадратом, то элемент f(X₃) также является квадратом. В этом случае на этапе 12 предусматривают вычисление квадратного корня элемента f(X₃). Таким образом, на этапе 16 определяют точку Р, абсцисса Х₃ и ордината Y₃ которой удовлетворяют следующему выражению:

Y 3 = f ( X 3 ) .

Заметим, что если произведение f(X₁).f(X₂) является квадратом элемента, то из этого следует, что f(Х₃) также является квадратом. Тем не менее, чтобы определение точки на эллиптической кривой требовало постоянного времени, предусматривают применение проверки 10, в ходе которой проверяют, что элемент f(X₃) действительно является квадратом. Эта проверка 10 позволяет обеспечить постоянное время при применении способа, соответствующего одному варианту осуществления настоящего изобретения.

В противном случае, то есть когда элемент f(X₁).f(X₂) не является квадратом элемента, можно сказать, что или f(X₁) или f(X₂) является квадратом. Следовательно, мы можем сначала предусмотреть проверку на этапе 13, является ли квадратом элемент f(X₁). Если проверка завершилась положительно, то на этапе 14 вычисляют квадратный корень упомянутого элемента с целью получения ординаты точки Р:

Y 1 = f ( X 1 ) .

Таким образом, на этапе 17 мы получаем точку Р с абсциссой X₁ и ординатой Y₁.

Если проверка на этапе 13 выдает отрицательный ответ, то можно заключить, что элемент f(X₂) является квадратом. Следовательно, на этапе 15 мы получаем ординату Y₂ точки Р на эллиптической кривой в соответствии с выражением:

Y 2 = f ( X 2 ) .

Тогда точку P(X₂, Y₂) кривой можно получить на этапе 18.

Заметим, что достижение этапов 16, 17 или 18 с целью получения точки на эллиптической кривой в соответствии с одним вариантом осуществления настоящего изобретения требует аналогичных операций. Таким образом, независимо от входных параметров t и u, невозможно осуществить атаку на основе затраченного времени.

Тогда точку P(X_i, Y_i), для i, равного от 1 до 3, можно целесообразно использовать в следующих криптографических приложениях: при шифровании, или хешировании, или подписывании, или аутентификации, или идентификации, так как определение этой точки не предоставляет никаких элементов, которые могут помочь взломать секретность этой точки.

В поле F_q, в котором q соответствует 3 mod 4, возможно различными путями проверить, является ли элемент квадратом. Проверки того, является ли элемент квадратом, такие как проверки 10 и 13 с фиг.1, могут быть осуществлены следующим образом.

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