Развитие методов и средств обеспечения целостности и конфиденциальности регистрируемой информации системы информационной безопасности организации воздушного движения тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат физико-математических наук Лёвин, Валерий Юрьевич

• Лёвин, Валерий Юрьевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Лёвин, Валерий Юрьевич

Введение

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

1.1. Постановка задачи.

1.2. Цифровая подпись и однонаправленные хеш—функции в задаче обеспечения целостности и конфиденциальности цифровой информации.

1.3. Протоколы и стандарты цифровой подписи, особенности и выявленные недостатки

1.4. Выводы и основные этапы решения поставленных задач.

2. Кодирование данных точками эллиптических кривых

2.1. Анализ спектра конечного поля и теорема симметрии.

2.2. Детерминированный алгоритм кодирования конечных алфавитов точками эллиптических кривых.

2.3. Вероятностный алгоритм кодирования конечных алфавитов точками эллиптических кривых.

3. Получение формулы расчета размеров ключей в протоколах цифровой подписи целевой системы

3.1. Понятие сложности алгоритма цифровой подписи

3.2. Анализ сложности решения задачи дискретного логарифмирования в мультипликативной группе конечного поля.

3.3. Анализ сложности решения задачи дискретного логарифмирования в группе точек эллиптической кривой.

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

4. Модификация однонаправленных хеш—функций с целью повышения эффективности их программно—аппаратных реализаций

4.1. Анализ трудоемкости основных атак на однонаправленные хеш—функции

4.2. Повышение устойчивости однонаправленных хеш—функций, на основе совершенствования метода Шнайера

4.3. Внутреннее повышение устойчивости однонаправленных хеш—функций

4.4. Построение реализаций хеш—функций на основе модифицированных стандартов блочного шифрования.

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

5.1. Совершенствование и реализация алгоритма цифровой подписи Эль— Гамаля на основе эллиптических кривых устойчивого к изначальной фальсификации подписываемой информации.

5.2. Совершенствование и описание реализации алгоритма цифровой подписи с восстановлением на основе эллиптических кривых.

5.3. Реализация алгоритма цифровой подписи Шнорра на основе эллиптических кривых с целью построения эффективной схемы слепой подписи.

5.4. Построение и реализация алгоритма "слепой"цифровой подписи на основе эллиптических кривых.

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

5.6. Описание программно—аппаратного комплекса.

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

Стремительное развитие информационных технологий оказывает существенное влияние на все стороны жизни общества. Широкое использование телекоммуникаций, технологий Интернет, небывалые масштабы информатизации систем управления в различных сферах деятельности человека и технологических процессах привели к резкому возрастанию потребности в обеспечении информационной безопасности. Ключевое значение при этом отводится целостности и конфиденциальности (достоверности и аутентичности) передаваемой цифровой информации. Таким образом, в развитии инфраструктуры информационной безопасности различных информационно—аналитических систем целостность и конфиденциальность цифровой информации являются центральными задачами. Особое внимание этим вопросам отводится при построении единой системы обработки, анализа и документирования регистрируемой информации в интересах предупреждения и расследования авиационных происшествий. Концепция безопасности такой информационно-аналитической системы изложена в Распоряжении Правительства Российской Федерации "Обеспечение безопасности полетов воздушных судов государственной авиации Российской Федерации в 2010—2014 годах"от 22 апреля 2009 г. По этой причине, исследование проблемы обеспечения целостности и конфиденциальности регистрируемой и передаваемой в подобной системе цифровой информации является крайне важной и актуальной задачей.

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

Настоящая работа, посвящена исследованию и совершенствованию алгоритмов цифровой подписи на основе эллиптических кривых, решающих задачу обеспечения целостности и конфиденциальности цифровой информации в процессе ее сбора, хранения и передачи в рамках развития инфраструктуры информационной безопасности автоматизированной системы управления полетами, навигации, посадки и связи аэродромов государственной авиации (именуемой далее АСУП НПО или целевой системой). В работе предложены алгоритмы цифровой подписи на основе эллиптических кривых которые, по эффективности применения в целевой системе, существенно превосходят имеющиеся аналоги. Установлено, что стандартные алгоритмы цифровой подписи Эль—Гамаля на эллиптической кривой неустойчивы к определенным методам их компрометации, таких как изначальная фальсификация, внедрение скрытых каналов передачи данных и ряд других. Данные особенности не удовлетворяют настоящим повышенным требованиям к безопасности и быстродействию, предъявляемым системой информационной безопасности организации воздушного движения. Для решения поставленной в работе задачи автором систематизированы и дополнены математические знания в области эллиптических кривых, алгоритмов цифровой подписи с восстановлением, с дополнением, алгоритмов 11 слепой" подписи на эллиптических кривых. Процесс построения надежных протоколов цифровой подписи на эллиптической кривой рассматривается в диссертации как единый метод, включающий в себя не только асимметричный алгоритм'подписи, но и алгоритм выработки уникального хеш—значения сообщения. При изучении однонаправленных хеш—функций разработаны методы, позволяющие строить надежные однонаправленные хеш—функции, как из "недоверенных"хеш—функций, так и из произвольных алгоритмов блочного шифрования. Следует отметить, что в процессе разработки предлагаемых методов удалось в несколько раз увеличить количество ключей MAC—хеш—функций, основанных на алгоритмах блочного шифрования, являющихся сетями Фейстеля (например, ГОСТ 28147-89, DES) применяемых автором для построения хеш—функций без снижения их быстродействия. Одним из ключевых достоинств указанного решения является тот факт, что была максимально сохранена структура подобных шифров, что позволяет создавать эффективные аппаратные реализации усовершенствованных MAC—хеш-функций. Кроме этого в работе рассмотрены подходы к решению ряда сопутствующих задач и примеры, позволяющие использовать модель эллиптической кривой не только для построения эффективного протокола цифровой подписи в системе информационной безопасности организации воздушного движения, но и для развития математического обеспечения и создания программных средств, связанных с обеспечением целостности и конфи денциалыюсти информации в процессе ее сбора, хранения и передачи.

