Пример совместного использования GMP и OpenMP для повышения производительности

DSA — алгоритм для создания и проверки электронной подписи с использованием открытого ключа, основанный на вычислительной сложности взятия логарифмов в конечных полях.

Алгоритмы, использующие “большие числа” — всегда хорошие кандидаты на распараллеливание. Дело в том, что даже при современной мощности процессоров многие задачи являются довольно сложными с вычислительной точки зрения. Хотя криптографические алгоритмы, как правило, очень тяжело поддаются распараллеливанию (например, когда значение, вычисленное на предыдущем шаге алгоритма, используется на текущем шаге), чисто математические задачи все же дают определённый простор для распараллеливания.

В данной статье рассмотрим возможность распараллеливания алгоритма DSA.

Кратко рассмотрим алгоритмы, затем перейдём к их анализу с целью нахождения блоков, которые можно распараллелить.

Алгоритмы работают не с исходным сообщением, а с его цифровым дайджестом, сгенерированным при помощи хэш-функции H(x).
Алгоритмы используют следующие параметры:

  • простое число q, размерность которого в битах совпадает с размерностью значений, генерируемых хэш-функцией;
  • простое число p, такое, что (p-1) mod q = 0. Размерность данного числа задаёт криптостойкость системы и должна быть не менее 1024 бит;
  • число g, такое, что его мультипликативный порядок по модулю p равен q (g = h(p-1)/q mod p, 1<h<p-1, g ≠ 1);
  • закрытый ключ x — число в интервале (0; q);
  • открытый ключ y, y = gx mod p.

Подпись (rs) сообщения H генерируется следующим образом:

  1. Выбор случайного числа k из диапазона (0; q).
  2. Вычисление r = (gk mod p) mod q.
  3. Вычисление s = (k⁻¹(H + xr)) mod q.
  4. В маловероятном случае, когда r или s равны нулю, переход к шагу 1.

Проверка подписи (r, s) сообщения H осуществляется следующим образом:

  1. Вычисление w = s⁻¹ mod q.
  2. Вычисление u₁ = Hw mod q.
  3. Вычисление u₂ = rw mod q.
  4. Вычисление v = ((gu₁yu₂) mod p) mod q
  5. Если v = r, то подпись верна.

Я ранее писал, что технология OpenMP наиболее эффективна, если код включает длительные циклы без зависимостей. Но в реализации алгоритмов создания и проверки подписи циклов нет. К счастью, OpenMP не ограничивает нас только циклами.

Среди конструкций для разделения совместной работы есть директива SECTIONS, указывающая, что заключённые в неё разделы (секции) будут разделены между всеми потоками. Каждая секция выполняется только одним потоком, при этом различные секции могут быть выполнены различными потоками.

В этом случае для распараллеливания необходимо найти выражения, которые могут быть вычислены независимо друг от друга. Например, для алгоритма генерации подписи это будут вычисление r и k⁻¹ mod q, для алгоритма проверки подписи можно распараллелить два блока (которые будут выполняться последовательно):

  1. Вычисление u₁ и u₂.
  2. Вычисление gu₁ mod p и yu₂ mod p.

А в алгоритме генерации ключей распараллелить можно только генерацию простых чисел (два простых числа будут вычислены со скоростью одного).

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

[-]
View Code C
struct dsa_pubkey {
    mpz_t p;    /* prime */
    mpz_t q;    /* group order */
    mpz_t g;    /* group generator */
    mpz_t y;    /* g^x mod p */
};

struct dsa_privkey {
    struct dsa_pubkey public;
    mpz_t x;    /* secret exponent */
};

void dsa_sign(mpz_t r, mpz_t s, mpz_t hash, struct dsa_privkey* key)
{
    mpz_t k;
    mpz_t kinv;
    mpz_t tmp;

    gmp_randstate_t state;

    unsigned int nlimbs;

    mpz_init(k);
    mpz_init(kinv);
    mpz_init(tmp);
    gmp_randinit_default(state);

    nlimbs = mpz_size(key->public.q);

    while (1) {
        do {
            mpz_urandomb(k, state, nlimbs * sizeof(mp_limb_t) * 8);
        } while (mpz_cmp(k, key->public.q) >= 0);

        #pragma omp parallel sections
        {
            #pragma omp section
            {
                /* r = g^k mod p mod q */
                mpz_powm(r, key->public.g, k, key->public.p);
                mpz_mod(r, r, key->public.q);
            }

            #pragma omp section
            {
                /* Kinv = k^-1 mod q */
                mpz_invert(kinv, k, key->public.q);
            }
        }

        if (0 == mpz_cmp_ui(r, 0)) {
            continue;
        }

        /* s = (Kinv * (x*r + hash)) mod q */
        mpz_mul(tmp, key->x, r);
        mpz_add(tmp, tmp, hash);

        mpz_mul(s, kinv, tmp);
        mpz_mod(s, s, key->public.q);

        if (0 == mpz_cmp_ui(s, 0)) {
            continue;
        }

        break;
    }

    mpz_clear(k);
    mpz_clear(kinv);
    mpz_clear(tmp);
}

int dsa_verify(mpz_t r, mpz_t s, mpz_t hash, struct dsa_privkey* key)
{
    mpz_t v;
    mpz_t w;
    mpz_t u1;
    mpz_t u2;
    int res;

    if (mpz_cmp(r, key->public.q) >= 0 || mpz_cmp(s, key->public.q) >= 0) {
        return 0;
    }

    mpz_init(w);
    mpz_invert(w, s, key->public.q); /* w = (s^(-1)) mod q */

    #pragma omp parallel sections
    {
        #pragma omp section
        {
            /* u1 = H*w mod q */
            mpz_init(u1);
            mpz_mul(u1, hash, w);
            mpz_mod(u1, u1, key->public.q);
        }

        #pragma omp section
        {
            /* u2 = r*w mod q */
            mpz_init(u2);
            mpz_mul(u2, r, w);
            mpz_mod(u2, u2, key->public.q);
        }
    }

    #pragma omp parallel sections
    {
        #pragma omp section
        {
            /* v = g^u1 mod p */
            mpz_init(v);
            mpz_powm(v, key->public.g, u1, key->public.p);
            mpz_clear(u1);
        }

        #pragma omp section
        {
            /* w = y^u2 mod p */
            mpz_powm(w, key->public.y, u2, key->public.p);
            mpz_clear(u2);
        }
    }

    mpz_mul(v, v, w); /* v = (g^u1 mod p)*(y^u2 mod p) */
    mpz_mod(v, v, key->public.p);
    mpz_mod(v, v, key->public.q);

    res = (0 == mpz_cmp(v, r)) ? 1 : 0;

    mpz_clear(w);
    mpz_clear(v);

    return res;
}
Добавить в закладки

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

3
Май
2009

Комментарии к статье «Параллельная версия генерации и проверки подписи по алгоритму DSA» (1)  »

  1. progg.ru says:

    Параллельная версия генерации и проверки подписи по алгоритму DSA | Ars Longa, Vita Brevis…

    Thank you for submitting this cool story - Trackback from progg.ru…

Подписаться на RSS-ленту комментариев к статье «Параллельная версия генерации и проверки подписи по алгоритму DSA» Trackback URL: http://blog.sjinks.org.ua/security/552-parallel-dsa-signature-generation-verification-with-openmp/trackback/

Оставить комментарий к записи «Параллельная версия генерации и проверки подписи по алгоритму DSA»

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

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

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