Лабораторная работа

Сост.докт.физ-мат.наук, профессор каф. САИТ ВМК

Казанского федерального университета Ш.Т.Ишмухаметов

Название работы. Шифрование и аутентификация пользователей на основе электронно-цифровой подписи (ЭЦП) с использованием эллиптических кривых.

Цель. Ознакомиться с методами шифрования и установки ЭЦП с использованием механизма эллиптических кривых, разработать и написать программу выработки пар «открытый/закрытый» ключ по методу ЭК. Выполнить задачи аутентификации пользователей, выработки общих ключей и шифрования данных.

Задание на лабораторную работу

1. Изучить теоретический материал по данной лабораторной работе.

2. Разработать программный комплекс генерации параметров эллиптической кривой, аутентификации пользователей, шифрования/расшифровки данных. Взять значение простого числа p, являющегося характеристикой поля, в интервале 10000-12000.

3. Найти базовую точку В, порождающую все элементы кривой. Подсчитать порядок кривой n= #E (число точек на кривой).

4. Найти базовую точку G на кривой простого порядка q >500, являющего делителем n (если такой точки не окажется, то надо поменять кривую). В частном случае, q может равняться n.

5. Выполнить тестовые шифрование и расшифровку произвольного сообщения.

Теоретический материал. Подход на основе эллиптических кривых имеет преимущество по сравнению с задачей факторизации числа, используемой в RSA, или задачей целочисленного логарифмирования, применяемой в алгоритме Диффи-Хелмана и в DSS, заключающийся в том, что в данном случае обеспечивается эквивалентная защита при меньшей длине ключа. Длина ключа ЭК, равная 180 бит, эквивалентна длине ключа RSA 1024 бита.

Эллиптической кривой называют множество пар точек (X,Y), удовлетворяющих уравнению:

у² =х³+ ах+b (mod p), p-простое число, (1)

вместе с бесконечно удаленной точкой, обозначаемой через O (не путать с началом координат), где координаты (x, y) являются элементами конечного поля, GF_p.

Можно наложить ограничения на множество значений переменных х, y, и коэффициентов a, b, c. Ограничивая область определения уравнения значимым для приложений числовым множеством (полем), мы получим эллиптическую кривую, заданную над рассматриваемым полем. На рисунке изображен общий вид эллиптической кривой, определенной на множестве действительных чисел.

Рис. 1. Общий вид эллиптической кривой в R².

Эллиптические кривые используются в криптографии с середины 80-х г. прошлого века в качестве инструмента решения некоторых теоретико-числовых задач и в качестве основы для построения криптосистем. Любая кривая над полем действительных чисел, задаваемая уравнением общего вида (1), обладает следующими свойствами, в формулировке которых условимся точку касания считать за два пересечения:

1. Любая вертикальная (параллельная оси Оу) прямая, не пересекает кривую ни разу или пересекает ее дважды.

2. Любая другая прямая пересекает кривую один или три раза.

Добавим к множеству точек эллиптической кривой фиктивный элемент " О " (называемый обычно "бесконечной точкой"), который будет играть роль нулевого элемента конструируемой аддитивной группы: для любой точки Р эллиптической кривой положим Р + О = О + Р = Р. Операции отрицания и сложения определяем чтобы для каждой прямой, пересекающей эллиптическую кривую дважды или трижды, "сумма" всех точек пересечения с учетом их кратности при касании была "равна нулю":

R + R' = O - для вертикальных прямых,

P + Q+R = O - для невертикальных прямых (см. рис. 1).

Первое соотношение определяет правило отрицания - аддитивным обратным элементом для любой точки R эллиптической кривой является другая точка пересечения кривой и вертикальной прямой: R' = -R. Второе соотношение определяет правило сложения точек: суммой двух точек кривой является отрицание третьей точки пересечения кривой и прямой, проведенной через первые две: Р + Q = -R = R' (см. рис. 1). Для определенных аддитивных операций выполняются все требования к операциям в абелевых группах:

1. Операция сложения точек очевидным образом коммутативна: для любых точек Р, Q эллиптической кривой справедливо Р + Q = Q + Р.
2. В проективной геометрии доказывается ассоциативность операции сложения точек: для любых трех точек Р, Q, R эллиптической кривой справедливо (Р + Q) + R = P + (Q+R).

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

Дата добавления: 2015-10-29