Дипломная работа: Ассиметричное шифрование на базе эллиптических кривых

w4

 U4

Рис. 5. Функция ценности критерия

Теперь вычислим ri для этого введем вектора:

U1 = (U1*, 1, 1, 1)

U2 = (1,U2*, 1, 1 )

U3 = (1, 1, U3*, 1)

U4= (1, 1, 1, U4*)

Выберем для Uk* такие значения,что бы эти вектора были приблизительно равны, тогда получим: U1* = 6, U2* = 8, U3* = 7, U4= 8. Из эквивалентности U1 и U2, U1 и U3, U1 и U4, и дополнив условием нормировки коэффициентов rk получим систему из четырех уравнений:

r1 w1(6) = r2 w2(8)

r1 w1(6) = r3 w3(7)

r1 w1(6) = r4 w4(8)

r1 + r2 + r3 + r4 = 1

Подставляя значения wk из соответствующего графика где:

w1(6) = 0,625

w2(8) = 0,75

w3(7) = 0,68

w4(8) = 0,84

и выражая все через r1 получаем следующие значения коэффициентов rk

r1 = 0,28

r2 = 0,23

r3 = 0,25

r4 = 0,20

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

Отсюда аддитивный интегральный критерий будет иметь вид:

Y = 0,28 w1(u1) + 0,23 w2(u2) + 0,25 w3(u3) + 0,20 w4(u4) (2)

где функция wk - зависимость веса критерия от его значения;

uk - частный критерий эффективности;

w1(u1) – зависимость веса критерия (наличие развитого графического интерфейса) от его значения;

w2(u2) – зависимость веса критерия (время реакции системы не превышает 4 секунды) от его значения;

w3(u3) – зависимость веса критерия (достаточно полная справочная система) от его значения;

w4(u4) – зависимость веса критерия (выбор справочных значений из списка) от его значения.

Используя значения из таблиц 7,8,9(пункт 1.3.6) находим коэффициенты для уравнений прямых, рисунки 2,3,4 (пункт 1.3.6), выбранных участков графиков, получаем следующие значения зависимости веса критерия от его значения:

1) w1=0,083u1+0,17, берем из таблицы 10 (пункт 1.3.5.) значение u1 и получаем w1=0,083*7 + 0,17 = 0,75

2) w2=0,125u2-0,25, берем из таблицы 10 (пункт 1.3.5.) значение u2 и получаем w1=0,125*10 - 0,25 = 1

3) w3=0,0625u3+0,25, берем из таблицы 10 (пункт 1.3.5.) значение u3 и получаем w3=0,0625*5+0,25=0,56

4) w4=0,083u4+0,17, берем из таблицы 10 (пункт 1.3.5.) значение u4 и получаем w4= 0,083*6+0,17=0,67

Подставим w1, w2, w3 и w4 в уравнение аддитивного интегрального критерия 2 и рассчитаем оценку ПП.

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

Y = 0,28*0,75 + 0,23*1+ 0,25*0,56+ 0,20*0,67 = 0,71

Потребуем, чтобы разрабатываемый программный продукт имел оценку по интегральному аддитивному показателю, рассчитываемому по формуле 1 (пункт 1.3.6), не ниже 0,71.

1.4 Заключение по выбранным характеристикам

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

·  Значение показателя - наличие развитого графического интерфейса –должно быть не менее 7 баллов по выбранной шкале;

·  Значение показателя - время реакции системы не превышает 2 секунды –должно быть не менее 10 баллов по выбранной шкале;

·  Значение показателя - достаточно полная справочная система – должно быть не менее 5 баллов по выбранной шкале;

·  Значение показателя - выбор справочных значений из списка – должно быть не менее 6 балла по выбранной шкале.

·  Значение аддитивного интегрального критерия должно быть не менее 0,71.

2.1 Введение

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

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

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

Расшифрование данных с помощью открытого ключа невозможно.

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

·  зашифрование - расшифрование; отправитель шифрует сообщение с использованием открытого ключа получателя;

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

Асимметричные криптосистемы имеют следующие особенности:

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

·  открытыми являются алгоритмы зашифрования и расшифрования.