Необходимо отметить, что Постановлением Правительства РФ от 18 июня 1998 года JY2 605 (ст. 1, п. 4) определено: "Единая система организации воздушного движения Российской Федерации имеет стратегическое значение для безопасности государства". Отмеченные выше обстоятельства определяют актуальность задачи обеспечения целостности и конфиденциальности цифровой информации.

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

Научная новизна результатов диссертации состоит в развитии методов использования модели эллиптической кривой в протоколах цифровой подписи, используемых для защиты целевой системы, а также в усовершенствовании однонаправленных хеш—функций с целью повышения их устойчивости к различным методам их компрометации: генерация коллизий, "нехватка,,ключей, разглашение служебных параметров, нарушение целостности и ряд других. Предложено улучшение метода Шнайера борьбы с туннельными коллизиями хеш—функций. Создан мультиключевой алгоритм реализации хеш—функций, при котором ключ может обновляться на каждом раунде, что позволило существенно увеличить порядок ключевого множества. На основе метода Полларда получена формула расчета длин ключей, позволяющая определять уровень безопасности систем на основе эллиптических кривых. Применен системный подход к созданию эффективных средств обеспечения целостности и конфиденциальности информации, объединяющий полученные результаты по однонаправленным хеш—функциям, ключевой подсистеме, схемам цифровой подписи и выработке технологических параметров.

Практическая значимость диссертационной работы заключается в разработанных автором в интересах системы обеспечения информационной безопасности организации воздушного движения методах построения безопасных протоколов цифровой подписи на основе эллиптических кривых, в создании эффективных, с позиции программно-аппаратных реализаций, алгоритмов построения однонаправленных хеш—функций. По результатам диссертационной работы автором спроектирован и реализован комплекс средств по работе с эллиптическими кривыми, однонаправленными хеш—функциями, протоколами цифровой подписи. При решении задачи обеспечения целостности и конфиденциальности цифровой информации в процессе ее сбора, хранения и передачи, удалось конструктивно решить вопрос создания резерва ключей, "отсечении11 недоверенной стороны, оперативной модификации и противодействия методам компрометации. Результаты диссертации используются при разработке автоматизированной системы управления полетами, навигации, посадки и связи для аэродромов государственной авиации (далее именуемой АСУП НПС или целевой системой).

Внедрение результатов работы. Результаты диссертации нашли свое применение при разработке "Автоматизированной системы управления полетами, навигации, посадки и связи аэродромов государственной авиации"(ОКР шифр—"Рейс—2000"). Получен Акт от одного из ведущих предприятий по созданию программно—аппаратных комплексов управления воздушным движением—ОАО НПО "Лианозовский Электромеханический За-вод"Концерна ПВО "Алмаз—Антей "об использовании результатов разработки методов и средств обеспечения целостности и конфиденциальности регистрируемой информации.

Заключение диссертации по теме «Методы и системы защиты информации, информационная безопасность», Лёвин, Валерий Юрьевич

1.4. Выводы и основные этапы решения поставленных задач

