автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:Методы защиты информации посредством почти пороговых схем разделения секрета

На правах рукописи

МЕДВЕДЕВ НИКИТА ВЛАДИМИРОВИЧ

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

Специальность 05.13.19 - Методы и системы защиты информации, информационная безопасность

Автореферат

диссертации на соискание ученой степени кандидата технических наук

11 0 К Т. 2012

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

005053144

Работа выполнена в ФГБОУ ВПО "Уральский государственный университет путей сообщения" на кафедре "Высшая и прикладная математика".

Официальные оппоненты:

Научный руководитель: доктор физико-математических наук, профессор

Титов Сергей Сергеевич

доктор технических наук, профессор, заведующий кафедрой информационной безопасности института математики и компьютерных наук ФГБОУ ВПО "Тюменский государственный университет" Захаров Александр Анатольевич

кандидат технических наук, доцент, ФГАОУ ВПО "Санкт-Петербургский государственный университет аэрокосмического приборостроения кафедра информационных систем Шехунова Наталья Александровна

ФГОУ ВПО "Институт Федеральной службы безопасности Российской Федерации", г. Екатеринбург

Ведущая организация:

Защита диссертации состоится 24 октября 2012 года в 13:00 час. на заседании диссертационного совета Д218.008.06 на базе ФГБОУ ВПО "Петербургский государственный университет путей сообщения" по адресу: 190031, г. Санкт-Петербург, Московский пр., д. 9, ауд. 1-217.

С диссертацией можно ознакомиться в библиотеке Петербургского государственного университета путей сообщения и на сайте Минобрнауки www.vak.ed.gov.ru.

Автореферат разослан 24 сентября 2012 года.

Ученый секретарь диссертационного совета Кудряшов

кандидат технических наук, профессор Владимир Александрович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования.

Современный этап развития общества характеризуется возрастающей ролью информационной сферы, которая, являясь системообразующим фактором жизни общества, активно влияет на состояние безопасности различных направлений деятельности. Национальная безопасность Российской Федерации существенным образом зависит от обеспечения информационной безопасности, и в ходе технического прогресса эта зависимость будет возрастать1. Поэтому вопросы, связанные с математическими методами и задачами зашиты информации являются чрезвычайно важными2. Такие вопросы приводят также и к сложным задачам разграничения доступа к информации и разделения секрета3,4. Одними из основных криптографических примитивов в теории и практике защиты информации являются схемы разделения секрета (CPG). Часто их относят также к механизмам защиты. Основная идея СРС состоит в раздаче долей секрета участникам таким образом, чтобы заранее заданные коалиции участников (разрешенные коалиции) могли однозначно восстановить секрет (совокупность этих множеств называется структурой доступа), а неразрешенные - не получали никакой дополнительной информации, к имеющейся априорной, о возможном значении секрета, такие СРС называются совершенными. Особый интерес вызывают идеальные СРС, т.е. такие, где размер доли секрета, предоставляемый участнику, не больше размера секрета. Если разрешенными коалициями являются любые множества из п или более элементов, то такие СРС называются пороговыми "п из iV" СРС, где N - количество всех участников.

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

1 Доктрина информационной безопасности [Электронный ресурс]. Российская газета [сайт]. http://www.rg.ru/ofiCTal/doc/min_and_vedom/mim_bezop/doctr.shtm (дата обращения: 09.07.2012).

введение в криптографию / Под общ. ред. В.В. Ященко. - СПб: Питер, 2001. - 288 с.

3Гайдамакнн H.A. Автоматизированные информационные системы, базы в банки данных. Вводный курс: Учсо-ное пособие. - М.: Гелиос АРВ, 2002. - 368 с.

4Гайдамакин H.A. Разграничение доступа к информации » компьютерных системах. - Екатеринбург: Изд. Урал.

Ун-та, 2003. - 328 с.

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

