Пример выполнения Задания3. Алгоритм Диффи-Хеллмана

Вариант № 15, группа 2091 (№ 1)

Номер в списке группы i = 15

Номер группы k = 1

P = 37

Открытый элемент P = 37. Найти примитивный элемент поля. Секретный ключ каждого участника i = 15, вычислить ключ обмена для участника с номером 35-15 = 20.

GF(37) = <0, 1, 2, 3, …, 35, 36, 37>

Найдем примитивный элемент поля GF(37).

Требуется найти такое число, принадлежащее интервалу [2,37], которое при возведении в 37-ю степень по модулю 37 будет давать в результате единицу. Если же единица будет получена раньше, чем при возведении в 36-ю степень, результаты возведения в степень начнут повторяться, и через выбранный элемент не удастся представить все элементы поля. Исходя из таких соображений, получаем несложный алгоритм нахождения примитивных элементов поля GF(37).

Алгоритм нахождения примитивных элементов поля GF(37).

int _tmain(int argc, _TCHAR* argv[])

{

long int mem, i, j, num, deg, modul, res;

unsigned char mas[38];

deg = 0; modul = 37; mem = 2;

while (mem < 36)

{

num = mem; deg = 0;

while (deg!= 36)

{

res = 1; deg = 0;

for (i = 0; i < 36; i++) mas[i] = 0;

do

{

res = res*num; res = res % modul;

deg++; mas[deg] = res;

}

while(res!= 1);

num++;

}

std::cout << num-1 << std::endl;

for (i = 0; i < 36; i++)

{

for (j = 0; j < 36; j++)

{

if ((i!= j) && (mas[j] == mas[i]))

std::cout << "Wrong" << std::endl;

}

mem = num;

}

}

}

В результате выполнения программы получим следующие значения:

2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35

Выберем значение α = 2.

Секретный ключ участника А: X_A = 15.

Секретный ключ участника B: Y_B = 35-15 = 20.

Открытый ключ участника А:

Открытый ключ участника B:

Обменный ключ участника А:

Обменный ключ участника B:

Значения обменного ключа для А и В совпадают.

Обменный ключ: K = 26

Поиск по сайту: