Содержание к диссертации
Введение
Глава 1. Анализ проблем разграничения доступа с использованием схем разделения секрета 21
Глава 2. Разработка метода разграничения коллективного доступа на основе почти пороговой схемы разделения секрета на эллиптических кривых 37
2.1 Метод разграничения коллективного доступа с использованием схем разделения секрета на эллиптических кривых 41
2.2 Пример идеальной почти пороговой схемы разделения секрета на эллиптической кривой 49
2.3 Решение задачи В.Н. Ушакова о критерии всюду плотного расположения рациональных точек на эллиптических кривых 51
2.4 Интерпретация всюду плотности в почти пороговых схемах разделения секрета на эллиптических кривых 61
Глава 3. Построение почти пороговых схем разделения секрета и матроидов 66
3.1 Бесконечная серия почти пороговых схем разделения секрета и матроидов 68
3.2 Идеальные совершенные почти пороговые схемы разделения секрета над GF(2) 80
3.3 Идеальные совершенные почти пороговые схемы разделения секрета над GF(q) 92
3.4 Об идеальных совершенных почти пороговых схемах разделения секрета на эллиптических кривых 95
3.5 Информационная скорость в схемах разделения секрета 100
Глава 4. Методика разграничения доступа к информационным ресурсам и практические решения на основе почти пороговых схем разделения секрета 109
Заключение
- Метод разграничения коллективного доступа с использованием схем разделения секрета на эллиптических кривых
- Решение задачи В.Н. Ушакова о критерии всюду плотного расположения рациональных точек на эллиптических кривых
- Идеальные совершенные почти пороговые схемы разделения секрета над GF(2)
- Об идеальных совершенных почти пороговых схемах разделения секрета на эллиптических кривых
Введение к работе
Актуальность темы исследования.
Современный этап развития общества характеризуется возрастающей ролью информационной сферы, которая, являясь системообразующим фактором жизни общества, активно влияет на состояние безопасности различных направлений деятельности. Национальная безопасность Российской Федерации существенным образом зависит от обеспечения информационной безопасности, и в ходе технического прогресса эта зависимость будет возрастать. Поэтому вопросы, связанные с методами и задачами защиты информации, являются чрезвычайно важными. Такие вопросы приводят также и к сложным задачам разграничения коллективного доступа к информационным ресурсам при помощи схем разделения секрета. Часто схемы разделения секрета (СРС) относят также к механизмам защиты.
Основная идея разграничения коллективного доступа на основе СРС состоит в раздаче долей секрета участникам таким образом, чтобы заранее заданные коалиции участников (разрешенные коалиции) могли однозначно восстановить секрет (совокупность этих множеств называется структурой доступа), а неразрешенные - не получали никакой дополнительной информации, к имеющейся априорной, о возможном значении секрета, такие СРС называются совершенными. Особый интерес вызывают идеальные СРС, т.е. такие, где размер доли секрета, предоставляемый участнику, не больше размера секрета. Если разрешенными коалициями являются любые множества из п или более элементов, то такие СРС называются пороговыми "п из N" СРС, где N - количество всех участников.
В системах разграничения коллективного доступа основанных на СРС имеется ряд актуальных проблем: оценка степени неидеальности СРС, изучение однородных СРС, максимальное количество участников в линейных пороговых СРС. При этом общая проблема описания матроидов, соответствующих СРС, пока не решена. Поскольку эти проблемы признаны сложными, представляется естественным решать частные задачи, ведущие к решению общих проблем.
Актуальной задачей является, в том числе, реализация сложных структур разграничения коллективного доступа в идеальных схемах, т.к. известно, что существуют СРС, реализующие произвольную структуру доступа, но они могут не быть идеальными. Таковыми, например, могут быть однородные схемы. В связи с этим, особый интерес вызывают
однородные структуры разграничения коллективного доступа и близкие к ним, так называемые почти пороговые, которые допускают, тем не менее, идеальную реализацию. Это направление исследований связано с известной гипотезой Г.А. Кабатянского о том, что степень неидеальности может расти экспоненциально, как при неэффективной реализации пороговой СРС. Современные инструменты исследования этого вопроса -теория матроидов, геометрия эллиптических кривых. Представленная диссертация лежит в русле опровержения этой гипотезы. Использование рациональных точек на эллиптических кривых ранга больше нуля позволяет рассматривать системы разграничения коллективного доступа на основе почти пороговых СРС с бесконечным числом участников. При этом возникает задача всюду плотности множества рациональных точек на эллиптической кривой, которая интерпретируется в диссертации как аналог совершенности в таких СРС. Построение однородных совершенных идеальных схем приводит к задаче изучения почти пороговых матроидов.
Почти пороговость проявляется и в рубрикаторных идеалах по Н.А. Гайдамакину, основное свойство которых можно сформулировать как возможность принятия ответственного решения полным набором заместителей даже в случае отсутствия их начальника. Здесь затрагивается проблема незаменимости, связанная с отсутствием гибкости в структуре управления.
Вопросам изложения теории защиты информации, разграничения коллективного доступа, а также описания СРС и матроидов, посвящены труды и основополагающие работы ряда отечественных и зарубежных специалистов. Проблемы информационной безопасности описываются Ю. С. Хариным, А.А. Корниенко, Н.А. Молдовяном, А.А. Молдовяном, В.М. Зима, Д.П. Зегждой, В.И. Берником, Г.В. Матвеевым, СВ. Агиевичем, В.В. Яковлевым, В.И. Васильевым, М.А. Еремеевым, СЕ. Ададуровым, А.Ю. Щербаковым, О.О. Михальским, А.С. Першаковым, A.M. Ивашко, О.В. Казариным и другими. Вопросам разграничения доступа на основе СРС, а также соответствующим им матроидам, посвящены работы В.В. Ященко, Н.П. Варновского, Ю.В. Нестеренко, Г.А. Кабатянского, Н.А. Гайдамакина, П.Н. Девянина, Н.А. Шехуновой, Е.Т. Мирончикова, В.Г. Проскурина, А.В. Черемушкина, П.А. Гырдымова, А.Ю. Зубова, А.В. Зязина, В.Н. Овчинникова, Г.Р. Блейкли, А. Шамира, М.О. Аса-нова, В.А. Баранского, В.В. Расина, О.А. Логачёва, А.А. Сальникова, В. Липского, М. Ito, A. Saito, Т. Nishizeki, P.D. Seymour, D.J.A. Welsh. Математический аппарат, используемый в диссертации, подробно рас-
смотрен М.М. Глуховым, В.Д. Белоусовым, Н.Х. Ибрагимовым, A.M. Ильиным, В.А. Колывагиным, А.И. Маркушевичем, Л.С. Понтрягиным, А.Ф. Сидоровым, М. Холлом, И.В. Стеллецким, Т.С. Фофановой. Исследованию эллиптических функций и кривых, используемых при разграничении коллективного доступа в диссертации, посвящены труды А.А. Болотова, СБ. Гашкова, А.Б. Фролова, А.А. Часовских, В.В. Соловьева, В.А. Садовничего, В.В. Белокурова, И.И. Ахиезера, Э. Кнэппа, В.В. Острика, М.А. Цфасмана, Ю.П. Соловьева, Е.Т. Шавгулидзе, В.И. Ушакова, Н. Коблица, А.Г. Ростовцева и других.
Существующие методы разграничения коллективного доступа на основе СРС со сложной структурой доступа обладают следующими недостатками:
-
Отсутствует метод "автоматической" реализации произвольной структуры доступа для идеальных схем разделения секрета.
-
Метод разграничения коллективного доступа на основе схемы разделения секрета Ито-Саито-Нишизски обладает экспоненциально растущей степенью неидеальности при увеличении числа участников и разрешенных коалиций. Поэтому такие СРС имеют низкую информационную скорость и реализация их на практике весьма проблематична, а иногда даже нецелесообразна.
-
Предлагаемые западными специалистами однородные СРС со сложной структурой доступа являются конкретными примерами реализации схем с определенным числом участников и коалиций. Такие СРС являются не масштабируемыми.
Таким образом, выявлена проблемная ситуация, определяемая как противоречие между необходимостью обеспечения высокого уровня конфиденциальности, целостности, доступности информационных ресурсов при коллективном доступе и неразработанностью методов, алгоритмов и средств построения более сложных, чем пороговые, структур доступа в идеальных СРС. Разрешение данной проблемной ситуации требует создания метода разграничения коллективного доступа на основе почти пороговых схем разделения секрета. При этом создание такого метода должно быть направлено на повышение информационной скорости за счет использования идеальных схем. В представленной диссертации предлагаются целые классы идеальных почти пороговых СРС и матро-идов, а не конкретные примеры, следовательно, такие системы разграничения коллективного доступа являются масштабируемыми по количеству участников и мощности множества секретов.
Объектом исследования в диссертационной работе является система
разграничения коллективного доступа к информационным ресурсам на основе схем разделения секрета, а предметом исследования - метод создания идеальных схем разделения секрета со сложными структурами доступа при организации коллективного доступа.
Цель исследования - увеличение информационной скорости схем разделения секрета со сложными структурами доступа в реализации систем разграничения коллективного доступа к информационным ресурсам.
Для достижения поставленной цели решалась научная задача построения и описания класса схем разделения секрета с более сложными структурами доступа, чем у пороговых схем, но с сохранением таких важнейших свойств как совершенность и идеальность.
Достижение поставленной цели и научной задачи потребовало решения следующих частных задач исследований:
-
Проведение анализа современных методов разграничения доступа посредством схем разделения секрета.
-
Разработка метода разграничения коллективного доступа на основе почти пороговой схемы разделения секрета на эллиптических кривых.
-
Установление условия наличия аналога совершенности схем разделения секрета с бесконечным числом участников на эллиптических кривых, т.е. условия всюду плотности множества рациональных точек на эллиптической кривой.
-
Разработка совершенных идеальных почти пороговых СРС над любым конечным полем, а также выявление свойств соответствующих мат-роидов и их связь с помехоустойчивым кодированием.
-
Разработка практических рекомендаций по применению и программной реализации метода разграничения коллективного доступа на основе почти пороговых схем разделения секрета.
Методы выполнения исследований. Для решения задач диссертационного исследования в работе применялись методы теории защиты информации, теории кодирования, теории множеств, теории чисел, алгебраической геометрии, теории эллиптических кривых, теории матрои-дов. Частные задачи исследований решаются аналитическими и численными методами с использованием прикладных компьютерных программ.
Теоретическая основа и методологическая база исследования: труды отечественных и зарубежных ученых в области информационной безопасности, разграничения доступа, схем разделения секрета, матрои-дов и эллиптических кривых.
Основные результаты, выносимые на защиту:
-
Метод разграничения коллективного доступа к информационным ресурсам на основе почти пороговой схемы разделения секрета на эллиптических кривых.
-
Критерий всюду плотного расположения множества рациональных точек на эллиптической кривой E(Q) и доказательство гипотезы В.Н. Ушакова, интерпретация всюду плотности как аналога совершенности в идеальных почти пороговых СРС с бесконечным количеством участников.
-
Бесконечная серия линейных идеальных почти пороговых СРС над любым конечным полем, исчерпывающее описание бинарных идеальных совершенных почти пороговых СРС.
-
Схема идеальной совершенной почти пороговой СРС при помощи эллиптической кривой, в которой многочлен третьей степени используется для генерации проверочной матрицы над конечным полем кода линейной СРС.
5. Практическая реализация метода разграничения коллективного
доступа на основе почти пороговых схем разделения секрета.
Научная новизна. Все основные результаты работы являются новыми, а именно:
-
Разработан метод разграничения коллективного доступа, использующий идеальные почти пороговые СРС при помощи многочленов на эллиптических кривых.
-
Доказана "гипотеза А" В.Н. Ушакова, и получен критерий всюду плотного расположения множества рациональных точек на эллиптической кривой, проинтерпретирована всюду плотность множества точек на эллиптической кривой как аналог совершенности в идеальных почти пороговых СРС.
-
Описан класс линейных кодов как идеальных совершенных почти пороговых СРС и соответствующих почти пороговых матроидов.
-
Разработана линейная идеальная совершенная почти пороговая СРС на эллиптической кривой при помощи многочлена не выше третьей степени.
Достоверность полученных результатов диссертационной работы определяется правильным использованием понятийного аппарата теории защиты информации, корректным использованием выбранного математического аппарата, апробированием результатов диссертационных исследований на научных конференциях, семинарах и их внедрением.
Практическая значимость результатов исследования состоит в возможности увеличения информационной скорости разграничения коллек-
тивного доступа к информационным ресурсам за счет использования идеальных схем разделения секрета, а также в возможности разрабатывать более гибкие системы управления и делегирования прав.
Реализация результатов работы. Основные результаты диссертационных исследований внедрены в следующих организациях:
-
Екатеринбургский филиал ФГУП "ЗащитаИнфоТранс" (Министерство транспорта Российской Федерации) - утверждена и введена в действие "Методика разграничения доступа к документам с информацией ограниченного распространения".
-
ФГБОУ ВПО "Уральский государственный университет путей сообщения" - в лекционных курсах и лабораторных работах дисциплин "Дискретная математика", "Криптографическая защита информации", "Теория информационных процессов и систем", изучаемых студентами по направлениям 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] - в изданиях, входящих в перечень рекомендованных ВАК РФ.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав основного содержания с выводами по каждому разделу, заключения, восьми приложений, списка литературы, включающего 157 наименований. Материалы диссертации изложены на 164 страницах, включающих 10 рисунков с графиками и иллюстрациями, 19 таблиц и 8 программ.
Метод разграничения коллективного доступа с использованием схем разделения секрета на эллиптических кривых
Приведем пример проблемы отсутствия идеальности в схемах разграничения доступа с помощью метафоры ключей. Такая метафора может быть описана как доступ в комнату с секретом через несколько дверей, по числу разрешённых коалиций, в каждой из которых несколько замков (по числу участников в коалиции), так что у каждого участника целая связка таких ключей, каждый ключ - для своей двери. Идеальная же схема -когда у каждого участника один ключ от одного замка одной двери (на которой - замки для каждого участника). При этом эта дверь автоматически должна открываться, когда вставившие свои ключи участники образуют разрешённую коалицию. Небольшая степень неидеалыюсти вполне допустима, например, когда участники имеют два ключа или "полтора", т.е. ключ и вспомогательный "ключик". Однако для произвольной структуры доступа определить эту степень неидеалыюсти - все еще очень трудная задача!
Степень неидеалыюсти для схем Ито-Саито-Нишизеки растёт экспоненциально [129]. В отсутствии других способов и методов построения идеальных схем со сложными структурами доступа останется только смириться с этим и строить схемы типа Ито-Саито-Нишизеки.
В реальной же ситуации, например, для десяти участников коллективного доступа, если секрет - это PIN-код, четыре десятичных цифры. Для идеальной схемы каждый участник получает в качестве доли тоже 4 цифры, а по схеме Ито-Саито-Нишизеки - порядка 4 210 цифр, т.е. это уже тысячи цифр, а для ста участников - порядка 4 2100 цифр, что нереально. Поэтому задача разработки метода построения схем разделения секрета со сложной структурой доступа весьма актуальна.
Альтернативный подход, представленный в данной диссертации - описание идеальных схем и близких к ним, таким образом, чтобы для большинства из "произвольных" структур доступа автоматически строить удовлетворяющие конкретным реалиям идеальные схемы коллективного доступа. Реализации этого метода защиты информации и посвящена дис сертация. При этом классификация схем и особенно их исчерпывающее описание (как для бинарных СРС, т.е. битовых, "тумблерных" и т.п.) позволяет сразу указать на структуры доступа, не допускающие идеальной реализации, что весьма важно для применения в конкретных реалиях.
Как известно [97], проблема создания систем защиты информации включает две взаимодополняющие задачи: 1) разработка системы защиты информации; 2) оценка разработанной системы защиты информации. Вторая задача решается путем анализа се технических характеристик с целью установления, удовлетворяет ли система защиты, информации комплексу требований к данным системам.
Поскольку в названии представленной диссертации фигурирует слово "метод" стоит дать ему пояснение, в том числе с точки зрения теории защиты информации.
Метод (от греч. methodos - путь исследования, теория, учение) - способ достижения какой-либо цели, решения конкретной задачи; совокупность приемов или операций практического или теоретического освоения (познания) действительности.
С точки же зрения защиты информации методы и средства обеспечения безопасности информационных ресурсов включают в себя [97]: препятствие, управление доступом, маскировка, регламентация, принуждение, побуждение. Поскольку направление исследований в диссертации соответствует пункту 11 специальности 05.13.19, а именно- системы разграничения доступа, поэтому наиболее интересен для нас раздел управление доступом. Рассмотрим его более подробно согласно книге Ю.М. Черкасова [97].
Управление доступом - метод защиты информации регулированием использования всех ресурсов компьютерной информационной системы (элементов баз данных, программных и технических средств) [97].
Управление доступом включает следующие функции защиты: 1) идентификацию пользователей, персонала и ресурсов системы (присвоение каждому объекту персонального идентификатора); 2) опознание (установле ниє подлинности) объекта или субъекта по предъявленному им идентификатору; 3) проверку полномочий (проверка соответствия дня недели, времени суток, запрашиваемых ресурсов и процедур установленному регламенту); 4) разрешение и создание условий работы в пределах установленного регламента; 5) регистрацию (протоколирование) обращений к защищаемым ресурсам; 6) регистрацию (сигнализация, отключение, задержка работ, отказ в запросе) при попытках несанкционированных действий [97].
Далее представлен критический анализ проблемы отсутствия методов построения идеальных масштабируемых непороговых СРС, а также приведены примеры конкретных реализаций таких СРС.
Традиционная форма делегирования прав коллективу (заместителям, совету, коллегии выборщиков и т.п.) описывается так называемыми пороговыми схемами разделения секрета, которые можно описать голосованием по большинству, по квалифицированному большинству, наличием кворума для принятия ответственного решения и т.п. Современные реалии требуют описания более сложных ситуаций (например - отказ в полномочиях тем коалициям, которые, хотя и составляют количественное большинство, но могут принять неквалифицированное решение при голосовании, недопустимо ущемляющее, например, интересы меньшинства). Задача систем разграничения коллективного доступа на основе СРС - в предотвращении таких конфликтов. Плодотворной метафорой здесь является доступ к "красной кнопке" или восстановление кода цифрового замка по его частям. Особый интерес вызывают идеальные СРС, т.е. такие, где размер доли секрета, предоставляемый участнику, не больше размера секрета. Совершенными называются такие СРС, где заранее заданные коалиции участников могут однозначно восстановить секрет, а неразрешенные - не получают никакой дополнительной, к имеющейся априорной, информации о возможном значении секрета [104].
Решение задачи В.Н. Ушакова о критерии всюду плотного расположения рациональных точек на эллиптических кривых
Поскольку тема диссертации посвящена разработке метода разграничения коллективного доступа на основе СРС применим полученные в предыдущем параграфе крайне необходимые теоретические результаты для практической реализации. Важным вопросом является определения наличия совершенности в СРС на эллиптических кривых с бесконечным количеством участников. При этом доказанные выше утверждения и следствия о критерии всюду плотности выступают инструментом для решения этого непростого вопроса.
Так как в рассматриваемой системе разграничения коллективного доступа иа основе СРС иа эллиптических кривых может быть бесконечное число участников, то ошибки приближения и округления недопустимы. Поэтому для параметризации участников используются рациональные точки (т.е. точки имеющие рациональные координаты). Если бы точки на эллиптической кривой располагались не всюду плотно, то получались бы "пробелы" (интервалы, где нет рациональных точек) иа эллиптической кривой. При этом происходит нарушение условия совершенности, а именно, злоумышленник может получить информацию о том, что вблизи каких-то точек на эллиптической кривой нет точек, соответствующих участникам СРС. Например, если точки есть только иа правой ветви эллиптической кривой, то поиск точек для злоумышленника значительно уменьшается. Таким образом, решение вопроса всюду плотности расположения рациональных точек на эллиптической кривой является важным шагом в обосновании асимптотической совершенности в реализации таких СРС. В этом параграфе диссертации предлагается интерпретировать всюду плотность как аналог совершенности в СРС с бесконечным количеством участников. Исходя из этого, идеальная почти пороговая СРС с бесконечным количеством участников существует, где аналогом совершенности выступает всюду плотность.
Для реализации метода разграничения коллективного доступа на основе почти пороговой схемы разделения секрета "п, (п + 1) из оо" при помощи многочлена на эллиптических кривых необходимо иметь хотя бы одну точку на эллиптической кривой, которая образует бесконечную серию точек путем сложения ее самой с собой (т.е. ранг кривой больше нуля).
Приведем на конкретном примере основные этапы метода разграничения коллективного доступа на основе СРС "3, 4 из со". Поскольку для разделения секрета используется аппарат эллиптических кривых, то метод разграничения доступа будет аналогичен методу, приведенному в первом параграфе этой главы диссертации.
1. На первом этапе дилер исходя из существующих реалий и необходимости организации определенной структуры доступа выбирает конкретную эллиптическую кривую, ранг которой больше нуля - у2 = Xі — 25х. Следует отметить, что в такой СРС участников может быть бесконечно много.
2. Дилер параметризует участников СРС, т.е. каждому участнику ставится в соответствие своя точка на эллиптической кривой (логин).
Для этого дилер строит бесконечную серию точек, складывая некоторую рациональную точку, например Р = (0;5), саму с собой бесконечное количество раз по известным формулам [16,85]. В результате, получается следующая серия рациональных точек: Р = (0;5), 2Р — ( ; у), ЗР = /136. 13_\ лр _ /29225. 34367154 і і р _ / 302605985697619947492153859400 .
V 25 125/ V 4624 314432 / " 1LI V4716699019915224344579437255201 _ 49548596871149386888678983673087222548277540505\ 10243709318107253752182336461879315495690522801 / 3. Дилер выбирает известный только ему многочлен на эллиптической кривой степени три.
В общем виде он выглядит следующим образом: F(P) = а(х) + /3{х)у, где степень многочлена определяется по формуле degF=max{2dego;, 2deg(3 +3}=3, т.е. многочлен F(x, у) = (Вх + С) + Еу, где В, С и Е известны только дилеру. В этом конкретном случае пусть В = 34, С = 55 и Е = 89, т.е. многочлен на кривой имеет следующий вид: F(x, у) — (34гс+55)+89у. 29225.
4. Дилер назначает хранителя секрета, пусть это точка 4Р = {- t 3436715 314432") котоР&я известна всем.
5. Дилер рассчитывает значение секрета - подставляет координаты точки хранителя секрета в известный только ему многочлен F(х, у). Сек ПРТ ПЯКРН Р(29225- _3436П5\ _ 2210Q5C75 реї равен г \ 4(J24 , 314432 / 314432 6. Аналогично дилер получает доли секрета (пароли) для необходимого количества участников СРС, подставляя в многочлен F(x, у) = (34а; + 55) + 89у координаты точки, соответствующей участнику. Например, участник под номером один имеет точку Р = (0; 5) и его доля секрета s\ — F(x,y) = (34 0 + 55) + 89-5 = 500, участник под номером два имеет точку 2Р = ( ; у) и его доля секрета S2 = F(x, у) = (34 + 55) + 89 у = р, участник под номером три имеет точку ЗР = (-Щ; j ) и его доля секрета s3 = F(x, у) = (-34 Щ + 55) - 89 = —Ц и т.д. При этом бесконечно удаленная точка также является равноправным участником СРС. Участник, получивший в соответствие эту точку, имеет в качестве доли секрета старший коэффициент многочлена дилера F(x, у), в этом примере - Е — 89.
Второй этап - восстановление секрета. Для этого необходимо объеди нится трем участникам, чтобы восстановить секрет, т.е. решить систему из трех линейных уравнений с тремя неизвестными. Определитель такой системы уравнений должен быть не равен нулю. Например, секрет восстанавливают первый, второй и третий участники:
Идеальные совершенные почти пороговые схемы разделения секрета над GF(2)
Во второй главе были описаны СРС при помощи многочленов на эллиптических кривых. В них участники параметризуются точками на эллиптической кривой, а их долями секрета являются значение секретного многочлена в этой точке на кривой. Подход этого параграфа - использовать многочлен третьей степени на эллиптической кривой для генерации проверочной матрицы над GF{q) кода линейной идеальной совершенной СРС. Возьмем три конечные точки эллиптической кривой, находящиеся на одной прямой. Сумма этих точек будет равна нулю 0, т.е. бесконечно удаленной точке кривой [70]. Тогда по теореме о главных дивизорах [46] существует многочлен F третьей степени на эллиптической кривой с корнями в этих точках, т.е. F{Pi) — 0 (г = 1,2,3), при degP—3 имеем Р(Р) = (ах+Ь)-\-су, где с ф 0, при degP=2 имеем Р(Р) = ах+Ь, где а ф 0, а при degF=l многочлена не существует. При этом эти точки могут совпадать. Таким образом, получается три случая: 1) если Р\ ф Ръ Ф Рг Ф Р\, то Pi + Р2 + Р3 = 0; 2) если Pi=P2, то 2РХ + Р3 = 0 или, если Р2 = Р3, то Рг + 2Р2 = 0; 3) если Р1 = Р2 = Р3, то ЗРХ = 0.
Значение многочлена степени три в каждой конечной точке эллиптической кривой определяет строки проверочной матрицы Н. При этом ненулевые элементы строк проверочной матрицы Н определяют циклы С = М \ Z векторного матроида М над СР(д), а нулевые элементы -нуль-множества Z, где М - множество конечных точек кривой над GF(q). Нуль-множества Z задаются прямыми, пересекающимися с эллиптической кривой, при этом сумма точек пересечения прямой, соответствующей нуль-множеству Z, с кривой равна нулю: если Pi Р2 ф Р% Рі, то Zi = {РьР2,Рз}, и Pi + Р2 + Р3 = 0; если Рх = Р2, то Z2 = {Pi,P2}, и либо 2Pi + Р3 = 0, либо Pi + 2Р3 = 0; если Рх = Р2 = Р3, то Zz = {Pi}, и ЗРі = 0.
Проверим выполнение первой аксиомы матроида в терминах антицик лов. Поскольку циклы матроида определяются как дополнения нуль-множеств, то потребуем, чтобы в нуль-множествах матроида М не было одноэлементных нуль-множеств. Это означает, что на эллиптической кривой нет точек второго и третьего порядка. Тогда, поскольку нуль-множества определяются по двум или трем различным точкам эллиптической кривой, то эти точки задают единственную прямую на плоскости. Поэтому антицикла в антицикле, т.е. одной прямой внутри другой прямой, быть не может. Итак, при условии \Z\ 2, т.е. нуль-множества Z определяются прямыми по двум или трем различным конечным точкам на эллиптической кривой, первая аксиома матроида выполняется.
Проверим выполнение второй аксиомы матроида в терминах циклов. Пусть Q Є (Сі П С2), тогда F±(Q) ф 0 и F2(Q) ф 0. Существует ли такой цикл С, что С С (Ci U С2) \ Q? Если прямые, соответствующие нуль-множествам Zi и Z2, не имеют общих точек пересечения на кривой Zi П Z2 — 0, то объединение соответствующих циклов Ci U С2 есть вся кривая без бесконечно удаленной точки кривой, т.е. Ci U С2 = М. В этом тривиальном случае вторая аксиома матроида с очевидностью выполняется. Пусть Е - конечная точка на эллиптической кривой, тогда через нее и через любую другую точку кривой можно провести прямую, соответствующую нуль-множеству Z3. Следовательно, во множестве CiUC2 = М есть цикл Сз = М \ Z%. Если же разные нуль-множества Zi и Z2 пересекаются на кривой, т.е. ZiC\ Z2 ф 0, то только в одной точке, иначе они будут совпадать. Поэтому \Zi П Z2\ = 1. При этом объединение соответствующих им циклов Сі и С2 есть вся кривая кроме бесконечно удаленной точки 0 и точки пересечения Pi нуль-множеств. Итак, пусть R = {-Pi}, R = Zi П Z2 и Д = 1, тогда d U С2 = М \ R. Пусть точка Q $ (Zx U Z2), тогда Pi ф Q, и во множестве Ci U С2 \ {Q} — М \(R{J {Q}) должен содержаться цикл - проверим это. Из Q Є (Сі П С2) вытекает, что прямая PiQ определяет нуль-множество з, содержащее две различные точки Pi и Q, так что искомым циклом будет Сз = М \ Z- . Следовательно, вторая аксиома матроида выполняется. Итак, доказано
Утверждение 3.16. Если па эллиптической кривой пет точек второго и третьего порядка, то миооїсество ее конечных точек М с определенными выше через нуль-мпооїсества циклами является матроидом.
Поскольку нуль-множества матроида М определяются прямыми, которые могут иметь две или три различные точки пересечения с эллиптической кривой, то отсюда вытекает
Утверждение 3.17. Мощность циклов матроида М равна либо N — 4, если \Z\ = 3, либо N-Z, если \Z\ = 2, где N = \GEC{GF(q))\. Из утверждения 3.17 следует, что при помощи многочлена третьей степени на эллиптической кривой реализуется линейная идеальная совершенная почти пороговая СРС "fc — 3,; — 2 из fc", где k число участников СРС, к = \М\ - 1.
Таким образом, почти пороговым СРС соответствуют матроиды, которые было естественно назвать почти пороговыми, в том смысле, что его антициклы имеют близкие мощности (отличающиеся не более чем на единицу).
Рассмотрим пример реализации идеальной совершенной почти пороговой СРС при помощи эллиптических кривых падСР(З). Возьмем эллиптическую кривую Q,: у2 = х3 — Ах + 4 над полем GF{2 ). Всего эта кривая имеет G = EC(GF(3)) = 7 точек, включая бесконечно удаленную, которые образуют абелеву группу. При этом группа G изоморфна Z7, т.е. G = Z7, поэтому каждую точку кривой можно сопоставить с вычетом по модулю семь. Конечным точкам соответствуют ненулевые вычеты, так что М — {1,2,3,4,5,6}. В силу этого изоморфизма будем обозначать точки так: 1 = (2; 2), 2 = (0; 2), 3 = (1; 1), 4 = (1; 2), 5 = (0; 1), б = (2; 1) = -1. Тогда возможны три варианта: 1) Р\ + Р2 = 0, degF = 2; 2) 2Pi + Pi = О, degF = 3; 3) F1+F2+F3 = 0, degF = 3
Об идеальных совершенных почти пороговых схемах разделения секрета на эллиптических кривых
Рассмотрим переход от уравнения эллиптической кривой в канонической форме у2 — х3 + ах + Ь к уравнению кривой в инвариантах функции Вейерштрасса w2 = 4z3 — g2z — #з , z = р(и); w — р (и), где д2, 7з вещественные инварианты [8]. Произведем замену w = 2у, z = х. Получаем 4л/ = 4z3 - g2z - 5з, т. е. у2 = z3 - g2z/4 #3/4, где а = -д2/4, Ь = -#з/4. При этом из-за изменения масштаба при растяжении переменных между дискриминантами имеется связь 5 — д2 — 27д2 и А = — 16(4а3 + 2762). Так, П-кривая у2 = х3 — Ах + 4 в инвариантах функции Вейерштрасса имеет вид: w2 = 4z3 —16z+16, т. е. д2 — 16, д% = —16. Для данной эллиптической кривой дискриминант А = -1б(-4 64 + 27 16) = -2816 = -28 11 [91].
Если инварианты д2, д вещественны, то либо все три корня Єї, є2, е3 многочлена 4z3 — g2z — д% вещественны, либо один корень вещественный (за него примем е2), а остальные два — комплексные сопряженные [8].
В первом случае если дискриминант 5 положителен, 5 = д\ — 27 ?3 О, пронумеруем вещественные корни так, чтобы е\ е2 е3. Все корни предполагаются различными; это исключает обращение дискриминанта в нуль. Во втором случае, если дискриминант 5 отрицателен, е\ и ез комплексно сопряжены. Так, для П-кривой е2 — —2.38297576..., е\ « 1.191487 + 0.508851г, е3 « 1.191487 - 0.508851г. Эти факты - следствие формулы
Функция р{и) с вещественными инвариантами (при любом знаке дискриминанта) имеет на вещественной оси только вещественные значения. Действительно, в случае вещественных инвариантов все коэффициенты разложения функции р в ряд P(U) = + 20U +28" +" 131 вещественны. Отсюда следует, что и р (и) вещественна при и Є №.. Вещественны и значения, принимаемые функцией р(и) на мнимой оси, при этом для вычисления полезно соотношение р{гщ 92,9г) = р{щ 92, -дз)- (3-1) Выведем выражения для периодов 2wi, 2ш$ функции р(и) через инварианты. 1. В случае 5 0 рассмотрим для вещественных значений формулу Ц= / —гГ= z = p{u), (3.2) J /4х6-g2x-gz z где под корнем при х ei подразумевается его арифметическое значение. Отсюда вытекает, что при уменьшении р от +оо до е\ величина и растет монотонно от 0 до си\. Следовательно, + 0О « = / dX (3.3) J л/4х6 - д2х - д3 Єї Возьмем функцию р(щ д2, —дз) и обозначим ее периоды через 2u7i, 2uz-Корнями многочлена 4ж3 — д2х + д3, расположенными в порядке убывания, будут е\ = — ез,&2 = — Є2,ез = —Єї. При этом соотношение (3.1) показывает, что о/1 = —, о/3 = —г- (3.4) г г По аналогии с формулой (3.3) можем написать +00 +0О _ Г dx Г dx ui = / , , шз = г І , I y/4xz - g2x + g3 J y/4x3 - g2x + дъ Єї -e3 Таким образом, периоды 2ш\, 2и% выражены через инварианты д2, ?з в виде интегралов, причем 2u/i — число вещественное, а 2с з — число чисто мнимое. Это значит, что в рассмотренном случае положительного S параллелограммом периодов является прямоугольник. 132 2. В случае 5 0 с помощью аналогичных соображений из (3.2) полу +оо dx чим Ш2 J л/4аг (3.5) 92Х - дз Є2 Снова возьмем функцию р(и;д2: —дз)- В прежних обозначениях получим, аналогично, + 00 ш2 = (3.6) dx J л/4 -Є2 у/Іх3 - д2х + дз Примем теперь во внимание равенства (3.4), а также, чтоа;2 = — ш\ з, ш2 — —bJ\ — со . Мы найдем CJI + о;з = — 2, wi — w3 = 2- Таким образом, складывая и вычитая величины (3.5), (3.6), получим периоды 2OJI, 2шз-Мы видим, что в случае 6 0 периоды 2а;ь 2о;з — числа сопряженные, откуда следует, что параллелограммом периодов является ромб.
Нам нужны те значения переменной w, для которых и р(и), и р (и) вещественны. В данном случае по модулю ромба периодов это будут только числа и на вещественной оси, полупериод ш2 = —(ші + соз) вещественный, группа изоморфна одномерному тору Т = K(mod 2и2) (см. рис. 7).