Актуальной задачей является, в том числе, реализация сложных структур доступа в идеальных схемах, т.к. известно, что существуют СРС, реализующие произвольную структуру доступа, но они могут не быть идеальными5. Таковыми, например, могут быть однородные схемы6. В связи с этим, особый интерес вызывают однородные структуры доступа и близкие к ним так называемые почти пороговые, которые допускают, тем не менее, идеальную реализацию. Это направление исследований связано с известной гипотезой о том, что степень неидеальности может расти экспоненциально, как при неэффективной реализации пороговой СРС. Современные инструменты исследования этого вопроса -теория матроидов, геометрия эллиптических кривых. Представленная диссертация лежит в русле опровержения этой гипотезы. Использование рациональных точек на эллиптических кривых ранга больше нуля позволяет рассматривать почти пороговые СРС с бесконечным числом участников. Построение рациональных приближений высокой точности приводит к проблеме всюду плотности множества E(Q) рациональных точек на эллиптических кривых как аналога совершенности. Построение однородных совершенных идеальных схем приводит к задаче изучения почти пороговых матроидов.

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

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

5Ito М., Saito A., Nishizeki Т. Secret sharing scheme realizing any access structure. - Proc. IEEE Globecom'87, 1987. - C. 99-102.

®Marti-Farre J., Padro C. Secret sharing schemes on sparse homogeneous access structures with rank three. // Electronic Journal of Combinatorics, 11(1), 2004, Research Paper 72, 16 pp.

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

Вопросам изложения теории защиты информации, разграничения доступа, а также описания СРС и матроидов, посвящены труды и основополагающие работы ряда отечественных и зарубежных специалистов: В.В. Ященко, Н.П. Варновского, Ю.В. Нестеренко, Г.А. Кабатянского, П.Н. Девянина, В.Г. Проскурина, A.B. Черемушкина, П.А. Гырдымо-ва, А.Ю. Зубова, A.B. Зязина, В.Н. Овчинникова, H.A. Гайдамакина, Г.Р. Блейкли, A. Shamir, М.О. Асанова, В.А. Баранского, В.В. Расина, O.A. Логачёва, A.A. Сальникова, M. Ito, A. Saito, Т. Nishizeki, P.D. Seymour, D.J.A. Welsh, В. Липского. Проблемы информационной безопасности описываются Ю.С. Хариным, В.И. Берником, Г.В. Матвее-вем, C.B. Агиевичем, H.A. Молдовяном, A.A. Молдовяном, В.В. Яковлевым, A.A. Корниенко, М.А. Еремеевым, С.Е. Ададуровым, А.Г. Ко-тенко, Г.И. Кожомбердиевой, И.С. Киселевым, Ю.Н. Максимовым, Е.А. Аникевич, В.М. Зима, А.Ю. Щербаковым, О.О. Михальским, A.C. Пер-шаковым, Д.П. Зегждой, A.M. Ивашко, Е.Б. Беловым, В.П. Лосем, Р.В. Мещеряковым, A.A. Шелупановым, О.В. Казариным. Математический аппарат, используемый в диссертации, подробно рассмотрен М.М. Глу-ховым, В.Д. Белоусовым, Н.Х. Ибрагимовым, A.M. Ильиным, В.А. Ко-лывагиным, А.И. Маркушевичем, Л.С. Понтрягиным, А.Ф. Сидоровым, М. Холлом, И.В. Стеллецким, Т.С. Фофановой. Исследованию эллиптических функций и кривых, используемых при разделении секрета в диссертации, посвящены труды A.A. Болотова, С.Б. Гашкова, A.B. Фролова, A.A. Часовских, В.В. Соловьева, В.А. Садовничего, Е.Т. Щавгу-лидзе, В.В. Белокурова, Н.И. Ахиезера, Э. Кнэппа, В.В. Острика, М.А. Цфасмана, Ю.П. Соловьева, Е.Т. Шавгулидзе, В.Н. Ушакова, Н. Коб-лица, А.Г. Ростовцева. Подробный обзор литературы приведен в тексте диссертации.

Объектом исследования в диссертационной работе является теория и практика разделения секрета, а предметом исследования - конструк-

з

ции сложных структур доступа на основе идеальных СРС и их применение в защите информации.

Целью исследования является изучение класса идеальных схем разделения секрета, близких к пороговым, а именно, схем, в которых минимальные разрешённые коалиции участников имеют близкую (в частности, одинаковую) мощность. Такие схемы названы в работе почти пороговыми.

Поставленная цель достигнута путем решения следующих задач:

1) предложить СРС на эллиптических кривых, изучить их основные свойства и структуры доступа;

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

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

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

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

Основные положения, выносимые на защиту:

1. Конструкция идеальной почти пороговой СРС при помощи многочленов на эллиптических кривых.

2. Критерий всюду плотного расположения множества рациональных точек на эллиптической кривой Е(<0) и доказательство гипотезы В.Н. Ушакова, интерпретация всюду плотности как аналога совершенности в идеальных почти пороговых СРС с бесконечным количеством участ-

НИКОВ.

3. Исчерпывающее описание бинарных идеальных совершенных почти пороговых СРС и их связь с кодами Рида-Маллера первого порядка.

4. Конструкция бесконечных серий линейных идеальных почти пороговых СРС над любым конечным полем.

5. Конструкция идеальной совершенной почти пороговой СРС при помощи эллиптической кривой, где многочлен третьей степени используется для генерации проверочной матрицы над конечным полем кода линейной СРС.

Научная новизна. Все основные результаты работы являются новыми, а именно:

1) впервые предложены идеальные почти пороговые СРС при помощи многочленов на эллиптических кривых;

2) приоритет в доказательстве "гипотезы А" В.Н. Ушакова и получении критерия всюду плотного расположения множества рациональных точек на эллиптической кривой принадлежит соискателю. Впервые проинтерпретирована всюду плотность множества точек на эллиптической кривой как аналог совершенности в идеальных почти пороговых СРС;

3) впервые описан класс линейных кодов как идеальных совершенных почти пороговых СРС и соответствующих почти пороговых матроидов.

4) впервые реализована линейная идеальная совершенная почти пороговая СРС на эллиптической кривой при помощи многочлена не выше третьей степени.

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

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

Реализация результатов работы. Основные результаты диссер-

тационных исследований внедрены в следующих организациях:

1. Екатеринбургский филиал ФГУП "ЗащитаИнфоТранс" (Министерство транспорта Российской Федерации) - утверждена и введена в действие "Методика разграничения доступа к документам с информацией ограниченного распространения".

2. ФГБОУ ВПО "Уральский государственный университет путей сообщения" - в лекционных курсах и лабораторных работах дисциплин "Дискретная математика", "Криптографическая защита информации", "Теория информационных процессов и систем", изучаемых студентами по направлениям 230400 - "Информационные системы и технологии" и 090900 - "Информационная безопасность".

Апробация результатов. Основные результаты диссертации докладывались на научных конференциях и семинарах: на международной конференции "Безопасность информационного пространства" (г. Екатеринбург, 2006 г.); на межвузовской научно-технической конференции "Молодые ученые - транспорту" (г. Екатеринбург, УрГУПС, 2007 г.); на ассамблее студентов и школьников "Молодежь - будущее атомной промышленности России" (г. Снежинск, 2007 г.); на международной молодежной школе-конференции "Проблемы теоретической и прикладной математики" (г. Екатеринбург, ИММ УрО РАН, 2008, 2010, 2011, 2012 гг.); на международной научно-практической конференции СВЯЗЬ-ПРОМ-2008 (г. Екатеринбург, 2008 г.); на VIII региональной научно-практической конференции студентов, аспирантов и молодых ученых "Безопасность информационного пространства" (г. Челябинск, 2009 г.); на IX научно-практической конференции молодых специалистов "Автоматизация. Инновация. Качество" (г. Нижний Тагил, 2010 г.); на научном семинаре УНП БИТ (г. Екатеринбург, УрГУПС, 2010 г.); на научном семинаре кафедры "Системы и технологии защиты информации" (г. Екатеринбург, УрГУПС, 2010 г.); на научном семинаре кафедры "Прикладная математика" (г. Екатеринбург, УрГУПС, 2010 г.), а также - на международной конференции CSEDays (пленарный доклад, г. Екатеринбург, 2011 г.); на международном Российско-Корейском семинаре "Russia-Korea Workshop on advanced computer and information technologies" (г. Екатеринбург, 2011, 2012 гг.); на научном

семинаре члена-корреспондента РАН Ушакова В.Н. (г. Екатеринбург, ИММ УрО РАН, 2011 г.); на международной конференции "Транспорт 21 века: Исследования. Инновации. Инфраструктура" (г. Екатеринбург, 2011 г.); на региональной конференции ВИП "Безопасность информационного пространства" (г. Екатеринбург, 2011 г.); на внутривузовской конференции "Математические методы решения исследовательских задач" (г. Екатеринбург, УрГУПС, 2011 г.); на региональной конференции "Математические методы и модели в теоретических и прикладных исследованиях" посвященной 55-летию УрГУПС и 80-летию со дня рождения И.Я. Каца (г. Екатеринбург, УрГУПС, 2011 г.); на внутривузов-ском семинаре аспирантов УрГУПС (г. Екатеринбург, 2012 г.), на международной научно-практической конференции "Интеллектуальные системы на транспорте" (г. Санкт-Петербург, ПГУПС, 2012 г.); на семинаре кафедры "Вычислительной техники и защиты информации" под руководством В.И. Васильева (г. Уфа, Уфимский государственный авиационный технический университет, 2012 г.). Всего сделаны доклады на двадцати четырех конференциях и семинарах различного уровня.

Публикации. Основные результаты диссертации опубликованы в 17 работах [1-17], в том числе 5 [1-5] - в изданиях; входящих в перечень

рекомендованных ВАК РФ.

Структура и объем диссертации. Диссертационная работа состоит из введения, трех глав основного содержания с выводами по каждому разделу, заключения, списка литературы, включающего 155 наименований. Материалы диссертации изложены на 121 странице, включающих 10 рисунков с графиками и иллюстрациями, 14 таблиц и 2 программы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

безопасности.

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

В этой главе предлагается использовать эллиптическую кривую и точки на ней для параметризации участников, и исследуются свойства получающейся СРС. Разделение секрета на эллиптической кривой происходит по следующему алгоритму: дилер выбирает эллиптическую кривую ЕС над конечным полем с необходимым количеством точек (не менее N). Каждому из участников СРС (в том числе хранителю секрета) ставится в соответствие точка на эллиптической кривой, включая, возможно, "бесконечно удаленную". Затем дилер выбирает многочлен степени п на этой кривой. Коэффициенты этого многочлена известны только ему. Точка на эллиптической кривой, которая обозначает участника - хранителя секрета, известна всем. Дилер подставляет координаты этой точки в выбранный им многочлен, вычисляет значение секрета. Для того чтобы каждому участнику раздать его долю секрета, дилер подставляет координаты точки участника в многочлен, получая долю секрета для него. В итоге участник имеет точку на эллиптической кривой (login) и долю секрета (password). Для восстановления секрета нескольким участникам необходимо объединиться, чтобы восстановить коэффициенты выбранного дилером многочлена. Технологически это сводится к решению некоторой системы уравнений. Участники, составляющие разрешенную коалицию, получают искомый многочлен, куда подставляют координаты точки, обозначающей секрет. В итоге они получают секрет, который сформировал дилер [10]. Описание минимальных разрешенных коалиций (структуры доступа) дает

Теорема 1.1. Для п различных точек на эллиптической кривой ЕС существует многочлен степени п, имеющий эти точки своими корнями, тогда и только тогда, когда сумма этихп точек равна нулю в группе точек данной кривой.

