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

Пример совместного использования 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 = g^x mod p.

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

1. Выбор случайного числа k из диапазона (0; q).
2. Вычисление r = (g^k 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 = ((g^u₁y^u₂) mod p) mod q
5. Если v = r, то подпись верна.

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

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

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

1. Вычисление u₁ и u₂.
2. Вычисление g^u₁ mod p и y^u₂ mod p.

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

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