Асимметричные криптосистемы 3 страница. В дальнейшем будем считать, что эллиптическая кривая задана уравнением (1.24) с ограничением на коэффициенты (1.26)

. (1.26)

В дальнейшем будем считать, что эллиптическая кривая задана уравнением (1.24) с ограничением на коэффициенты (1.26).

Пусть на эллиптической кривой заданы две точки и (см. рис. 1.4). Проведенная через эти точки прямая пересечет кривую в третьей точке . Получим точку путем изменения знака ординаты точки .

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

Описанная операция имеет вид:

, (1.27)

и называется композицией точек или сложением точек на эллиптической кривой.

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

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

. (1.28)

Операция (1.28) называется удвоением точки.

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

Определим координаты результирующей точки на основе координат точек и .

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

.

Тогда уравнение прямой будет иметь вид

,

откуда

. (1.29)

Если подставить (1.29) в (1.24) получим

.

Проведя необходимые преобразования получаем кубическое уравнение

,

где , .

По теореме Виета для кубических уравнений [6] имеем

,

откуда

. (1.30)

Подставив найденное значение в уравнение прямой (1.29), определим ординату точки

, .

Изменив знак ординаты точки получим

. (1.31)

Таким образом, получены координаты точки .

Рассмотрим случай, когда и результирующая точка . Дифференцируя обе части (1.24) по получаем

.

Угловой коэффициент касательной равен значению производной в точке

.

Дальнейшие рассуждения аналогичны рассмотренному выше случаю, координаты точки определяются по тем же формулам (1.30) и (1.31).

Если ордината точки равна нулю, то касательная проходит параллельно оси ординат и .

Основные свойства точек на эллиптической кривой:

1) ;

2) ;

3) ;

4) .

Как видно перечисленные свойства точек на эллиптической кривой совпадают со свойствами целых чисел при использовании операции сложения. Рассмотрим еще несколько свойств композиции точек

1) , для любого целого числа ;

2) ;

3) .

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

В результате получаем кривую

. (1.32)

В уравнении (1.32) коэффициенты принимают целочисленные значения, а все вычисления выполняются по . В соответствии с (1.26) на налагается условие

. (1.33)

Множества состоит из точек , , удовлетворяющих (1.32) и точки в бесконечности . Количество точек в обозначается # . Эта величина имеет важное значение для эллиптической криптографии.

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

Число точек на кривой, при надлежаще выборе параметров и , может быть простым числом, # . В этом случае любая точка (кроме точки ) является генератором всего множества точек. Такая кривая предпочтительна и может быть вычислена за приемлемое время. Если по каким-то причинам такую кривую не удалось отыскать и # , то в существует подмножество из точек, генератором которого может служить любая точка , такая что .

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

.

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

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

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

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

1. Выбирается случайное число .

Битовая длина числа , , должна быть такой, чтобы сделать невозможным применение общих методов нахождения логарифмов на эллиптической кривой. Величина 160 бит в настоящее время вполне приемлема. С другой стороны, криптосистема на эллиптической кривой должна быть не менее стойкой, чем блочная криптосистема AES. Стойкость криптосистемы AES определяется длиной ее ключа (128, 196, 256 бит), а для криптосистем на эллиптических кривых при равной криптостойкости величина модуля должна быть в два раза больше, т.е. 256, 392, 512 бит, соответственно [7,9].

2. Выбирается числа , такие что и .

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

3. Определяют число точек на эллиптической кривой # .

Это самый трудоемкий этап. Базовый алгоритм (алгоритм Схоуфа) определения числа точек эллиптической кривой подробно рассмотрен в [7,9]. Важно, чтобы имело большой простой делитель , а лучше всего само было простым числом .

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

Если поиск кривой с занимает слишком много времени, то допускают, чтобы , где - небольшое число.

Необходимо отметить, что стойкость криптосистемы на эллиптической кривой определяется не модулем , числом элементов в подмножестве точек кривой. Однако, если - небольшое число, то является величиной того же порядка что и .

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

4. Проверка выполнения неравенств для всех , . Если неравенство не выполняется, то необходимо вернуться ко второму этапу.

Эта проверка предотвращает возможность MOV-атаки, названной в честь ее авторов - Menezes, Okamoto, Vanstone, а также исключает из рассмотрения суперсингулярные эллиптические кривые и кривые с # .

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

6. Определение точки . На данном этапе искомая эллиптическая кривая найдена, определены параметры , число точек и размер подмножества точек .

Если , то любая точка, кроме точки , является точкой-генератором .

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

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

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

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

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

Каждый абонент сети выбирает случайное число , , которое является секретным ключом, и вычисляет точку

,

которая является открытым ключом. Параметры эллиптической кривой и открытые ключи передаются всем пользователям сети.

Абонент желает передать сообщение абоненту . Открытый текст должен удовлетворять условию .

Абонент выбирает случайное число , . Затем вычисляет:

,

,

и производиться шифрование

.

Полученную криптограмму абонент передает абоненту .

Абонент вычисляет

,

.

□ ,

то есть . ■

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

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

1.8. Криптосистемы, основанные на задаче «об укладке рюкзака»

При рассмотрении односторонних функций в пункте 1.1 было отмечено, что криптосистемы, основанные на задаче «об укладке рюкзака» в настоящее время не находят применения. Однако, в данном пункте мы все же рассмотрим кратко принцип построения криптосистем, основанных на использовании задачи «об укладке рюкзака». Такими криптосистемами являются криптосистемы Меркля-Хеллмана и Хора-Ривеста [2].

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

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

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

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

Дата добавления: 2014-12-26