Циклическая группа G порядка p

Циклическая группа G порядка p

В дискретных логарифмах, используемых в методах Диффи-Хеллмана и Эль-Гамаля, мы используем форму:

Y = gˣ (mod p)

и где p - простое число. Значения h будут в диапазоне от 0 до p-1. Это определяется как конечное поле (ℤp). Если использовать простое число 13, мы получим значения 0, 1… 12.

Но как мы можем быть уверены, что каждое значение x (от 0 до p-1) даст уникальный результат Y?

Циклическая группа G порядка p

Читая о криптографии, встречали ли вы когда-нибудь термин циклическая группа G порядка p с генератором g? Мы надеемся, что эта статья объяснит, что это значит.

Итак, с дискретными логарифмами и методом Диффи-Хеллмана мы получаем:

Y = gˣ (mod p)

где у нас есть значение генератора (g) и простое число p. Проблема в том, что, хотя мы знаем Y, g и p, чрезвычайно сложно определить x значение, если мы используем большое простое число. Один из методов - это бэби-шаг, гигантский шаг [здесь].

Итак, можем ли мы использовать любое значение g и должно ли оно быть как можно большим? Ответ на оба эти вопроса - «Нет!». Если выбрать простое число 7, а затем выбрать значения g 2, 3, 4… 9, а затем вычислить результаты, мы получим:

Теперь посмотрим на g = 2, мы получим на выходе 2, 4, 1, 2, 4… для значений последовательности x = 1, 2,… 6. Это означает, что мы не получаем уникального вывода для значений от 1 до 6 (где максимальное значение будет шесть, поскольку мы берем модуль 7). Но посмотрите на g = 3, мы получим 3 (3¹ mod 7), 2 (3² mod 7), 6 (3³ mod 7), 4 (3⁴ mod 7), 5 (3⁵ mod 7). , и 1 (3⁶ mod 7), что означает, что мы получаем уникальное значение для всех возможных выходов от 1 до 6, которое затем повторяется. Для простого числа 7 допустимые значения g - 3 и 5.

Но, чтобы продемонстрировать принцип, я проделал длинный путь, так как мне узнать все возможные значения G для данного простого числа (p)? Вот хороший простой метод на Python, который я создал для тестирования до p):

import sys
import random
p=11
def getG(p):
  for x in range (1,p):
	rand = x
	exp=1
	next = rand % p
	while (next <> 1 ):
		next = (next*rand) % p
		exp = exp+1
		
	if (exp==p-1):
		print rand
print getG(p)

Вы можете попробовать здесь:

Вот быстрая демонстрация