Криптографический протокол Диффи–Хеллмана (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
void dh_calc_public_key(void)
{
    mpz_powm(A, g, a, p);
}

Генерация закрытого ключа:

[-]
View Code C
/* Предполагается, что у нас есть некоторая процедура void* generate_key(size_t key_size_bytes),
    генерирующая случайное число размером 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):

[-]
View Code C
void dh_calc_shared_secret(mpz_t k, const mpz_t B) const
{
    mpz_powm(k, B, a, p);
}

Генерация чисел g и p (простая; функцию для генерации простых чисел Софи Жермен напишу в свободное время):

[-]
View Code C
void generate_prime(size_t size_bytes, mpz_t result)
{
    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 должны совпадать
Добавить в закладки
  • del.ici.ous
  • Digg
  • Furl
  • Google
  • Simpy
  • Spurl
  • Y! MyWeb
  • БобрДобр
  • Мистер Вонг
  • Яндекс.Закладки
  • Текст 2.0
  • News2
  • AddScoop
  • RuSpace
  • RUmarkz
  • Memori
  • Закладки Google
  • Писали
  • СМИ 2
  • Моё Место
  • Сто Закладок
  • Ваау!
  • Technorati
  • RuCity
  • LinkStore
  • NewsLand
  • Lopas
  • Закладки - I.UA
  • Connotea
  • Bibsonomy
  • Trucking Bookmarks
  • Communizm
  • UCA

Связанные записи

15
Апр
2008

Комментарии к статье «Реализация криптографического протокола Диффи-Хеллмана обмена ключами с использованием GMP» (3)  »

  1. Vladimir says:

    Подсмотрено у Mozilla: коррекция для dh_generate_p_g().

    Пусть p — сгенерированное безопасное простое число. Тогда q = (p-1)/2 — число Софи Жермен. Генерируем случайное число g, принадлежащее интервалу [2; p-1].

    [-]
    View Code C
    do {
        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);

    Я код еще не тестировал, но выглядит он довольно интересно :-)

  2. Vladimir says:

    Обещанная генерация безопасных простых чисел.

    Внимание: случайное число будет криптографически безопасным лишь в том случае, если для его генерации использовался криптографически безопасный генератор случайных чисел.

    Я привожу только базовый код, без всяких лишних проверок.

    [-]
    View Code C
    void generate_prime(size_t size_bytes, mpz_t result)
    {
        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;
            }
        }
    }
  3. Vladimir says:

    Еще один (дешевый) вариант проверки числа на простоту: использование теста на псевдо-простоту, основанного на малой теореме Ферма:

    [-]
    View Code C
    int fermat_test(mpz_t a, unsigned int w)
    {
        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 проверяемое число тестируется с двойкой:

    [-]
    View Code C
    if (0 == fermat_test(value_being_tested, 2)) {
    //Составное число
    }

Подписаться на RSS-ленту комментариев к статье «Реализация криптографического протокола Диффи-Хеллмана обмена ключами с использованием GMP» Trackback URL: http://blog.sjinks.org.ua/security/102-diffie-hellman-key-exchange-implementation-with-gmp/trackback/

Оставить комментарий к записи «Реализация криптографического протокола Диффи-Хеллмана обмена ключами с использованием GMP»

Вы можете использовать данные тэги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Оставляя комментарий, Вы выражаете своё согласие с Правилами комментирования.

Подписаться, не комментируя