×
20.11.2014
216.013.08f4

КОДИРОВАНИЕ ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ

Вид РИД

Изобретение

Юридическая информация Свернуть Развернуть

Правообладатели

№ охранного документа
0002533693
Дата охранного документа
20.11.2014
Краткое описание РИД Свернуть Развернуть
Аннотация: Изобретение относится к криптографической обработке сообщений, основанной на использовании точек эллиптической кривой, и, в частности, такой криптографии, которая носит детерминистический характер. Техническим результатом является повышение уровня защиты и сокращение времени вычислений при криптографической обработке за счет эффективного получения точек на эллиптической кривой и отсутствия зависимости времени вычисления от кодируемого сообщения. В электронном компоненте выполняют криптографическое вычисление, содержащее этап получения точек Р на эллиптической кривой. Определяют параметр (11), затем получают координаты Х и Y точки Р (13) посредством применения к этому параметру функции (12). Функция является обратимой и детерминистической функцией. После этого точку Р используют для применения в криптографии для шифрования, или хеширования, или подписи, или аутентификации, или идентификации. 7 н. и 5 з.п. ф-лы, 1 ил.
Реферат Свернуть Развернуть

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

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

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

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

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

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

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

где а1, а2, а3, а4 и a6 являются элементами множества А элементов,

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

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

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

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

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

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

φ(А)mod3=1,

причем указанная функция является обратимой и детерминистической функцией, выраженной рациональной дробью в a1, а2, а3, а4 и а6 и в указанном параметре в А и достигающей, по меньшей мере, числа d/4I точек Р при I, равном 1 для конечного поля Fq;

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

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

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

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

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

φ(A)=q-1

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

φ(А)=ppcm(p1 - 1, р2 - 1,…, pi - 1)

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

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

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

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

хφ(A)=1

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

(x3)(2φ(А)+1)/3=x3(2φ(А)+1)/3=x2φ(A)+1=x

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

x(2φ(A)+1)/3=x1/3

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

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

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

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

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

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

Y2=X3+аХ+b, при а=а2 и b=а6.

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

и

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

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

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

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

q=2n;

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

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

Y2+XY=X3+аХ2+b, при а=а2 b=а6; и

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

Y=uX+w2

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

где w=a+u2+u.

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

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

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

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

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

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

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

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

f(h)+h′.G,

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

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

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

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

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

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

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

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

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

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

где a1, а2, а3, а4 и а6 являются элементами множества А элементов,

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

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

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

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

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

φ(А)mod3=1,

причем указанная функция является обратной функцией детерминистической функции, выраженной рациональной дробью в а1, а2, а3, а4 и a6 и в указанном параметре в А и достигающей по меньшей мере числа d/4I точек Р при I, равном 1 для конечного поля Fq;

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

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

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

где а1, а2, a3, a4 и a6 являются элементами множества А элементов,

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

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

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

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

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

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

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

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

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

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

где a1, а2, a3, а4 и а6 являются элементами множества А,

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

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

φ(А)=1mod3, (2)

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

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

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

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

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

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

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

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

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

и

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

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

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

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

b=y2-x3-ах

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

Действительно, прежде всего все точки P1 с координатами (x1, y1), Р2 с координатами (х2, y2) и Р с координатами (x, y) являются точками эллиптической кривой Еa,b.

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

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

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

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

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

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

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

fa,b(u)=P

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

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

q/4≤#Im(fa,b)≤q

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

В варианте выполнения настоящего изобретения можно использовать эллиптические кривые на кольце Z/qZ, где q является произведением I простых чисел p1, …, pI. Китайская теорема об остатках, результат модулярной арифметики, рассматривающая решение системы конгруэнтностей, утверждает, что Z/qZ является изоморфным к Z/p1Z x… x Z/pIZ. Поэтому можно в равной степени исследовать эллиптические кривые на каждом из Z/piZ. Однако, поскольку каждое рi является простым числом, то по сути дела Z/piZ является полем, которое можно обозначить Fpi. Кроме того, поскольку каждое рi строго превышает 3, уравнение эллиптической кривой на Fpi является уравнением типа Вейерштрасса.

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

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

pi/4≤#Im(fa,b)≤pi

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

p1/4 x … x pI/4=q/4I≤#Im(fa,b)≤p1 x … x pI=q

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

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

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

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

2nmod3=2

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

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

w=а+u2+u

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

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

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

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

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

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

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

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

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

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

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

fa(u)=(x,y)

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

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

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

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

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

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

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

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

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

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

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