Защита информации в асимметричной криптосистеме основана на секретности ключа Кс.

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

·  вычисление пары ключей (Ко, Кс) должно быть простым;

·  отправитель может легко вычислить криптограмму, зная открытый ключ Ко и сообщение М;

C = ЕКо(М) (3)

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

М = DКс (С) (4)

·  при попытке вычислить секретный ключ Кс противник наталкивается на непреодолимую вычислительную проблему, даже зная открытый ключ Ко;

·  при попытке вычислить исходное сообщение М противник также наталкивается на непреодолимую вычислительную проблему, даже зная пару (Ко, С).

2.2 Анализ существующих алгоритмов

Для выполнения дипломной работы понадобилось изучить два вида алгоритмов:

·  алгоритмы нахождения НОД;

·  алгоритмы ассиметричного шифрования.

Алгоритмы нахождения НОД

Алгоритм Евклида

Алгоритм Евклида — алгоритм для нахождения наибольшего общего делителя двух целых чисел или наибольшей общей меры двух однородных величин.

Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Историками математики (Цейтен и др.) было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника). Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

Ряд математиков средневекового Востока (Сабит ибн Курра, ал-Махани, Ибн ал-Хайсам, Омар Хайям) попытались построить на основе алгоритма Евклида теорию отношений, альтернативную по отношению теории отношений Евдокса, изложенной в V книге «Начал» Евклида. Согласно определению, предложенному этими авторами, четыре величины, первая ко второй и третья к четвёртой, имеют между собой одно и то же отношение, если при последовательном взаимном вычитании второй величины в обеих парах на каждом шаге будут получаться одни и те же неполные частные.

Алгоритм Евклида для целых чисел

Пусть a и b целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое rk — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

a = bq0 + r1

b = r1q1 + r2

r1 = r2q2 + r3

rk − 2 = rk − 1qk − 1 + rk

rn − 1 = rnqn

Тогда НОД(a,b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности.

Существование таких r1,r2,..., то есть возможность деления с остатком m на n для любого целого m и целого , доказывается индукцией по m.

Проще сформулировать алгоритм Евклида так: если даны натуральные числа a и b и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.

Бинарный алгоритм

Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел, основанный на использовании следующих свойств НОД:

·  НОД(2m, 2n) = 2 НОД(m, n),

·  НОД(2m, 2n+1) = НОД(m, 2n+1),

·  НОД(-m, n) = НОД(m, n)

Алгоритм

·  НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;

·  НОД(1, n) = 1; НОД(m, 1) = 1;

·  Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);

·  Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);

·  Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);

·  Если m, n нечётные, то НОД(m, n) = НОД(n, |m - n|).

Так как алгоритм является Хвостовой рекурсией, то рекурсию можно заменить итерацией.

Криптосистема шифрования данных RSA

В настоящее время наиболее изученным методом криптографической защиты, основанным на трудности факторизации больших чисел и трудности вычисления дискретных логарифмов, является алгоритм RSA (названый по начальным буквам фамилий ее изобретателей Rivest, Shamir, Adleman). Этот алгоритм может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.

Схема RSA представляет собой блочный шифр, в котором открытый и зашифрованный тексты представляются целыми числами из диапазона от 0 до N – 1 для некоторого N, т.е. открытый текст шифруется блоками, каждый из которых содержит двоичное значение, меньшее некоторого заданного числа N. Это значит, что длина блока должна быть меньше или равна log2(N).

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

где N – модуль, P и Q являются случайными большими взаимно простыми числами. Их выбирают равной длины и хранят в секрете для обеспечения максимальной безопасности.

Множество ZN с операциями сложения и умножения по модулю N образует арифметику по модулю N.

Открытый ключ Ко выбирают случайным образом так, чтобы выполнялись условия

где (N) – функция Эйлера, которая указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N.

Кроме того, открытый ключ Ко и функция Эйлера ϕ(N) также должны

быть взаимно простыми.

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

Данное вычисление возможно, поскольку получатель знает пару простых чисел (P, Q) и может легко найти ϕ(N), при этом Кс и N должны быть взаимно простыми. Задачу зашифрования открытого текста М в криптограмму С можно решить, используя открытый ключ Ko, по следующей формуле:

