Быстрые алгоритмы вычисления преобразований на основе эллиптических кривых тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат наук Хлебородов Денис Сергеевич

• Хлебородов Денис Сергеевич
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Хлебородов Денис Сергеевич

Введение

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

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

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

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

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

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

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

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

1.4.1 Операции вида dP Ш Q

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

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

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

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

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

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

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

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

1.7 Выводы

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

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

2.1.1 Уровень С\

2.1.2 Уровень С2

2.1.3 Уровень С3

2.1.4 Уровень А

2.1.5 Уровень С5

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

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

2.4 Эффективная операция БД

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

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

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

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

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

2.6 Эффективные композитные операции

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

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

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

2.8 Выводы

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

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

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

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

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

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

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

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

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

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

3.4 Выводы

Заключение

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

Введение диссертации (часть автореферата) на тему «Быстрые алгоритмы вычисления преобразований на основе эллиптических кривых»

Введение

Актуальность темы исследования. Преобразования на основе эллиптических кривых широко используются в средствах защиты информации, в частности, при вычислении цифровых подписей в отечественном (ГОСТ Р 34.10-2012 [8]) и ряде зарубежных (FIPS PUB 186 [43], ANSI X9.62 [15], SECG [66]) стандартах.

Главное преимущество подхода, используемого в системах преобразований на основе эллиптических кривых, по сравнению с другими подходами, используемыми в преобразованиях на основе простых полей (FFC) и на основе факторизации целых чисел (IFC) заключается в возможности обеспечить тот же уровень безопасности при существенно более коротких ключах (таблица 1, [44]).

Таблица 1

Соответствие уровней безопасности

Уровень, Симметричные Система преобразований данных

бит алгоритмы FFC (DSA, DH), IFC (RSA), ECC (ECDS),

бит к бит f бит

80 2TDEA L = 1024, N = 160 1024 160... 223

112 3TDEA L = 2048, N = 224 2048 224... 255

128 AES-128 L = 3072, N = 256 3072 256... 383

192 AES-192 L = 7680, N = 384 7680 384... 511

256 AES-256 L = 15360, N = 512 15360 512+

В первой колонке таблицы 1 указано количество бит безопасности, которые обеспечивают соответствующие системы преобразований данных. Во второй колонке приведены названия алгоритмов симметритричных преобразований. В остальных колонках, представлены соответствующие длины ключей. К группе FFC относятся алгоритмы DSA (Digital Signature Algorighm) и DH (Diffie-Hellman), к группе IFC — алгоритм RSA (Rivest, Shamir и Adleman), а ECC — алгоритм подписи на основе эллиптических кривых ECDS (Elliptic Curve Digital Signature). Как видно из таблицы 1, ECC обеспечивает уровень безопасности 256 бит при длине ключа в 30 раз меньше, чем системы преобразований FFC и IFC. Это возможно благодаря тому, что на настоящее время неизвестно о существовании субэкспоненциальных алго-

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

Преобразования на основе эллиптических кривых находят также свое применение в алгоритмах факторизации целых чисел (метод Ленстры [7] — ECM, Elliptic Curve Factorization Method) и в алгоритмах тестирования натуральных чисел на «простоту». Как следствие, упомянутые выше алгоритмы представляют как практический, так и теоретический интерес.

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

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

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

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

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

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

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

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

Объект и предмет исследования. Объектом исследования являются преобразования на основе эллиптических кривых. Предметом исследования являются алгоритмы в группе точек эллиптической кривой.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации. Результаты исследований опубликованы в шести научных работах [9-14], из которых пять [9-13] — в изданиях, рекомендованных ВАК Министерства образования и науки РФ.

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

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

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

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

Материал раздела 1.4 посвящен композитным операциям вида ¿Р Ш Q и ¿Р, d Е 2, Р^ Е Е ). Описаны дополнительные возвожности снижения сложности алгоритмов вычисления операций с точкой.

В разделе 1.5 приведен метод замены умножений на возведения в квадрат за счет использования классов эквивалентности точки в координатах Якоби и алгебраической подстановки 2аЬ = (а + Ь)2 — а2 — Ь2, где а,Ь Е . В завершении первой главы рассмотрен ряд методов скалярного умножения точки, основная идея реализации которых развивает методы, рассмотренные в разделе 1.3.

В разделе 1.6 рассмотрены методы скалярного умножения точки на основе многоосновного несовместного представления скаляра тШАЕ и ттЬ^АЕ с предварительными вычислениями и без предварительных вычислений.

