Нир: «Разработка программного комплекса шифрования данных, на основе использования точек эллиптической кривой» - umotnas.ru o_O
Нир: «Разработка программного комплекса шифрования данных, на основе использования точек эллиптической кривой» - umotnas.ru o_O
|
Похожие работы
|
Нир: «Разработка программного комплекса шифрования данных, на основе использования - страница №4/4
Пример 5.2. Эллиптическая кривая задается уравнением: , где , , , , , , , , , , . Результат представлены в таблице 5.6. Таблица 5.6 – Разложения на простые множители
Тогда с помощью точек эллиптической кривой можно закодировать алфавит, содержащий слов. Таким образом, мы провели анализ алгоритмов кодирования алфавитов точками эллиптической кривой. По итогам этого анализа можно утверждать, что вероятностный метод кодирования обладает двумя существенными недостатками: 1. При большой мощности алфавита вероятность его не закодировать возрастает и становиться больше, чем вероятность его закодировать. 2. С помощью данного метода возможно закодировать алфавит в раз меньше, чем количество точек на эллиптической кривой. Детерминированный метод кодирования алфавита может привести к переходу от криптостойкой эллиптической кривой к дуальной не криптостойкой эллиптической кривой. Так, в примере 5.1 показано, что задачу дискретного логарифмирования можно решить за 4 часа 30 минут. При условии, что современная техника может выполнять операций в секунду с точками эллиптической кривой, эта применение этого метода теряет смысл. Предложен новый алгоритм кодирования, предназначенный для эллиптических кривых, заданных над кольцом . Использование эллиптической кривой над кольцом позволяет применять систему остаточных классов для выполнения арифметических операций в кольце , что существенно уменьшает время выполнения арифметических операций с точками на эллиптической кривой, следовательно, уменьшается время кодирования и декодирования информации, и требуется меньшая вычислительная мощность. Схема Шамира позволяет секрет разделить на частей , ,…, так, что выполняются следующие два условия: 1. С помощью любых и более частей можно восстановить секрет ; 2. С помощью любых частей нельзя ни восстановить секрет, ни получить о нем никакой дополнительной информации кроме той, которая уже имеется. Пороговые схемы, удовлетворяющие условию 2, называются совершенными пороговыми схемами разделения секрета. В работе [55] предложен алгоритм многоточечного разделения точек на эллиптической кривой, в котором используется спаривание из работы [56]. В работе [55] показано, что эта схема является совершенной и криптостойкой, если выполняются следующие четыре условия: 1. Честных пользователей в схеме должно быть не менее ; 2. Задача нахождения дискретного логарифма в группе точек эллиптической кривой должна быть трудно вычислимой; 3. Задача вычисления дискретного логарифма в мультипликативной группе должна быть трудно вычислимой; 4. Распространено не более точек. Из условия 3 и условия применимости алгоритма Полига-Хеллмана-Зильбера, изложенного в работах [57], следует, что порядок группы точек эллиптической кривой при разложении на множители должен содержать большое простое число. Таким образом, нам необходим алгоритм, с помощью которого можно эффективно находить порядок группы точек эллиптической кривой. Одним из наиболее известных алгоритмов является алгоритм Шуфа, изложенный в работах [57], и его усовершенствование Элкисаном и Аткиным, известное как алгоритм SEA, изложенное в работах [58-59]. Сложность этих алгоритмов составляет и соответственно. Для выполнения условия 2 требуется, чтобы , из чего следует, что, используя самый быстрый универсальный алгоритм SEA для нахождения , требуется операций, что приблизительно равно , а, так как современная вычислительная техника может выполнять операций в секунду, то потребуется 55 часов для нахождения порядка одной эллиптической кривой. Это делает данный алгоритм неприемлемым для использования в практических целях. Альтернативным решением данной проблемы является построение криптосистемы на эллиптической кривой , заданной конечным кольцом , , – различные простые числа и для всех . Для построения схемы разделения секрета введем операцию спаривание на эллиптической кривой аналогичную операции, приводимой в работе [56]. Для любой точки выполняется следующее равенство: , где – точка в бесконечности. Обозначим за множество точек эллиптической кривой, которая задана уравнением над полями . Для построения спаривания важно знать структуру группы точек эллиптической кривой. Ниже приведена теорема, описывающая структуру группы, когда эллиптическая кривая задана над полем , где – простое число, и порядок группы точек эллиптической кривой выражается формулой . Теорема 6.1 [60] Если , то группа циклическая. Если , то группа изоморфна в случае , или изоморфна в случае . Если , , то группа циклическая. Если , , то группа или циклическая или изоморфна . Из теоремы 6.1 следует, что в случае, когда и – четное число, группа точек представляется в виде прямой суммы или . Обозначим эти группы , где или . Так как представляется в виде прямой суммы циклических групп, то можно зафиксировать некоторую образующую пару точек и таким образом, чтобы с их помощью можно было представить в любую точку. Рассмотрим точки и , принадлежавшие , где . Для некоторых зафиксированных целых определим функцию следующим образом: Пусть , и – три Абелевы группы. Билинейное спаривание является отображением среди этих трех групп, и отображение должно удовлетворять свойству билинейности: для , , , . Следующая теорема показывает, что функция задает билинейное спаривание.
Для всех ,
Для всех . и
Для любых , .
Для всех , . Кроме того, если для всех , тогда . называется спариванием, поскольку оно отображает в (аналогично традиционным спариваниям Вейля и Тейта). Пусть и . Зададим спаривания как , , с помощью множество точек , и целых чисел , где , , , , , , , , , и Замечание. Значения , , представляются в системе остаточных классов числами , , по основаниям . Приведем небольшой пример для построения билинейного спаривания. Пример 6.1. Пусть задана эллиптическая кривая : и , тогда и имеет восемь торсионных точек третьего порядка: , , , , тогда билинейное спаривание можно задать с помощью следующих точек: и . , , , , , , , , что изоморфно . Схема разделения точек на эллиптической кривой Пусть задано множество точек, которые нам нужно разделить между участниками . Это может быть сообщением, представленным в виде точек, или ключом к криптосистеме. Начальная фаза Обозначим дилера и участников схемы разделения точек . Дилер совершает следующие шаги для определения параметров, использующих схемы: 1. Дилер выбирает эллиптическую кривую над , где , – попарно различные простые числа, так, чтобы . выбирает целое четное число и вычисляет множество чисел ; 2. выбирает образующую пару и целые числа , которые задают спаривание ; 3. Дилер опубликовывает , что является открытым ключом. Дилер использует следующий алгоритм распространения секретов между участниками так, чтобы любые или более участников могли легко восстановить секрет, а любые или меньше участников не могли этого сделать и получить какую-либо дополнительную информацию о секрете. 1. вычисляет матрицу :
2. выбирает случайных чисел каждое для и ; 3. вычисляет и ; 4. В завершении сообщает пар (секретный ключ) пользователю для всех , где . После распространения секретов дилер может распространять точки среди участников, используя следующий алгоритм: 1. Для части других точек сообщает дилер , выбирая случайно и вычисляя для всех , , причем каждая точка представляется в виде ; 2. вычисляет для всех , и публикует (открытый ключ). Алгоритм восстановления точки Предположим, что различных пользователей захотели восстановить точек .Они восстанавливаются по следующему алгоритму: 1. Каждый берет массив целых чисел из открытого ключа, где , ; 2. Каждый вычисляет , где и , где и ; 3. Каждый группой псевдосекрет к , где ; 4. Каждый вычисляет , где и ; 5. Каждый загружает точку из открытого ключа и восстанавливает , как ; 6. Из множества восстанавливается точка , где и . Анализ безопасности Покажем, что построенная -пороговая схема разделения секрета является совершенной. Для этого докажем следующую теорему. Теорема 6.3:. Если, по крайней мере пользователей честных, тогда любые пользователей ничего не узнают о , где – зафиксированное целое число, принадлежащее отрезку . Доказательство. Пусть произвольных пользователей знают и , , , , , , где . Пусть
тогда . Ранг равен , так как матрица состоит из столбцов матрицы Вандермонда и , если . Из теории линейных уравнений любое значение из . Тот же самый результат сохраняется и для , поэтому любые пользователей ничего не узнают о . Теорема доказана. Приведем лемму из работы [55], в которой говорится о том случае, когда и которая потребуется при доказательстве теоремы о вероятности выбора случайной точки. Лемма 6.1: [55]. Если и , то тогда и только тогда, когда принадлежит множеству . В следующей теореме мы покажем, что вероятность выбора наугад точек , задающих точку , очень мала. Теорема о случайном выборе точки. Вероятность случайного выбора какой-то одной зафиксированной точки так, чтобы равна тому, что . Из леммы 3.1 получим, что . Таким образом, вероятность случайного выбора одной зафиксированной точки равна так, чтобы равна . Вероятность случайного выбора независимых точек , где вычисляется по формуле произведения вероятностей. При условии, что вероятность случайного выбора точки равна , получим вероятность выбора случайной точки так, что для всех равной . Теорема доказана. Итак, предложенная схема разделения секрета является безопасной при выполнении двух условий: 1. По крайней мере пользователей в схеме честных. 2. Распространено не более, чем точек. Преимущество в реализации -пороговой схемы разделения секрета на эллиптической кривой над заключается в том, что при использовании проективной системы координат можно эффективно использовать систему остаточных классов, что существенно ускоряет процесс шифрования и дешифрования информации. 7 Разработка рекомендаций по использованию результатов проведенной НИР Результаты работы могут быть использованы для разработки типовых процессов передачи данных на основе современных информационных технологий в региональных компаниях телекоммуникаций; для реализации эффективных алгоритмов передачи информации в распределенных вычислительных сетях; в качестве прототипа для разработки систем передачи информации с использованием эллиптической кривой, заданной над конечным кольцом, обладающих параллелизмом машинным операций Результаты исследования могут быть использованы на предприятиях и в организациях, занимающихся разработкой информационных систем для решения задач передачи информации в распределенных вычислительных четях, входящих в состав холдинга ОАО «Связьинвест» (ОАО «Волгателеком», ОАО «Центральная телекоммуникационная компания», ОАО «Северо-Западный Телеком», ОАО «Южная телекоммуникационная компания», ОАО «Уралсвязьинформ», ОАО «Сибирьтелеком», ОАО «Дальневосточная компания электросвязи») и альтернативных операторов (ОАО «ТрансТелеком»), а также ВУЗах, где имеются телекоммуникационные специальности. Заключение В результате научно-исследовательской работы по теме «Разработка программного комплекса шифрования данных, на основе использования точек эллиптической кривой» были проведены следующие исследования: 1. Анализ алгоритмов симметричного и асимметричного шифрования на точках эллиптических кривых. 2. Разработан генератор псевдослучайных чисел на базе использования квадратичных полей Галуа и точек эллиптической кривой, в рамках которого доказано утверждение о длине периода указанной последовательности. 3. Разработаны алгоритмы операций сравнения, сложения и умножения чисел над простым полем в двух модульной системе остаточных классов. 4. Разработан алгоритм кодирования алфавита точками эллиптической кривой 5. Разработана схема разделения секрета на точках эллиптической кривой и показана, что разработанная схема является совершенной схемой разделения секрета. Как видно из отчетных материалов, все исследовательские задачи по проекту выполнены полностью с должным качеством. При плановых показателях публикации в изданиях 2 публикаций по факту опубликованы 2 публикации. Список использованных источников
|
|
|