Быстрые алгоритмы вычисления преобразований на основе эллиптических кривых Хлебородов Денис Сергеевич

Содержание к диссертации

Введение

1 Операции в группе точек эллиптической кривой 14

1.1 Эллиптические кривые 14

1.2 Преобразования на основе эллиптических кривых 17

1.3 Операции на основе эллиптических кривых

1.3.1 Операции в простом поле 17

1.3.2 Арифметические операции с точкой 18

1.3.3 Скалярные арифметические операции 24

1.4 Композиция операций 27

1.4.1 Операции вида dP ЕВ Q 27

1.4.2 Операции вида dP 35

1.5 Метод замены умножений 42

1.5.1 Быстрые формулы для традиционных операций 44

1.5.2 Быстрые формулы для композитных операций 46

1.6 Многоосновные скалярные умножения 47

1.6.1 Метод многоосновного несовместного представления 47

1.6.2 Метод многоосновного несовместного представления с окном 48

1.6.3 Метод расширенного многоосновного несовместного представления с ок

2 Эффективные алгоритмы вычисления преобразований на основе эллип тических кривых 52

2.1 Архитектура системы алгоритмов 52

2.1.1 Уровень С\ 52

2.1.2 Уровень С-2 53

2.1.3 Уровень з 54

2.1.4 Уровень С 54

2.1.5 Уровень 5 55

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

2.3 Эффективные эллиптические кривые 56

2.4 Эффективная операция DA 56

2.5 Эффективные алгоритмы скалярного умножения точки эллиптической кривой

2.5.1 Алгоритм на основе метода бинарного представления скаляра 57

2.5.2 Алгоритм на основе метода бинарной несовместной формы представления скаляра 64

2.5.3 Алгоритм на основе метода несовместной формы представления скаляра c окном 68

2.5.4 Алгоритм на основе метода несовместной формы представления скаляра со скользящим окном 2.6 Эффективные композитные операции 78

2.7 Эффективный алгоритм мультискалярного умножения

2.7.1 Быстрые предвычисления 85

2.7.2 Основная часть алгоритма 89

2.8 Выводы 89

3 Композиции алгоритмов вычисления преобразований на основе эллиптических кривых 91

3.1 Вычислительная сложность алгоритмов вычисления операций с большими це лыми числами 91

3.1.1 Операция сложения 91

3.1.2 Операция умножения 91

3.2 Вычислительная сложность операций в простом поле 93

3.2.1 Приведение по модулю 93

3.2.2 Мультипликативный обратный элемент 93

3.3 Алгоритмы скалярного умножения точки эллиптической кривой, полученные композициями 94

3.3.1 Алгоритмы без предварительных вычислений точек 94

3.3.2 Алгоритмы с предварительными вычислениями точек 105

3.4 Выводы 117

Заключение 118

Список литературы

• Операции в простом поле
• Критерий эффективности алгоритмов вычисления преобразований на основе эллиптических кривых
• Алгоритм на основе метода бинарного представления скаляра
• Вычислительная сложность операций в простом поле

Введение к работе

Актуальность проблемы. Преобразования на основе эллиптических кривых широко используются в системах защиты информации с открытым ключом, в частности, при вычислении цифровых подписей в отечественном (ГОСТ Р 34.10–2012) и ряде зарубежных (FIPS PUB 186, ANSI X9.62, SECG) стандартах. Такие системы защиты информации, построенные на основе эллиптических кривых, позволяют снизить вычислительные затраты, энергопотребление и объем используемой памяти при обеспечении высокого уровня безопасности. Преобразования на основе эллиптических кривых находят также свое применение в алгоритмах факторизации целых чисел (метод Ленстры — ECM, Elliptic Curve Factorization Method) и в алгоритмах тестирования натуральных чисел на «простоту». Как следствие, упомянутые выше алгоритмы представляют как практический, так и теоретический интерес.

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

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

1. Провести критический сравнительный анализ известных на настоящее время алгоритмов в группе точек эллиптической кривой.