Задачу расшифрования криптограммы С можно решить, используя секретный ключ Кс, по следующей формуле:

Процесс расшифрования можно записать так:

Подставляя значение в предыдущие 2 формулы, получаем:

Таким образом, получатель, который создает криптосистему, защищает два параметра: секретный ключ Кс и пару чисел P и Q, произведение которых даёт модуль N. Одновременно публикует значения модуля N и открытого ключа Ко, поэтому противнику известны только значения Ко и N. Если бы криптоаналитик смог разложить число N на множители P и Q, то он узнал бы тройку чисел (P,Q, Ko), значение функции Эйлера ϕ(N) = (P – 1) (Q – 1) и определил значение секретного ключа Kc.

Однако, как отмечалось выше, разложение большого числа N на множители вычислительно не осуществимо при длине выбранных P и Q не менее 100 десятичных знаков.

2.3 Используемые алгоритмы

Расширенный алгоритм Евклида

Формулы для ri могут быть переписаны следующим образом:

r1 = a + b(- q0)

r2 = b − r1q1 = a(− q1) + b(1 + q1q0)

gcd(a,b) = rn = as + bt

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

Связь с цепными дробями

Отношение a / b допускает представление в виде цепной дроби:

.

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу t / s, взятому со знаком минус:

.

Ускоренные версии алгоритма

·  Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остатка:

· 

где

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

ECЕS

В алгоритме ECES (Elliptic Curve Encryption Scheme) на первом этапе должны быть определены параметры, являющиеся общей открытой информацией для всех пользователей системы:

·  конечное поле GF(p);

·  эллиптическая кривая E(GF(p));

·  большой простой делитель количества точек кривой p;

·  точка G, координаты которой имеют порядок, что и число p.

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

·  выбирает случайное целое число Kc, 1 < Kc < p -1;

·  вычисляет точку Kо = Kc P.

При этом секретным ключом пользователя является число Kc, открытым ключом - точка Kо. Кроме того, сообщение M разбивается на блоки длиной 2L - 16 бит, где L равно ближайшему большему целому от log2 p;

·  выбирается случайное целое число k, 1 < k < n - 1;

·  вычисляется точка (х1, у1) = kP;

·  вычисляется точка (х2, у2) = k Kо.

Известно несколько подходов к зашифрованию - расшифрованию информации, предполагающих использование эллиптических кривых. Мы рассмотрим наиболее простой из этих подходов. Как было изложено выше, зашифрованное сообщение пересылается в виде значения (х, у) для точки Pm. Здесь точка Рm будет представлять зашифрованный текст и впоследствии будет расшифроваться. В качестве параметров данной криптосистемы рассматривается точка G и эллиптическая группа Еp (а, b).

Пользователи А и В выбирают секретные ключи KcА и KcB, а также генерируют открытые ключи KоA = KcА P и KоB = KcB P соответственно. Чтобы зашифровать сообщение Рm, пользователь А выбирает случайное положительное целое число k и вычисляет криптограмму Сm с помощью открытого ключа стороны В, - KоB, состоящую из двух точек

Cm = {(kG), (Pm + k KоB) }.

Чтобы расшифровать эту криптограмму, пользователь В умножает первую точку (kP) на cвой секретный ключ KcB и вычитает результат из второй точки:

(Рm + k KоB) - KcB (kP) = Рm + k(KcB P) - KcB (kP) = Рm.

Пользователь А замаскировал сообщение Рm с помощью добавления к нему маски k KоB.. Однако следует заметить, что никто не сможет убрать маску k KоB, кроме пользователя, который знает значение k и имеет личный ключ KcB. Противнику для восстановления сообщения придется вычислить k по данным P и kP, что является трудной задачей. В качестве примера возьмем

р = 751, ЕP = (-1, 188) и P = (0, 376).

Все расчеты в данном примере выполняются по модулю p.

Предположим, что пользователь А отправляет пользователю В сообщение, которое кодируется точкой Рm = (562, 201), и выбирает случайное число k = 386. Открытым ключом В является KоB = (201, 5). Мы имеем 386(0, 376) = (676, 558) и (562, 201) + 386(201, 5) = (385, 328).

