Эллиптическая криптография. Ильичев Д.О._МОп-1601б. Д. О. Ильичев (И. О. Фамилия)
 Скачать 1.03 Mb.
|
|
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего образования «Тольяттинский государственный университет» Институт математики физики и информационных систем (наименование института полностью) Кафедра «Прикладная математика и информатика» (наименование) 02.03.03 Математическое обеспечение и администрирование информационных систем (код и наименование направления подготовки, специальности) Технология программирования (направленность (профиль) / специализация) ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА (БАКАЛАВРСКАЯ РАБОТА) на тему __«Реализация и исследование криптографического алгоритма на эллиптических кривых» Студент Д.О.Ильичев (И.О. Фамилия) (личная подпись) Руководитель доцент, к.ф.–м.н. ,Г.А.Тырыгина (ученая степень, звание, И.О. Фамилия) Консультант (ы) О.А.Головач (И.О. Фамилия) Тольятти 2020 2 Аннотация Название бакалаврской работы - Реализация и исследование криптографического алгоритма на эллиптических кривых. Целью бакалаврской работы является реализация криптографического алгоритма шифрования данных на основе эллиптических кривых. Объект исследования – алгоритмы защиты информации от несанкционированного доступа. Предметом исследования являются криптографические алгоритмы шифрования на основе эллиптических кривых. В первой главе описывается теория эллиптических кривых, их математические свойства, их плюсы и минусы. Так же были описаны свойства их умножения, свойства сложения, групповой закон и какие кривые стоит выбирать при решении определенных задач. Во второй главе описываются алгоритмы и протоколы на эллиптических кривых с суперсингулярными кривыми и с несуперсингулярными кривыми, а также как на точках распределяется информация и какие точки лучше для этого выбирать. В третьей главе показана реализация криптографического алгоритма на эллиптических кривых. В качестве такого алгоритма был выбран алгоритм Диффи-Хеллмана. Была приведена его числовая и программная реализация. Было проведено исследование этого алгоритма на работу с большими значениями ключей и с нулевыми значениями. Бакалаврская работа выполнена на 39 страницах, состоит из введения, трёх глав, включающих 38 изображений, 46 формул, заключения, списка используемой литературы, включающего 26 источников, из них 9 на иностранном языке. 3 Abstract The title of the graduation thesis is « Implementation and research of cryptographic algorithm on elliptic curves» The aim of the work is to implement a cryptographic algorithm for encrypting data based on elliptic curves. The object of the thesis is algorithms for protecting information from unauthorized access. The subject of the senior thesis is cryptographic encryption algorithms based on elliptic curves. The first part of the thesis describes the theory of elliptic curves, their mathematical properties, their advantages and disadvantages. The properties of their multiplication, the properties of addition, the group law, and which curves should be chosen when solving certain problems were also described. The second part of the thesis describes algorithms and protocols on elliptic curves with supersingular curves and with non-supersingular curves, as well as how points are distributed information and which points are better for this The third part of the thesis shows the implementation of the cryptographic algorithm on elliptic curves. Diffie-Hellman algorithm was chosen as the algorithm. Its numerical and software implementation was given. A study of this algorithm was carried out to work with large values of keys and with zero values. The graduation work consists of an explanatory note on 39 pages, introduction, including 38 figures, 46 formulas, the list of 26 references including 9 foreign sources. Оглавление Введение ........................................................................................................................ 5 Глава 1. Информация об эллиптической криптографии .......................................... 7 1.1 Теория об эллиптических кривых .................................................................. 7 1.2 Математические свойства эллиптических кривых .......................................... 7 1.3 Выбор параметров для кривой ......................................................................... 10 1.4 Свойства сложения абелевой группы .............................................................. 12 1.5 Групповой закон для эллиптических кривых ................................................. 12 1.6 Геометрическое сложение эллиптических кривых ........................................ 12 1.7 Эллиптическая криптография .......................................................................... 13 1.8 Плюсы и минусы эллиптической криптографии ........................................... 14 Глава 2. Эллиптические кривые в криптографии .................................................... 16 2.1 Алгоритмы на эллиптических кривых ............................................................ 16 2.1.1 Эллиптические кривые над полем GF( ) ............................................... 16 2.1.2 Скалярное умножение на суперсингулярных кривых ............................. 17 2.1.3 Скалярное умножение на несуперсингулярных кривых ......................... 18 2.2 Протоколы на эллиптических кривых ............................................................. 20 2.2.1 Выбор точки и размещение данных .......................................................... 20 2.2.2 Распределение ключей ................................................................................ 21 2.2.3 Криптосистемы Эль-Гамаля ....................................................................... 24 2.2.4 Протоколы цифровой подписи .................................................................. 25 2.2.5 Электронная подпись Эль-Гамаля с возвратом сообщения – схема Nyberg-Rueppel. .................................................................................................... 27 Глава 3. Реализация и тестирование алгоритма ...................................................... 30 3.1 Протокол Дифии-Хеллмана .............................................................................. 30 3.2 Числовая реализация ......................................................................................... 30 3.3 Программная реализация .................................................................................. 32 3.4 Результаты .......................................................................................................... 36 Заключение .................................................................................................................. 38 Список используемой литературы ............................................................................ 40 5 Введение Целью бакалаврской работы является реализация криптографического алгоритма шифрования данных на основе эллиптических кривых. Объект исследования – алгоритмы защиты информации от несанкционированного доступа. Предметом исследования являются криптографические алгоритмы шифрования на основе эллиптических кривых. Жизнеспособность общества все больше зависит от развития информационной среды. Информация является важной частью в функционировании государственных и общественных институтов, в жизни каждого человека. В нынешних условиях сформировался новый вид трудовой деятельности, связанный с хранением, распространением и получением информации. Информатизация ведет к созданию общего мирового информационного пространства, к унификации информационных технологий различных стран мира. Новые технологии открывают большие возможности. Вместе с тем катастрофически возрастает цена потерь в случае нештатной ситуации или снижения надежности систем обработки и передачи информации. Можно наблюдать, что в настоящее время все более зримо проявляется зависимость экономики от надежности систем защиты информации. В нынешних условиях защита информации становится все более актуальной и одновременно все более сложной проблемой. Это обусловлено как массовым применением методов автоматизированной обработки данных, так и широким распространением методов и средств несанкционированного доступа к информации. Поэтому важную роль в организации противодействия потенциальным угрозам занимает подход, 6 при котором средства защиты информации используются комплексно, каждое в соответствии со своим предназначением. Внедрение и активное использование современных информационных технологий существенно повысили уязвимость информации, циркулирующей в современных информационно-телекоммуникационных системах. Несанкционированное искажение, копирование, уничтожение информации в настоящее время затрагивает не только процессы, относящиеся к сфере государственного управления, но и интересы физических лиц. С каждым днём увеличивается объем информации и увеличивается её спрос, а значит, и растёт её ценность, поэтому возрастают требования к её защите Актуальность темы бакалаврской работы объясняется необходимостью противостоять современным способам несанкционированного доступа к информации. 7 Глава 1. Информация об эллиптической криптографии 1.1 Теория об эллиптических кривых Нил Коблиц и Виктор Миллер в 1985 году предложили использовать эллиптические кривые в криптосистемах. В 1998 году в стандартах США для решения задачи связанной с цифровой подписью использовались эллиптические кривые, а в России такой же стандарт, был принят в 2001. Важным плюсом криптосистем на эллиптических кривых является более высокая стойкость при равной трудоемкости по сравнению с обычными криптосистемами. Это из-за того, для того чтобы вычислить обратную функцию для эллиптических кривых существуют лишь алгоритмы с экспоненциальным ростом трудоемкости, в то время как для обычных систем известны лишь субэкспоненциальные методы. Криптостойкость, которая достигается в алгоритме RSA с использованием модуля в 128-байт, на эллиптических кривых используется с размером модуля в 20 байт. 1.2 Математические свойства эллиптических кривых Эллиптические кривые – это кривые которые задаются кубическим уравнением третьей степени, с использованием переменных из поля k и точкой на бесконечной прямой [1]. Уравнение этой кривой можно записать следующим образом , (1.1) где a , b – действительные числа. Так как график кривой параллелен оси абсцисс, чтобы найти точки, являющиеся корнями, нужно решить уравнение третьей степени. , (1.2) Здесь можно использовать формулу Кардано. Дискриминант вычисляется по формуле 1.3 ( ) ( ) (1.3) 8 При дискриминанте меньше нуля, уравнение (1.2) имеет три разных решения a, b, z; при дискриминанте равном нулю, уравнение (1.2) имеет три корня, a, b, c, два из которых одинаковые, при дискриминанте больше нуля, уравнение (1.2) имеет одно решение a и два комплексно сопряженных. Графики по результатам вычислений представлены на рисунках 1.1-1.3. Рисунок 1.1 – Кривая с D <0 Рисунок 1.2 – Кривая c D =0 Рисунок 1.3 – Кривая с D >0 На рисунке 1.4 показаны примеры эллиптических кривых. 9 Рисунок 1.4 – Эллиптические кривые Всего существует два вида эллиптических кривых сингулярные и несингулярные. Несингулярные кривые – это эллиптические кривые дискриминант которых не равен нулю ( ) (1.4) где a и b коэффициенты уравнения (1.1). Сингулярные кривые редко используются, т.к. есть риск значительно снизить криптостойкость алгоритмов и протоколов Ниже на рисунке 1.2 продемонстрирован пример несингулярной кривой Рисунок 1.2 – несингулярная кривая Точки на эллиптической кривой можно подвергать таким операциям как сложение. Для этого воспользуемся формулой: (1.5) где P, Q, R – это точки этой кривой. График сложения точек показан на рисунке 1.3 10 Рисунок 1.3 – Сложение точек Предположим что ( ) координаты точки P, а ( ) координаты точки Q. Вычислим коэффициент (1.6) тогда координаты точки (P+Q) равны ( ) (1.7) ( ) ( ) (1.8) 1.3 Выбор параметров для кривой Выбираем наиболее ценные переменные для того чтобы избавиться от попыток взлома и перехвата информации, для определенных кривых. Этот выбор является наиболее хорошим в плане лучшей криптостойкости. Для использования этой стратегии применяются особенные методы, но в результате этого метода кривые отличаются от небольшой пары кривых и создают угрозы на присутствие необычных явлений, из-за которых существует вероятность изобретения алгоритма для их хакинга. Далее описывается алгоритм нужных действий для получения правильной кривой. Сперва нужно выбрать число Р. У этой точки порядок величины зависит от количества точек на прямой. Тогда число p измеряемое в битах, считается по формуле [ ] , и она должна быть такой чтобы алгоритм нахождения логарифмов на кривой был невозможным. Переменная t =16 байт на данном этапе слишком мала, она легко вычисляется если 11 приложить несколько вычислительных усилий. Но размер в 20 байт невозможна для современных криптосистем. Следующим шагом определяются два произвольных числа a и b 0 (mod p) и ( ) ( ). При определении точек можно заметить, что коэффициент b не используется. Поэтому для продуктивных вычислений лучше выбирать случайно только величину b, а величина a выбирается определенно. Далее находим количество точек, которые находятся на прямой. Это переменная n. Для лучших вычислений делитель n должен быть равен числу q. При n делящимся на группу подмножеств, алгоритм Диффи – Хеллмана легко справляется с вычислением логарифма на кривой с помощью этих маленьких подмножеств. При слишком большой затрате времени можно принять n=hq, где h небольшое число. Далее проверяем условие неравенства ( ) для всех k на промежутке от 0 до 32. Эта проверка может предотвратить MOV атаку, а также позволяет избежать использование суперсингулярных кривых. Проверяем выполняется ли равенство . Кривые с q = p называются аномальными и для них предложены эффективные методы вычисления логарифмов. Если все условия выполняются, то мы получаем пригодную для вычислений кривую. Теперь нам известны переменные р, а, b, число точек прямой n и размер подмножества точек q. Далее нужно вычислить G, которая является генератором этого подмножества. Если размер подмножества равен числу точек, то любая точка является генератором. Если размер подмножества меньше числа точек, выбирается случайная точка G’, до того момента пока не получим [ ⁄ ] . Для вычисления случайной точки на кривой, берем случайное число x которое меньшее р, вычисляем ( ) и извлекаем квадратный корень √ . 12 Если есть решение этого уравнения, то вычисляем точку (x, y), если решение иррациональное, то выбираем другое число х. 1.4 Свойства сложения абелевой группы Чтобы множество G было группой, необходимо записать сложение таким образом, чтобы оно отвечало четырем основным свойствам: если a и b входят в множество G, то a+b входит в это множество G. Это свойство называется замыканием; (a + b) + c = a + (b + c), это свойство ассоциативности; если существует единичный элемент 0, при котором a + 0 = 0 + a = a; если у каждого элемента есть противоположная величина, то есть для каждого a существует такое b, что (a + b) = 0 и последнее свойство — это коммутативность (a + b = b + a) Если выше перечисленные свойства выполняются, то группа называется абелевой. 1.5 Групповой закон для эллиптических кривых Эллиптические кривые можно определить в группу: • элементы этой группы являются точками эллиптической кривой; • бесконечно удаленная точка 0 – это единичный элемент; • обратная величина точки P – это точка, симметричная относительно оси x; • Сумма трех ненулевых точек, которые лежат на одной прямой (1.9) 1.6 Геометрическое сложение эллиптических кривых Формула (1.9) позволяет нам описать геометрический способ сложения двух точек P и Q. Через две эти точки мы проводим прямую, которая пересечет кривую в некоторой точке R, при условии, что P, Q, R находятся на 13 одной прямой. Если мы возьмем обратную величину точки R, то это и будет сумма точек P + Q. Рисунок 1.4 – График суммы точек P + Q В геометрическом сложении есть несколько особенностей: если P или Q равны нулю, то мы не сможем провести через них прямую, т.к. 0 не находится на плоскости xy. Но из-за того, что мы обозначили 0 как единичный элемент, то для любой P и Q будет выполняться условие (P + 0 = P) (0 + Q = Q). если P = -Q, то прямая, которую мы построим через эти две точки будет вертикальна и не будет пересекать кривую в точке. Если P является обратной величиной Q, то P + Q = 0. если P = Q, тогда через точку проходит бесконечное количество прямых. Представим, что есть некая точка Q’ которая не равна P. Далее нужно сделать так чтобы точка Q’ стремилась к точке P. Благодаря этому прямая проходящая через P и Q’ будет касательной к кривой. 1.7 Эллиптическая криптография Эллиптическая криптография – наука изучающая эллиптические кривые над проектными плоскостями [1]. 14 Круг использования эллиптических кривых довольно большой. Они используются в алгоритмах цифровой подписи, асимметричного шифрования и обмена ключами. Эллиптические кривые часто применяются в алгоритмах шифрования данных: алгоритм обмена ключами. Два абонента делятся секретным ключом, который будет одинаковым для обоих. Используют они канал для передачи сообщений, который не защищен от прослушивания, но защищён от фальсификации. Ключ, который они получают, они используют для обмена сообщениями; алгоритм цифровой подписи используется для авторизации пользователей, отправки электронных версий документов и других данных. Если в электронной версии документа стоит подтвержденная цифровая подпись, значит она имеет юридическую силу. алгоритм с открытым ключом. Это алгоритм зашифровывания информации. В этом алгоритме доступный ключ отправляется по открытому каналу и применяют его для проверки электронной подписи и шифрования сообщения. Для расшифровки сообщения и создания электронной подписи используется закрытый ключ. 1.8 Плюсы и минусы эллиптической криптографии Основные плюсы: размер ключа меньше чем в асимметричной криптографии [2]; эллиптические алгоритмы работают быстрее классических. благодаря тому, что длина ключа относительно небольшая, а скорость работы алгоритма асимметричной криптографии на эллиптических кривых достаточно высокая, эти алгоритмы могут использоваться в смарт-картах и других устройствах которые имеют ограниченные вычислительные ресурсы [2]; 15 дискретное логарифмирование на эллиптических кривых не имеют субэкспоненциальных алгоритмов для решения [2]; Основные минусы эллиптической криптографии: эллиптическая криптография будет терять свою актуальность при появлении алгоритмов с использованием логарифмирования. в эллиптической криптографии нужно учитывать на какой кривой происходят вычисления и какой ключ используется. Если их не учитывать появляется вероятность угрозы алгоритмов путем появления уязвимостей, а также вероятность ошибки [2]. В данной главе были продемонстрированы математические свойства эллиптических кривых, приведены наиболее популярные системы, в которых используется эллиптическая криптография, выявлены ее плюсы и минусы. Благодаря вышеперечисленной информации следует вывод, что полностью перейти на эллиптическую криптографию возможно, но этот переход не является необходимым. 16 |