ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

## 1598. DSA Attack

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

### Вступление

The DSA (Digital Signature Algorithm) is a public-key cryptographic algorithm for creating digital signatures. The signature is created secretly but can be verified publicly. This means that only one subject can create a signature, but anyone can verify its correctness. The algorithm is based on the computational complexity of taking logarithms in finite fields.
Parameter generation
The first phase of key generation is a choice of algorithm parameters which may be shared between different users of the system.
• Choose an approved cryptographic hash function H (for example SHA-2). The hash output may be truncated to the size of a key pair.
• Decide on a key length L and N. This is the primary measure of the cryptographic strength of the key. The minimal recommended values for L and N are 1024 and 160.
• Choose an N-bit prime q. N must be less than or equal to the hash output length.
• Choose an L-bit prime modulus p such that p − 1 is a multiple of q.
• Choose g, a number whose multiplicative order modulo p is q. This may be done by setting g = h(p − 1) / q mod p for some arbitrary h (1 < h < p − 1), and trying again with a different h if the result comes out as 1. Most choices of h will lead to a usable g; commonly h = 2 is used.
Per-user key generation
Given a set of parameters, the second phase computes private and public keys for a single user:
• Choose x by some random method, where 0 < x < q.
• Calculate y = gx mod p.
• Public key is (p, q, g, y). Private key is x.
Signing
Let m be the message and H(m) the hash value of that message.
• Generate a random per-message value k where 0 < k < q.
• Calculate r = (gk mod p) mod q.
• In the unlikely case that r = 0, start again with a different random k.
• Calculate s = k−1(H(m) + xr) mod q.
• In the unlikely case that s = 0, start again with a different random k.
• The signature is (r, s).
Verifying
• Reject the signature if 0 < r < q or 0 < s < q is not satisfied.
• Calculate w = s−1 mod q.
• Calculate u1 = H(m) w mod q.
• Calculate u2 = rw mod q.
• Calculate v = ((gu1yu2) mod p) mod q.
• The signature is valid if v = r.

### Задача

Given the public key (q, p, g, y) and the hash value of the message H(m) you are to create a valid signature (r, s).

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

The single line of input contains integers N, L, q, p, g, y, H(m). The following limitations are applied:
• 3 ≤ N ≤ 36;
• 6 ≤ L ≤ 60, LN + 3;
• q is an exactly N-bit integer;
• p is an exactly L-bit integer;
• 1 < g < p;
• 0 ≤ y < p;
• H(m) is an N-bit integer.
The public key is guaranteed to be generated as described above.

### Результат

The single line of output should contain the integers r and s separated with space. The pair (r, s) must be valid DSA signature for the public key (q, p, g, y). There are multiple valid signatures, you may output any of them.

### Пример

исходные данныерезультат
3 6 5 41 10 16 2
3 3
Автор задачи: Prepared by Vladimir Yakovlev. Text by Wikipedia, the free encyclopedia.