Московский государственный университет имени М.В. Ломоносова

Факультет вычислительной математики и кибернетики

Магистерская программа «Математическое и программное обеспечение

защиты информации»

Магистерская диссертация

«СРАВНИТЕЛЬНЫЙ АНАЛИЗ СТОЙКОСТИ

НЕКОТОРЫХ КЛАССОВ СХЕМ

РАЗДЕЛЕНИЯ СЕКРЕТА»

Работу выполнил студент Пьянов С.М.

Научный руководитель:

к. ф.-м. н., доцент Применко Э.А.

Москва 2013

ОГЛАВЛЕНИЕ

1. АННОТАЦИЯ

2. ВВЕДЕНИЕ

3. ПОСТАНОВКА ЗАДАЧИ

3.1. Описание ПАК

3.2. Определение задачи

3.3. Параметры

3.3.1. Секрет

3.3.2. K и N

4. ОБЗОР СУЩЕСТВУЮЩИХ РЕШЕНИЙ

РАССМАТРИВАЕМОЙ ЗАДАЧИ И ЕЕ МОДИФИКАЦИЙ............. 4.1. Введение в обзор

4.2. Пороговые схемы разделения секрета

4.2.1. Схема Шамира

4.2.2. Схема, основанная на эллиптической кривой

4.2.3. Схема Блэкли

4.2.4. Схема Карнин-Грин-Хеллмана

4.2.5. Схема Асмута-Блума

4.2.6. Усложнение схемы Шамира (произвольный выбор точек)... 4.2.7. Схема последовательного восстановления секрета.............. 5. ИССЛЕДОВАНИЕ И ПОСТРОЕНИЕ РЕШЕНИЯ ЗАДАЧИ..... 5.1. Теоретическое исследование рассмотренных пороговых СРС... 5.1.1. Схема Шамира

5.1.2. Схема, основанная на эллиптической кривой

5.1.3. Схема Блэкли

5.1.4. Схема Карнин-Грин-Хеллмана

5.1.5. Схема Асмута-Блума

5.1.6. Выводы по теоретическому исследованию рассмотренных пороговых СРС

5.2. Теоретическое построение решения задачи

5.2.1. Выбор математической библиотеки для реализации пороговых СРС

5.2.2. Задача реализации сравниваемых пороговых СРС................. 5.2.3. Задача реализации унифицированной инфраструктуры тестирования пороговых СРС

5.2.4. Задача практического сравнения реализованных пороговых СРС 6. ОПИСАНИЕ ПРАКТИЧЕСКОЙ ЧАСТИ

6.1. Выбор математической библиотеки

6.2. Описание реализации сравниваемых пороговых СРС................. 6.2.1. Описание обобщенных компонентов

6.2.2. Схема Шамира

6.2.3. Схема, основанная на эллиптической кривой

6.2.4. Схема Асмута-Блума

6.3. Описание реализации унифицированной инфраструктуры тестирования

6.4. Сравнение реализованных пороговых СРС

7. ЗАКЛЮЧЕНИЕ

8. СПИСОК ЦИТИРУЕМОЙ ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 1. ИСХОДНЫЙ КОД СХЕМЫ ШАМИРА.............

ПРИЛОЖЕНИЕ 2. ИСХОДНЫЙ КОД ЭЛЛИПТИЧЕСКОЙ

СХЕМЫ

ПРИЛОЖЕНИЕ 3. ИСХОДНЫЙ КОД СХЕМЫ АСМУТА-БЛУМА

ПРИЛОДЕНИЕ 4. ИСХОДНЫЙ КОД ИНФРАСТРУКТУРЫ

ТЕСТИРОВАНИЯ

1. АННОТАЦИЯ В представленной магистерской диссертации рассмотрены различные классы пороговых схем разделения секрета (СРС), такие, как схема Шамира, схема Блэкли, схема Карнин-Грин-Хеллмана, схема Асмута-Блума, схема, основанная на эллиптических кривых. На основе представленных алгоритмов порогового разделения секрета произведен анализ сложности, рассмотрены теоретические проблемы реализации.

На основе теоретических изысканий построена программная модель тестирования реализаций пороговых СРС. Реализованы некоторые пороговые СРС и произведены испытания на различных тестовых значениях параметров.

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

В настоящее время актуальным является вопрос защиты секретных ключей различных программно-аппаратных комплексов (ПАК) с распределенной структурой доступа, таких как удостоверяющие центры (УЦ) и аппаратные модули защиты конфиденциальной информации (HSM – Hardware Secure Module). Известны различные методы повышения секретности ключей, среди которых можно выделить метод, основанный на применении схем разделения секрета (СРС). По таким схемам секретный ключ (разделяемый секрет) путем математических преобразований «разделяется» на частей (долей) секрета и выдается участникам структуры доступа ПАК. Далее, для восстановления исходного секретного ключа необходимо «собрать вместе» долей секрета. Такие схемы называются – пороговыми схемами разделения секрета.