Анализ литературных источников, представленных автором в главе 1 настоящей работы, позволяет сделать вывод о том, безопасность любого протокола цифровой подписи непосредственно зависит от сложности обращения и сложности вычисления коллизий хэш—функции. В первом случае, например, можно вычислить сообщение для имеющейся подписи, а во втором—заготовить пару сообщений с одинаковыми значениями хэш-функции, подписать одно из них, а потом заменить одно сообщение другим. Более того, накопившийся десятилетиями статистический материал, известные уязвимости в указанных схемах цифровых подписей только усугубляют ситуацию. Как следствие, протоколы цифровой подписи нуждаются не только в постоянной доработке, но и в глубоком анализе их эффективности. Действительно, установлено, что протокол цифровой подписи ГОСТ Р 34.10-2001, ECDSA являются частными случаями схемы Эль—Гамаля цифровой подписи, которая является неустойчивой к изначальной фальсификации сообщений и к внедрению скрытых каналов передачи информации с высокой пропускной способностью, а также других методов компрометации. Конструирование и поддержание единой информационной системы, которая определена целью настоящей работы невозможно без решения поставленных ранее задач. В ходе подготовки диссертации решалась задача построения схем цифровой подписи, не обладающих отмеченными выше недостатками. За основу бралась эллиптическая кривая, так как в работе удалось доказательно обосновать целесообразность использования модели эллиптической кривой в протоколах цифровой подписи целевой системы. Для достижения поставленной цели в работе сформулированы и решаются следующие задачи.

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

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

• Построение алгоритмов кодирования данных точками эллиптических кривых, пригодных для применения в системах реального времени.

• Создание математических методов совершенствования и модификации однонаправленных хеш—функций с целыо повышения их эффективности при программно-аппаратных реализациях.

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

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

На первом этапе рассмотрены вопросы: построения однонаправленных хеш-функций нужных порядков; разработка методики совершенствования произвольной однонаправленной хеш—функции с целыо увеличения количества ключей и эффективного отсечения "недоверенной" стороны и ряд других. При решении подобных задач необходимо было учитывать требования, предъявляемые особенностями информационного объекта. Так, инфраструктура информационной безопасности единой информационно-аналитической системы управления полетами, навигации, посадки и связи государственной авиации обладает большим числом типов информационных потоков, приведенных на рисунке 1.8. Для каждого информационного потока вводятся как долгосрочные, так и

Объекты (центры и боевые посты)УС и РТ( (аэродрома и гарнизона)

КП ЛВБСиПеО

СКП аэродрома вштабеАВВСиЛЙО

Дежурный] врач I