В главе 2 для построения эффективных алгоритмов вычисления преобразований на основе эллиптических кривых и оценки их вычислительной сложности применяется иерархический подход. С этой целью, в разделе 2.1 предложена пятиуровневая архитектура системы алгоритмов. Множество алгоритмов всех уровней С архитектуры обозначается Л: Л = и5=1 Сг. Каждый из уровней С^, представляет собой множество алгоритмов а Е С^, являющихся основой для получения алгоритмов вышележащего уровня методом композиции ^а : 1 —> Сг,ъ = 2,5. Таким образом, вычислительная сложность алгоритма на каждом из уровней зависит от композиции алгоритмов нижележащих уровней.

Введение архитектуры системы алгоритмов предоставляет следующие преимущества:

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

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

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

архитектура хорошо «ложиться» на модель разработки с использованием объектно-ориентированного подхода на языках высокого уровня;

— предоставляет широкие возможности для применения параллельных вычислений, на всех или на отдельных уровнях архитектуры системы;

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

На основе полученной архитектуры системы алгоритмов в разделе 2.2 были введены критерии эффективности, используемые для оценки алгоритмов вычисления преобразований на основе эллиптических кривых. Первый критерий касается вычислительной сложности алгоритмов La(n), в соответствии с которым для искомого алгоритма а Е C она должна быть минимальна La(n) = L%min(n), среди известных алгоритмов на множестве эллиптических кривых E : L%min = minc££iCE Lc(n). Вторым критерием является объем дополнительной памяти S (а) для хранения данных, связанных с предварительными вычислениями и необходимой для работы искомого алгоритма S : Л —> Z+. Кроме этого, были выделены случаи, когда при условии выполнения критерия минимальной вычислительной сложности, в первом случае должно выполняться также условие, что S(а) = 0, а во втором S(а) = 0.

В разделе 2.3 задано множество эллиптических кривых E, на котором, в соответствии с установленным критерием, осуществляется поиск наиболее эффективных алгоритмов. Эллиптические кривые выбраны в соответствии с рекомендациями открыто публикуемого стандарта обработки информации FIPS PUB 186, разработанного NIST (Национальный институт стандартов и технологий США).

Разделы 2.4 и 2.5 посвящены эффективным алгоритмам скалярного умножения точки на эллиптической кривой для случаев, когда ни точка Р Е Е(Fp), ни скаляр d Е Z предварительно не известны. Первая часть раздела посвящена алгоритмам а, для которых S(а) = 0, а вторая часть, для которых S(а) = 0.

Проведено детальное исследование бинарного метода представления скаляра. Получен более быстрый алгоритм, чем предложенный Д. Гордоном и оцененный Н. Сулливаном скалярного умножения точки эллиптической кривой на основе бинарного метода.

При этом, наиболее эффективное применение бинарного метода возможно на L2R-направлении работы алгоритма, который основан на бинарном методе и представлении точек эллиптической кривой в координатах Якоби. Получены эффективные R2L и L2R алгоритмы на основе бинарного метода — вЩПь и ß^ira и доказано два утверждения относительно средней вычислительной сложности этих алгоритмов.

Теорема 13. Алгоритм а^2^ (алг. 1) вычисления скалярного умножения точки dP, d G Z, P G E(Fp), d = (dn-\,... ,d0)2 имеет среднюю вычислительную сложность:

г , ч т (15 23Ал, (21 3\ 0

L„R2L(п) = I + —п - — M + —п - - S. ав™w у 2 4 ) \ 2 4 )

Теорема 14. Алгоритм а^П (алг. 2) вычисления скалярного умножения точки dP, d G Z, P G E(Fp), d = (dn-i,... ,d0)2 имеет среднюю вычислительную сложность:

г , ч т /13 19\ ( 13 13\ 0

LnL2R (п) = I + —п--M + —п--S.

ав™у 1 \2 2 ) \ 2 2 J

Для полученных алгоритмов выполняется соотношение S(a^t) = S(а^П) = 0. Проанализирован метод бинарной несовместной формы представления скаляра (Non-adjacent Form, NAF) и на его основе получен новый, более быстрый, чем известный алгоритм скалярного умножения точки эллиптической кривой Д. Гордона, оценка для которого приводилась Н. Сулливаном. Было доказано утверждение относительно вычислительной сложности полученного алгоритма «naf.

Теорема 16. Алгоритм ^naf (алг. 4) вычисления скалярного умножения точки dP, d G Z, P G E (Fp), d = (dn-i,... ,d0), di G {-1,0,1} имеет среднюю вычислительную сложность:

