Открытое распределение ключей

Кроме принципа построения криптосистемы с открытым ключом, Диффи и Хеллмэн в той же работе предложили еще одну новую идею – открытое распределение ключей. Они задались вопросом: можно ли организовать такую процедуру взаимодействия абонентов A и B по открытым каналам связи, чтобы решить следующие задачи:

1) вначале у A и B нет никакой общей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) у A и B появляется, т.е. вырабатывается;

2) противник, который перехватывает все передачи информации и знает, что хотят получить A и B, тем не менее не может восстановить выработанный общий ключ A и B.

Диффи и Хеллмэн предложили решать эти задачи с помощью функции F (x) = α ^x (mod p), где p – большое простое число, x – произвольное натуральное число, α – некоторый примитивный элемент поля GF (p).

Примитивным называется такой элемент a из GF (p), что каждый элемент поля, за исключением нуля, может быть представлен в виде степени a. Можно доказать, хотя это и не просто, что примитивный элемент всегда существует.

Общепризнано, что инвертирование функции α ^x (mod p), т.е. дискретное логарифмирование, является трудной математической задачей (см. этюд 3.4).

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

Числа p и α считаются общедоступными.

Абоненты A и B независимо друг от друга случайно выбирают по одному натуральному числу – скажем x (A) и x (B). Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:

y (A)= α ^{x (A)}(mod p), y (B)= α ^{x (B)}(mod p).

Потом они обмениваются этими элементами по каналу связи. Теперь абонент A, получив y (B) и зная свой секретный элемент x (A), вычисляет новый элемент

y (B) ^{x (A)}(mod p)=(α ^{x (B)}) ^{x (A)}(mod p).

Аналогично поступает абонент B:

y (A) ^{x (B)}(mod p)=(α ^{x (A)}) ^{x (B)}(mod p).

Из свойств поля следует, что тем самым у A и B появился общий элемент поля, равный α ^{x (A) x (B)}. Этот элемент и объявляется общим ключом A и B.

Из описания протокола видно, что противник знает p, α, α ^{x (A)}, α ^{x (B)}, не знает x (A) и x (B) и хочет узнать a ^{x (A) x (B)}. В настоящее время нет алгоритмов действий противника, более эффективных, чем дискретное логарифмирование, а это – трудная математическая задача. (Рекомендуем самостоятельно найти за противника общий ключ, используя алгоритм дискретного логарифмирования и не принимая во внимание вопросы его сложности.)