Впервые, задачи криптографического разделения секрета для случая пороговой структуры доступа были независимо сформулированы и решены Шамиром (A. Shamir) [1] и Блэкли (G.R. Blakley) [2]. За три десятилетия существования, задача разделения секрета превратилась в активно развивающуюся область современной криптографии. Наиболее полные обзоры математики разделения секрета можно найти в учебниках [3] [4] [5].

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

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

Изучение некоторых классов пороговых схем разделения секрета;

Проведение теоретического анализа сложности алгоритмов и проблем Разработка программной модели тестирования реализаций схем Реализация отдельных схем разделения секрета;

Испытания реализованных схем на различных значениях параметров;

3. ПОСТАНОВКА ЗАДАЧИ

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

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

Работа с ключами Обычно HSM реализует некоторое подмножество следующих механизмов управления ключами:

генерация ключевого материала (случайных чисел);

генерация секретных ключей и асимметричных ключевых пар;

модификация/диверсификация секретных (симметричных) ключей;

распределение/импорт/экспорт ключей;

хранение ключей;

обнуление (удаление) ключей.

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

Источники ключей:

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

внешний – импорт ключевого материала, созданного вне HSM;

удаленная выработка общего ключа – ключ вырабатывает в процессе выполнения некоторого криптографического протокола, например ДиффиХеллмана, одним из участников которого является HSM.

При импорте/ экспорте готовых ключей реализуются следующие варианты:

ручной ввод ключей (например, с клавиатуры);

автоматизированный ввод/вывод с ключевого носителя (например, при помощи смарт-карты).

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

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

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

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

симметричные криптографические примитивы (шифрование):