LaNAF (п) = I + (у п - 10) M п - S.

Для предложенного алгоритма aNAF выполняется соотношение S(qnaf) = 0. Проанализирован метод несовместной формы представления скаляра с окном w (wNAF) и на его основе получен новый, более быстрый, чем известный wNAF-алгоритм Д. Хен-керсона скалярного умножения точки эллиптической кривой «wnaf. Доказано утверждение относительно вычислительной сложности предложенного алгоритма «wnaf. Теорема 17. Алгоритм aWNAF (алг. 5) вычисления скалярного умножения точки dP, d G Z, P G E (Fp), d = (dn-i,... ,do) имеет среднюю вычислительную сложность:

— / 11n \ / 3п \

LaWNAF(n,w) = I + — + 2п - 10 j M + - — - 8) S,

где w — ширина окна предварительных вычислений. При этом потребуется 2W-2 - 1 предварительных вычислений точек. Вычислительная сложность предварительных вычислений составит:

L<Tc (n,w) = 11 (2W-2 - 1) M + (3 ■ 2W-2 + 2) S.

Для предложенного алгоритма awNAF выполняется соотношение S(awNAF) = 2W-2 - 1. Проанализирован метод несовместной формы представления скаляра со скользящим окном w (s\wNAF) и на его основе получен новый, более быстрый, чем известный s\wNAF-

алгоритм Д. Хенкерсона скалярного умножения точки эллиптической кривой од^мАр. Доказано утверждение относительно вычислительной сложности предложенного алгоритма ««\wNAP.

Теорема 18. Алгоритм а8\шмАР (алг. 6) вычисления скалярного умножения точки ¿Р, й Е Ъ, Р Е Е(Ер), й = (¿п-1,... имеет среднюю вычислительную сложность:

¿«.\-nafМ = I +( _+1га( ) + 2п — ю) М + (бп — +3П( ) — б) Я,

где т — ширина окна предварительных вычислений и ь(т) = | — 3-?-2. При этом потребуется 3 (2'ш-2 — 1) предварительных вычислений точек. Вычислительная сложность предварительных вычислений составит:

'2W — (—1)г

4sSak ^ = 11 ( -3 - ^ M + (2W - ("1)W + 2) S-

- (—1)w ^

Для предложенного алгоритма as\wNAF выполняется соотношение S(as\wNAF) = 4 (2W-2 —

1).

В разделе 2.5 получены алгоритмы, применяемые для вычисления мультискалярного умножения точек. В первой части раздела получены эффективные алгоритмы вычисления композитных операций вида dP, Р Е Е(Fp), d Е {19, 23, 29, 31}, сформулировано и доказано утверждение относительно их вычислительной сложности.

Теорема 19. Вычисление композитных операций вида dP, Р Е Е(Fp), d Е {19, 23, 29, 31} выполнимо со следующей вычислительной сложностью.

1. Операция 19 Р вычислима алгоритмом 7 со сложностью 25M + 33S в общем случае и со сложностью 28M + 24S при a = —3.

2. Операция 23 Р вычислима алгоритмом 8 со сложностью 34M + 29S в общем случае и со сложностью 36M + 23S при a = —3.

3. Операция 29 Р вычислима алгоритмом 9 со сложностью 29M + 35S в общем случае и со сложностью 32M + 26S при a = —3.

4. Операция 31Р вычислима алгоритмом 10 со сложностью 31M + 35S в общем случае и со сложностью 34M + 26S при a = —3.

Использование параметра a = —3, позволяет снизить вычислительную сложность за счет упрощения выражений в формулах сложения (ADD) и удвоения (DBL).

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

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

поскольку после их работы занимаемая память должна быть освобождена. При таком подходе сложность работы основного алгоритма суммируется со сложностью работы алгоритмов предварительных вычислений, поэтому, полученные эффективные композитные операции снижают сложность алгоритмов скалярного умножения точки с предварительными вычислениями. Значительное снижение вычислительной сложности скалярного умножения за счет использования композитных операций вида ¿Р, Р Е Е (Ер), при й > 31 в качестве предварительно вычисленных не наблюдалось. Эффективные композитные операции при й < 19 были получены В. Дмитровым, Л. Имбертом и П. Мишра.

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

предварительных вычислений всех частичных сумм вида гР Ш ^0, г = 1,п,] = 1,т,Р,( Е Е(Ер). В связи с этим, в разделе 2.7, предложен эффективный алгоритм вычисления всех частичных сумм такого вида, а также сформулировано и доказано утверждение относительно его вычислительной сложности.

Теорема 20. Вычисление всех частичных сумм вида гР Ш jQ для г = 1,n,j = 1,т,Р,Q Е Е(Fp) выполнимо алгоритмом с вычислительной сложностью:

L(n,m) = (11nm — 6n + 3)M + (5nm — 3n + 1)S.

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

В главе 3 приведены оценки вычислительной сложности алгоритмов, полученных композициями Tci, г = 1,4 для случаев, когда S(aci) = 0 и S(aci) = 0, VCi.

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

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

В ходе исследования в разделе 3.3 получены композиции алгоритмов Tci, г = 1,4 вычисления скалярного умножения точки dР, d Е Z+, Р Е Е (Fp), при выполнении соотношений S (aci) = 0 и S(aci) = 0, VCj. Относительно вычислительной сложности полученных алгоритмов в подразделе 3.3.1, сформулировано и доказано утверждение при выполнении соотношения S (aCi) = 0.

Теорема 21. Алгоритм ac4 вычисления скалярного умножения точки dP, d Е Z+, Р Е Е(Fp) полученный композицией , имеет среднюю вычислительную сложность:

Lac4 (n) = n log n ^d log n log log n + c^ 15n — 14,8^

где C\ и Cm — константы, связанные с вычислением операций мультипликативного обратного элемента и умножения в простом поле Fp соответственно, без предварительных вычислений точек, S(ac4) = 0.

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

ьас2 (п) = сщ2 + см (25й - п1о'3-

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

В подразделе 3.3.2 сформулировано и доказано утверждение при выполнении соотношения 5 (ас) = 0.

Теорема 22. Алгоритм ас4 вычисления скалярного умножения точки ¿Р, й Е Р Е Е(Ер) полученный композицией Тс4, имеет среднюю вычислительную сложность:

Ьаг, (п,ш) = пlogn (а lognloglogп + См II -ч + 6,8 ) п - 14,8 ) ) ,

с4 \ \Дш + ь(т) ) ))

где С\ и См — константы, связанные с вычислением операций мультипликативного обратного

А ( __I

элемента и умножения в простом поле соответственно, и(ш) = 3 — 3 2то-2, ш > 2, ш Е 1Л — размер окна, при выполнении Б (ас') = 3 (2ад_2 — 1) предварительных вычислений точек.

В ходе доказательства также было показано существование алгоритма ас' с оценкой вычислительной сложности:

1а. (п,ш) = сщ2 + см(( 9,2 , + 6,8^) п — 14,8^) п1о%3.

2 + у(т) ) )

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

Доказано, что искомый алгоритм ас'4 имеет наименьшую сложность вычислений при размере окна ш = 7, при этом требуется предварительное вычисление £(ас' 1-ш=7) = 41 точки эллиптической кривой.

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

