Математическое обеспечение и администрирование информационных систем

 

 

Министерство образования и науки Российской Федерации  

Федеральное государственное автономное образовательное 

учреждение высшего образования 

«САНКТ-ПЕТЕРБУРГСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 

ПЕТРА ВЕЛИКОГО» 

Институт компьютерных наук и технологий 

Кафедра Компьютерные интеллектуальные технологии

 

«Допустить к защите» 

Зав. каф. КИТ, к.т.н. 

______________ А.В. Речинский 

«____» ____________ 20___ г. 

ДИПЛОМНАЯ РАБОТА СПЕЦИАЛИСТА 

РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ КРИПТОГРАФИЧЕСКИХ 

АЛГОРИТМОВ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ НАД 

БИНАРНЫМ КОНЕЧНЫМ ПОЛЕМ 

специальность: 010503 «Математическое обеспечение и администрирование 

информационных систем» 

Выполнил: 

Кудрявцев Алексей Михайлович 

Подпись______________ 

Руководитель: 

доцент кафедры КИТ ИКНТ, 

к.ф-м.н., Пак Вадим Геннадьевич 

Подпись______________ 

Рецензент: 

ген. дир. интернет-агентства BrickTop, 

Петровский Павел Дмитриевич 

Подпись______________ 

 

 

 

Санкт-Петербург 

2015 

2 

 

СОДЕРЖАНИЕ 

 

Введение ................................................................................................................... 8

 

1. Введение в предметную область. .................................................................... 11

 

1.1. Проблематика современной криптографии................................................. 12

 

1.2. Эллиптическая криптография ....................................................................... 13

 

1.3. Математика эллиптической кривой и конечных полей ............................. 14

 

1.3.1. Сложение точек на эллиптической кривой .......................................... 15

 

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

 

1.3.3. Оценка числа элементов группы точек эллиптической кривой ......... 17

 

1.4. Выбор набора параметров для эллиптической кривой .............................. 18

 

1.5. Эллиптические кривые, рекомендованные NIST ....................................... 19

 

1.6. Выбор размер ключа ...................................................................................... 19

 

1.7. Введение в криптоанализ .............................................................................. 20

 

1.8. Виды атак ........................................................................................................ 21

 

1.8.1. Атака по времени .................................................................................... 21

 

1.8.2. Предотвращение временной атаки ........................................................ 21

 

1.8.3. Атака «Человек посередине» ................................................................. 22

 

1.8.3. Полный перебор ...................................................................................... 22

 

1.8.4. Предотвращение атаки «полного перебора» ........................................ 23

 

1.8.5. Квантовый взлом ..................................................................................... 23

 

2. Шифрования с помощью эллиптических кривых ......................................... 24

 

2.1. Сферы применения криптосистем с открытым ключом ............................ 24

 

2.2. Преимущества алгоритмов криптосистемы с открытым ключом ............ 24

 

2.3. Недостатки алгоритмов криптосистемы с открытым ключом .................. 25

 

2.4. Преимущества криптосистем на эллиптических кривых .......................... 25

 

2.5. Использование криптосистем на эллиптических кривых .......................... 26

 

3. Системный анализ задачи ................................................................................ 28

 

3.1. Выбор точки и размещение данных ............................................................. 28

 

3.2. Выбор основного поля Fq и эллиптической кривой E ............................... 28

 

3 

 

3.3.

 

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

 

3.4. Формирование ключей алгоритма Эль-Гамаля .......................................... 30

 

3.5. Алгоритм шифрования Деффи-Хеллмана ................................................... 31

 

3.6.

 

Шифрование с помощью алгоритма Диффи-Хеллмана ............................. 32

 

4. Практическая реализация ................................................................................. 33

 

4.1. Функция нахождения обратного элемента .................................................. 34

 

4.2. Процедура удвоения точки на эллиптической кривой ............................... 34

 

4.3. Процедура сложения точек на эллиптической кривой .............................. 35

 

4.4. Статистические данные ................................................................................. 36

 

Заключение ............................................................................................................ 44

 

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

 

Приложение ........................................................................................................... 48