Введение к работе
Актуальность темы На современном этапе развития общества большую роль играют электронные средства передачи, хранения и обработки информации. Не вызывает сомнений, что для того, чтобы использовать информационные технологии в различных областях жизнедеятельности человека, необходимо обеспечить их безопасность.
Новейшие достижения в области информации в значительной мере основываются на исследованиях конечных алгебраических структур: полей, колец, Абелевых групп. Так, например, в 80-х годах прошлого столетия ученые Коблиц и Миллер предложили использовать для построения систем не числовые мультипликативные Абелевые группы, а аддитивную Абелевую группу точек эллиптических кривых. Так появилось новое направление в построении теоретико-числовых систем, использующих аддитивную группу точек эллиптической кривой. Системы, построенные на точках эллиптической кривой, являются одним из самых перспективных направлений разработки вычислительных систем. Это обусловлено тем, что эллиптическая кривая обеспечивает максимально возможную надежность теоретико-числовых систем на один бит размера задачи.
Наиболее уязвимым местом систем, построенных на точках эллиптической кривой, считается малая скорость преобразований. Их создатели отмечали элегантность математического аппарата данных систем, но скептически относились к возможности практического применения. Однако за последнее десятилетие было проведено множество исследований эффективности вычислений операций в группе точек эллиптической кривой, которые показали, что системы, построенные на точках эллиптической кривой, существенно выигрывают по сравнению со своими прототипами не только в размере данных, но и в скорости преобразований. В конце XX — начале XXI веков началось активное утверждение национальных стандартов преобразования информации, использующих эллиптическую кривую: в США — FIPS 186-2-2000, в Российской Федерации — ГОСТ Р34.10-2001, на Украине — ДСТУ 4145-2002 и др. Таким образом, на сегодняшний день насчитывается несколько десятков корпоративных и национальных стандартов систем, построенных на точках эллиптических кривых.
Известно, что самыми трудоемкими операциями в конечном поле являются операции «инверсия в конечном поле» и «редукция по модулю». Использование проективных координат позволяет избежать операции «инверсия в конечном поле» при выполнении арифметических операций с точками эллиптической кривой. Так как выполнение арифметических операций («сложение», «вычитание», «умножение» чисел) в системе остаточных классов позволяют избежать вычисления редукции по большому модулю, то с учетом всего выше сказанного большую актуальность приобретает разработка систем, построенных на точках эллиптической кривой, заданной над конечным кольцом.
Соответствие темы диссертации требованиям паспорта специальности ВАК (по физико-математическим наукам). Диссертационная работа выполнена в соответствии с пунктами 1, 3, 6 и 8 паспорта специальности 05.13.18 - «Математическое моделирование, численные методы и комплексы программ» (физико-математические науки) ВАК Министерства образования и науки РФ.
Объектом исследования данной диссертации являются системы на эллиптической кривой, а предметом исследования — эффективные методы и алгоритмы преобразований с точками эллиптической кривой, заданной над конечным кольцом.
Цель работы. Повышение эффективности (скорости выполнения операций) преобразований с использованием эллиптических кривых.
Научная задача заключается в разработке эффективных моделей, методов и модулярных алгоритмов на точках эллиптической кривой в непозиционной системе остаточных классов.
При этом были решены следующие частные задачи:
Разработка алгоритма представления алфавита точками эллиптической кривой.
Разработка метода нахождения количества точек эллиптической кривой, заданной над конечным кольцом.
3.Разработка метода нахождения корней многочленов над конечным полем.
Разработка методов периодического обновления данных, построенных на точках эллиптической кривой, заданной над конечным кольцом.
Разработка пороговой схемы разделения данных на точках эллиптической кривой, заданной над конечным кольцом.
Разработка системы компьютерного моделирования в среде разработки Borland Delphi 7.0., моделирующая разработанную математическую модель, методы и алгоритмы преобразования данных в распределенных вычислительных сетях.
Методы исследования. Для решения поставленных в работе научных задач использованы методы теории вероятностей, математического моделирования, алгебры, теории чисел, теории модулярных вычислений в системе остаточных классов, а также математический и системный анализ.
Достоверность и обоснованность полученных в диссертационной работе теоретических результатов и формулируемых на их основе выводов обеспечивается строгостью производимых математических выкладок. Справедливость выводов относительно эффективности предложенных методов подтверждена компьютерным моделированием.
Научная новизна работы заключается в следующем:
Предложен алгоритм представления алфавита точками эллиптической кривой.
Предложен метод нахождения количества точек эллиптической кривой, заданной над конечным кольцом.
Предложен метод периодического обновления данных, построенный на точках эллиптической кривой, заданной над конечным кольцом с использованием Вихря Мерсенна.
Предложен метод периодического обновления данных, построенный на базе линейных рекуррентных последовательностей на эллиптической кривой над конечными кольцами.
Предложена пороговая схема разделения точки на точки эллиптической кривой, заданной над конечным кольцом.
Разработана система компьютерного моделирования в среде разработки Borland Delphi 7.0., моделирующая разработанную математическую модель, методы и алгоритмы преобразования данных в распределенных вычислительных сетях.
Практическая значимость. Разработанные методы и модулярные алгоритмы существенным образом повышают эффективность алгоритмов, построенных на точках эллиптической кривой, заданной над конечным кольцом, в том числе реализованных в виде программы в среде Borland Delphi 7.0. Полученные результаты могут быть использованы при создании специализированных высокопроизводительных систем, работающих в реальном режиме времени, функционирующих в непозиционной системе счисления.
На защиту выносятся следующие основные положения:
Алгоритм представления алфавита точками эллиптической кривой.
Алгоритм разделения точек на точки эллиптической кривой.
Метод периодического обновления данных, построенный с использованием Вихря Мерсенна на точках эллиптической кривой, заданной над конечным кольцом.
Метод периодического обновления данных, построенный с использованием ЕС - последовательностей на точках эллиптической кривой, заданной над конечным кольцом.
Математическая модель обработки данных в распределенных вычислительных сетях, построенная с использованием точек эллиптической кривой.
Комплекс программ в среде разработки Borland Delphi 7.0., моделирующих разработанные алгоритмы преобразования данных в распределенных вычислительных сетях.
Апробация результатов работы. Результаты работы были представлены в журнале «Информационные технологии» (Москва, 2011 г.), в журнале «Нейрокомпьютеры: разработка и применение» (Москва, 2010 г.), в журнале «Инфоком-муникационные технологии» (Самара, 2010 г.), в журнале «Научно-технические ведомости СПбГПУ» (Санкт-Петербург, 2010 г.), в журнале «Научные ведомости Белгородского государственного университета» (Белгород, 2010 г.), в журнале «Вестник Ижевского государственного технического университета» (Ижевск, 2010 г.), в журнале «Вестник Поморского государственного университета» (Архангельск, 2010 г.), в журнале «Вестник Ставропольского государственного университета» (Ставрополь, 2008, 2009 г.), в трудах участников XI международной
научно-практической конференции «Информационная безопасность 2010» (Таганрог, 22-25 июня 2010 г.), на третьей международной научно-технической конференции «Инфокомуникационные технологии в науке, производстве и образование» (Ставрополь, 1-5 мая 2008 г.), на международной научно-технической конференции «Актуальные проблемы и инновации в экономике, управлении, образовании, информационных технология» (Ставрополь, 12-15 мая 2009 г.), на международной научно-технической конференции «Параллельная компьютерная алгебра» (Ставрополь, 12-15 октябрь 2010 г.) в журнале «Молодой ученый» (Чита, 2010) и на постоянно действующем межвузовском семинаре «Моделирование и нейросетевые технологии» (СГУ, Ставрополь, 2008-2010 гг.).
Публикации. Основные результаты диссертации достаточно полно изложены в 17 научных статьях, 9 из которых опубликованы в центральных научно-технических журналах, рекомендованных ВАК РФ, а 4 статьи - в трудах международных научных конференций.
Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 145 наименований и 1 приложения. Работа содержит 198 страниц машинописного текста, включая 16 рисунков, 4 таблицы и 1 приложение.