канальное шифрование (шифрование данных на канальном и сетевом уровнях шифрование данных по запросу пользователя/процесса (шифрование на прикладном уровне);

асимметричные криптографические примитивы;

формирование и проверка цифровой подписи / хеширование;

аутентификация пользователей на базе протоколов с использованием цифровой подписи;

протоколы выработки общих ключей;

аутентификация;

выработка одноразовых паролей;

выработка и проверка PIN-кодов и иных контрольных данных;

выработка имитозащитных вставок (кодов аутентификации сообщений);

высокоуровневые протоколы;

установление защищенных сеансов связи (протоколы прикладного уровня);

платежные банковские транзакции;

поддержка машиносчитываемых проездных документов;

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

удостоверяющих центров и центров регистрации (CA и RA);

серверов онлайн проверки статусов сертификатов (OCSP-серверы);

серверов меток времени (TSP-серверы).

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

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

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

Практическое же использование функционала во всех остальных выделенных классах HSM возможно при наличии даже одного модуля.

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

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

интегрированные модули для банкоматов и терминалов в точках обслуживания (например, кассы магазинов):

o шифрование PIN-кодов, вводимых при использовании карт;

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

o создание и использование набора ключей при выпуске смарт-карт o генерация, печать и рассылка PIN-кодов, для генерации и проверки PIN-кодов, PVV (PIN Verification Value) и CVV (Code Verification Value), а также проведения операций со смарт-картами.

SSL-шлюзы При построении безопасных web-сервисов, работа с которыми производится посредством протокола HTTPS (HTTP внутри SSL/TLS-туннеля), востребованными являются SSL-шлюзы или SSL-ускорители, обеспечивающие установление большого числа SSL-соединений в единицу времени. Наибольшее значение для SSLшлюзов имеет производительность, которая составляет 1000 и более вновь открываемых соединений в секунду.

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

3.3. Параметры Исходя из общего описания HSM и следуя выводам дополнительных исследований, проведенных в [6], сформулированы основные требования к параметрам пороговой схемы разделения секрета.

3.3.1. Секрет Секретом (технологическим ключом защиты) в ПАК «ViPNet HSM» является 256-битный симметричный ключ. Дополнительно, схема разделения секрета должна предусматривать возможность разделения 512-битных ключей (| | бит).

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

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

4. ОБЗОР СУЩЕСТВУЮЩИХ РЕШЕНИЙ

РАССМАТРИВАЕМОЙ ЗАДАЧИ И ЕЕ

МОДИФИКАЦИЙ

4.1. Введение в обзор Методы пространственного разделения секретной информации образуют одну из основ систем активной безопасности распределённых компьютерных систем. Среди таких методов широко применяются криптографические схемы разделения секрета. Необходимо пояснить, что данные схемы позволяют разделить секрет между некоторым количеством участников обмена информацией, соблюдая следующие условия [3]:

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

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

Пусть в информационном взаимодействии участвуют абонентов.

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

Участники схемы, где, будем считать несущественные относительно, если для любого неразрешенного множества множество также является неразрешенным. Следовательно, элемент существенен относительно структуры Соответствующие случайные величины обозначаются следующим образом - это множество всех возможных секретов. Значение секрета выбирается с вероятностью и с помощью схемы разделения секрета распределяется в виде между всеми абонентами схемы с вероятностью. При этом схема строится следующим образом. Каждый информации о проекциях секрета, которые получили другие участники схемы. Так Рассмотрим схему разделения секрета с точки зрения теории вероятностей [3, 7].

Определение 1. Пара называется совершенной вероятностной схемой разделения секрета, реализующей структуру доступа, если выполнены следующие условия:

Далее введем понятие энтропии дискретной случайной величины. Под энтропией будем понимать меру степени неопределенности дискретной случайной определяется формулой Модифицируем условия 1 и 2 из определения 1 с учетом понятия энтропии:

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

Существует матрица Элементы данной матрицы составляют комбинаторную схему разделения секрета, а строки формируют «правила» распределения секрета. Матрицу будем называть кодом комбинаторной схемы разделения секрета, а ее строки – словами.

При выборе правила распределения секрета для заданного значения необходимо. В комбинаторной модели необходимо:

слова из однозначно определялась значениями его координат из множества ;

из множества, количество кодовых слов матрицы с данным значением нулевой координаты не зависит от.

Исходя из вышесказанного, можно дать определение совершенной комбинаторной схемы разделения секрета:

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

матрицы однозначно определяется значениями ее координат из множества.

из множества число строк матрицы с данным значением нулевой координаты не зависит от.

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

Далее сформулируем более общее определение совершенной комбинаторной схемы разделения секрета [7].

За обозначение кода, полученного из удалением координат (номера Пусть обозначает число различных слов в коде. Для произвольной комбинаторной схемы, задаваемой кодом, определим на множествах Определение 3. Будем говорить, что код задает совершенную эквивалентно, если Для любых совершенной вероятностной схемы разделения секрета для всех справедливо неравенство [8, 9] Основной характеристикой таких систем заключается в том, что объем секрета не меньше объема информации, предоставляемой участнику.

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

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

Далее рассмотрим некоторые классы пороговых СРС.

4.2.1. Схема Шамира Идея, на которой основана данная схема, заключается в том, что для интерполяции многочлена степени — требуется точек. Если известно меньшее количество точек, то интерполяция будет невозможной.

– большое простое число. должно быть больше любого секрета, который – число долей секрета.

– минимальный размер разрешенной группы.

Подготовительная фаза образом и составляет секретный полином Генерация долей секрета Каждому участнику посылается его доля секрета. Долей секрета участника является пара чисел. При этом коэффициенты полинома «забываются».

Восстановление секрета Каждая такая доля является точкой многочлена, который имеет степень Поэтому, обладая точками этого многочлена, участники могут восстановить коэффициенты многочлена, либо решив систему линейных сравнений относительно интерполяционным многочленом Лагранжа [1]:

4.2.2. Схема, основанная на эллиптической кривой Подготовительная фаза Пусть - эллиптическая кривая, определённая в конечном поле.

Свойства точек эллиптической кривой определяются как свойства аддитивных абелевых групп. Соответственно для них определяются операции сложения:

Для точек эллиптической кривой значимой также является операция умножения точки на число:

Приведенное представление операций на эллиптической кривой позволяет провести аналогию с математическим аппаратом нейронных сетей конечного кольца и его адаптацией для систем разделения секрета. Выражение (4) описывает суммирование на нейроне, выражение (5) - весовую операцию.

Очевидно, что применяя (4) и (5), а также аппарат нейронных сетей, можно сформировать полином следующего вида [10]:

секрет. Выражение (6) описывает некий условный полином, состоящий из координат точек, операции над которыми выполняются по правилам сложения точек на эллиптической кривой.

Пусть, тогда можем сформировать матрицу весовых коэффициентов нейронной сети Генерация долей секрета Частные секреты получаем, подставляя в выражение различные. Пусть номер абонента, которому отсылается секрет. Тогда частные секреты абонентов равны Выражение (7) примет вид На рис. 1 представлена нейронная сеть конечного кольца генератора частных Рис. 1. Эллиптический генератор частных секретов.

Восстановление секрета Рассмотрим пороговую схему. Частные секреты абонентов в общем случае получаются в соответствии с выражением (приведено из [10] с сохранением символов определения) где - общее количество секретов на первом шаге, - номер секрета.

Для структуры доступа выражение (8) преобразуется к виду Найдём общее выражение. Пусть на первом шаге При этом, в силу приведенной операции, слагаемое при равно нулю.

Путём аналогичных преобразований окончательно можно получить Значения и и есть восстановленный секрет [10].

На рис. 2 представлена модель сети генератора общего секрета по известным частным.

Рис. 2. Модель сети генератора общего секрета 4.2.3. Схема Блэкли Как известно, система линейно независимых сравнений от неизвестных по простому модулю имеет ровно одно решение.

На этом основана пороговая схема Блэкли, созданная в 1979 году. Секрет разделяется между абонентами так, что любая группа, состоящая не менее, чем из абонентов, является разрешенной [2].

Параметрами схемы являются:

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

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

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

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

Замечание Если свои доли секретов объединят абонентов (то есть неразрешенная группа), то система сравнений, составленная ими, даст в качестве решения не точку, а множество точек, лежащих на гиперплоскости размерности, и определить наверняка, какая из них содержит секрет, невозможно. В этом случае секретом может оказаться любое значение из с равной вероятностью.

4.2.4. Схема Карнин-Грин-Хеллмана Подготовительная фаза матрицы размером, образованной из этих векторов, равен. Вектор – это вектор, образующий секрет [9].

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

4.2.5. Схема Асмута-Блума Подготовительная фаза Выбирается, такое что:

Генерация долей секрета Восстановление секрета Собрав вместе долей секрета, составляется и, используя китайскую теорему об остатках, решается система сравнений относительно неизвестного :

Решив систему, участники получают общий секрет.

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

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

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

В случае с большими порядками самого секрета появляется сложность вычислений.

4.2.7. Схема последовательного восстановления секрета Подготовительная фаза Подготовительная фаза наследуется из схемы Шамира Генерация долей секрета Генерация долей секрета производится согласно изначальному алгоритму схемы Шамира.

Восстановление секрета [12] 2. Составляем из все наборы частей секрета длины без повторений ( ) секрета, Восстановленные секреты в каждой подгруппе идентичны 5. Выбираем максимальное значение среди 6. Задаем 8. Поочередно берем из, восстанавливаем (с учетом позиции)

5. ИССЛЕДОВАНИЕ И ПОСТРОЕНИЕ РЕШЕНИЯ

ЗАДАЧИ

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

Для оценки ресурсоемкости примем следующие допущения:

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

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

5.1.1. Схема Шамира Анализ сложности математического алгоритма Анализ ресурсоемкости вычислений Этап разделения секрета на доли o При просчете значения каждого монома в полиноме мы получим o Из вышеперечисленных вычислений следует, что все отдельные операции по вычислению значений мономов полинома требуют o Значение вычисляемой доли принимает максимальную длину только при финальном сложении значения мономов с секретом.

o Вывод: для разделения секрета на доли необходимо Этап восстановления секрета o При подсчете значений интерполяционного многочлена Лагранжа будем просчитывать отдельно операции над делимым и над o Вывод: для восстановления секрета необходимо больше 112 кбайт 5.1.2. Схема, основанная на эллиптической кривой Анализ сложности математического алгоритма Этап разделения секрета на доли:

Этап восстановления секрета:

Анализ ресурсоемкости вычислений Этап разделения секрета на доли o Так как объем оперативной памяти точки на эллиптической кривой не превышает объем, необходимый для хранения самого секрета, то схема наследует ресурсоемкость исходной схемы Этап восстановления секрета o Для восстановления секрета необходимо 5.1.3. Схема Блэкли Анализ сложности математического алгоритма Этап разделения секрета на доли:

Анализ ресурсоемкости вычислений Этап разделения секрета на доли максимальной длины равной | |, откуда мы получаем объем o Откуда получаем, что всякая точка (уравнение гиперплоскости) o Вывод: для разделения секрета на доли необходимо Этап восстановления секрета o Для восстановления секрета необходимо решить систему линейных алгебраических уравнений. Единственным допущением является то, что найти необходимо всего 1 неизвестное, а именно первое, которое и является секретом. Наилучший вариант для целочисленной арифметики является метод Крамера. Для вычисления значения 1 неизвестной необходимо просчитать в поле, откуда размером промежуточных значений можно пренебречь (не превышают длину удвоенного модуля);

o Вывод: для восстановления секрета необходимо 5.1.4. Схема Карнин-Грин-Хеллмана Анализ сложности математического алгоритма Анализ ресурсоемкости вычислений Этап разделения секрета на доли o Так как секрет представляется в виде матричного произведения 2-х векторов, то объем оперативной памяти для хранения координат o Вывод: для разделения секрета на доли необходимо Этап восстановления секрета o Для восстановления секрета необходимо решить систему линейных алгебраических уравнений. Наилучший вариант для целочисленной арифметики является метод Крамера. Для вычисления значения необходимо просчитать производить в поле, откуда размером промежуточных значений можно пренебречь (не превышают длину удвоенного модуля);

o Вывод: для восстановления секрета необходимо 5.1.5. Схема Асмута-Блума Анализ сложности математического алгоритма Анализ ресурсоемкости вычислений Этап разделения секрета на доли больший размерности модуля, но меньший удвоенного модуля o Объем оперативной памяти для хранения 1 доли секрета o Вывод: для разделения секрета на доли необходимо Этап восстановления секрета o Для восстановления секрета необходимо 24576 байт для хранения 5.1.6. Выводы по теоретическому исследованию рассмотренных пороговых СРС Согласно проведенным исследованиям мною были выбраны три пороговые схемы разделения секрета для дальнейшего рассмотрения, а именно: схема Шамира, схема Асмута-Блюма, схема, основанная на эллиптических кривых.

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

Выбрать математическую библиотеку;

Реализовать выбранные для практического сравнения пороговые СРС;

Разработать унифицированную структуру тестирования пороговых СРС;

Провести практические испытания и составить отчет о тестировании разработанных алгоритмов разделения секрета;

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

Работа с расширяемыми числами – необходимо иметь возможность настраивать максимальный размер чисел, использующихся в математических Работа с простыми числами – желательно иметь возможность средствами математической библиотеки проверять на простоту заданные числа (в частности для схемы Асмута-Блума и для вычисления общего модуля);

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

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

Последним, но не менее важным качеством, которым должна обладать математическая библиотека должна быть скорость выполнения математических операций.

5.2.2. Задача реализации сравниваемых пороговых СРС Для практического тестирования, необходимо реализовать 3 выбранных пороговых СРС (схема Шамира, схема Асмута-Блума, схема, основанная на эллиптических кривых) в виде независимых исходных кодов. Реализация каждой такой схемы должна отвечать следующим требованиям:

Программная независимость – каждая реализация отдельной пороговой схемы не должна зависеть от реализаций остальных схем;

Общий программный интерфейс – каждая отельная реализация пороговой схемы должна иметь одинаковый программный интерфейс для унификации и удобства использования при тестировании, и, как следствие, общие классыродители;

Общая логика работы с параметрами – каждая отдельная реализация пороговой схемы должна предсказуемо работать со входными параметрами и возвращать результат в заданных типах:

o На вход операции разделения секрета необходимо принимать o На выходе операции разделения секрета необходимо получать доли секрета в виде потока байт с дополнительными параметрами o На вход операции восстановления секрета необходимо принимать массив долей в виде потока байт с дополнительными параметрами o На выходе операции восстановления секрета необходимо получать 5.2.3. Задача реализации унифицированной инфраструктуры тестирования пороговых СРС Проведение тестирования реализаций пороговых СРС требует разработки инфраструктуры тестирования и набора тестов. Для проведения тестирования предлагается следующий набор тестов:

Тесты граничных условий:

Тесты полного набора:

o Для произвольных значений ключей проверить условие Тесты на проверку порога схем:

o Для произвольных значений ключей заданной длины (256 и Провести проверку на некоторых произвольных группах доступа.

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

5.2.4. Задача практического сравнения реализованных пороговых СРС В результате проведения тестирования реализованных пороговых схем получить сравнительную таблицу и выбрать наиболее практичный, быстрый и наименее ресурсоемкий алгоритм для дальнейшей доработки и внедрения в ПАК «ViPNet HSM».

6. ОПИСАНИЕ ПРАКТИЧЕСКОЙ ЧАСТИ

6.1. Выбор математической библиотеки Для реализации рассмотренных схем разделения секрета в качестве математической библиотеки была выбрана библиотека MIRACL.

Основные достоинства математической библиотеки MIRACL:

Открытый исходный код – позволяет проверить работу конечных математических функций;

Простота программного интерфейса – доступ ко всем объектам библиотеки (структуры и функции) происходит унифицировано, не требует доработок надстроек использования;

Обширный математический аппарат – наличие в библиотеке функций математики больших чисел, математики эллиптических кривых, работы с простыми числами, арифметики в поле, некоторых дополнительных математических примитивов (таких как наибольший общий делитель и китайская теорема об остатках);

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

6.2. Описание реализации сравниваемых пороговых СРС 6.2.1. Описание обобщенных компонентов Для реализации трех выбранных пороговых схем разделения секрета мною были описаны дополнительные общие типы и класс-родитель.

Описание общих типов В рамках программной реализации схем, мною были описаны и использованы следующие программные типы:

typedef unsigned char byte;

typedef unsigned short uint16;

typedef unsigned int uint32;

typedef unsigned long long uint64;

Тип byte описывает символы в беззнаковом определении (код символа от до 255 по таблице ASCII).

Типы uint* описывают беззнаковые целочисленные типы различной длины.

Для удобства представления доли разделенного секрета были реализованы следующие программные классы:

class tShadow_shamir ~tShadow_shamir() memset(&shadow[0], 0, shadow.size());

Класс tShadow_shamir описывает структуру долей разделенного секрета по пороговой схеме разделенного секрета Шамира, а так же используется для долей разделенного секрета для схемы, основанной на эллиптической кривой.

Целочисленная переменная point хранит значение точки для просчета значения полинома.

Массив байт shadow хранит значение полинома (доли секрета) в байтном представлении.

class tShadow_primes memset(&shadow[0], 0, shadow.size());

Класс tShadow_primes описывает структуру долей разделенного секрета для схемы Асмута-Блума:

Массив байт Di хранит значение простого модуля;

Массив байт P хранит значение общего модуля вычислений;

Массив байт shadow хранит значение доли секрета.

Описание программного класса-родителя Для реализации унифицированного программного интерфейса был реализован класс-родитель для всех пороговых СРС – class srs.

В рамках данного класса описаны переменные:

KeyLength – длина ключа (секрета);

K, N – параметры схема разделения секрета;

modP – общий простой модуль (основание для поля);

bnZero – представление нуля в качестве большого числа (для более быстрой и удобной операции сравнения).

Были так же реализованы следующие виртуальные функции:

GenerateShKeyParts() – публичная функция-инициатор операции разделения секрета;

RestoreKey() – публичная функция-инициатор операции восстановления исходного секрета;

CalcShadow() – приватная функция для просчета одной доли секрета.

Все схемы разделения секрета реализованы как классы-потомки данного базового класса.

6.2.2. Схема Шамира Пороговая схема разделения секрета Шамира реализована в классе srs_shamir. Далее приведено детальное описание реализации. Исходный код приведен в приложении А.

Свойства Для реализации пороговой схемы Шамира к свойствам базового класса было добавлено свойство params – массив целочисленных значений произвольных коэффициентов полинома.

Методы GenerateShKeyParts( Параметры: key – входной параметр ключа, который необходимо разделить на доли; shKetParts – выходной параметр, хранящий значение долей разделенного секрета.

Описание: метод рассчитывает значения долей разделенного секрета для параметров и согласно схеме Шамира.

CalcShadow( Параметры: key – входной параметр ключа, который необходимо разделить на доли; point – входной параметр, значение точки для просчета конкретного значения полинома степени; shadow – выходной параметр, значение доли разделенного секрета.

Описание: приватный метод, рассчитывает значение одной доли разделенного секрета.

RestoreKey( Параметры: shKeyParts – входной параметр, массив долей разделенного секрета, из которых происходит восстановление изначального секрета; key– выходной параметр, значение восстановленного секрета.

Описание: метод восстановления секрета по долям, использующий интерполяционную схему Лагранжа.

GenerateRandomParams() Описание: метод генерации произвольных значений коэффициентов для полинома Лагранжа.

6.2.3. Схема, основанная на эллиптической кривой Пороговая схема разделения секрета, основанная на эллиптической кривой реализована в классе srs_elliptic. Далее приведено детальное описание реализации. Исходный код приведен в приложении Б.

Свойства params – массив произвольных точек заданной эллиптической кривой – значения коэффициентов полинома Лагранжа.

SKP – точка на заданной эллиптической кривой – значение секрета.

Методы GenerateShKeyParts( Параметры: key – входной параметр, секрет, который необходимо разделить;

shKeyParts – выходной параметр, хранящий значение долей разделенного секрета.

Описание: метод рассчитывает значения долей разделенного секрета для параметров и согласно схеме, основанной на эллиптической кривой.

CalcShadow( Параметры: key – входной параметр, секрет, который необходимо разделить;

point - входной параметр, значение точки для просчета конкретного значения полинома степени; shadow - выходной параметр, значение доли разделенного секрета.

Описание: приватный метод, рассчитывает значение одной доли разделенного секрета.

FindEParams( Параметры: x – входной параметр, большое число, определяющее координату для секрета; y – входной параметр, большое число, определяющее координату для секрета; a и b – выходные параметры, задающие эллиптическую кривую.

Описание: по значению секрета, представленного в виде точки на эллиптической кривой, высчитываются параметры эллиптической кривой, которой данная точка принадлежит.

GenerateRandomParams(big a, big b) Параметры: a и b – параметры заданной эллиптической кривой.

Описание: находит произвольных точек на заданной кривой и записывает их в свойство класса params.

RestoreKey( Параметры: shKeyParts – входной параметр, массив долей разделенного секрета, из которых происходит восстановление изначального секрета; key– выходной параметр, значение восстановленного секрета.

Описание: метод восстановления секрета по долям, использующий итерационную схему.

CaclRestPoint( Параметры: ePvect–входной, выходной параметр, массив точек на эллиптической кривой; iPvect – входной параметр, массив целых чисел; param – входной параметр, текущий параметр итерационной схемы восстановления секрета.

Описание: просчитывает новых значений точек и записывает их в ePvect.

BytesFromPoint( Параметры: p – входной параметр, значение точки на эллиптической кривой;

– выходной параметр, представление точки в виде массива байт ( Описание: представляет точку на эллиптической кривой как массив байт.

PointFromBytes( Параметры: vb – входной параметр, массив байт; p – выходной параметр, точка на эллиптической кривой.

Описание: представляет массив байт в виде точки на эллиптической кривой 6.2.4. Схема Асмута-Блума Пороговая схема разделения секрета Асмута-Блума реализована в классе srs_primes. Далее приведено детальное описание реализации. Исходный код приведен в приложении В Свойства Для реализации пороговой схемы Асмута-Блума к свойствам базового класса было добавлено свойство D – массив больших чисел – значения простых модулей для просчета долей разделенного секрета.

Методы GenerateShKeyParts( Параметры: key – входной параметр, секрет, который необходимо разделить;

shKeyParts – выходной параметр, хранящий значение долей разделенного секрета.

Описание: метод рассчитывает значения долей разделенного секрета для параметров и согласно схеме Асмута-Блума.

Параметры: shKeyParts – входной параметр, массив долей разделенного секрета, из которых происходит восстановление изначального секрета; key– выходной параметр, значение восстановленного секрета.

Описание: метод восстановления секрета по долям, использующий китайскую теорему об остатках.

GeneratePrimes() Описание: генерирует простых чисел, больших заданного модуля modP и помещает их в массив D.

6.3. Описание реализации унифицированной инфраструктуры тестирования Унифицированная инфраструктура тестирования состоит из следующих блоков:

Блок задания тестовых параметров;

В блоке задания тестовых параметров создаются экземпляры классов srs_shamir, srs_elliptic и srs_primes, задаются начальные значения параметров разделения секрета ( и ), создаются тестовые значения секретов, которые необходимо разделить.

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

Исходный код инфраструктуры тестирования приведен в приложении Г.

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

СРС Шамира СРС Асмута-Блума Объем требуемой памяти: 3456 байт 274432 байт 4243456 байт СРС на основе эллиптической кривой В ходе тестирования реализованных пороговых схем разделения секрета было выявлено, что схема, основанная на эллиптической кривой, в том виде, в каком она изложена в [10], не работает. Результаты, приведенные в таблице, относительно этой схемы, показывают параметры работы алгоритма, но результат операций неверен.

По результатам проведенного тестирования, безусловно, видно, что наиболее эффективной оказалась пороговая схема разделения секрета Шамира. Эта схема была выбрана для дальнейшей доработки и для внедрения в ПАК «ViPNet HSM»

В ходе выполнения магистерской диссертации была описана и успешно выполнена практическая задача реализации пороговой схемы разделения технологического мастер-ключа и которая была успешно внедрена в ПАК «ViPNet HSM».

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

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

8. СПИСОК ЦИТИРУЕМОЙ ЛИТЕРАТУРЫ

1. Shamir А. Ноw to share a secret // Com. Of the ACM. - 1979. - Vol. 22, №11. P.612-613.

2. Blakley G.R. Safeguarding cryptographic keys // Proc. Of AFIPSNasiona ComputerConference. -1979. - 48. - P.313- 3. Ященко В.В. Введение в криптографию. - Санкт-Петербург: МЦНМО, 2001. с.

4. Шнайер Б. Прикладная криптография. - М.: Изд-во Триумф, 2003. - 816 с.

5. Чмора А. Современная прикладная криптография. - М.: Гелиос АРВ, 2001. с.

6. Андрущенко А.С., Уривский А.В., Пьянов С.М. Исследование возможностей создания специального ПАК – промежуточный н.-т. отчет, шифр темы: «НИР «Пронто-И», 2013. – 170 с.

7. Блэкли Р.Г., Кабатянский Г.Р. Обобщение идеальные схемы, разделяющие секрет и матройды // Проблемы передачи информации. – 1997. – Т.33. - №3. – C. 42-46.

8. Capocelli R.M., De Santis A., Cargano L., Vaccaro U. On the Size of Shares for Secret Sharing Schemes // J. Cryptology. – 1993. V.6 – P. 157-167.

9. Carnin E.D., Greene J.W., Hellman M.E. On Secret Sharing Systems // IEEE Trans.

Inform. Theory. – 1983. – V.29. - №1. – P.231-241.

10. Спельников А.Б. Эллиптическая пороговая схема разделения секрета – Вест.

Сам. гос. техн. ун-та, серия Физ.-мат науки – 2009. – №1(18). – С.251-259.

11. C. Asmuth, J. Bloom. A modular approach to key safeguarding // Information Theory, IEEE Transactions on. — 1983. — В. 2. — Т. 29.

12. L. Harn, C. Lin. Detection and identification of cheaters in (t, n) secret sharing scheme. – Des. Codes Cryptography – 52(1) – 2009 – P. 15-

ПРИЛОЖЕНИЕ 1. ИСХОДНЫЙ КОД СХЕМЫ ШАМИРА

Заголовочный файл srs_shamir.h #pragma once #include "stdafx.h" #include "srs_class.h" class srs_shamir: public srs public:

std::vector params;

bool Init(uint16 kLen, uint16 kParam, uint16 nParam);

void GenerateShKeyParts( std::vector &shKeyParts);

void RestoreKey( const std::vector &shKeyParts, void GenerateRandomParams();

private:

void CalcShadow( Файл исходного кода srs_shamir.cpp #include "srs_shamir.h" bool srs_shamir::Init(uint16 kLen, uint16 kParam, uint16 nParam) KeyLength = kLen;

void srs_shamir::GenerateShKeyParts( const std::vector &key, std::vector &shKeyParts) if (key.size() == 0) printf("Not a valid key");

if (size(modP) == 0) expb2(8*KeyLength, maxKeyLen);

incr(maxKeyLen, 1, maxKeyLen);

nxprime(maxKeyLen, modP);

if (params.size() == 0) GenerateRandomParams();

void srs_shamir::CalcShadow( const std::vector &key, const uint32 point, std::vector &shadow) big bnShadow = mirvar(0);

big bnKey = mirvar(0);

bytes_to_big( (const char*)&key[0], while ((i--) > 1) convert(params[K-i-1], a);

add(bnShadow, a, bnShadow);

add(bnShadow, bnKey, bnShadow);

mr_free(bnKey);

VCDec();

divide(bnShadow, modP, modP);

shadow.resize(KeyLength);

big_to_bytes( mr_free(bnShadow);

VCDec();

void srs_shamir::GenerateRandomParams() params.push_back(s);

void srs_shamir::RestoreKey( const std::vector &shKeyParts, std::vector &key) if (shKeyParts.size() == 0) printf("Not valid shadows");

if (shKeyParts.size() != K) printf("Not valid shadows count");

big res = mirvar(0);

VCInc();

for (uint16 i = 1; i key_len+1 ? 3*k_param : key_len+1));

printf("TEST SHAMIR.. OK\n\n");

void test_srs::TestF_Primes(bool keyGen) printf("TEST PRIMES.. START\n");

printf(" PARAMS: K=%d N=%d KEY-LENGTH=%d\n", k_param, n_param, key_len);

miracl *mip2 = mirsys(2*key_len*k_param, 256);

if (keyGen) //Создание произвольного ключа shared_key.resize(key_len);

irand((int)time(NULL));

bigbits(8*key_len, rnd_2);

big_to_bytes(key_len, rnd_2, (char *)&shared_key[0], TRUE);

clock_t begin, end;

double time_spent;

srs_primes srs;

srs.Init(key_len, k_param, n_param);

std::vector shadows;

shadows.resize(srs.N);

std::vector restKey;

begin = clock();

srs.GenerateShKeyParts(shared_key, shadows);

end = clock();

time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

printf(" SHARE TIME: %f\n", time_spent);

if (n_param != k_param) if ((n_param != 5) && (k_param != 3)) printf("wrong params...");

sh.erase(sh.end()-i);

sh.erase(sh.end()-i);

srs.RestoreKey(sh, restKey);

time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

printf(" RESTORE TIME (%d): %f\n", i, time_spent);

else srs.RestoreKey(shadows, restKey);

time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

printf(" RESTORE TIME: %f\n", time_spent);

if (shared_key == restKey) printf("\n MAX BIG VARS COUNT = %d\n", srs.vars_max);

printf(" MEMORY USAGE = %d BYTES\n\n", srs.vars_max*(2*key_len*k_param));

printf("TEST PRIMES.. OK\n\n");

void test_srs::TestF_Elliptic(bool keyGen) printf("TEST ELLIPTIC.. START\n");

printf(" PARAMS: K=%d N=%d KEY-LENGTH=%d\n", k_param, n_param, key_len);

miracl *mip3 = mirsys(3*k_param > key_len+1 ? 3*k_param :

key_len+1, 256);

if (keyGen) //Создание произвольного ключа shared_key.resize(key_len);

irand((int)time(NULL));

bigbits(8*key_len, rnd_3);

big_to_bytes(key_len, rnd_3, (char *)&shared_key[0], TRUE);

clock_t begin, end;

double time_spent;

srs_elliptic srs;

srs.Init(key_len, k_param, n_param);

std::vector shadows;

shadows.resize(srs.N);

std::vector restKey;

begin = clock();

srs.GenerateShKeyParts(shared_key, shadows);

end = clock();

time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

printf(" SHARE TIME: %f\n", time_spent);

if (n_param != k_param) if ((n_param != 5) && (k_param != 3)) time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

srs.RestoreKey(shadows, restKey);

time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

printf(" RESTORE TIME: %f\n", time_spent);

printf("TEST ELLIPTIC.. OK\n\n");

void test_srs::Test_MaxValues() printf("TEST MAX VALUES.. START\n\n");

n_param = 128;

k_param = n_param;

//Схема Шамира TestF_Shamir(true);

//Схема Асмута-Блума TestF_Primes(true);

//Схема эллиптики TestF_Elliptic(true);

printf("TEST MAX VALUES.. OK\n\n");

void test_srs::Test_CriticalValues_Thresholds() printf("TEST CRITICAL VALUES.. START\n\n");

printf("N=K=1");

n_param = 1;

k_param = n_param;

//Схема Шамира TestF_Shamir(true);

//Схема Асмута-Блума TestF_Primes(true);

//Схема эллиптики TestF_Elliptic(true);

n_param = 32;

k_param = n_param;

printf("КЛЮЧ = 000000000000...\n");

shared_key.resize(key_len);

for (int i = 0; i < key_len; i++) //Схема Шамира TestF_Shamir(false);

//Схема Асмута-Блума TestF_Primes(false);

//Схема эллиптики TestF_Elliptic(false);

printf("КЛЮЧ = FFFFFFFFFFFF...\n");

shared_key.resize(key_len);

for (int i = 0; i < key_len; i++) //Схема Шамира TestF_Shamir(false);

//Схема Асмута-Блума TestF_Primes(false);

//Схема эллиптики TestF_Elliptic(false);

printf("TEST CRITICAL VALUES.. OK\n\n");

void test_srs::Test_NormalValues() printf("TEST NORMAL VALUES.. START\n\n");

n_param = 5;

k_param = 3;

//Схема Шамира TestF_Shamir(true);

//Схема Асмута-Блума TestF_Primes(true);

//Схема эллиптики TestF_Elliptic(true);

printf("TEST NORMAL VALUES.. OK\n\n");