Функцию fa,b согласно варианту выполнения настоящего изобретения используют для определения точки на эллиптической кривой. G, точку-генератор группы используемых точек, то есть точек отображения fa,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)=gcd

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

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

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

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

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


КОДИРОВАНИЕ ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
КОДИРОВАНИЕ ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
КОДИРОВАНИЕ ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
КОДИРОВАНИЕ ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
КОДИРОВАНИЕ ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
КОДИРОВАНИЕ ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
КОДИРОВАНИЕ ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
КОДИРОВАНИЕ ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
КОДИРОВАНИЕ ТОЧЕК ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
Источник поступления информации: Роспатент

Показаны записи 1-10 из 20.
27.05.2013
№216.012.4576

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

Изобретение относится к области карт с интегральной схемой. Техническим результатом является повышение надежности. Раскрывается смарт-карта, включающая в себя модуль (3) обработки, ассоциированный с ROM (4) и с программируемым ROM (5), ROM, содержащее рабочую программу, которая может быть...
Тип: Изобретение
Номер охранного документа: 0002483359
Дата охранного документа: 27.05.2013
27.06.2014
№216.012.d549

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

Изобретение относится к способу и устройству выполнения криптографического преобразования в электронном компоненте. Технический результат заключается в повышении безопасности установки соединений с аутентификацией пароля за счет повышения эффективности выполнения криптографического...
Тип: Изобретение
Номер охранного документа: 0002520379
Дата охранного документа: 27.06.2014
20.11.2014
№216.013.0696

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

Изобретение относится к способу, устройству и системе проверки устройства с помощью контроллера на основе пароля. Технический результат заключается в повышении безопасности за счет шифрования с параметризацией на эллиптической кривой. Способ содержит этапы, на которых на основе случайного числа...
Тип: Изобретение
Номер охранного документа: 0002533087
Дата охранного документа: 20.11.2014
27.04.2015
№216.013.465d

Карта с интегральной микросхемой с защищенным входным/выходным буфером

Изобретение относится к вычислительной технике. Технический результат заключается в обеспечении защиты карты. Карта с интегральной микросхемой содержит блок обработки, связанный с оперативным запоминающим устройством и со средствами обмена данными с внешним устройством, причем оперативное...
Тип: Изобретение
Номер охранного документа: 0002549517
Дата охранного документа: 27.04.2015
27.06.2015
№216.013.5999

Способ поиска объекта с использованием устройства верификации и соответствующие устройства

Изобретение относится к вычислительной технике. Технический результат заключается в обеспечении защиты идентификации объектов для предотвращения отслеживания объектов третьими лицами. Способ поиска объекта, принадлежащего набору объектов, с использованием устройства верификации, причем...
Тип: Изобретение
Номер охранного документа: 0002554478
Дата охранного документа: 27.06.2015
10.02.2016
№216.014.c27c

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

Изобретение относится к области шифрования сообщений на основе использования точек на эллиптической кривой. Технический результат - повышение надежности криптографического шифрования за счет выполнения аутентификации и идентификации за одно и то же время. Способ выполнения аутентификации пароля...
Тип: Изобретение
Номер охранного документа: 0002574826
Дата охранного документа: 10.02.2016
10.04.2016
№216.015.2c33

Защита от пассивного сниффинга

Изобретение относится к защите исполнения криптографического алгоритма (ALG) от пассивного сниффинга. Технический результат - эффективная защита от пассивного сниффинга. Способ защиты исполнения криптографического алгоритма (ALG) от пассивного сниффинга реализует маскирование (MSK) данных,...
Тип: Изобретение
Номер охранного документа: 0002579990
Дата охранного документа: 10.04.2016
10.06.2016
№216.015.48e7

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

Изобретение относится к вычислительной технике. Технический результат заключается в улучшении характеристики маскирования перехода к концу срока службы электронного устройства при поддержании уровня безопасности. Способ маскирования перехода к концу срока службы электронного устройства, в...
Тип: Изобретение
Номер охранного документа: 0002586871
Дата охранного документа: 10.06.2016
13.01.2017
№217.015.872a

Защита апплетов от анализа скрытых каналов

Изобретение относится к области защиты апплетов от анализа. Техническим результатом является эффективная защита от атак через скрытые каналы. Раскрыто электронное устройство для защиты от атак, оснащенное виртуальной машиной для исполнения апплета, при этом виртуальная машина выполнена с...
Тип: Изобретение
Номер охранного документа: 0002603545
Дата охранного документа: 27.11.2016
13.01.2017
№217.015.88a9

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

