Нир: «Разработка программного комплекса шифрования данных, на основе использования точек эллиптической кривой» - umotnas.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Разработка генератора псевдослучайных чисел на точках эллиптической... 1 58.07kb.
Методические указания к лабораторным работам по курсу «Теория информациии... 3 447.96kb.
Реализация программного комплекса, моделирующего вычислительные комплексы... 1 72.18kb.
Минимизация ошибок и сбоев программного обеспечения 1 62.06kb.
М. М. Степанова Разработка в программном комплексе distolymp подсистем... 1 11.13kb.
Расчётно-графическая работа Новый стандарт симметричного шифрования aes 1 173.9kb.
Программа здесь >>>> система шифрования и встраивания информации... 1 15.61kb.
Инструкция по обработке археологических данных в программном комплексе... 1 313.02kb.
Шифр нир (окр) Наименование нир (окр) 1 113.24kb.
«Защита программного обеспечения от несанкционированного использования... 1 11.48kb.
5 Оценка стоимости разработки программного комплекса 1 71.74kb.
Учебное пособие для студентов Новосибирск 2003 10 3596kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Нир: «Разработка программного комплекса шифрования данных, на основе использования - страница №3/4


4 Анализ методов и алгоритмов умножения точки эллиптической кривой на скаляр
В последние годы интенсивно развивается и имеет важные приложения в различных областях науки и техники прикладная теория чисел. Например, в настоящее время, практически весь мировой парк средств асимметричной криптографии (алгоритмы Диффи-Хеллмана и RSA) в математическом плане основан на теоретико-числовых задачах, которые приводят к большим объемам вычислений над многоразрядными числами [46].

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



  1. Алгоритмов проверки простоты целых чисел специального вида.

  2. Алгоритмов проверки простоты целых чисел произвольного вида.

  3. Методов факторизации, то есть методов поиска разложения целых чисел на множители.

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

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

Один из интересных способов кодирования информации и выполнения действий с многоразрядными числами основан на некоторых простых фактах теории чисел. Идея этого метода состоит в том, чтобы иметь несколько модулей , , …, , которые попарно взаимно просты, и оперировать не непосредственно с числами , а с его “остатками” , , ..., .

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

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



Утверждение 4.1 .

Доказательство

Для доказательства нам достаточно показать, что делится на . Для этого представим в виде , где и и . Рассмотрим 2 случая.

1 Случай. Если , то и

следовательно делится .

2. Случай. Если , то , следовательно делится .

Утверждение доказано.

Пример 4.1 Вычислить

Решение


Используя утверждение + получим





Как видно из примера 2, что операция редукция по модулю при применение утверждения 2 сводится к операции сложения и вычитания.



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

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



Алгоритм 4.1 Нахождения представления числа ()

Вход:

Выход:

  1. For to do





  2. While And do ;

  3. If then

    1. For to do



  4. For to do





  5. Writeln()

Алгоритм 4.1 основан на следующем утверждении.

Утверждение 4.1 Пусть заданно число в системе остаточных классов по модулям , то тогда справедливо равенство

, где

Доказательство





Утверждение доказано.



Алгоритм 4.2 Сравнение чисел в СОК ()

Вход: ,,

Выход: если то 1. Если то 0. Если то -1.





  1. If then

    1. Writeln(-1)

    2. Goto 15

  2. If then

    1. Writeln(1)

    2. Goto 15

  3. If And then



    1. While And do

    2. If then

      1. Writeln(-1)

      2. Goto 15

    3. If then

      1. Writeln(1)

      2. Goto 15

    4. If then

      1. Writeln(0)

  4. End

Алгоритм 4.3 Сложение чисел и по модулю простого числа в СОК ()

Вход: , , ,

Выход:



  1. Flag:=

  2. If then

    1. Writeln()

Else

    1. Writeln()

  1. End.

Алгоритм 4.4 Нахождения представления числа ()

Вход:

Выход:

  1. For to do





  2. While And do ;

  3. If then

    1. For to do





  4. For to do





  5. Writeln()

Алгоритм 1.5 Умножение двух чисел и по модулю ()

Вход: , , , ,

Выход:





























  1. Writeln()

Утверждение 4.2 Алгоритм умножения чисел в СОК по модулю простого числа работает корректно.

Доказательство

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

, где ,

, где

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

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

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



,

(4.1)

где — сложность сложения двух точек, — сложность удвоения. Из этого алгоритма можно выделить три стратегии ускорения:

Рисунок 4.1 – Блок-схема двоичного алгоритма вычисления

Можно ускорить представление, например, использовать представление по другому основанию.

Можно уменьшить количества учениц двоичного представления . Это уменьшит количество сложений в предложенном алгоритме

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

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



Блок-схема алгоритма вычисление двоичного сбалансированного представления представлена на рисунке 4.2.



Рисунок 4.2 – Блок-схема алгоритма вычисление двоичного сбалансированного представления

Сбалансированное двоичное представление имеет следующее свойства:

1. Произведение двух подряд идущих символов последовательности будет нулевым.