Глава 1

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

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

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

Определение 1 (см. [49]). Эллиптической кривой Е над полем К называется кривая, определяемая уравнением:

Е(К) : у2 + а1ху + а3у = х3 + а2х2 + а4х + а6, (1.1)

где {а\, а2,а3,а4,а6} Е К и А = 0, а А является дискриминантом Е, который определяется следующим образом:

А = —¿24 — 8 ¿3 — 27 ¿2 + 9 444, 4 = + 4а2,

4 = 2 а4 + а^3, (1.2)

4 = а2 + 4 а6,

7 _ 2 I 2 2

¿8 — <3.1 <3>6 — Й1Й3Й4 + Й2^3 — ^4.

Соотношение Е определяется над полем К, а коэффициенты {а1,а2,а3,а4,а6} являются элементами поля К. Условие А = 0 обеспечивает гладкость эллиптической кривой, что означает отсутствие точек кривой, в которых она имела бы две или более различных касательных. Свойства эллиптической кривой зависят от поля и характеристик уравнения (1.1).

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

Определение 2 (см. [28,60]). Пусть Fp является простым полем и для a,b Е Fp выполняется неравенство 4a3 + 27b2 ф 0 (mod р). Тогда эллиптическая кривая Е(Fp), определенная параметрами a,b Е Fp; состоит из набора решений или точек Р = (х,у), где х,у Е Fp уравнения:

Е(Fp) : у2 фх3 + ах + b (modp), (1.3)

вместе с особой точкой О, именуемой точкой в бесконечности. Уравнение у2 ф х3 + ах + Ь (mod р) называется определяющим уравнением Е(Fp).

