1598. Атака на DSA @ Timus Online Judge

1598. Атака на DSA

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

DSA (англ. Digital Signature Algorithm – алгоритм цифровой подписи) – это криптографический алгоритм с открытым ключом для создания цифровых подписей. Подпись создается конфиденциально, но может быть проверена публично. Это значит, что только один субъект может создать подпись, но любой может проверить ее правильность. Алгоритм основан на вычислительной сложности нахождения логарифмов в конечных полях.

Генерация параметров

Первый этап генерации ключей – это выбор параметров алгоритма, которые могут быть использованы для нескольких пользователей системы.

Определите длины ключа L и N. Это основной показатель криптографической стойкости ключа. Минимальные рекомендуемые значения для L и N – 1024 и 160 соответственно.
Выберите подходящую криптографическую хеш-функцию H (например, SHA-2). Результат хеш-функции должен быть N-битным числом.
Выберите N-битное простое число q.
Выберите L-битный простой модуль p таким образом, чтобы p − 1 было кратно q.
Выберите число g такое, что его мультипликативный порядок по модулю p равен q. Это можно сделать, если задать g = h ^{(p − 1) / q} mod p для некоторого произвольного h (1 < h < p − 1) и повторить попытку с другим h, если результат получится равным 1. Большинство вариантов h приводит к пригодному для использования g; обычно используется h = 2.

Генерация ключей для каждого пользователя

На втором этапе для выбранного набора параметров алгоритма вычисляются секретный и открытый ключи для одного пользователя:

Некоторым случайным методом выберите x, где 0 < x < q.
Вычислите y = g ^x mod p.
Открытый ключ – это (p, q, g, y). Секретный ключ – это x.

Подпись

Пусть m будет сообщением, а H(m) – значением хеша от этого сообщения.

Сгенерируйте случайное число k, где 0 < k < q.
Вычислите r = (g^k mod p) mod q.
В маловероятном случае, если r = 0, начните сначала с другого случайного k.
Вычислите s = k⁻¹(H(m) + x ∙ r) mod q.
В маловероятном случае, когда s = 0, начните сначала с другого случайного k.
Подпись – это пара (r, s).

Проверка подписи

Отклоните подпись, если не соблюдается ограничение 0 < r < q или 0 < s < q.
Вычислите w = s⁻¹ mod q.
Вычислите u₁ = H(m) ∙ w mod q.
Вычислите u₂ = r ∙ w mod q.
Вычислите v = ((g^u₁ ∙ y^u₂) mod p) mod q.
Подпись действительна, если v = r.

Задача

Имея открытый ключ (q, p, g, y) и значение хеша H(m), необходимо создать действительную подпись (r, s).

Исходные данные

Единственная строка содержит целые числа N, L, q, p, g, y, H(m). Действуют следующие ограничения:

3 ≤ N ≤ 36;
6 ≤ L ≤ 60; L ≥ N + 3;
q – в точности N-битное целое число;
p – в точности L-битное целое число;
1 < g < p;
0 ≤ y < p;
H(m) – N-битное целое число.

Гарантируется, что открытый ключ сгенерирован так, как описано выше.

Результат

Выведите целые числа r и s, разделенные пробелом. Пара (r, s) должна быть действительной DSA-подписью для открытого ключа (q, p, g, y). Существует несколько действительных подписей, вы можете вывести любую из них.

Пример

исходные данные	результат
3 6 5 41 10 16 2	3 3

Автор задачи: Подготовил Владимир Яковлев