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

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

Цели работы:

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

Задачи:

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

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

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

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

y² + a₁xy + a₃y = x³ + a₂x² + a₄x + a₆

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

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

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

y² (mod p) = x³+ax+b(mod p).

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

4a³ + 27b² (mod p) ≠ 0. 

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

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

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

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

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

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

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

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

Правило 4. Правило сложения двух точек. Если Р(х₁, у₁), а Q(x₂,y₂), где P≠Q, x₁≠x₂ , то сумма двух точек Р+Q равна третьей точке с координатами: (х₃,y₃) = (х₁,y₁)+(х₂,y₂) , где координаты (х₃,y₃) определяются по формулам:

x₃  = α² - x₁ - x₂(mod p),

y₃ = α(x₁ – x₂ ) - y₁(mod p),

Где α = (y₂ - y₁)/(x₂ - x₁), если P≠Q или α = (3x₁² – a)/(2y₁), если P=Q.

Правило 5. Правило удвоения точки. Если P(x₁,y₁), причем у₁≠0, то 2Р=2(х₁,у₁)=(х₃,у₃), где координаты (х₃,у₃), находятся по формулам: 

x₃ = α² - 2x₁, 

y₃ = α(x₁ – x₃) - y₁, 

α = (3x₁² + a)/(2y₁).

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

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

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

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

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

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

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

– конечное поле F_p ; 

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

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

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

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

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

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

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

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

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

– каждому блоку поставить в соответствие определенную точку M_i кривой E_p(a,b) , с координатами (x_i,y_i);

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

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

– вычисляется точка kP^B=(x₁,y₁); 

– вычисляется точка kQ^B=(x₂,y₂);

– вычисляется сумма двух точек: шифруемой M₁=(x_i,y_i) и точки  kQ^B=(x₂,y₂); 

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

E₀={(x₁,y₁)} 

E₁={(x₂,y₂)}

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

– координаты точки-подсказки kP^B умножаются на свой закрытый ключ d^B, то есть вычисляется точка d^BkP=d^B(x₁,y₁);

– полученный результат вычитается из координат криптограммы E₁, в результате вычитания остаются координаты исходной точки M₁ : M₁+kQ^B-d^BkP^B=M₁+k(d^BP^B)-d^B(kP^B)=M₁. 

В эллиптической криптографии нет действия вычитания точек, поэтому особо следует отметить, что вычитание здесь необходимо заменять на сложение с взаимно обратной точкой (d^BkP^B), координаты которой равны (x₁,-y₁) (см. правило 3).

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

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

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

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

Сначала Алиса и Боб генерируют собственные закрытые и открытые ключи. У Алисы есть закрытый ключ d_A и открытый ключ H_A=d_AG, у Боба есть ключи d_B и H_B=d_BG.

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

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

Посредник перехватывает H_A и H_B, но не может определить ни d_A, ни d_B, не решив задачу дискретного логарифмирования.

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

S= d_AH_B =d_A(d_BG)= d_B(d_A G)= d_BH_A

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

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