Статья:

Эллиптические кривые в конечных полях и их использование в кодировании информации

Конференция: XXVIII Студенческая международная научно-практическая конференция «Технические и математические науки. Студенческий научный форум»

Секция: Физико-математические науки

Выходные данные
Николаева Я.Я., Тарасов А.А. Эллиптические кривые в конечных полях и их использование в кодировании информации // Технические и математические науки. Студенческий научный форум: электр. сб. ст. по мат. XXVIII междунар. студ. науч.-практ. конф. № 5(28). URL: https://nauchforum.ru/archive/SNF_tech/5(28).pdf (дата обращения: 22.09.2020)
Лауреаты определены. Конференция завершена
Эта статья набрала 380 голосов
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

Эллиптические кривые в конечных полях и их использование в кодировании информации

Николаева Яна Яковлевна
студент, Самарский национальный исследовательский университет имени академика С. П. Королёва, РФ, г. Самара
Тарасов Александр Александрович
студент, Самарский национальный исследовательский университет имени академика С. П. Королёва, РФ, г. Самара
Додонова Наталья Леонидовна
научный руководитель, доцент, Самарский национальный исследовательский университет имени академика С. П. Королёва, РФ, г. Самара

 

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

 

Цели работы:

  1. Узнать что такое эллиптические кривые;
  2. Выяснить как они используются в криптографии;
  3. Изучить алгоритмы шифрования и дешифрования на эллиптических кривых;

Задачи:

  1. Найти области практического применения.

В данной статье мы рассмотрим алгоритмы несимметричного шифрования информации, основанные на применении алгоритма эллиптических кривых в конечном поле простых чисел. 

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

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

y2 + a1xy + a3y = x3 + a2x2 + a4x + a6

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

Конечное поле - конечное множество, на котором определены произвольные операции, называемые сложением, умножением, вычитанием и делением, (кроме деления на 0) в соответствии с аксиомами поля.

Эллиптическая криптография строится на том, что все значения вычисляются по модулю p, где p – простое число. Элементами такой эллиптической кривой являются пары, положительных целых чисел, которые меньше p и удовлетворяют частному виду эллиптической кривой:

y2 (mod p) = x3+ax+b(mod p).

Такую кривую принято обозначать Ep(a,b), а пары (х,у) – точками кривой. При этом числа a и b должны удовлетворять условию:

4a3 + 27b2 (mod p) ≠ 0. 

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

Если мы проведём линию, проходящую через P и Q, эта прямая пересечет третью точку кривой R (это подразумевается, потому что P, Q и R находятся на одной прямой).

Если мы возьмем обратную по y величину этой точки −R, мы найдём сумму P+Q.

 

 

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

Для расчета точек эллиптической кривой Ep(a,b), применимы следующие правила :

Правило 1. 0+0=0.

Правило 2. Если P(x,y) , то P + 0 = P .

Правило 3. Если P(х,у), то Р + (х, -у) = 0 . 

Правило 4. Правило сложения двух точек. Если Р(х1, у1), а Q(x2,y2), где P≠Q, x1≠x2 , то сумма двух точек Р+Q равна третьей точке с координатами: (х3,y3) = (х1,y1)+(х2,y2) , где координаты (х3,y3) определяются по формулам:

x= α2 - x1 - x2(mod p),

y3 = α(x1 – x2 ) - y1(mod p),

Где α = (y2 - y1)/(x2 - x1), если P≠Q или α = (3x12 – a)/(2y1), если P=Q.

Правило 5. Правило удвоения точки. Если P(x1,y1), причем у1≠0, то 2Р=2(х11)=(х33), где координаты (х33), находятся по формулам: 

x3 = α2 - 2x1

y3 = α(x1 – x3) - y1

α = (3x12 + a)/(2y1).

Целью работы является изучение алгоритма шифрования на основе уравнений эллиптических кривых в конечном поле Fp , где p – простое число (p > 3). 

Алгоритм шифрования :

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

– сгенерировать открытый и закрытый ключи; 

– пользователю A выполнить операцию шифрования сообщения M ; 

– пользователю B выполнить операцию дешифрования криптограммы E . 

Исходными данными алгоритма являются: 

– конечное поле Fp

– уравнение эллиптической кривой Ep(a,b) в конечном поле Fp

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

– координаты точки P, координаты которой должны иметь тот же порядок, что и число n.

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

– выбирается случайное целое число 1<d<p-1;  

– вычисляется точка Q = dP . 

Секретным ключом пользователя является число d , открытым ключом – точки P Q, и Ep(a,b).

Шифрование сообщения (пользователь A шифрует сообщение M для пользователя B): 

– разделить сообщение на блоки; 

– каждому блоку поставить в соответствие определенную точку Mi кривой Ep(a,b) , с координатами (xi,yi);

– выбирается первая точка M1 из множества точек Mi , координаты которой необходимо зашифровать; 

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

– вычисляется точка kPB=(x1,y1); 

– вычисляется точка kQB=(x2,y2);

– вычисляется сумма двух точек: шифруемой M1=(xi,yi) и точки  kQB=(x2,y2); 

– криптограммой является две точки: E0 (это точка-подсказка: передается только в начале сеанса связи) и E1 (собственно зашифрованное сообщение) с координатами: 

E0={(x1,y1)} 

E1={(x2,y2)}

Дешифрование криптограммы (пользователь B дешифрует полученную от пользователя A криптограмму):

– координаты точки-подсказки kPB умножаются на свой закрытый ключ dB, то есть вычисляется точка dBkP=dB(x1,y1);

– полученный результат вычитается из координат криптограммы E1, в результате вычитания остаются координаты исходной точки M1 : M1+kQB-dBkPB=M1+k(dBPB)-dB(kPB)=M1

В эллиптической криптографии нет действия вычитания точек, поэтому особо следует отметить, что вычитание здесь необходимо заменять на сложение с взаимно обратной точкой (dBkPB), координаты которой равны (x1,-y1) (см. правило 3).

Шифрование с помощью ECDH

ECDH — это разновидность алгоритма Диффи-Хеллмана для эллиптических кривых.

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

Рассмотрим этапы данного алгоритма:

Сначала Алиса и Боб генерируют собственные закрытые и открытые ключи. У Алисы есть закрытый ключ dA и открытый ключ HA=dAG, у Боба есть ключи dB и HB=dBG.

Заметьте, что и Алиса, и Боб используют одинаковые параметры области определения: одну базовую точку G на одной эллиптической кривой в одинаковом конечном поле.

Алиса и Боб обмениваются открытыми ключами HA и HB по незащищенному каналу.

Посредник перехватывает HA и HB, но не может определить ни dA, ни dB, не решив задачу дискретного логарифмирования.

Алиса вычисляет S=dAHB (с помощью собственного закрытого ключа и открытого ключа Боба), а Боб вычисляет S=dBHA (с помощью собственного закрытого ключа и открытого ключа Алисы). S одинаков и для Алисы, и для Боба.  На самом деле:

S= dAHB =dA(dBG)= dB(dA G)= dBHA

Однако посреднику известны только HA и HB (вместе с другими параметрами области определения) и он не сможет найти общий секретный ключ S.

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