Для точки Р = (хр, ур) хр является х-координатой Р, а ур является у-координатой Р. Такого рода представление точки Р называется ее аффинными координатами.

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

Теорема 1 (Х. Хассе). Для # Е(Fp) выполняется следующее соотношение:

р+1 - 2^< #Е(Fp) < р + 1 + 2^р. (1.4)

Определение 3. Набор точек на Е(Fp) (1.3) представляет собой абелевую группу с операцией сложения — Ш.

Можно определить закон сложения точек на Е, который определяется следующии далее правилами [1,3,4,54].

1. Правило сложения точки в бесконечности:

О Ш О = О.

2. Сложение точки в бесконечности с любой другой точкой:

(х, у) Ш О = О Ш (х, у) = (х, у), У(х, у) Е Е(Fp).

3. Правило сложения двух точек с одинаковыми х-координатами, когда точки либо различны или имеют -координату равную 0:

(х, у) Ш (х, - у) = О, У(х, у), (х, - у) Е Е (Fp),

т.е. отрицательной точкой (х,у) является Е1(х,у) = (х, — у).

4. Правило сложения двух точек с различными х-координатами: пусть (хг, уг) € Е(Ер) и (^2,Ы € Е(Ер) такие точки, что хх = х2 [21]. Тогда (хг,уг) Ш (х2,у2) = (жз,Уз), где

х3 = Л — х1 — х2 (modp), уз = Л(х1 — хз) — у\ (mod р), Л = ——— (mod р).

х2 — х1

:i.5)

5. Правило сложения точки с собой (удвоение точки): пусть (хг, уг) € Е(Ер) и уг = 0. Тогда (хг,ух) Ш (х2,у2) = (хз,уз), где

х3 = Л2 — 2х1 (mod р),

уз = Л(х1 — хз) — yi (mod р),

Л = ——— (modp). 2 1

:i.6)

Групповой закон (1.5) проиллюстрирован на рис. 1.1 (а), а (1.6) на рис. 1.1 (б) [49].

Рисунок 1.1 — Групповой закон а) Сложение Р Ш Q б) Удвоение 2Р

В основе преобразований, основанных на эллиптических кривых (ECC, Elliptic Curve Cryptography), лежит скалярное умножение точек эллиптической кривой. Дано целое число к и точка Р Е Е (Fp), скалярное умножение представляет собой процесс сложения точки Р с собой к раз.

Результат скалярного умножения обозначается кР.

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

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

Задача дискретного логарифмирования на эллиптической кривой (ECDLP, Elliptic Curve Discrete Logarithm Problem) формулируется следующим образом [45,46,61,67]. Дана эллиптическая кривая Е, определенная над простым полем Fp, точка Р Е Е(Fp) порядка п и точка Q Е (Р), найти I Е [1,п — 1] такое, что Q = 1Р. Целое I является дискретным логарифмом Q по основанию Р и обозначается I = logP Q.

Список литературы диссертационного исследования кандидат наук Хлебородов Денис Сергеевич, 2016 год

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

1. Алексеева О.В., Болотов А.А., Гашков С.Б., Лиссук М., Гашков С.Б., Лиссук М. «О методах вычисления кратных для точек эллиптических кривых над полями Галуа»// Вестник Московского энергетического института. — 2000. — № 4. — С. 97-100.

2. Ахо А., Хопкрофт Дж., Ульман Дж. «Построение и анализ вычислительных алгоритмов». — М: Мир, 1979, — 536 с.

3. Болотов А.А., Гашков С.Б., Фролов А.Б. «Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых». — М: КомКнига, 2006, — 280 с.

4. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. «Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы». — М: Ко-мКнига, 2006, — 328 с.

5. Василенко О.Н. «Новые методы вычисления кратной точки на эллиптической кривой над конечным полем», Тр. по дискр. матем., 11, № 2, Физматлит, М., 2008, 5-30.

6. Василенко О.Н. «О вычислении кратных точек на эллиптических кривых над конечными полями с использованием нескольких оснований систем счисления и новых видов координат», Матем. вопр. криптогр., 2:1 (2011), 5-28.

7. Василенко О.Н. «Теоретико-числовые алгоритмы в криптографии». — М: МЦНМО, 2003, — 336 с.

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

9. Хлебородов Д. С. Быстрые алгоритмы вычисления преобразований на основе эллиптических кривых с предварительными вычислениями // Вестник МГТУ им. Н.Э. Баумана. Серия «Приборостроение». — 2015. — № 3. — С. 65-78.

