Быстрый поиск

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

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. Проектный раздел

2.1 Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C = ЕКо(М) (3)

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

М = DКс (С) (4)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n$

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

a = bq0 + r1

b = r1q1 + r2

r1 = r2q2 + r3

$\cdots$

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

$\cdots$

rn − 1 = rnqn

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

Существование таких r1,r2,..., то есть возможность деления с остатком m на n для любого целого m и целого $n\ne 0$ , доказывается индукцией по 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)

$\cdots$

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

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

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

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

$\frac ab=[q_0; q_1, q_2,\cdots,q_n]$ .

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

$[q_0; q_1, q_2,\cdots,q_{n-1}] = -\frac ts$ .

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

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

$r_i \equiv r_{i-2} \pmod{r_{i-1}},$

где

$-\frac{r_{i-1}}{2}\leq r_i\leq\frac{r_{i-1}}{2}.$

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

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, что является трудной задачей. В качестве примера возьмем

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