Таким образом, пользователь А должен послать зашифрованный текст {(676, 558), (385, 328)}.

2.4 Выполнение алгоритмов

Нахождение обратного элемента с помощью расширенного алгоритма Евклида

Теоретические сведения

Вычисляем значение х, в выражении х * А=В mod С

1.  Выбор 2-х взаимно простых чисел А и С;

2.  Выбор числа В < С;

3.  Устанавливаем начальные значения для вычисления обратного элемента:

4.  Подставляем значения в формулы:

5.  Последовательно выполняем вычисление шага 4, пока . В ответ пойдет последний, отличный от нуля остаток

6.  После вычисления мы получим следующее равенство:

7.  Подставляем полученное значение r в выражение и вычисляем значение x:

8.  Подставляем полученный результат в исходное выражение

х * А=В mod С и проверяем полученный результат.

Алгоритм формирования конечного поля Галуа GF(p) и подсчет количества точек эллиптической кривой n=#Ep

Теоретические сведения

На момент начала формирования поля GF(p) необходимо иметь инициализованные переменные эллиптической кривой, такие как p (простое число), a, b, а также выбрать координату х первой точки. Рассмотрим порядок формирования GF(p):

1.  Проверяем условие несингулярности кривой:

2.  Рассчитываем координату Y первой точки по формуле:

3.  Находим следующую точку поля, путем удваивания первой точки:

4.  Каждую следующую точку рассчитываем по формулам:

Условием выхода из цикла является деление на 0. К полученному количеству точек необходимо добавить точку бесконечности О с координатами O[0,0].

Алгоритм ассиметричного шифрования на базе эллиптических кривых ECES

Теоретические сведения

В алгоритме ECES (Elliptic Curve Encryption Scheme) на первом этапе должны быть определены параметры, являющиеся общей открытой информацией, для всех пользователей системы:

·  подгруппа точек эллиптической кривой q (в данном примере примем q = р);

·  конечное поле GF(q);

·  эллиптическая кривая E(GF(q));

·  точка Р, координаты которой имеют порядок, что и число р.

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

·  выбирает случайное целое число d, 1 < d < р-1

·  вычисляет точку О = dP.

При этом секретным ключом пользователя является число d, открытым ключом – точка Q. Обмен конфиденциальной информацией производится в два этапа. Рассмотрим детально процесс обмена информацией между пользователями сети (а точнее между отправителем и получателем В). Методика выполнения пунктов 1-6 подробно описана в предыдущем алгоритме.

Действия отправителя:

1.  Выбираем случайным образом число р, с учетом вьшолнения условий: р>3;

2.  Выбор коэффициениов эллиптической кривой а и b:

3.  Проверяем выполнение условия

4.  Выбираем случайным образом координату X точки эллиптической кривой;

5.  Вычисляем значение координаты точки У,

;

6.  Определяем поле Галуа GF(p), а также количество точек на эллиптической кривой p.

7.  Выбираем точку Р, координаты которой имеют порядок, что и число p

8.  Определяет порядок подгруппы группы точек эллиптической кривой q;

9.  После чего отправитель пересылает получателю следующие данные:

·  конечное поле GF(q);

·  эллиптическую кривая E(GF(q));

·  порядок подгруппы группы точек эллиптической кривой q;

·  точку Р.

10.  Выбираем случайное число КсA - секретный ключ отправителя,

1 < КсА < p-1;

11.  Вычисляем точку КоА - открытый ключ отправителя КоА = КсAР;

12.  Выбираем случайное число k (2-й секретный ключ отправителя),

1 < k < p-1;

13.  Вычисляем точку кР (которая является первой точкой криптограммы);

Действия получателя:

14.  Выбираем случайное число КсB - секретный ключ получателя, 1 < КсВ <p - 1;

15.  Вычисляем точку КоВ - открытый ключ отправителя КсB = КсB Р;

16.  Отправляем получателю свой открытый ключ КoB;

Действия отправителя:

17.  Разбиваем исходное сообщение на блоки (символы ASCII (CP Win 1251));

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

Страницы: 1, 2, 3, 4, 5