Нир: «Разработка программного комплекса шифрования данных, на основе использования точек эллиптической кривой»

Утверждение 2.1 [41] , где - неприводимый многочлен над .

Доказательство

Так как поле характеристики , то , следовательно

Из утверждения 1 следует, что , а , то

Утверждение доказано.

Из утверждения 2.1 следует критерий выбора двучлена для построения последовательности.

Критерий 2.1 [41] Двучлен будет образующим элементом в , только если - образующий элемент в .

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

Ростовцев и Маховенко в своей работе [42] предложили на базе супервырожденных эллиптических кривых и генератора BBS последовательности построить генератор псевдослучайных чисел. Уравнение кривой , где и , или , где . Генератор вычисляет координаты точек и использует в качестве элементов псевдослучайных последовательностей один или несколько младших -координат. Числа и должны быть простыми, а элемент 2 – образующим элементом для обеих групп и . Таким образом, ключом для предсказания последующих бит является , а для предшествующих битов – .

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

Предложенный генератор обладает хорошими статистическими свойствами.

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

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

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

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

Рассмотрим трехуровневую иерархическую систему ключей. Основу этой иерархии составляет принцип разделения ключей в зависимости от их практического использования. В соответствие с этим принципом все ключи делятся на три группы [25, 43]:

1. Главные ключи или мастер-ключи (ГК).

2. Ключи шифрования ключей или ключи обмена между узлами сети (КК).

3. Ключи шифрования данных или рабочие (сеансовые) ключи (КД).

Главные ключи находятся на самом высоком уровне иерархии, их безопасность обеспечивается только надежным хранением на ключевых носителях. Обычно эти ключи используются для зашифровывания ключей, находящихся на следующем уровне иерархии, который образуют ключи шифрования ключей (КК).

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

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

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

Существуют две основных модели построения схем распределения ключей между пользователями компьютерной сети [44]:

1. Схемы типа «точка-точка».

2. Централизованные схемы.

Схемы типа «точка-точка» обеспечивают прямой обмен сеансовыми ключами между пользователями сети. Основной недостаток этих схем состоит в необходимости подтверждения подлинности субъектов сети.

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

Необходимо отметить, что в обеих моделях распределения ключевой информации предполагается обеспечение подлинности сеанса связи. Это можно осуществить, используя механизм запроса-ответа или механизм отметки времени [43].

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

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

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

Рассмотрим примеры ключевого транспорта и соглашений о ключах, построенные на основе симметричных и асимметричных алгоритмов шифрования и реализованные в рамках схем «точка-точка» и централизованных схем.

В качестве примера ключевого транспорта, основанного на симметричном шифровании и действующего в рамках модели «точка-точка», приведем схему распределения ключей Шамира, которая позволяет распределить сеансовые ключи без предварительного распределения пользователями некоторой ключевой информации [25]. Данный ключевой транспорт, реализуемый в виде криптографического протокола, обеспечивает защиту от пассивного нарушителя, но не обеспечивает аутентификацию передаваемых сообщений.

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

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

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

(2.7)

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

(2.8)

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

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

1. С использованием масок ключей и изменяющихся ключей;

2. На основе подтверждения подлинности ключей;

3. С использованием контрольных векторов.

Рассмотрим данные группы методов контроля за использованием ключевого материала.

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

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

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

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

На основании всего выше сказанного можно сделать следующие выводы.

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

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

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

1.Заранее заданные разрешенные множества участников (коалиции), образующие так называемую структуру доступа, могут однозначно восстановить секрет.

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

Второе условие является отличительной особенностью совершенных СРС.

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

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

Участника схемы , где , будем считать несущественным относительно , если для любого неразрешенного множества множество также является неразрешенным. Из сказанного выше следует, что элемент является существенным относительно структуры доступа , если существует множество такое, что , но . Иными словами, для существует содержащее его множество , где - совокупность минимальных (относительно включения) множеств из .

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

Теперь зададим множества и совместное распределение вероятностей на их декартовом произведении . Соответствующие случайные величины обозначим через . Множество - это множество всех возможных секретов. Значение секрета выбирается с вероятностью и с помощью СРС распределяется в виде «проекций» между всеми абонентами схемы с вероятностью . При этом СРС строится таким образом, что каждый -тый участник получает свою долю секрета , знает все множества , оба распределения вероятностей и , но не имеет никакой информации о проекциях секрета, полученных другими абонентами. Данные распределения вероятностей и могут быть эквивалентно заменены на одно

(3.1)

Исходя из всего выше сказанного, дадим вероятностное определение совершенной СРС [45]:

Определение 3.1 Параназывается совершенной вероятностной СРС, реализующей структуру доступа , если выполнены следующие условия:

1. для .

2. для .

Условие 1) отражает первое свойство СРС, а именно – участники из разрешенного множества вместе могут однозначно восстановить значение секрета. Условие 2) – это условие совершенности, которое заключается в том, что участники, образующие неразрешенное множество не могут получить дополнительную информацию о секрете , т.е. вероятность того, что значение секрета , не зависит от значений «проекций» при .

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

Переформулируем условия 1) и 2) определения 3.1 на языке энтропии:

(3.2)

где , если , и в противном случае.

Данное выше вероятностное определение совершенной СРС может быть переведено на комбинаторный язык.

Матрица вида

(3.3)

элементы которой , называется матрицей комбинаторной СРС, а её строки – «правилами» распределения секрета.

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

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

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

Определение 3.2 Матрица задает совершенную комбинаторную СРС, реализующую структуру доступа , если выполняются следующие условия:

1.Для любого множества нулевая координата любой строки матрицы однозначно определяется значениями её координат из множества .

2.Для любого множества и любых заданных значений координат из множества число строк матрицы с данным значением нулевой координаты не зависит от .

Очевидно, что эта модель является частным случаем вероятностной модели, когда все ненулевые значения одинаковы. А именно, код вероятностной СРС - это , «правила» распределения секрета выбираются из него независимо и равновероятно, а условия 1) и 2) определения 1.4 переформулированы на мощностном языке.

Сформулируем более общее определение совершенной комбинаторной СРС [45].

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

Определение 3.3 Будем говорить, что код задает совершенную комбинаторную СРС, если , или, эквивалентно, если

(3.4)

где определяется так же, как и в (3.2).

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

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

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

(3.5)

Из неравенства (3.5) и из определения идеальных СРС следует, что совершенная вероятностная схема называется идеальной, если для всех .

Для совершенной комбинаторной СРС справедливо неравенство для всех . А это означает, что совершенная комбинаторная СРС называется идеальной, если для всех выполняется равенство .

На сегодняшний день структуры доступа , для которых существуют реализующие их идеальные (вероятностные или комбинаторные) СРС, описываются с помощью теории матроидов.

Под матроидом будем понимать конечное множество и семейство подмножеств множества , называемых независимыми множествами, для которых выполняются следующие аксиомы [45]:

1.Пустое множество независимо, т.е. .

2.Каждое подмножество независимого множества независимо, т.е. если и , то .

3.Если и , то существует элемент такой, что .

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

1..	(3.6)
2..	(3.7)
3. Если,то.	(3.8)

Обратно, если некоторая функция обладает свойствами (2.4) – (2.6), то независимые множества, определяемые как , задают матроид, а функция является ранговой функцией.

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

1.Никакое собственное подмножество цикла не является циклом.

2.Если , то содержит цикл.

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

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

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

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

Отметим тот факт, что теорема, аналогичная теореме 3.1, была доказана и для вероятностно идеальных СРС.

Рассмотрим суть этого подхода.

Для того, чтобы доказать связь обобщенных (комбинаторных и вероятностных) идеальных СРС с матроидами, необходимо показать, что функции и , где , обладают свойствами (3.1) – (2.6), т.е. задают матроид. Все эти свойства, кроме свойства целочисленности функций, легко проверяются. Единообразное доказательство целочисленности функций и затрудняется тем, что они не обладают одинаковыми свойствами. Это выражено в том, что функция является субмодулярной, т.е. , а функция не всегда такова.

Введем в рассмотрение класс функций, удовлетворяющий более слабым аксиомам, но который включает в себя и функции типа , и функции типа .

Рассмотрим вещественную функцию , определенную на подмножествах множества и удовлетворяющую условиям:

1. .	(3.9)
2. , если .	(3.10)
3. .	(3.11)

Свойства (3.9) и (3.11) могут быть эквивалентно заменены на одно . Очевидно, что все эти свойства выполняются и для , и для .

Функцию , удовлетворяющую свойствами (3.9) – (3.11), назовем совершенной, если для любого множества справедливо равенство

где .

Будем говорить, что функция совершенно реализует структуру доступа , если

(3.12)

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

(3.13)

В силу свойств (3.12) и (3.13) для любой точки и любого множества справедливо соотношение .

Точка называется -неотделимой от множества , если , и точка называется сильно -отделимой от множества , если .

Так как всюду ниже функция фиксирована, то будем просто говорить об отделимости и неотделимости точки .

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

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

Лемма 3.1 Если точка сильно отделима от множества , но неотделима от множества , то и .

Так как мы предполагаем, что все точки существенные, то из леммы 1.3 вытекает

Следствие Для справедливы неравенства:

- для любой совершенной вероятностной СРС,

- для любой совершенной комбинаторной СРС.

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

В предположении идеальности функции лемму 3.1 можно обобщить:

Лемма 3.2. Если точка сильно отделима от множества , но точка неотделима от множества , то точка сильно отделима от множества и точка неотделима от множества .

Наложим еще некоторые дополнительные условия на функцию :

1. Если точка неотделима от множества и , то точка неотделима от множества .	(3.14)
2. Если точка сильно отделима от множества и , то точка сильно отделима от множества .	(3.15)

Функцию , определенную на множестве всех подмножеств множества , для которой выполнены свойства (3.8) - (3.15), назовем обобщенной идеальной СРС, реализующей структуру доступа .

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

Лемма 3.3 Если для любого точка сильно отделима от множества , то для любого .

Лемма 3.4 Если точка неотделима от множества и точка неотделима от множества , то точка неотделима от множества .

Лемма 3.5 Если точка сильно отделима от множества , но точка неотделима от множества , то существует точка , неотделимая от множества .

Если в лемме 3.5 положить , то получим

Следствие Если точка неотделима от множества , то существует точка , которая неотделима от множества .

На основании выше приведенных лемм можно доказать теорему [45]:

Теорема 3.2 Любая обобщенная идеальная СРС является целочисленной функцией.

Из теоремы 3.2 вытекает основной результат, доказывающий связь обобщенных идеальных СРС с матроидами:

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

На основании всего выше сказанного можно сделать следующие выводы.

Обобщенные идеальные СРС по существу не отличаются от матроидов, и условия (3.8) - (3.15) вместе с условием, что для любого найдется множество такое, что

,

дают еще одно определение связного матроида.

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

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

Уточнить, каким образом идеальные СРС «лежат» между общими и линейными матроидами, на сегодняшний день представляется чрезвычайно сложной задачей.

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

<< предыдущая страница следующая страница >>