ПУАТО (ПУЛГе*Б> внййуд ВВП РА\

КДП аэродрома+ ПУ УС и РТО (ПУОбсрто)

КПКЛВО

Наблюдатель за включением форсажа

КП иэп + КП ртб + ПУ ЦЛСУ

Сипы и средства ПСС

Стоянка ДОС (дежурное звено)

Элементы системы НОиНП

ПУЕСОрВД

Пост ИАС ПУИАС

Штабная Дежурные средства АТО

Стоянки самолетов

Рис. 1.6. Схема типов информационных потоков объекта краткосрочные ключи, что подчеркивает сложность организации ключевого обмена и возникающие при этом вопросы нехватки ключей для поддержки жизненного цикла указанной системы. По этой причине решалась задача конструирования хеш—функций с неограниченным набором ключей, обладающих высоким быстродействием. Предложен мульти-ключевой алгоритм построения хеш—функции, в котором ключ может изменяться на каждом раунде. Отметим, что множество аппаратных решений, применение современной микроэлектроники требует оптимального быстродействия на разных архитектурах 8,16,32,64 разрядных процессоров. Последнее обстоятельство принималось во внимание при построении методик организации однонаправленных хеш—функций, сохраняющих уникальную архитектуру построений. Полученные решения представлены в главе 4 настоящей работы.

На втором этапе исследования рассматривались задачи: построение схем цифровой подписи на основе эллиптических кривых, обладающих высокой надежностью (в смысле, введенном в разделе 1.1) и быстродействием в целевой системе. Изучение эффективности работы указанных схем приведены в главах 3, 5 настоящей работы. Следует отметить важность решения задач построения протоколов "слепой"подписи, подписи с восстановлением. Действительно, одной из ключевых особенностей информационного объекта является тот факт, что возникает необходимость сведения к минимуму количества секретных параметров, необходимых для верификации подписи. Подчеркивая важность построения схем слепой"цифровой подписи, решалась задача обеспечения анонимности подписывающей стороны. Последнее означает, что необходимо добиться того, чтобы по подписи и сообщению было невозможно однозначно определить подписывающую сторону. На втором этапе, в работе рассматривалась задача построения схем цифровой подписи на эллиптических кривых стойких к внедрению в схему потайных (скрытых) каналов передачи данных с высокой пропускной способностью. Показано, что решение указанной задачи на несколько порядков повысит уровень информационной безопасности объекта, затрудняя процесс внедрения вредоносных агентов в каналы передачи данных. Примеры конкретных эллиптических кривых и сопутствующих технологических параметров, пригодных для схем цифровой подписи, а так же результаты изучения процессов инвертирования, умножения, сложения в группе точек эллиптической кривой приведены в приложении.

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

По результатам приведенных в настоящей работе исследований, автором разработан и прошел тестовые испытания программно—аппаратный комплекс, состоящий из модуля ECDSM (Elliptic Curve Digital Signature Module), станции объективного разбора (СОР) и комплекса программ EL. Подробное описание перечисленных программно—аппаратных решений представлено в разделе 5.7. Написанные автором программы и полученные в диссертационной работе результаты нашли свое применение при разработке "Автоматизированной системы управления полетами, навигации, посадки и связи аэродромов государственной авиации"(ОКР шифр—1"Рейс—2000"). Получен АКТ от НПО "Лианозовский Электромеханический Завод" Концерна ПВО "Алмаз—Антей "об использовании результатов разработки методов и средств обеспечения целостности и конфиденциальности регистрируемой информации, соответствующий АКТ представлен в приложении к диссертационной работе. Модуль ECDSM и программный комплекс СОР применяются Научно-технологическим центром "Электронтех"РАН в современных многоканальных цифровых магнитофонах (МЦМ) и станциях воспроизведения. Учитывая, что Постановлением Правительства РФ от 18 июня 1998 года № 605 (ст. 1, п. 4) определено: "Единая система организации воздушного движения Российской Федерации имеет стратегическое значение для безопасности государства", представленные в настоящей работе решения являются актуальными и востребованными при рассмотрении методов обеспечения целостности и конфиденциальности передаваемой цифровой информации в рамках системы информационной безопасности организации воздушного движения.

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

Глава 2

Кодирование данных точками эллиптических кривых

Во многих, распространенных на практике системах объект должен быть представлен в виде набора точек на эллиптической кривой. Данное представление является малоизученным, несмотря на то, что впервые о необходимости такого представления было заявлено еще в 1985 Н. Коблицом [36]. В работе [68] задачу в такой постановке удалось конструктивно решить. Основные результаты последней работы представлены в данной главе. В рамках ее выполнения, автору удалось сформулировать и доказать теорему симметрии дискретного спектра конечного поля. Использование указанной теоремы, позволило ему разработать детерминированные и вероятностные схемы кодирования символов конечного алфавита точками эллиптических кривых. Применение полученных автором результатов, позволяет в единой инфраструктуре информационной безопасности целевой системы в полной мере применять протоколы цифровой подписи и системы выработки ключей и передачи сообщений на основе эллиптических кривых. Следует отметить то обстоятельство, что разработанные алгоритмы кодирования способны работать в системах реального времени, что делает их востребованными с практической точки зрения.

2.1. Анализ спектра конечного поля и теорема симметрии

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

Для построения указанных алгоритмов необходимо ввести несколько определений. Рассмотрим простое поле Fp и эллиптическую кривую в общей форме, заданную над этим полем (1.16). Для этой эллиптической кривой определены две величины: дискриминант и инвариант. Введем стандартные обозначения: Ь2 = а\ + Аа21 Ь4 = 2а4+а1аз, = а|+4аб, Ь3 — а\ + 4а2ав — а^а^ + а2а2 — а|, — Ь\ — 24£>4, Сб = —Щ + 36Ь2^4 — 216Ь^.

Теперь для любого поля К определим дискриминант Д кривой (1.16) формулой

Д = -Ь% - 8Ь\ - 27% + 9Ь2Ь4Ьв. (2.1)

Если сЪ.ахК 2, 3, то дискриминант определяют формулой

Д = {<$- с26) / 1728. (2.2)

Для справки, 1728 = 2633. Далее, если Д ф 0, то определим 3—инвариант кривой (1.16) формулой

3 (Е) = сЦ Д (2.3)

Определение 2.1.1. Допустимой заменой переменных над полем в уравнении (1.16) называется замена: х = и2 х + г у = и^у + + I где и, г, й, Ь £ Fp, и ф 0.

Заметим, что это своего рода переход к другой системе координат, который в матричной форме записывается в виде: аЛ /х'\ /и2 0 г\ у\ = Л Л ; А = и3 Л . (2.5)

Подобные замены переменных оставляют на месте особую точку О, которая в проективных координатах имеет вид (0:1:0). Легко проверить, что замена, обратная к допустимой, будет допустимой. С точностью умножения переменных на константы кривая, заданная в форме (1.16), после допустимой замены переходит в эллиптическую кривую вида (1.16). С этим обстоятельством свяжем следующее определение.

Определение 2.1.2. Две эллиптические кривые, связанные допустимое заменой переменных, называются изоморфными.

Для дальнейшего построения алгоритмов представления необходимо ввести понятие дуальных эллиптических кривых. Пусть эллиптическая кривая задана в форме Вейер-штрасса (1.18). Рассмотрим для неё допустимую замену переменных, которая сохраняет вид кривой. В уравнении эллиптической кривой (1.18) отсутствуют члены у, ху, х2. Данное свойство влечет за собой то, что у такой замены переменных г = 5 = Ь — 0. Действительно, если г ф 0, то наша эллиптическая кривая перейдет в кривую, которая задается уравнением, где в правой части будет член х2. По этой причине г = 0; если же я ф 0, то в левой части полученного уравнения будет член ух\ а если t ф 0, то в левой части полученного уравнения будет у. Следовательно, определение допустимой замены переменных, сохраняющих вид кривых, для эллиптических кривых в форме Вейерштрасса приобретает вид:

2 '

X = их

2-6) у = и у