Итак, если в коалиции участников меньше чем п, то такая коалиция будет неразрешенной. Если в коалиции участников ровно п, и сумма точек-участников не равна 0, то это разрешенная коалиция. Если в коалиции участников ровно п, и сумма точек-участников равна 0, то это неразрешенная коалиция. Добавление в неразрешенную коалицию изп участников любого другого участника, не состоящего в этой коалиции, делает данную коалицию разрешенной.

Для таких схем, в которых минимальные разрешенные коалиции СРС имеют близкую мощность (либо п, либо п+1), введён термин почти пороговые схемы. Как оказалось, почти пороговые СРС на эллиптических кривых не являются однородными и пороговыми, кроме двух тривиальных случаев.

В связи с рассмотрением подходов к решению проблемы о максимально возможном числе N участников пороговой СРС "п из И" доказана Теорема 1.2. В конечной абелевой группе С? для данного п такого, что 0 < п < 1С?!, не существует п-подмножества, сумма элементов которого равна нулю, в следующих лишь случаях:

1) либо С - элементарная абелева группа вида Ъ\, причем п = 2 при в > 1 или п = 2" - 2 при в > 2;

2) либо в группе С? имеется единственный (ненулевой) элемент

второго порядка, ип = |(3|.

Для СРС на эллиптических кривых эта теорема означает, что схема разделения секрета будет пороговой лишь в двух тривиальных случаях: 1) группа изоморфна Ъг или Ъ\ (точки на оси абсцисс), п = 2; 2) схема является пороговой "Я из Я" схемой, и порядок группы точек эллиптической кривой равен Ы, где N = 21,1 - нечетно.

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

Теорема 2.1. Связная компонента нуля группы Е(Ш.) топологически изоморфна одномерному тору Т.

Следствие 2.1. Группа Е(Ж) топологически изоморфна либо одномерному тору Т (при А < 0), либо 2ч © Т (при А > 0).