¹ГОСТ Р 34.10-2012. «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи», 2012

²FIPS 186-2. Digital Signature Standard (DSS). National Institute of Standards and Technology, 2000

³ANSI X9.62:2005. Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), 2005

⁴SEC 1: Elliptic Curve Cryptography. Standards for Efcient Cryptography, 2009

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

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

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

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

Методы исследований. В качестве методов исследований применялись: теория алгоритмов; теория сложности вычислений; аппарат высшей алгебры и теории чисел; компьютерное моделирование.

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

Научная новизна исследования заключается в следующем.

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

2. Получены новые алгоритмы и модификации алгоритмов в группе точек эллиптической кривой.

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

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

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

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

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

5. Новые алгоритмы вычисления преобразований на основе эллиптических кривых и новые оценки их вычислительной сложности.

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

7. Результаты сравнительного анализа эффективности композиций алгоритмов вычисления преобразований на основе эллиптических кривых.

Публикации. Результаты исследований опубликованы в шести научных работах [1–6], из которых пять [1–5] — в изданиях, рекомендованных ВАК Министерства образования и науки РФ. Список работ представлен в заключительной части автореферата.

Апробация результатов работы. Результаты диссертационного исследования докладывались на следующих конференциях и семинарах:

международная научно-практическая конференция «Инженерные системы» (24–26 апреля 2013 года, г. Москва);

семинар кафедры «Информационная безопасность» МГТУ имени Н. Э. Баумана в 2014 году;

семинар кафедры «Математическое моделирование» МГТУ имени Н. Э. Баумана в 2014 году;

семинар «Математические методы криптографического анализа» на факультете ВМиК МГУ имени М. В. Ломоносова в 2015 году;

семинар кафедры «Прикладной информатики и теории вероятностей» РУДН в 2015 году;

семинар кафедры «Информационная безопасность» на факультете ВМиК МГУ имени М. В. Ломоносова в 2016 году.

Структура и объем работы. Рукопись диссертации состоит из введения, трех глав, заключения и библиографического списка. Диссертация изложена на 125 страницах, содержит 24 иллюстрации и 23 таблицы. Библиографический список включает 73 наименования.

Операции в простом поле

В итоге, поскольку предложенная операция утроения требует одно удвоение и одно специальное сложение, сложность составляет (4М + 4S) + (5М + 2S) = 9М + 6S.

Данный результат на одно умножение меньше, чем утроение, предложенное [34]. Тем не менее, операции были изменены для частного случая а = —3, уменьшающего сложность утроения до ЮМ + 4S, что быстрее чем предложенное утроение. Общая сложность вычисления составляет 9М + 5S, что делает его более эффективным для утроения точки.

Обобщение к композитным операциям dP Описанный подход, ускоряющий утроение, может быть обобщен для любого нечетного положительного целого d 3 (для повышения эффективности d также должно быть нечетным). Ускоренная операция dP Рассмотрим следующее соотношение: dP = (2Р ЕВ Р) ЕВ 2Р ЕВ 2Р ЕВ ..., (1.33) где каждое сложение может быть вычислено специальным сложением с идентичной Z-координатой (1.33).