При подобной замене переменных, если ввести обозначения а = и4а, b' — uGb, то Еаь : У2 = х3 + ах + b —> Еа>ъ, : у'2 = х'3 + ах' + Ь'.

Следовательно, Еаь = Еа>ь' О а' = u4a,b' = и6Ь, для некоторого и G Fp. Введем вспомогательное определение.

Определение 2.1.3. Пусть над полем Fp заданы две эллиптические кривые:

ЕаЬ у2 = х3 + ах + Ь и Ea'b' : у2 = х3 + а'х + У, причем a,b,a',b' G Fp. Далее, пусть имеет место следующее соотношение: а' = v2a b' = v3b, где v G Fp— квадратичный невычет по модулю р. Тогда такие кривые назовем дуальными.

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

Напомним несколько определений. Пусть а—целое число, р > 2—простое число, тогда возможно корректно определить понятие символа Лежандра [61]. Данный символ появился при изучении решений квадратичных сравнений [61] вида х2 = а( mod р.) При этом, если такое х существует, то число а называется квадратичным вычетом по модулю р, в противном случае—квадратичным невычетом по модулю р. Формально, символ Лежандра является способом обозначения является ли данное число квадратичным невычетом или нет. Символ Лежандра имеет обширное применение в теории чисел и ее приложениях, так как обладает рядом свойств (мультипликативность, квадратичный закон взаимности и рядом других) [61]. Применение данных свойств позволяет создать рекурсивный алгоритм вычисления значения символа Лежандра, не требующий разложения на простые множители. Пусть нужно вычислить ( — |, а < р. Представим а в виде а = 2ЬЬ, где 6—нечетное

Pj число. Далее, основываясь на представленных выше свойствах символа Лежандра, имеем: р mod Ъ\

После чего для нахождения символа I --- I опять применяем этот алгоритм. Заметим, что скорость сходимости этого метода высока и равна скорости сходимости классического алгоритма Евклида, что составляет 0((1пр)2)—двоичных операций [61]. Данное свойство алгоритма позволяет успешно использовать его на практике и в соответствующих алгоритмах кодирования.

Для оценки числа точек на эллиптической кривой над простым полем используем теорему Хассе 1.3.2. Приведем свое, краткое доказательство этой теоремы, необходимое для полученной автором теоремы симметрии. 1 Заметим, что char (Fp) = р. что совпадает с количеством элементов в поле Fp. Следовательно, эллиптическая кривая может иметь не более 2р + 1 различных Fp—точек, т.е точку О и 2р пар (х, у) х, у Е Fp, удовлетворяющих уравнению у2 = х3 + ах + Ь. А именно для каждого из р значений х имеется не более двух значений у, удовлетворяющих уравнению у2 — х3 + ах + Ь. Пусть х —> 1, если х является квадратом элемента из F* ,

2.7) х —► —1, в противном случае. Такое отображение называют квадратичным характером Fp. Положим, что х(0) = 0. Тогда х(х) — ( — ] является символом Лежандра. По этой причине, число решений у Е F„ КРУ уравнения у2 = и равно 1 + х(и)> а число решений уравнения у2 — я3 + ах + Ь, с учетом точки в бесконечности равно

1 + 5^(1 + + ах + Ь)) =р+ 1 + ^2(х(х3 + ах + Ь)). хе¥„ xeF„

Следует ожидать, что х{х3 + ах + Ь) одинаково часто принимает значения ±1. Вычисление этой суммы подобно "случайному блужданию "в статистических испытаниях Бер-нулли (когда мы подбрасываем монетку р раз, продвигаясь на шаг вперед, если выпал герб и на шаг назад, если выпала решка). В теории вероятности подсчитано, что после р бросаний случайное блуждание оказывается на расстоянии ^/р от исходного положения. Сумма + ах + Ь)) ведет себя подобно случайному блужданию. Более точно удалось доказать, что ^ (х(я3 + ах + Ь)) < 2^/р. Данная теорема позволяет подсчитывать хе¥р количества точек на различных эллиптических кривых, заданных над простыми полями, что структурирует предложенный автором анализ.

Пусть эллиптическая кривая задана в форме Вейерштрасса над простым полем уравнением вида у2 = х3 + Ах + В, А, В Е Опираясь на теорему Хассе, формула