10. Хлебородов Д. С. Эффективные алгоритмы скалярного умножения точки эллиптической кривой без предварительных вычислений // Глобальный научный потенциал. — 2014. — № 7. — С. 35-41.

11. Хлебородов Д. С. Эффективный алгоритм скалярного умножения точки эллиптической кривой на основе NAF-метода // Программная инженерия. 2016. — № 1. — С. 21-28.

12. Хлебородов Д. С. Эффективный алгоритм предварительных вычислений в умножениях групп точек эллиптической кривой // Перспективы науки. — 2014. — № 6. — С. 48-54.

13. Хлебородов Д. С. Эффективные композитные операции в группе точек эллиптической кривой // Наука и бизнес: пути развития. — 2014. — № 6. — С. 26-31.

14. Хлебородов Д. С., Варфоломеев А. А. Эффективность алгоритмов цифровой подписи на эллиптических кривых в системах электронного документооборота // Труды VI научно-практической конференции «Инженерные системы 2013» / Под общ. ред. А. Пупкова. М. — С. 196-202.

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

16. Avanzi R. Aspects of Hyperelliptic Curves over Large Prime Fields in Software Implementations // Cryptographic Hardware and Embedded Systems - CHES 2004 / Ed. by Joye; Marc; Quisquater; Jean-Jaques; CHES 2004. — Vol. 3156 of 0302-9743. — Cambridge, MA, USA: Springer Berlin Heidelberg, 2004. — 8. — Pp. 148-162. — 6th International Workshop Cambridge.

17. Software Implementation of the NIST elliptic curves over prime fields / M. Brown, D. Han-kerson, J. Lopez, A. Menezes // Progress in Cryptology CT-RSA 2001. — 2001. — 4. — Vol. 2020. — Pp. 250-265.

18. Scalar multiplication on weierstras elliptic curves from co-z arithmetic / R. Goundar, M. Joye, A. Miyaji et al. // Cryptographic Engineering. — 2011. — no. 1. — P. 161-176.

19. Energy-Efficient Software Implementation of Long Integer Modular Arithmetic / J. Grob-schadl, R. Avanzi, E. Savas, Tillich S. // Cryptographic Hardware and Embedded Systems -CHES 05. — 2005. — 9. — Vol. 3659. — Pp. 75-90.

20. Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs / N. Gura, Patel A., A. Wander et al. // Cryptographic Hardware and Embedded Systems - CHES 04. — 2004. — 8. — Vol. 3156. — Pp. 119-132.

21. Handbook of Elliptic and Hyperelliptic Curve Cryptography / R. Avanzi, H. Cohen, C. Doche et al.; Ed. by C Henri, F. Gerard. — Boca Raton: Chapman & Hall CRC, 2006.

22. Bernstein D., Lange T. Explicit-formulas database. — 2014. — URL: http://hyperelliptic.org/EFD (дата обращения - 03.01.2015).

23. Bernstein D., Lange T. Inverted Edwards Coordinates // Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. — 2007. — 12. — Vol. 4851. — Pp. 20-27.

24. Bernstein D. Curve25519: new Diffie-Hellman speed records. — 2006. — URL: http://cr.yp.to/talks.html (дата обращения - 10.05.2014).

25. Bernstein D. High-Speed Diffie-Hellman, Part 2 / IND0CRYPT'06. — 2006. — Tutorial Session.

26. Billet O., Joye M. The Jacobi Model of an Elliptic Curve and Side-Channel Analysis // 15th International Symposium, AAECC-15. — 2003. — 7. — Vol. 2643, no. 15. — Pp. 34-42.

27. Bosma W. Signed bits and fast exponentiation // Journal de theorie des nombres de Bordeaux. — 2001. — 1. — no. 9935. — Pp. 27-41.

28. Brier E., Joye M. Fast Point Multiplication on Elliptic Curves through Isogenies // The name of the journal. — 2003. — 4. — Vol. 2643, no. 15. — Pp. 43-50.

29. Trading Inversions for Multiplications in Elliptic Curve Cryptography / M. Ciet, M. Joye, K. Lauter, P. Montgomery // Designs, Codes and Cryptography. — 2006. — 5. — Vol. 39. — Pp. 189-206.

30. Chae H., Hwang H. Fast Implementation of Elliptic Curve Arithmetic in GF(pn) // Public Key Cryptography. — 2000. — 12. — Vol. 1751. — P. 405-421.

31. Chudnovsky D., Chudnovsky G. Sequences of numbers generated by addition in formal groups and new primality and factorization tests // Advances in Applied Mathematics - ADVAN APPL MATH. — 1986. — 9. — Vol. 7. — Pp. 385-434.