Теорема 2.2. Любая точка бесконечного порядка порождает группу, содержащую всюду плотную подгруппу связной компоненты нуля в группе Е(Щ.

Следствие 2.2. Если эллиптическая кривая на полем <0> имеет ранг больше нуля, то рациональные точки на ее правой ветви располагаются всюду плотно.

Следствие 2.3. При А > 0, любая точка бесконечного порядка, лежащая на левой ветви эллиптической кривой, порождает подгруппу, всюду плотную в Е(Ш.).

Следствие 2.4. В случае А > 0, если ранг эллиптической кривой над (О больше нуля, и есть хотя бы одна рациональная точка на левой ветви эллиптической кривой, то множество рациональных точек всюду плотно на всей кривой.

Рассмотрено приложение этой теоремы к конкретной кривой В.Н.Ушакова у2 = х3 — 4а:+ 4. Проведены конкретные расчеты с длинными числами в системе МАТЬАВ. На основе теоремы Лагранжа о подгруппах и теоремы Лутц-Нагеля о точках кручения на эллиптической кривой доказано, что точек кручения на этой кривой нет. Поэтому каждая рациональная точка этой кривой является точкой бесконечного порядка и, в частности, точка Р — (2; 2). Следовательно, серия точек тР, т € является бесконечной, и ранг исследуемой кривой г > 1. Отсюда и из следствия 2.2 вытекает обосновывающее "гипотезу А" В.Н. Ушакова следующее

Утверждение 2.1. Множество рациональных точек на эллиптической кривой у1 = х3 — 4х + 4 всюду плотно.

На основе гипотезы Берча и Свиннертон-Дайера, в части, доказанной В.А. Колывагиным, численно получено

"Утверждение 2.2. Ранг эллиптической кривой у2 = х3 — Ах + 4 равен единице.

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

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

Как известно7'8 разрешенные коалиции идеальной совершенной схемы разделения секрета определяются циклами некоторого связного матроида, изучение которого и дает структуру доступа. Естественно назвать матроид почти пороговым, если все его циклы n-элементны, но, возможно, не все его n-элементные подмножества - циклы.

Путем комбинаторных рассуждений получено

Утверждение 3.1. Для мощности цикла один, два и три связного почти порогового непорогового матроида не существует.

Это утверждение подчеркивает сложность проблемы существования почти пороговых матроидов. Рассмотрением 8-битовых строк (байтов) получено

Утверждение 3.2. Для мощности цикла четыре простой связный почти пороговый непороговый матроид существует.

Добавление к четырнадцати циклам этого матроида пустого множества и всего восьмиэлементного множества дает шестнадцатиэлемент-ную элементарную абелеву группу.

Предложена конструкция удвоения элементов матроида с последующим их разделением, так, что получается бесконечная серия матроидов М$ с мощностью циклов п = 2е на т = 2п = 2а+1-элементном множестве (s = 2,3,...).

'Введение в криптографию / Под общ. ред. В.В. Ященко. - СПб: Питер, 2001. - 288 с.

8Глухов М.М., Елизаров В.П., Нечаев A.A. Алгебра: учебник для вузов. - М.: Гелиос АРБ, - 2003. - ЗЗЬ с.

Утверждение 3.3. В простом связном почти пороговом непороговом матроиде с мощностью 2т имеется изоморфизм групп С^« —

Замечено, что в общем случае циклы связного почти порогового мат-роида с п = 2т~1 мощности N = 2т и соответствующие СРС описываются кодами Рида-Маллера первого порядка ЛМ( 1, т), что доказывает

"Утверждение 3.4. Существует бесконечная серия связных простых почти пороговых непороговых матроидов с мощностью 2т, которые описываются кодами Рида-Маллера первого порядка.

Итак, доказана

Теорема 3.1. Существует бесконечная серия идеальных битовых почти пороговых совершенных СРС, основанных на кодах Рида-Маллера первого порядка Ш(1,т), при п = 2т~1, N = 2т.

Рассмотрена проблема незаменимости участников СРС, препятствующих разграничению доступа:

"Утверждение 3.5. В матроиде, соответствующем СРС, нет незаменимых участников тогда и только тогда, когда для любых х ф у существует разделяющий их цикл С, т.е. х £ С, у € С.

Естественно назвать такие матроиды разделяющими и использовать в идеальных СРС только такие, т.е. разделяющие, матроиды.

Матроид называется бинарным, если он является векторным над полем 1,2 = СР(2). Рассмотрением факторгрупп группы С3 получено

Утверждение 3.6. В бинарном почти пороговом матроиде с мощностью циклов п > 4 мощность пересечения каждой пары циклов либо га/2, либо нуль.

Утверждение 3.7. Мощность циклов бинарного разделяющего почти порогового матроида есть степень двойки.

Утверждение 3.8. Бинарные связные разделяющие почти пороговые матроиды с 2к элементами и мощностью циклов п = 2к_1 определяются с точностью до перенумерации элементов (битов) кодами ЯМ{1, к), к >2.

Рассмотрением прообразов гомоморфизмов доказана

Теорема 3.2. Бинарные связные разделяющие почти пороговые СРС и их матроиды с мощностью циклов п > 4 описываются с точно-

стыо до перенумерации битов исчерпывающим образом кодами Рида-Маллера первого порядка и выколотыми кодами Рида-Маллера первого порядка.

Обобщение этой теоремы приводит к конструкции почти пороговых СРС и их матроидов над любым полем С^). Предложен двойственный вариант аксиоматизации матроидов с помощью антициклов (дополнений циклов) как нуль-множеств. На основе линейных функций, по аналогии с кодам Рида-Маллера, образующих проверочную матрицу кода и описывающих циклы матроида получено

Утверждение 3.9. Проективное пространство является матро-идом над с гиперпространствами в качестве антициклов.

Утверждение 3.10. Аффинное пространство является матрои-

дом над (З^Хд) с гиперпространствами в качестве антициклов.

Рассмотрена также конструкция линейной идеальной совершенной почти пороговой СРС на эллиптической кривой посредством многочлена третьей степени, который используется для генерации проверочной матрицы над (ЗЗД кода этой линейной СРС. Приведены примеры.

Утверждение 3.11. Мощность циклов матроида равна либо N-А, если Щ = 3, либо N-3, если \2\ = 2, где N = \СЕС(СЕ(д))\-

Также представлен расчет выигрыша информационной скорости получившихся в диссертации СРС по сравнению с СРС реализованными по технологии М. Ито, А. Саито, Т. Нишизеки с той же структурой доступа. Так, в таблице 3.1 показан выигрыш информационной скорости гу почти пороговой бинарной СРС по сравнению с СРС реализованной по технологии М. Ито, А. Саито, Т. Нишизеки.

Таблица 3.1 - Выигрыш в информационной скорости идеальных совершенных почти пороговых бинарных СРС.

Вид СРС Байтовая СРС Двухбайтовая СРС Трехбайтовая СРС

Выигрыш в Ту, % 300% 700% 1500%

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1) предложена конструкция схем разделения секрета при помощи многочленов на эллиптических кривых, изучены их свойства и структуры доступа;

2) установлен критерий всюду плотности множества рациональных точек на вещественной эллиптической кривой. При этом всюду плотность интерпретируется как аналог совершенности СРС с бесконечным количеством участников, доказана гипотеза В.Н. Ушакова: множество рациональных точек на эллиптической кривой у2 — х3 — 4х + 4 всюду плотно;