1полное и строгое доказательство приводится в [34] для подсчета точек на эллиптической кривой над простым полем может быть записана следующим образом:

Как несложно заметить, подсчет точек по этой формуле (2.8) требует 0(р1+£) арифметических операций, что для небольших значений р позволяет использовать ее на практике.

Пример 2.1.1. В приложении 5.6 приведен пример подсчета точек на эллиптических кривых по формуле (2.8).

Изучим, необходимые для решения поставленной задачи, свойства дуальных эллиптических кривых. Рассмотрим дуальные эллиптические кривые над полем ¥р вида: Къ : У2 = д(х), где д(х) = х3 + ах + 6; Еа>ъ< : у2 = дь(х), где ду{х) = х3 + а'х + Ь'. Причем имеет место следующее соотношение:

I ч а = и а

V = у3Ь, где V Е квадратичный невычет по модулю р. Заметим, что имеет место соотношение ду(х) = ь3д (-). Действительно, ду(х) = х3 + а'х + Ь' = х3 + и2ах + у3Ь =

V3 + а = У3д ^. Пусть Еаь, и Еач/—две дуальные эллиптические кривые над полем Тогда справедливо соотношение фЕаЪ + #Еа'ь' — 2р + 2.

Пример 2.1.2. В качестве иллюстрации представленных соотношений в приложении 5.6 приведены всевозможные дуальные кривые над полем .

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

Определение 2.1.4. Дискретным спектром поля назовем числовой отрезок вида }р + 1 — 2 Л/р[, .,р+1,.,[рЧ-1 + 2^/р] с приписанным каэ/сдой точке N этого отрезка количеством эллиптических кривых, на которых ровно N точек.

Если перебрать все эллиптические кривые над текущем полем, считая количество точек на каждой из них, то обнаружится симметрия вида: эллиптических кривых на которых р точек будет столько же, сколько эллиптических кривых, на которых р+ 2 точки и так далее. Заметим то обстоятельство, что если п < [2у/р]—целое число, эллиптическая кривая в форме (1.3.3) над простым полем, а Еу(¥р) — дуальная эллиптическая кривая в форме (1.18), причем #Е(¥Р) = р + 1 — п. Тогда #Е„(¥р) = р + 1 + п, если у—невычет, #Е(¥Р) = р + 1 — п—иначе. Приведенное замечание позволяет автору доказать теорему симметрии в следующей постановке.

Теорема 2.1.1. (Теорема симметрии спектра конечного поля.) Дискретный спектр поля симметричен относительно центра отрезка ]р + 1 — 2 х/р[, .,р + 1,.,[р + 1 + 2 ^/р]. Нужно показать, что соответствие Еаь —Еа>ъ> взаимооднозначно, то есть у двух различных эллиптических кривых в форме Вейерштрасса не может быть одинаковой дуальной кривой. Рассмотрим две кривые Еа1ь1} Еа2ь2 а.\, ¿1,02,62 £ Положим b\ = b2, а\ несравнимо с а2 по модулю р и что обе эти кривые перешли в кривую Еа>ь>- Данное предположение основано на том, что кривые должны быть различные (иметь хотя бы одну пару несравнимых по модулю р коэффициентов), случай когда таких пар две есть прямое следствие рассматриваемого. Заметим, что в рассматриваемом случае условие того, что кривые перешли в одну равносильно условию a\V2 = a2v2 mod р, но тогда ci\ = а2 mod р. Последнее невозможно, так как рассматривались кривые, у которых а\ несравнимо с а2 по модулю р (то есть заданные разными многочленами). Пришли к противоречию, взаимооднозначность отображения доказана. ■

Эта теорема'позволяет применением отображения Еаь —> Еа>ь> порождать кривые, связанные соотношением #Еаъ + #Еа>ь' — 2р + 2.

2.2. Детерминированный алгоритм кодирования конечных алфавитов точками эллиптических кривых

Рассмотрим простое поле Е = эллиптическую в форме Вейерштрасса (1.18), над этим полем и конечный алфавит А — {ао, а2, ■., ал/-1}, символы которого необходимо закодировать точками эллиптической кривой. Поставим в соответствие буквам алфавита их номера, и без ограничения общности будем считать, что закодировать буквы алфавита это одно и тоже, что и закодировать их номера. Возьмем произвольный квадратичный невычет V, рассмотрим две кривые: Еаь и к ней дуальную Еа>ъ'- Пусть т € [0,., М — 1]—число которое необходимо закодировать. Рассмотрим удвоенный отрезок: [0,., 2М — 2]. Пусть у{х) = х3 + ах + Ь, ду(х) = х3 + а'х + Ъ'. Теперь последовательно, начиная с 0 до 2М — 2, вычисляем символ Лежандра , т е [0,., 2М — 2], если = 1, то данному д{™)\ числу соответствует точка на первой кривой, а если - = — 1, то данному числу

