Ars Longa, Vita Brevis

Как реализовать протокол Диффи-Хеллмана на C с использованием библиотеки GMP

Криптографический протокол Диффи–Хеллмана (Diffie-Hellman Key Exchange) — алгоритм, позволяющий двум сторонам получить общий секретный ключ, используя частично защищенный канал связи. Под частично защищенным понимается канал, данные в котором защищены от модификации, но не от прослушивания (как утверждает Wikipedia, такие условия имеют место довольно часто).

В данной статье я приведу реализацию криптографического протокола Диффи-Хеллмана на языке С с использованием библиотеки GMP.

Рассмотрим неформальное определение алгоритма.

Предположим, что обоим абонентам известны некоторые два числа g и p. Эти числа могут быть известны всем заинтересованным лицам (иными словами, значения не являются секретными). Для создания секретного ключа оба абонента генерируют большие случайные числа: первый абонент — число a, второй абонент — число b. Затем первый абонент вычисляет значение A = gamod p и пересылает его второму, а второй вычисляет B = gbmod p и передаёт первому. Злоумышленник может получить оба этих значения, но модифицировать их по условию не может. На втором этапе первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение Bamod p = gabmod p, а второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение Abmod p = gabmod p. В результате оба абонента получат одно и то же число: K = gabmod p, которое может быть использовано в качестве секретного ключа, поскольку здесь злоумышленник встретится со практически неразрешимой за разумное время проблемой вычисления gabmod p по перехваченным gamod p и gbmod p, если числа g, p, a, b выбраны достаточно большими.

В практических реализациях, для a и b используются числа порядка 10100 и p порядка 10300. Число g не должно быть большим и обычно имеет значения 2 или 5.

Отмечу, что числа g и p должны быть простыми.

Рекомендуется, чтобы число p было безопасным простым числом, то есть p = 2q+1, где q — простое число (иными словами, q — простое число Софи Жермен).

Переходим к коду. Надеюсь, это поможет студентам СевНТУ специальности "Компьютерные системы и сети", изучающим дисциплину "Защита информация в компьютерных сетях" или как там она сейчас называется.

Процедура инициализации:

[-]
View Code C
mpz_t p; /* Public prime number */
mpz_t g; /* Public base */
mpz_t a; /* Private key */
mpz_t A; /* Public key */

void dh_init(void)
{
    mpz_init(p);
    mpz_init(g);
    mpz_init(a);
    mpz_init(A);
}

Процедура финализации:

[-]
View Code C
void dh_done(void)
{
    mpz_clear(p);
    mpz_clear(g);
    mpz_clear(a);
    mpz_clear(A);
}

Вычисление открытого ключа (A = gamod p):

[-]
View Code C
<div cla