Изобретение относится к управлению и контролю различных данных личной идентификации. Технический результат - создание производной идентификации на базе родительской идентификации, при этом между этими двумя идентификациями невозможно отследить на практике. Способ управления и контроля различных...
Тип: Изобретение
Номер охранного документа: 0002602785
Дата охранного документа: 20.11.2016
Показаны записи 1-10 из 17.
27.05.2013
№216.012.4576

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

Изобретение относится к области карт с интегральной схемой. Техническим результатом является повышение надежности. Раскрывается смарт-карта, включающая в себя модуль (3) обработки, ассоциированный с ROM (4) и с программируемым ROM (5), ROM, содержащее рабочую программу, которая может быть...
Тип: Изобретение
Номер охранного документа: 0002483359
Дата охранного документа: 27.05.2013
27.06.2014
№216.012.d549

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

Изобретение относится к способу и устройству выполнения криптографического преобразования в электронном компоненте. Технический результат заключается в повышении безопасности установки соединений с аутентификацией пароля за счет повышения эффективности выполнения криптографического...
Тип: Изобретение
Номер охранного документа: 0002520379
Дата охранного документа: 27.06.2014
20.11.2014
№216.013.0696

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

Изобретение относится к способу, устройству и системе проверки устройства с помощью контроллера на основе пароля. Технический результат заключается в повышении безопасности за счет шифрования с параметризацией на эллиптической кривой. Способ содержит этапы, на которых на основе случайного числа...
Тип: Изобретение
Номер охранного документа: 0002533087
Дата охранного документа: 20.11.2014
27.04.2015
№216.013.465d

Карта с интегральной микросхемой с защищенным входным/выходным буфером

Изобретение относится к вычислительной технике. Технический результат заключается в обеспечении защиты карты. Карта с интегральной микросхемой содержит блок обработки, связанный с оперативным запоминающим устройством и со средствами обмена данными с внешним устройством, причем оперативное...
Тип: Изобретение
Номер охранного документа: 0002549517
Дата охранного документа: 27.04.2015
27.06.2015
№216.013.5999

Способ поиска объекта с использованием устройства верификации и соответствующие устройства

Изобретение относится к вычислительной технике. Технический результат заключается в обеспечении защиты идентификации объектов для предотвращения отслеживания объектов третьими лицами. Способ поиска объекта, принадлежащего набору объектов, с использованием устройства верификации, причем...
Тип: Изобретение
Номер охранного документа: 0002554478
Дата охранного документа: 27.06.2015
10.02.2016
№216.014.c27c

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

Изобретение относится к области шифрования сообщений на основе использования точек на эллиптической кривой. Технический результат - повышение надежности криптографического шифрования за счет выполнения аутентификации и идентификации за одно и то же время. Способ выполнения аутентификации пароля...
Тип: Изобретение
Номер охранного документа: 0002574826
Дата охранного документа: 10.02.2016
10.04.2016
№216.015.2c33

Защита от пассивного сниффинга

Изобретение относится к защите исполнения криптографического алгоритма (ALG) от пассивного сниффинга. Технический результат - эффективная защита от пассивного сниффинга. Способ защиты исполнения криптографического алгоритма (ALG) от пассивного сниффинга реализует маскирование (MSK) данных,...
Тип: Изобретение
Номер охранного документа: 0002579990
Дата охранного документа: 10.04.2016
10.06.2016
№216.015.48e7

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

Изобретение относится к вычислительной технике. Технический результат заключается в улучшении характеристики маскирования перехода к концу срока службы электронного устройства при поддержании уровня безопасности. Способ маскирования перехода к концу срока службы электронного устройства, в...
Тип: Изобретение
Номер охранного документа: 0002586871
Дата охранного документа: 10.06.2016
13.01.2017
№217.015.872a

Защита апплетов от анализа скрытых каналов

Изобретение относится к области защиты апплетов от анализа. Техническим результатом является эффективная защита от атак через скрытые каналы. Раскрыто электронное устройство для защиты от атак, оснащенное виртуальной машиной для исполнения апплета, при этом виртуальная машина выполнена с...
Тип: Изобретение
Номер охранного документа: 0002603545
Дата охранного документа: 27.11.2016
13.01.2017
№217.015.88a9

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

Изобретение относится к управлению и контролю различных данных личной идентификации. Технический результат - создание производной идентификации на базе родительской идентификации, при этом между этими двумя идентификациями невозможно отследить на практике. Способ управления и контроля различных...
Тип: Изобретение
Номер охранного документа: 0002602785
Дата охранного документа: 20.11.2016
+ добавить свой РИД