2. Длина последовательности составляет .

3. Среднее количество единиц в векторе равно .

4. В худшем случае количество единиц составляет .

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

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

Рисунок 4.3 – Блок-схема алгоритма, использующего сбалансированное представление для вычисления .


Поскольку в среднем количество ненулевых символов в двоичной сбалансированной последовательности равно , то количество операций равно



(4.2)

Рассмотрим метод окон, схема которого приведена на рисунке 4.4:

Рисунок 4.4 – Схема метода окон

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

,

тогда

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

1. Длина последовательности составляет .

2. В среднем количество ненулевых элементов последовательности составляет .

Необходимое количество предвычислений составляет



.

Сложность вычислений в среднем составляет



,

(4.3)

так как метод окна обладает свойством (2).

В таблице 4.1 представлена сравнительная оценка временных показателей умножения точки эллиптической кривой на скаляр [47] при использовании различных систем счисления. (Время указано в миллисекундах)

Из таблицы 4.1 следует, что самым быстрым является метод окон, но у него есть один недостаток: необходимость больших предвычислений. Метод NAF немного уступает методу окон в скорости выполнения операций, но не требует предвычислений, поэтому в случае, когда у вычислительного устройства ограничена память, целесообразно использовать метод NAF. Сравнивая в таблице 4.1 столбец где приведено время работы методов и алгоритмов работающих в позиционной системе исчисления со столбцом в СОК, замечаем, что при выполнении операций в СОК можно получать существенное преимущество в скорости вычисления в среднем на 58%.
Таблица 4.1 – Сравнительная оценка временных показателей умножения точки эллиптической кривой на скаляр при использовании различных систем счисления




Название

Позиционная система исчисления

СОК

1

Двоичный

11.794

7.076

2

NAF

10.028

6

3

Метод окон

9.956

5.8

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

Алгоритмы кодирования алфавитов делятся на вероятностные и детерминированные.

Проанализируем вероятностный алгоритм кодирования алфавита точками эллиптической кривой (1.1), предложенный в 1985 году Н. Коблиц [48], блок-схема которого приведена на рисунке 5.1.

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



Рисунок 5.1 – Блок-схема вероятностного алгоритма кодирования алфавита точками эллиптической кривой

Рассмотрим алгоритм декодирования (рисунок 5.2).

Рисунок 5.2 – Блок-схема вероятностного алгоритма декодирования символа из точки эллиптической кривой

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

Недостатки алгоритма:

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

2. С помощью данного алгоритма можно закодировать алфавит, мощность которого равна , что приблизительно в раз меньше, чем количество точек на эллиптической кривой, согласно теореме Хассе.

Проведем анализ детерминированного алгоритма кодирования алфавитов точками эллиптических кривых, предложенного в работе [49].

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



Определение 5.1: Две эллиптические кривые:: и : , заданные над конечным полем , где — простое число, , , называются дуальными, если имеет место следующие соотношение:

,

(5.1)

где — квадратичный невычет по модулю .

Для дуальных эллиптических кривых справедлива следующая теорема.



Теорема 5.1 [49]: Пусть и — две дуальные эллиптические кривые над конечным полем , . Тогда



(5.2.)

Перейдем теперь к алгоритму кодирования рисунок 5.3.

Рисунок 5.3 – Блок-схема алгоритма кодирования алфавита точками эллиптической кривой


Рассмотрим применения алгоритма 3 к кодированию алфавита точками эллиптических кривых из работы [50], которые рекомендованы в США.

Пример 5.1. Эллиптическая кривая : задана над полем , где — простое число. Закодировать числа .

Рассмотрим эллиптическую кривую :





Так как — простое число вида , то является квадратичным невычетом в и, значит, .

Вычислим и :



Найдем, для каких значений значение выражения является квадратичным вычетом в , а для каких — невычетом в .

Результат вычислений приведен в таблице 5.1, где знаком «+» обозначается квадратичный вычет в , а знаком «–» обозначается квадратичный невычет в .
Таблица 5.1 – Таблица принадлежности точек для эллиптической кривой




0

1

2

3

4

5

6

7

8

9

10

11

12

13

14



+

+

-

-

-

-

-

+

+

-

-

+

-

-

-



-

-

+

+

+

+

+

-

-

+

+

-

+

+

+

Мы получили, что в строке эллиптической кривой количество плюсов равно 5, а в строке эллиптической кривой — 10 плюсов. Таким образом, кодирование будет осуществляться с помощью эллиптической кривой .

Для кодирования числа «0» воспользуемся строкой с номером 2. Этой строке соответствует точка

Таким образом, «0» будет закодирован точкой . Кратко будем записывать так.

















Найдем . Так как , то, используя теорему 5.1, получим, что



Из того, что максимальный множитель в разложении равен следует, что, используя метод Полларда, задачу дискретного логарифмирования можно решить за операций с точками на эллиптической кривой [42]. При условии, что современная техника может производить операций с точками на эллиптической кривой, то задачу дискретного логарифмирования на эллиптической кривой можно решить за 4 часа 30 минут. На основе этих данных мы можем сделать вывод, что данная эллиптическая кривая непригодна к использованию в криптографических целях.