32. Cohen H., Miyaji A., Ono T. Efficient Elliptic Curve Exponentiation using Mixed Coordinates // Advances in Cryptology - ASIACRYPT 98. — 1998. — 9. — Vol. 1514. — Pp. 51-65.

33. Crandall R., Pomerance C. Prime Numbers: A Computational Perspective. — 2 edition. — New York: Springer-Verlag, 2005.

34. Dimitrov V., Imbert L., Mishra P. Efficient and Secure Elliptic Curve Point Multiplication Using Double-Base Chains // Advances in Cryptology - ASIACRYPT 2005. — 2005. — 12. — Vol. 3788. — Pp. 59-78.

35. Dimitrov V., Jullien G., Miller W. An Algorithm for Modular Exponentiation // Information Processing Letters. — 1998. — 3. — no. 66. — P. 155-159.

36. Doche C., Icart T., Kohel D. Efficient Scalar Multiplication by Isogeny Decompositions // Public Key Cryptography - PKC 2006. — 2006. — 4. — Vol. 3958. — Pp. 191-206.

37. Doche C., Imbert L. Extended Double-Base Number System with Applications to Elliptic Curve Cryptography // Progress in Cryptology - INDOCRYPT 2006. — 2006. — 12. — Vol. 4329. — Pp. 335-348.

38. Duquesne S. Improving the Arithmetic of Elliptic Curves in the Jacobi Model // HAL. — 2007. — 5. — no. lirmm-00145805. — P. 101-105.

39. Edwards H. A normal form for elliptic curves // Bulletin of the American Mathematical Society. — 2007. — 8. — Vol. 44. — P. 393-422. — URL: http://www.ams.org/bull/2007-44-03/S0273-0979-07-01153-6/home.html (дата обращения - 21.08.2013).

40. Eisentrager K., Lauter K., Montgomery P. L. — Fast Elliptic Curve Arithmetic and Improved Weil Pairing Evaluation. — Department of Mathematics, University of California, Berkeley, 2003.

41. Elmegaard-Fessel L. — Efficient Scalar Multiplication and Security against Power Analysis in Cryptosystems based on the NIST Elliptic Curves over Prime Fields. — Master's thesis, University of Copenhagen, 2006.

42. Fay B. Double-and-Add with Relative Jacobian Coordinates. — 2014. — URL: http://eprint.iacr.org/2014/1014.pdf (дата обращения - 17.01.2015).

43. FIPS PUB 186-2. Digital Signature Standard (DSS). — National Institute of Standards and Technology (NIST), 2000. — 70 pp.

44. NIST PUB 800-57. Recommendation for Key Management Р Part 1: General (Revision 3). — National Institute of Standards and Technology (NIST), 2012. — 142 pp.

45. Freeman D., Scott M., Teske E. A Taxonomy of pairing-friendly elliptic curves // Cryptography ePrint Archive. — 2006. — no. Report 2006/372. — URL: http://eprint.iacr.org/2006/372 (дата обращения - 01.07.2015).

46. Galbraith S., Wang P., Zhang F. Computing Elliptic Curve Discrete Logarithms with Improved Baby-step Giant-step Algorithm // Cryptography ePrint Archive. — 2015. — no. Report 2015/605. — URL: https://eprint.iacr.org/2015/605 (дата обращения - 17.08.2015).

47. Gebotys C., Gebotys R. Secure Elliptic Curve Implementations: An Analysis of Resistance to Power-Attacks in a DSP Processor // Workshop on Cryptographic Hardware and Embedded Systems - CHES 03. — 2003. — 8. — Vol. 2523. — Pp. 114-128.

48. Gordon D. A Survey of Fast Exponentiation Methods // Journal of Algorithms. — 1998. — Vol. 27. — Pp. 129-146.

49. Hankerson D., Menezes A, Vanstone S. Guide to Elliptic Curve Cryptography. — New York: Springer-Verlag, 2004.

50. Hisil H., Carter G., Dawson E. New Formulae for Efficient Elliptic Curve Arithmetic // Progress in Cryptology - INDOCRYPT 2007. — 2007. — 12. — Vol. 4859. — Pp. 138-151.

51. Johnson S., Frigo M. A modified split-radix FFT with fewer arithmetic operations // IEEE TRANS. SIGNAL PROCESSING. — 2007. — 1. — no. 55. — P. 111-119.