Отметим, что последнее возможно, поскольку 2Р всегда имеет точку с идентичной Z-координатой в результате текущих вычислений. Например, в случае пятикратного увеличения точки (5Р), сложение следуемое за операцией утроения будет выглядеть как (ЗР) ЕВ2Р = (Хз, Уз, Zs) ЕВ (Х2, У2, Z-i). Если положить Л = Х[ — Хг в (1.7), точка 2Р = (Хг, У2, Z2) должна быть эквивалентна точки (Хг(Х( — Х2)2, Уг(Х( — Х2)3, (Х( — Х2)), которая имеет идентичную точке (Х3,Уз, Za) z-координату в формуле (1.32) и, таким образом, позволяет использовать специальное сложение (1.32). Кроме того, вычисление эквивалентной точки для 2Р не увеличивает вычислительную сложность, так как все необходимые вычисления выполняются внутри предыдущего сложения (см.(1.32)).

Сложность обобщения (1.33) равна 1DBL + 2 ADD7, d Є Z+ ,d 3 эффективное случайное простое число, DBL обозначает сложность традиционного удвоения, а ADD обозначает сложность специального сложения с идентичной z-координатой (т.е. 5М + 2S). Таким образом, сложность обобщенной композитной операции вида dP равна: (І — 1 1DBL Н (5М + 2Ь), (1.34) где DBL = 4М + 4S при рассмотрении особого случая а = —3. Иным способом, DBL = 4М + 4S (1.8). Оценим сложность вычисления точки кратности пять (5Р), семь (7Р) и одиннадцать (IIP) и сравним результаты с результатами, получаемыми при вычислении традиционным способом. Утверждение 11 (см. [57]). Вычисление операции вида dP, Р Є E(FP), d Є {5,7,11}; выполнимо со следующей вычислительной сложностью. 1. Операция ЪР вычислима со сложностью 14М + 10S в общем случае и со сложностью 14М + 8S при а = —3. 2. Операция 7Р вычислима со сложностью 19М + 12S в общем случае и со сложностью 19М + 10S при а = —3. 3. Операция ИР вычислима со сложностью 29M + 16S в общем случае и со сложностью ЗОМ + 16S при а = —3. Используя (1.34), можно оценить сложность вычисления точки кратности пяти (d = 5) как (4M + 6S) + 2(5M + 2S) = 14M + 10S, если а выбирается случайно. При а = —3, сложность нового пятикратного увеличения уменьшена до (4М + 4S) + 2(5М + 2S) = 14М + 8S.

В отличие от традиционного пятикратного сложения, вычисляемого как (22Р ЕВ Р), в данном случае при случайном а сложность равна (8М + 10S) + 2(12М + 4S) = 20М + 14S. При а = —3, сложность составит: 2(4М + 4S) + (12М + 4S) = 20М + 12S.

Следовательно, предложенное пятикратное увеличение позволяет значительно снизить сложность на 6М + 4S для вышеупомянутых случаев.

Для случая семикратного сложения (d = 7), сложность равна (4М + 6S) + 3(5М + 2S = 19М + 13S, если а выбирается случайно. Если а = —3, сложность нового семикратного сложения уменьшается до (4М + 4S) + 3(5М + 2S) = 19М + 10S.

В отличие от традиционного семикратного сложения, вычисляемого как 2(ЗР ЕВ Р) при случайном а, сложность равна: (4М + 6S) + (ЮМ + 6S) + (12М + 6S) = 26М + 16S. При а = —3, сложность составит (4М + 4S) + (ЮМ + 4S) + (12М + 4S) = 26М + 12S.

Следовательно, предложенное семикратное увеличение позволяется значительно снизить сложность 7М + 4S и 7М + 2S для вышеупомянутых случаев соответственно.

В случае одиннадцатикратного увеличения точки (d = 11), сложность составит (4М + 6S) + 5(5М + 2S) = 29М + 16S, если а выбирается случайно. Если а = —3, сложность нового одиннадцатикратного сложения уменьшается до (4М + 4S) + 5(5М + 2S) = 29М + 14S. В отличие от традиционного одиннадцатикратного сложения, вычисляемого как 22(ЗР) ЕВ Р при случайном а сложность равна: (8М + 10S) + (ЮМ + 6S) + (12М + 4S) = ЗОМ + 20S. При а = —3, сложность составит 2(4М + 4S) + (ЮМ + 4S) + (12М + 4S) = ЗОМ + 16S.

Следовательно, предложенное одиннадцатикратное увеличение позволяется значительно снизить сложность 1M + 4Sи 1M + 2S для вышеупомянутых случаев соответственно.

Комбинированный подход для операций dP более высокого порядка Отметим, что предыдущее обобщение (1.33) эффективно для d = 5,7,11 (пяти, семи и одиннадцатикратное сложения). Для вычислений, в которых d больше, чем эти значения рассмотрим комбинированный подход, использующий имеющиеся эффективные методы утроения, пяти и семикратного увеличения точки. Кроме того, можно воспользоваться преимуществом сложения предложенного подхода: композитные операции более высокого порядка вычисляют внутри себя композитные операции низкого порядка. Например, при вычислении утроения точки, получаем бесплатное удвоение. Аналогичным образом, вычисление пятикратного увеличения точки дает удвоение и утроение и т.д.

Вычисление композитных операций более высокого порядка описано далее (где d нечетное простое). Покажем только особый случай а = —3 (общий случай легко из него следует). Необходимо обратить внимание, что для некоторых вычислений требующих утроения, сложность может быть в дальнейшем уменьшена применением следующего далее эффективного алгоритма утроения. — Во-первых, 13Р = 2(5Р) ЕВ ЗР, что требует одно удвоение, одно пятикратное увеличение и одно общее сложение. Вычислительная сложность в таком случае составляет ЗОМ + 16S. Можно немного уменьшить эти затраты за счет эффективного утроения для вычисления 13Р как 22(ЗР) ЕВ Р, следовательно 29М + 17S. — Во-вторых, 17Р = 24РЕВР. Вычислительная сложность составляет 28M + 20S (скаляры, близкие к степени двойки, очевидно более эффективны, когда вычисляются только с удвоениями). Быстрая композитная операция 5Р ЕВ Q В разделе 1.4.1 было предложено вычисление операции ЪР ЕВ Q с использованием обобщения dP ЕВ Q (1.28). Можно улучшить эти результаты при случае а = — 3 путем простой комбинации обобщения dP (1.33) и традиционных общих сложений.

Таким образом, за счет использования эффективного пятикратного увеличения и последующего общего сложения сложность операции 5PEBQ равна 26М +12S для частного случая (а = — 3). Это превосходит результаты, приведенные в разделе 1.4.1 (28M + 11S).

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

В основе алгоритмов уровня 5 лежат алгоритмы уровня 3 и &А. Введение такой иерархии алгоритмов предоставляет следующие преимущества: — позволяет разработчикам программного и аппаратного обеспечения оценить вычислительные затраты преобразований и определить компромиссную реализацию между вычислительными затратами, сложностью реализации и необходимым объемом памяти для программ и данных;

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

Пусть Е - множество рассматриваемых кривых Е(р) (в разделе 2.3 будет уточнено множество рассматриваемых кривых), СІ — множество алгоритмов вычисления преобразований на основе эллиптических кривых уровня г архитектуры системы алгоритмов, представленной в подразделе 2.1. При г = 1 множество алгоритмов С\ будем называть множеством базовых алгоритмов.

Определение 14. Алгоритм а Є СІ, І 1 формируется композицией из t алгоритмов множества СІ-\: Та : Сіг — СІ. (2.2) Определение 15. Архитектура системы алгоритмов вычисления преобразований на основе эллиптических кривых представляет собой иерархию. Множество алгоритмов всех уровней такой архитектуры обозначается Л: Л = І І СІ. (2.3) г=1 Определение 16. Вычислительной (средней вычислительной) сложностью алгоритма а, является функция La(n) (Ьа(п)), определяющая зависимость времени (среднего времени) работы алгоритма а от входного параметра п.

Определение 17. Введем функцию S(a), а Є Л, определяющую объем дополнительной памяти, для хранения данных, связанных с предварительными вычислениями и необходимой для работы алгоритма а: S : Л — Ъ+. (2.4) Определение 18. Эффективным алгоритмом а Є СІ, полученный композицией Та, является такой алгоритм, для которого: Ьа(п) = Ьгтіп(п), Ьгтіп = min Lc(n). (2.5) сЄСіСЕ Отдельно рассмотрим случаи, когда при выполнении условия (2.5) справедливы соотношения S(a) = 0 и S(a) ф 0.

NIST утвердил набор эллиптических кривых для использования в приложениях защиты информации. Всего рекомендовано 15 кривых из которых пять кривых над простыми полями и десять — над расширениями бинарных полей. В данной работе рассматриваются только кривые, определенные над простыми полями вида: Е(р) : у = х + ах + Ъ. (2.6) В дальнейшем будем рассматривать подмножества кривых Е: Р192, Р224, Р256, Рзв4 и Рбі2.

Для получения быстрых алгоритмов скалярного умножения рассмотрим операцию DA. Теорема 12. Пусть Р = (Xi,Yi, Zi) и Q = (X2,Y2) — две точки в координатах Якоби и в аффинных координатах на эллиптической кривой Е(р) соответственно. Тогда операция D A 2Р ЕВ Q вычислима со сложностью равной 13М + 5S. Доказательство. Можно снизить сложность операции в терминах сложений в поле (т.е. смешанного и специального сложения) за счет использования единой формулы удвоения и сложения (DA): Х4 = /3 — а — 2Х[а , Y4 = {3(Х[а2 — Х4) — Y(a3, (2.7) Z4 = Z[a, где Х[ = X1(Z1X2 — Xi) , Y[ = Y\{ZXX2 — Xi) , Z i = Z\(ZlX2 — Xi), a = X3 — X[ = (ZlY2 — Y\) — (ZXX2 — Xi) — 3X1(Z1X2 — Xi) , /3 = Y3 — Y[ = —a(ZlY2 — Y\) — 2Yi(ZxX2 — X\) . Избегая промежуточных вычислений X3, У3 и Z% из первого сложения точки, можно непосредственно вычислить а = Х3 — Х[ и /3 = Ya — Y[ и сэкономить два сложения в поле Fp. Общая вычислительная сложность равна 13М + 5S + 12А и превосходит традиционное исполнение, состоящее из удвоения, которое следует за смешанным сложением: 12М + 7S + 16А, при а = —3 и 12М + 9S + 16А, если а выбрано случайно [10]. Другое исследование данной операции в координатах Якоби приведено в [42].

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

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

Алгоритм скалярного умножения на основе метода бинарного представления скаляра предусматривает (п — 1) удвоений (DBL) и (Н(п) — 1) сложений (ADD), где п = max([log( (Fp))] , logp ) — битовая длина d, а 1-L(n) — вес Хэмминга значения п. Сред 58 нее значение веса Хэмминга скаляра равняется 1. Как легко заметить, среднее количество удвоений превосходит количество сложений в два раза. Системой координат с самыми быстрыми удвоениями является система координат Якоби, поэтому будем в дальнейшем использовать эту систему.

Алгоритм на основе метода бинарного представления скаляра

Далее рассмотрим композиции алгоритмов в основе которых лежат методы скалярного умножения точки эллиптической кривой без предварительных вычислений. Теорема 21. Алгоритм ас4 вычисления скалярного умножения точки dP, d Є Ъ, P Є E(p) полученный композицией TcA, имеет среднюю вычислительную сложность 7 / ( /22 \ \ Par \п) = nlogn сі log п log log п + См —п — 14,8 , (3.8) 415 где cj и см — константы, связанные с вычислением операций мультипликативного обратного элемента и умножения в простом поле р соответственно, без предварительных вычислений точек, S(ac4) = 0.

Доказательство. Для доказательства данного утверждения рассмотрим различные композиции алгоритмов в соответствии с архитектурой, предложенной в разделе 2.7, определив вычислительную сложность каждой из них [13].

Композиция ТсХ В основе композиции J- d лежит алгоритм авіп Є С± С Л, основанный на L2R бинарном методе представления скаляра d (алгоритм 2), Тсх «ADD Х «DBL-7 Х DBL Х «SCALE — О-ВІП (2.2). Средняя вычислительная сложность алгоритма ас1 равна -- (п— 1\ т [п — 3\ Lar (ш = ADD + DBLM + DBL + SCALE. (3.9) На уровне С3 воспользуемся ускоренными алгоритмами сложения, удвоения и масштабирования точки эллиптической кривой: J-ADD : сім х «S — «ADD, J"DBL : сім х «S — CLDBL, - SCALE : «і x ам х as — «SCALE и FDBLJ ciM x as — aDBL;r. Вычислительная сложность операций составляет ADD = ИМ + 5S, DBL = 2M + 8S, SCALE = I + 3M + S. Алгоритм удвоения в аффинных координатах и конвертации результатов в координаты Якоби имеет вычислительную сложность DBL = 2М + 4S. Таким образом, средняя вычислительная сложность после композиции алгоритмов уровня3 и 4 равна = ,„ ( oo(«M,«s) DBL:;(aM,«s), cSLE(a„aM,«s), Do(aM,as) ) 7 fn \ / л т л л- f П — 3\ La„ (ш = (ИМ + 5S) + (2М + 4S) + (2М + 8S) + (I + ЗМ + S). 1-1 О S После приведения подобных слагаемых вычислительная сложность алгоритма ас1 равна 7 /13 25 \ /13 13 \ Lac (п) = I + —п М + —п S. (3.10) 1 2 2 2 2 Для композиции Jrc1 на уровне С-2 воспользуемся алгоритмами сложения, умножения, возведения в квадрат и нахождение мультипликативного обратного элемента в простом поле р. Эти алгоритмы имеют следующие составляющие оценок вычислительной сложности: А = Cpji,, М = CM log3, S = Cs log3, I = Сіп2, соответственно. Тогда алгоритм, полученный композицией J- d, будет иметь среднюю вычислительную сложность равную

Поскольку, S(a) = 0, для всех рассматриваемых алгоритмов а, то S(ac1) = 0. Это доказывает, что для искомого алгоритма, полученного композицией Тс1, не требуются предварительные вычисления точек. Композиция Тс2- В основе композиции Тс2 лежит алгоритм UNAF Є С4 С Л, основанный на методе бинарного несовместного представления (NAF) скаляра d (алгоритм 4), Тс2 «DA Х DBL-7 х aDBL х «SCALE — «NAF (2.2). Средняя вычислительная сложность алгоритма ас2 равна Lar in) = DA + DBL + n — 2 DBL + SCALE. (3.12) На уровне 3 воспользуемся ускоренными алгоритмами сложения, удвоения и масштабирования точки эллиптической кривой: J-DA : ам х «s — «DA, - DBL : «м х «s — «DBL, - SCALE : «і х ам х as — «SCALE и - DBL : ам x as — «DBL . Вычислительная сложность операций составляет DA = 13М + 5S, DBL = 2M + 8S, SCALE = I + 3M + S. Алгоритм удвоения в аффинных координатах и конвертации результатов в координаты Якоби имеет вычислительную сложность DBL = 2М + 4S. Таким образом, средняя вычислительная сложность после композиции алгоритмов уровня3 и С4 равна J С2 "O-NAF DA v«M }"S) DBL v M S/ t SCALE v«I «M «S/ J ADD v«M «S/ T fn— 3\ ( П — 3\ Lar (n) = (13M + 5S) + (2M + 4S) + n — 2 (2M + 8S) + (I + 3M + S). После приведения подобных слагаемых вычислительная сложность алгоритма ас2 равна т т ( л л- /21 \ Lac (гг) = 1+ —п — 10 М + —п — 8 S. (3.13) 2 3 3 Для композиции Тс2 на уровне 2 воспользуемся алгоритмами сложения, умножения, возведения в квадрат и нахождение мультипликативного обратного элемента в простом поле р. Эти алгоритмы имеют следующие составляющие оценок вычислительной сложности: А = САП, М = CM log3, S = Cs log3, I = Сіп2, соответственно. Тогда алгоритм, полученный композицией Тс2, будет иметь среднюю вычислительную сложность равную Lac (п) = с1п + ( —п 10 ] СмПlog + ( —п — 8 ) csnog . 2 2 3 С учетом cs — 0,6см будем иметь: Lac (п) = cin + см —п — 10 nog + 0,6см —п — 8 nog = 2 з з з) = с\п2 + см —п — 14,8 nog (3.14) Поскольку, S(a) = О, для всех рассматриваемых алгоритмов а, то S(ac2) = 0. Это доказывает, что для искомого алгоритма, полученного композицией Тс2, не требуются предварительные вычисления точек.

Композиция Тсг- В основе композиции Тсг лежит алгоритм авіп Є 4 С А, основанный на L2R бинарном методе представления скаляра d (алгоритм 2), Тсх «ADD Х «ВВІ/7 Х DBL Х «SCALE — о,Вт (2.2). Средняя вычислительная сложность алгоритма ас3 равна -- (п— 1\ т [п — 3\ La„ (ш = ADD + DBLM + DBL + SCALE. (3.15) На уровне 3 воспользуемся ускоренными алгоритмами сложения, удвоения и масштабирования точки эллиптической кривой: J-ADD : ам х as — «ADD, -7 DBL : СІМ x as — «DBL, - SCALE : ai x aM x as — «SCALE и - DBL7 «м x as — «DBL7 . Вычислительная сложность операций составляет ADD = ИМ + 5S, DBL = 2М + 8S, SCALE = I + ЗМ + S. Алгоритм удвоения в аффинных координатах и конвертации результатов в координаты Якоби имеет вычислительную сложность DBL = 2М + 4S. Таким образом, средняя вычислительная сложность после композиции алгоритмов уровня3 и 4 равна

Для композиции J-c3 на уровне С-2 воспользуемся алгоритмами сложения, умножения, возведения в квадрат и нахождение мультипликативного обратного элемента в простом поле р. Эти алгоритмы имеют следующие составляющие оценок вычислительной сложности: А = Cpji, М = См п log п, S = Csfilogn, I = C\n{\ogn)2 log log гг, соответственно.

Вычислительная сложность операций в простом поле

Для композиции J- d на уровне С-2 воспользуемся алгоритмами сложения, умножения, возведения в квадрат и нахождение мультипликативного обратного элемента в простом поле р. Отмеченные алгоритмы имеют следующие составляющие оценок вычислительной сложности: А = САП, М = CM log3, S = Cs log3, I = С\п2, соответственно. Тогда алгоритм, полученный композицией J- d, будет иметь среднюю вычислительную сложность равную

Поскольку, S(a) ф 0, для всех рассматриваемых алгоритмов а, то S(ac1) = 0. Это доказывает, что для искомого алгоритма, полученного композицией Тсг, требуются (2W_2 — 1) предварительные вычисления точек.

Композиция Тс2 В основе композиции Тс2 лежит алгоритм aw\NAF Є 4 С А, основанный на методе несовместного представления скаляра d с окном w, w 2, w Є Z+, (алгоритм 7), Сі : «DA x aDBL:r x aDBL x aSCALE — ««,\NAF (2.2). Средняя вычислительная сложность алгоритма ас2 равна

На уровне з воспользуемся ускоренными алгоритмами сложения, удвоения и масштабирования точки эллиптической кривой: J-DA : ам х as — CLDA, - DBL : «м х as — CLDBL, - SCALE : ai х aM х as — aSCALE и TDBLJ : aM x as — «DBL-7. Вычислительная сложность отмеченных алгоритмов составляет DA = 13M + 5S, DBL = 2M + 8S, SCALE = I + 3M + S, соответственно. Алгоритм удвоения в аффинных координатах и конвертации результатов в координаты Якоби имеет вычислительную сложность DBL = 2М + 4S. Таким образом, средняя вычислительная сложность после композиции алгоритмов уровня з и 4 равна

Для композиции Тс2 на уровне 2 воспользуемся алгоритмами сложения, умножения, возведения в квадрат и нахождение мультипликативного обратного элемента в простом поле р. Отмеченные алгоритмы имеют следующие составляющие оценок вычислительной сложности: А = Ср п, М = CM log3, S = Cs log3, I = С\П2, соответственно. Тогда алгоритм, полученный композицией Тс2, будет иметь среднюю вычислительную сложность равную

Композиция J"c3. В основе композиции J-c3 лежит алгоритм «WNAF Є А С Л, основанный на методе несовместного представления скаляра d с окном w, w 2, w Є Z+, (алгоритм 6), Тсх «DA х «DBL-7 х aDBL х «SCALE — «« NAF (2.2). Средняя вычислительная сложность алгоритма ас3 равна Lac (п, и ) = 1 DA + DBL + п 1 DBL + SCALE. (3.28) 3 w + 1 w + 1 На уровне Cs воспользуемся ускоренными алгоритмами сложения, удвоения и масштабирования точки эллиптической кривой: J-DA : «м х «s — «DA, -7 DBL : «м х as — «DBL, - SCALE : «і x aM x as — «SCALE и J"DBL,7 : «M x as — «DBL- . Таким образом, средняя вычислительная сложность после композиции алгоритмов уровня з и 4 равна aw NAF

Для композиции Тсг на уровне г воспользуемся алгоритмами сложения, умножения, возведения в квадрат и нахождение мультипликативного обратного элемента в простом поле р. Отмеченные алгоритмы имеют следующие составляющие оценок вычислительной сложности: А = Cpji, М = CM log/г, S = Cs logn, I = C\n{\ogn)2 log log гг, соответственно. Тогда алгоритм, полученный композицией Тсг, будет иметь среднюю вычислительную сложность равную отмеченных алгоритмов составляет DA = 13M + 5S, DBL = 2M + 8S, SCALE = I + 3M + S. Алгоритм удвоения в аффинных координатах и конвертации результатов в координаты Яко-би имеет вычислительную сложность DBLд = 2М + 4S. Таким образом, средняя вычислительная сложность после композиции алгоритмов уровня з и 4 равна

Для композиции TcA на уровне C-2 воспользуемся алгоритмами сложения, умножения, возведения в квадрат и нахождение мультипликативного обратного элемента в простом поле р. Отмеченные алгоритмы имеют следующие составляющие оценок вычислительной сложности: А = Cpji, М = cy\n\ogn, S = Cs logn, I = C\n{\ogn)2 log log гг, соответственно. Тогда алгоритм, полученный композицией J"c4, будет иметь среднюю вычислительную сложность равную Lar (n,w) = cin(logn) loglogn+ + CMniogn n + 2 - 10 + w + v(w) 3 w + v(w) n \ + 2 - w + v(w) + cs n log n n 8 - w + v(w) С учетом Cs — 0,6см будем иметь: 7 9,2 Lac (n,w) = niogn C\ log n log log n + CM , + 6,8 n- 14,8 . (3.33) 4 w + v(w)

В соответствии с установленным критерием эффективности и на основе полученных данных, наиболее эффективным алгоритмом является композиция ТсА при размере окна w = 7.

Ниже представлены средние оценки вычислительной сложности различных композиций алгоритмов нахождения кратной точки на множестве эллиптических кривых, без дополнительной памяти (таблица 3.5). На рисунках 3.7, 3.8, 3.9, 3.10, 3.11 и 3.12 представлена графическая интерпретация полученных результатов для множества кривых: сравнение средней вычислительной сложности композиций алгоритмов нахождения кратной точки на множестве эллиптических кривых Р{192,224,256,384,512} С Е при изменении ширины окна W = 3,7. По оси ординат отмечены значения средней вычислительной сложности L(n) для алгоритмов ас , ас , о с и аС . Как видно из графиков, наименьшую вычислительную сложность имеет алгоритм ас при размере окна w = 7, полученный композицией Тс .

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