Криптографический протокол Диффи–Хеллмана (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 — простое число Софи Жермен).
Переходим к коду. Надеюсь, это поможет студентам СевНТУ специальности "Компьютерные системы и сети", изучающим дисциплину "Защита информация в компьютерных сетях" или как там она сейчас называется.
Процедура инициализации:
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);
}
Процедура финализации:
{
mpz_clear(p);
mpz_clear(g);
mpz_clear(a);
mpz_clear(A);
}
Вычисление открытого ключа (A = gamod p):
{
mpz_powm(A, g, a, p);
}
Генерация закрытого ключа:
генерирующая случайное число размером key_size_bytes байт и возвращающая указатель на
сгенерированное число. Это число должно быть криптографически безопасным, и если у меня
будет время, я расскажу в следующих статьях, как генерировать такие числа */
void dh_generate_private_key(size_t key_size_bytes)
{
void* key = generate_key(key_size_bytes);
mpz_import(a, 1, -1, key_size_bytes, -1, 0, key);
free(key);
}
Вычисление общего секретного ключа по закрытому ключу и ключу, переданному от другого абонента (Bamod p или Abmod p):
{
mpz_powm(k, B, a, p);
}
Генерация чисел g и p (простая; функцию для генерации простых чисел Софи Жермен напишу в свободное время):
{
unsigned char* r = (unsigned char*)generate_key(size_bytes);
r[size_bytes-1] |= (unsigned char)0xC0;
r[0] |= (unsigned char)1; /* Если число простое, оно как минимум нечетное */
mpz_import(result, 1, -1, size_bytes, -1, 0, (const void*)r);
while (0 == mpz_probab_prime_p(result, 10)) {
mpz_add_ui(result, result, 2);
}
}
void dh_generate_p_g(size_t size_bytes)
{
generate_prime(size_bytes, p);
mpz_set_ui(g, 5);
}
Использование: пусть у нас есть два абонента, по традиции Alice и Bob.
| Alice | Bob |
|---|---|
mpz_t k;
mpz_init(k);
dh_init();
|
|
dh_generate_p_g(SIZE_PG);
transmit(p); /* Абстрактная процедура для передачи числа абоненту */
transmit(g);
|
|
dh_generate_private_key(SIZE_AB);
|
receive(p); /* Абстрактная процедура для приёма числа от абонента */
receive(g);
dh_generate_private_key(SIZE_AB);
|
dh_calc_public_key();
transmit(A);
|
dh_calc_public_key();
transmit(A); /* для Alice это B */
|
receive(A); /* B, которое передал Bob */
dh_calc_shared_secret(k, A);
|
receive(A);
dh_calc_shared_secret(k, A);
|
| Ключи k Alice и Bob должны совпадать | |
Меня зовут Владимир, я программист-фрилансер, специализирующийся на Web-программировании и програмировании под Linux.
По совместительству занимаюсь администрированием LAMP/LNMP-серверов и техническим переводом.
Подсмотрено у Mozilla: коррекция для
dh_generate_p_g().Пусть p — сгенерированное безопасное простое число. Тогда q = (p-1)/2 — число Софи Жермен. Генерируем случайное число g, принадлежащее интервалу [2; p-1].
if (mpz_cmp_ui(p, 2) < 0 || mpz_cmp(p, g) > 0) {
mpz_set(g, 2); //Mozilla устанавливает g в 3
}
mpz_powm(x, g, q, p);
if (0 != mpz_cmp_ui(x, 1)) {
//Мы нашли число g
break;
}
mpz_add_ui(g, g, 1);
} while(1);
Я код еще не тестировал, но выглядит он довольно интересно
Обещанная генерация безопасных простых чисел.
Внимание: случайное число будет криптографически безопасным лишь в том случае, если для его генерации использовался криптографически безопасный генератор случайных чисел.
Я привожу только базовый код, без всяких лишних проверок.
{
mpz_t q;
mpz_init(q);
while (1) {
unsigned char* r = (unsigned char*)generate_key(size_bytes);
r[size_bytes-1] |= (unsigned char)0x40;
r[0] |= (unsigned char)1; /* Если число простое, оно как минимум нечетное */
mpz_import(q, 1, -1, size_bytes, -1, 0, (const void*)r);
while (0 == mpz_probab_prime_p(q, 10)) {
mpz_add_ui(q, q, 2);
}
//Число q сгенерировано, мы знаем, что оно простое.
//Теперь нам нужно убедиться, что число 2q+1 тоже является простым
mpz_mul_ui(result, q, 2);
mpz_add_ui(result, result, 1);
if (0 != mpz_probab_prime_p(result, 10)) {
//2q+1 тоже является простым, следовательно, q - число Софи Жермен,
//а p - безопасное простое число
break;
}
}
}
Еще один (дешевый) вариант проверки числа на простоту: использование теста на псевдо-простоту, основанного на малой теореме Ферма:
{
mpz_t base;
mpz_t test;
int res;
mpz_init(base);
mpz_init(test);
mpz_set_ui(base, w);
mpz_powm(test, base, a, a);
res = (0 == mpz_cmp(base, test)) ? 1 : 0;
mpz_clear(base);
mpz_clear(test);
return res;
}
В Mozilla проверяемое число тестируется с двойкой:
//Составное число
}