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

 

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

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

Вычисляем значение х, в выражении х * А=В 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