V V ) соответствует точка на второй кривой. Действительно, выше показана справедливость соотношения ду(х) = У3д Заметим, что если ^ = —1, то д{т)—квадратичный невычет по модулю р. Но тогда ду(ту) будет являться квадратичным вычетом, верно и наоборот. Свойство быть вычетом или невычетом здесь равносильно существованию на соответствующей эллиптической кривой точки Рт(х,у) в которую переводится число т. Информацию о том, является ли д(т) и дь(ть) вычетом/невычетом удобно представить в виде таблицы 2.1, где + означает, что д(т) или дь(ту)—вычет, а--невычет. Следовательно, можно считать, что + соответствует существованию представления числа т в виде точки на соответствующей эллиптической кривой, а--отсутствие такого представления.

После того как дойдем до 2М — 2, выбираем ту кривую, на которой больше или равно М плюсов. Теперь заметим, тот факт, что при подстановки х в Е^у получаем +, тп 6 [о.2 Л/ — 2] КдЬ : у2 = х3 + аа: + Ь Еагь/ ' у2 = х3 + о'х 4- Ь' позиция на Е^ь позиция на Еп/у

0 + ч

1 + 12

2 - + • Л

3 - + ■ ^

4 + - »3 •

5 + •

6 + ы

7 - + ¿4 + +

2М-2 +

Заключение

Изложенные в настоящей работе результаты позволили автору решить задачу разработки и совершенствования алгоритмов цифровой подписи на основе эллиптических кривых, решающих задачу обеспечения целостности и конфиденциальности цифровой информации в процессе ее сбора, хранения и передачи в рамках системы информационной безопасности организации воздушного движения. Решение основной задачи обеспечения информационной безопасности подконтрольного объекта было разделено на несколько ключевых этапов. Указанное обстоятельство позволило осуществить наиболее полный анализ и повысить уровень детализации проведенного исследования. На первоначальном этапе удалось конструктивно решить задачу построения стойких MDC, MAC—хеш—функций. Разработанные автором методики позволяют не только строить надежные однонаправленные хеш—функции из произвольных однонаправленных хеш—функций, обладающих эффективными программно—аппаратными реализациями и решающими вопросы структуризации и организации процесса ключевого обмена и создания резерва ключей системы. Использование указанных решений позволяет пермоментно поддерживать уровень информационной безопасности подконтрольного объекта на высоком уровне. Кроме построения MDC—хеш—функций в работе приводятся схемы построения MAC—хеш—функций, которые в полном объеме решают задачу обеспечения аутентичности данных при их сборе, хранении и передаче. Используя разработанные методики построения однонаправленных хеш—функций на основе блочных шифров, удалось, на примере DES, построить однонаправленную хеш—функцию, обладающую необходимым быстродействием. Особенностью указанного решения является его мультиключевая структура, позволяющая изменять ключ на каждом раунде. Оперативная модификация мультиключевого алгоритма построения хеш—значения заключается в том, что появляется возможность применять любые блочные шифры, являющиеся сетями Фейстеля, основанные на фиксированных S—блоках, такие, например, как ГОСТ 28147-89, DES. За счет введения параметрического семейства латинских квадратов, позволяющих строить параметрические семейства S—блоков, удалось увеличить количество ключей и ввести их иерархию (например, при построении хеш—функции на основе модифицированного DES число ключей увеличено до 21024). Отметим, что в мультиключевом алгоритме расчета хеш—значения, используемый алгоритм блочного шифрования максимально возможно сохранил первоначальную архитектуру, при этом многократно снизилась эффективность применения дифференциального и линейного анализа. Предлагаемый мультиключевой способ построения хеш—функций обладает рядом преимуществ над имеющимися стандартами как по быстродействию, так и по архитектуре построения. Он удобен для программно—аппаратных реализаций, что делает его использование на микропроцессорах малой мощности особенно актуальным.

