Реализация криптографического протокола Диффи-Хеллмана обмена ключами с использованием GMP
Как реализовать протокол Диффи-Хеллмана на C с использованием библиотеки GMP
Криптографический протокол Диффи–Хеллмана (Diffie-Hellman Key Exchange) — алгоритм, позволяющий двум сторонам получить общий секретный ключ, используя частично защищенный канал связи. Под частично защищенным понимается канал, данные в котором защищены от модификации, но не от прослушивания (как утверждает Wikipedia, такие условия имеют место довольно часто). В данной статье я приведу реализацию криптографического протокола Диффи-Хеллмана на языке С с использованием [...]
← Вернуться к полной версии записи «Реализация криптографического протокола Диффи-Хеллмана обмена ключами с использованием GMP»…
Автор: Vladimir; опубликовано в: C/C++, Безопасность; метки: C/C++, Diffie-Hellman, GMP, алгоритмы, закрытый ключ, обмен ключами, открытый ключ, простые числа, Софи ЖерменАпр
2008
Комментарии к статье «Реализация криптографического протокола Диффи-Хеллмана обмена ключами с использованием GMP» (5) »
Пожалуйста, не используйте эту форму для комментирования! Данная форма предназначена исключительно для ботов.
Оставить комментарий к записи «Реализация криптографического протокола Диффи-Хеллмана обмена ключами с использованием GMP»
गते गते पारगते पारसंगते बोधि स्वाहा
Меня зовут Владимир, я программист-фрилансер, специализирующийся на 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 проверяемое число тестируется с двойкой:
//Составное число
}
[...] Год назад я писал о простых числах Софи Жермен. [...]
[...] реализации: Реализация криптографического протокола Диффи-Хеллма… Еще одна реализация на [...]