2. Рассмотрим эллиптическую кривую :

Найдем наименьший квадратичный невычет.

Числа 1, 4, 9 являются квадратичными вычетами , так как представимы в виде: , , .

Так как имеет вид , то из свойств символа Лежандра является квадратичным вычетом в , следовательно, и является квадратичным вычетом в .

Из того, что имеет вид , следует, что 3 является квадратичным вычетом в , значит, и является квадратичным вычетом в .

Вычислим символ Лежандра для чисел , , , получим:



, , , следовательно, наименьшим квадратичным невычетом в , является , значит, .

Найдем и :





Найдем, для каких значений значение выражения является квадратичным вычетом в , а для каких — невычетом в .

Результат вычислений представлен в таблице 5.2, где знаком «+» обозначается квадратичный вычет в , а знаком «–» обозначается квадратичный невычет в .
Таблица 5.2 – Таблица принадлежности точек для эллиптической кривой




0

1

2

3

4

5

6

7

8

9

10

11

12

13

14



-

-

-

-

+

+

-

+

-

+

+

-

-

-

-



+

+

+

+

-

-

+

-

+

-

-

+

+

+

+

Из таблицы видно, что в строке содержится 5 плюсов, а в строке — 10 плюсов. Таким образом, кодирование будет осуществляться с помощью эллиптической кривой .

















Найдем . Так как , то, используя теорему 5.1, получим, что

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

3. Рассмотрим эллиптическую кривую :



Так как — простое число вида , то является квадратичным невычетом в . Значит, Вычислим и :





Найдем, для каких значений значение выражения является квадратичным вычетом в , а для каких — невычетом в .

Результат вычислений представлен в таблице 5.3, где знаком «+» обозначается квадратичный вычет в , а знаком «–» обозначается квадратичный невычет в .
Таблица 5.3. – Таблица принадлежности точек для эллиптической кривой




0

1

2

3

4

5

6

7

8

9

10

11

12

13

14



+

-

+

-

-

+

-

+

+

-

-

-

-

-

-



-

+

-

+

+

-

+

-

-

+

+

+

+

+

+

Из таблицы видно, что в строке содержится 5 плюсов, а в строке — 10 плюсов. Таким образом, кодирование будет осуществляться с помощью эллиптической кривой .















Найдем . Так как , то, используя теорему 5.1, получим, что

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

4. Рассмотрим эллиптическую кривую :



Так как — простое число вида , то является квадратичным невычетом в и, значит,

Вычислим и :



Найдем, для каких значений значение выражения является квадратичным вычетом в , а для каких — невычетом в .

Результат вычислений представлен в таблице 5.4, где знаком «+» обозначается квадратичный вычет в , а знаком «-» обозначается квадратичный невычет в
Таблица 5.4 – Таблица принадлежности точек для эллиптической кривой




0

1

2

3

4

5

6

7

8

9

10

11

12

13

14



+

+

-

+

-

+

-

-

-

-

+

-

-

-

+



-

-

+

-

+

-

+

+

+

+

-

+

+

+

-

Из таблицы видно, что в строке содержится 6 плюсов, а в строке — 9 плюсов. Таким образом, кодирование будет осуществляться с помощью эллиптической кривой .

















Найдем . Так как , , то, используя теорему 5.1, получим, что

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

5. Рассмотрим эллиптическую кривую :



Так как — простое число вида , то является квадратичным невычетом в , значит,



Вычислим и :





Найдем, для каких значений значение выражения является квадратичным вычетом в , а для каких — невычетом в .

Результат вычислений представлен в таблице 5.5, где знаком «+» обозначается квадратичный вычет в , а знаком «–» обозначается квадратичный невычет в .
Таблица 5.5 – Таблица принадлежности точек для эллиптической кривой




0

1

2

3

4

5

6

7

8

9

10

11

12

13

14



+

-

-

+

-

+

+

+

-

-

+

-

-

+

+



-

+

+

-

+

-

-

-

+

+

-

+

+

-

-

Из таблицы видно, что в строке содержится 8 плюсов, а в строке — 7 плюсов. Таким образом, кодирование будет осуществляться с помощью эллиптической кривой .















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

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


над ,

(5.3)

где , – попарно простые числа и

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



Рисунок 5.4 – Блок-схема алгоритм кодирования алфавита точками эллиптической кривой, заданной уравнением (5.3)


Теперь для данного алгоритма предложим алгоритм декодирования (рисунок 5.5).

Функция переводит число из системы остаточных классов в десятеричную систему исчисления, где — пара чисел, представленных в системе остаточных классов, а — трехмерный массив, где каждой тройке чисел соответствует число, равное представлению восстанавливаемого числа в системе остаточных классов.

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

Рисунок 5.5 – Блок-схема алгоритм декодирования алфавита из точек эллиптической кривой, заданной уравнением (2.3)


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