Указанные решения рассматривались с целью построения хеш—функции, при рассмотрении же вопросов шифрования необходимо детально изучить вопросы слабых ключей и оптимальности выбора блоков замены. Данное обстоятельство подчеркивает необходимость проведения дальнейших исследований по данному направлению. Предложенные в работе решения позволяют строить хеш—функции с различными архитектурами и быстродействием. По этой причине, они представляют особую ценность при решении ряда практических задач. В работе удалось конструктивно разрешить вопрос о нехватке и создании резерва ключей, который является одним из центральных при обеспечении целостности и конфиденциальности цифровой информации реализации инфраструктуры информационной безопасности автоматизированной системы управления полетами, навигации, посадки и связи государственной авиации (АСУП НПС). При построении асимметричных протоколов цифровой подписи в работе использовалась модель эллиптической кривой. Показана, целесообразность применения модели эллиптической кривой в построении эффективных схем цифровой подписи на их основе, удовлетворяющих требованиям, предъявляемым к схемам целевой системой. Отметим, что применение эллиптической кривой в подобных протоколах позволяет использовать ключи существенно меньшего размера, чем в случае с имеющимися стандартами схем цифровой подписи в мультипликативной группе конечного поля. Проведен подробный, доказательно обоснованный расчет устанавливающий данную закономерность. Полученные при этом расчетные данные совпадают с, представленными в тексте работы, таблицами RSA, что свидетельствует об целесообразности и актуальности использования эллиптической кривой в протоколах цифровой подписи. С целью корректного применения систем на основе эллиптических кривых, в работе приводится ряд теорем и алгоритмов, позволяющих закодировать символы конечного алфавита точками эллиптической кривой. Решение указанной задачи позволяет в полном объеме использовать модель эллиптической кривой как при построении новых протоколов цифровой подписи, так и при применении имеющихся в целевой системе. Аналоги основных систем на основе эллиптических кривых изучены и представлены в приложении. Установлено, что имеющиеся протоколы цифровой подписи ECDSA, ГОСТ Р 34.10-01 не являются устойчивыми к изначальной фальсификации информации и к внедрению скрытых каналов передачи информации, обладающих высокой пропускной способностью и других методов компрометации. Предложены методики, позволяющие устранить указанные недостатки. Разработаны модели подписи с восстановлением, 11 слепой "подписи, подписи ECSDSA, подписи ECNRDSA на основе эллиптических кривых. Приведенные схемы успешно решают задачи анонимности подписывающей стороны (для схемы " слепой "подписи) и минимизации секретных данных системы, необходимых для принятия подписи (для схем с восстановлением и схем ECSDSA). Совершенствованы алгоритмы генерации эллиптических кривых и оптимального выбора точки основания с целью их эффективного применения в протоколах цифровой подписи целевой системы. Для всех типов эллиптических кривых оценена арифметическая трудоемкость основных групповых операций. При оценке арифметической трудоемкости, в рассмотрение введены не только характеристики конечного поля, но и различные способы представления его элементов. Подобные исследования представлены в приложении к работе. Автором реализован ряд программных средств для работы с эллиптическими кривыми и однонаправленными хеш—функциями. Исследованы методы рассчета основных технологических параметров, позволяющие успешного применять указанные схем цифровой подписи на основе эллиптических кривых в системе АСУП НПС.

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Лёвин, Валерий Юрьевич, 2010 год

1. Шпайер Б. Прикладная криптография, 2—ое издание, Протоколы, алгоритмы и исходные тексты на языке С, 2002.

2. Menezes A., Oorschot P., Vanstone S. Handbook of Applied Cryptography, CRC Press, 1996.

3. Алферов А.П., Зубов А.Ю.,Кузьмин А.С.,Черемушкин А.В. Основы криптографии, 3-е изд., изд—во Гелиос—АРВ, 2005

4. Griffiths G., Carlyle S. "The Tea Leaf Reader Algorithm: An Efficient Implementation of CRC 16 and CRC 32", Communications of the ACM, 30(7), pp. 617-620.

5. Knuth D.E. "The Art of Computer Programming", Volume 2: Seminumerical Algorithms, Section 4.6. (Кнут Д.Е. "Искусство программирования для ЭВМ", т. 2 "Получисленные алгоритмы"-М., "Мир", 1977).

6. Ross N. Williams "A painless guide to CRC error detection algorithms", 1993

7. Merkle R.C. "One Way Hash Functions and DES", Advances in Cryptology, CRYPTO'89 Proceedings, Springer—Verlag, 1990, pp. 428—446.

8. Shamir A., Biham E. "Differential cryptoanalysis of DES-like cryptosystems", advances in Cryptology, CRYPTO'90 Proceedings, Springer—Verlag, 1991, pp. 2-21.

9. Shamir A., Biham E. "Differential cryptoanalysis of the full 16-round DES", advances in Cryptology, CRYPTO'92 Proceedings, Springer—Verlag, 1993, pp. 487—496.

10. Shamir A., Biham E. "Differential cryptoanalysis of the Data Encryption Standard", Springer—Verlag, 1993.

11. Matsui M "Linear Cryptoanalysis Method for DES cipher", Advances in Cryptology, EUROCRYPT'93 proceedings, Springer-Verlag, 1994, pp. 386-397.12. ГОСТ 28147-89.

12. Chudov G., Leontiev S. "GOST 28147-89 Cipher Suites for Transport Layer Security (TLS)", CRYPTO-PRO December 8, 2008.

13. Hirose S. Some Plausible Constructions of Double-Block-Length Hash Functions. In: Robshaw, M.J.B. (ed.) FSE 2006, LNCS, vol. 4047, pp. 210-225, Springer, Heidelberg 200615.