3) предложена конструкция идеальных совершенных почти пороговых бинарных СРС и доказана теорема единственности: бинарные связные разделяющие почти пороговые СРС и их матроиды описываются исчерпывающим образом кодами Рида-Маллера первого порядка и выколотыми кодами Рида-Маллера первого порядка; предложена конструкция, дающая бесконечную серию линейных идеальных почти пороговых СРС над любым конечным полем с разделяющими почти пороговыми матроидами;

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ

Статьи, опубликованные в рекомендованных ВАК РФ изданиях:

1. Медведев Н.В., Титов С. С. Почти пороговые схемы разделения секрета на эллиптических кривых // Доклады Томского государствен-

кого университета систем управления и радиоэлектроники. Томск: Издательство Томского государственного университета систем управления и радиоэлектроники, № 1 (23), ч. 1, 2011. - С. 91-96.

2. Медведев Н.В., Титов С.С. О топологии эллиптических кривых. // Тр. Ин-та математики и механики УрО РАН. 2012. - Т. 18, № 1. -С. 242-250.

3. Медведев Н.В., Титов С.С. О конструкциях идеальных совершенных почти пороговых схем разделения секрета // Современные проблемы науки и образования. - 2012. - № 4; URL: http://www.science-education.ru/104-6622 (дата обращения: 09.07.2012).

4. Медведев Н.В., Титов С.С. Бинарные почти пороговые матроиды // Научно-технический вестник Поволжья. №4 2012г. — Казань: Научно-технический вестник Поволжья, 2012. - С. 136-142.

5. Медведев Н.В., Титов С.С. К вопросу об информационой безопасности при делегировании прав // Дискуссия: журнал научных публикаций. - Екатеринбург, 2012. - С. 111-114.

Статьи, опубликованные в других научных изданиях:

6. Медведев Н.В., Андреев P.A., Воробьев A.A. Реализация арифметики длинных чисел для исследования эллиптических кривых над полем рациональных чисел // Сборник научных трудов конференции "Молодежь - будущее атомной промышленности России". - Сне-жинск: СГФТА. - 2007.

7. Медведев Н.В. О разделении секрета на эллиптических кривых // Проблемы теоретической и прикладной математики: Труды 39-й Всероссийской молодежной конференции. - Екатеринбург: УрО РАН, 2008. - С. 378-382.

8. Медведев Н.В. О схеме разделения секрета Шамира. // Научные труды международной научно-практической конференции "СВЯЗЬ-ПРОМ 2008" в рамках 5го Евро-Азиатского форума "СВЯЗЬ-ПРОМ ЭКСПО-2008". - Екатеринбург: ЗАО "Компания Реал-Медиа", 2008. -С. 430-431.