52. Joye M., Yen S. New Minimal Modified Radix-r Representation with Applications to Smart Cards // Public Key Cryptography - PKC 2003. — 2002. — 1. — Vol. 2274, no. 55. — P. 375-384.

53. Karatsuba A. The Complexity of Computations // Proceedings of the Steklov Institute of Mathematics 211. — 1995. — P. 186-202.

54. Koblitz N. Introduction to Elliptic Curves and Modular Forms. Graduate Texts in Mathematics. — Springer, 1993.

55. Longa P., Gebotys C. Fast Multibase Methods and Other Several Optimizations for Elliptic Curve Scalar Multiplication // Public Key Cryptography - PKC 2009. — 2009. — 4. — Vol. 5443. — Pp. 443-462.

56. Longa P., Miri A. New Composite Operations and Precomputation Scheme for Elliptic Curve Cryptosystems over Prime Fields // Public Key Cryptography - PKC 2008. — 2008. — 4. — Vol. 4939. — Pp. 229-247.

57. Longa P., Miri A. New Multibase Non-Adjacent Form Scalar Multiplication and its Application to Elliptic Curve Cryptosystems (extended version) // Cryptography ePrint Archive.

— 2008. — no. Report 2008/052. — URL: https://eprint.iacr.org/2008/052.pdf (дата обращения - 25.10.2015).

58. Liardet P., Smart N. Preventing SPA/DPA in ECC Systems Using the Jacobi Form // Cryptographic Hardware and Embedded Systems — CHES 2001. — 2001. — 5. — Vol. 2162.

— Pp. 391-401.

59. M. James, Douglas S. Minimality and Other Properties of the Width-w Nonadjacent Form // Mathematics of Computation. — 2006. — 12. — Vol. 75, no. 253. — Pp. 369-384.

60. Meloni N. Fast and Secure Elliptic Curve Scalar Multiplication over Prime Fields using Special Addition Chains // Cryptography ePrint Archive. — 2006. — no. Report 2006/216.

— URL: http://eprint.iacr.org/2006/216 (дата обращения - 08.07.2015).

61. Menezes A. Handbook of Applied Cryptography. Discrete Mathematics and Its Applications.

— CRC Press, 1996.

62. Moller N. On Schonhage's algorithm and subquadratic integer gcd computation // Mathematics of Computation. — 2008. — 1. — Vol. 77, no. 261. — Pp. 589-607.

63. Montgomery P. Speeding the Pollard and Elliptic Curve Methods of Factorization // Mathematics of Computation. — 1987. — 1. — Vol. 48, no. 177. — P. 243-264.

64. Rivain R. Fast and Regular Algorithms for Scalar Multiplication over Elliptic Curves // Cryptography ePrint Archive. — 2011. — no. Report 2011/338. — URL: http://eprint.iacr.org/2011/338 (дата обращения - 08.07.2015).

65. Rokhlin V., Tygert M. Fast Algorithms for Spherical Harmonic Expansions // SIAM Journal on Scientific Computing. — 2006. — Vol. 27, no. 6. — P. 1903-1928.

66. SEC 1: Elliptic Curve Cryptography. Standards for Efficient Cryptography, Certicom Corp., 2009.

67. Semaev I. New Algorithm For the Discrete Logarithm Problem on Elliptic Curves // Cryptography ePrint Archive. — 2015. — no. Report 2015/310. — URL: https://eprint.iacr.org/2015/310 (дата обращения - 17.08.2015).

68. Solinas J. Generalized Mersenne Prime // Encyclopedia of Cryptography and Security. — 2 edition. — US: Springer, 2011. — Pp. 509-510.

69. Sullivan N. Fast Algorithms for Arithmetic on Elliptic Curves over Prime Fields // Cryptography ePrint Archive. — 2007. — no. Report 2008/060. — URL: https://eprint.iacr.org/2008/060 (дата обращения - 08.07.2015).

70. Takagi T., Yen S., Wu B. Radix-r Non-Adjacent Form // Information Security. — 2004. — 9. — Vol. 3225. — Pp. 99-110.

71. Signed Binary Representations Revisited / K. Okeya, K. Schmidt-Samoa, C. Spahn, T. Takagi // Advances in Cryptology - CRYPTO 2004. — 2004. — 8. — Vol. 3152. — Pp. 123-139.

72. Whittaker E., G. Watson. A Course of Modern Analysis. — 4 edition. — Cambridge Mathematical Library, 1996.

73. Woodbury A. Efficient Algorithms for Elliptic Curve Cryptosystems on Embedded Systems / MSc. Thesis // Worcester Polytechnic Institute. — 2001.