9. Медведев Н.В., Баутин С.П., Титов С.С. Проблема разделения секрета на эллиптических кривых. Проблемы прикладной математики и механики: Сб. научн. тр. // Под общ. ред. C.JI. Дерябина, д.ф.-м.н. - Екатеринбург: УрГУПС. Вып. 65(148) / Зт. - 2008. -С. 160-174.

10. Медведев Н.В., Баутин С.П., Титов С. С. Проблема разделения секрета на эллиптических кривых // Безопасность информационно: го пространства: материалы VIII региональной научно-практической конференции студентов, аспирантов и молодых ученых. - Челябинск: Издательский центр ЮУрГУ, 2009. - С. 212-214.

11. Медведев Н.В., Алексеев Д.В., Ершова A.B., Колосов И. С. Технология работы с эллиптическими кривыми над полями 3, 7, 9 и 13 // Проблемы прикладной математики, механики и информатики: Сб. научн. тр. // Под общ. ред. C.JI. Дерябина, д.ф.-м.н. - Екатеринбург: УрГУПС, 2010. - С. 136-145.

12. Медведев Н.В., Титов С.С. Схема разделения секрета на эллиптических кривых // Проблемы прикладной математики, механики и информатики: Сб. научн. тр. // Под общ. ред. C.JI. Дерябина, д.ф.-м.н. - Екатеринбург: УрГУПС, 2010. - С. 186-189.

13. Медведев Н.В., Титов С. С. Моделирование процесса разделения секрета посредством эллиптических кривых // Математическое моделирование в естественных науках // Тезисы докладов XX Всероссийской школы-конференции молодых ученых и студентов. Издательство Пермского национального исследовательского политехнического университета, 2011. - С. 62-63.

14. Медведев Н.В., Титов С. С. О проблемах разделения секрета на эллиптических кривых // Транспорт 21 века: Исследования. Инновации. Инфраструктура, Выпуск 97(180), УрГУПС, Екатеринбург. -2011.

15. Медведев Н.В., Титов С.С. О бинарных почти пороговых матрои-дах // Интеллектуальные проблемы на транспорте: тезисы докладов II международной научно-практической конференции "Интел-

лектТранс-2012". - СПб.: Петербургский гос. ун-т путей сообщения, 2012. - 83 с.

16. Медведев Н.В., Титов С. С. О схеме разделения секрета на эллиптических кривых с бесконечным количеством участников // Некоторые актуальные проблемы современной математики и математического образования. Герценовские чтения - 2012. Материалы научной конференции, 16-21 апреля 2012 г. - СПб.: БАН, 2012. - С. 230-234.

17. Медведев Н.В., Титов С.С. О почти пороговых матроидах и схемах разделения секрета // Вестник УрФО. Безопасность в информационной сфере. № 1(3), 2012. - С. 31-36.

Работы автора, примыкающие к теме диссертации.

18. Медведев Н.В. Информационная безопасность в сетях Wi-Fi. // Безопасность информационного пространства: материалы VII региональной научно-практической конференции студентов, аспирантов и молодых ученых. - Екатеринбург: ГОУ ВПО УрГУПС, 2008. -С. 114-117.

19. Медведев Н.В., Титов С.С. Шифрование в технологии Bluetooth // Безопасность информационного пространства: материалы VIII региональной научно-практической конференции студентов, аспирантов и молодых ученых. - Челябинск: Издательский центр ЮУрГУ, 2009. - С. 235-237.

20. Медведев Н.В. Алгоритм шифрования SAFER и возможности его улучшения // Проблемы теоретической и прикладной математики: Тезисы 41-й Всероссийской молодежной конференции. - Екатеринбург: Институт математики и механики УрО РАН, 2010. - С. 482486.

Подписано к печати (S .09.2012 Печ. л. - 1.3

Печать - ризография Бумага для множит, апп. Формат 60x84 1/16

Тираж 100 экз._Заказ ДО Щ. ___

СР ПГУПС 190031, С.-Петербург, Московский пр., 9

117