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.
The first phase of key generation is a choice of algorithm parameters which may be shared between different users of the system.
- 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 approved cryptographic hash function H (for example SHA-2). The hash output must be an N-bit integer.
- Choose an N-bit prime q.
- 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.
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 = g x mod p.
- Public key is (p, q, g, y). Private key is x.
Let m be the message and H(m) the hash value of that message.
- Generate a random per-message number 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) + x ∙ r) mod q.
- In the unlikely case that s = 0, start again with a different random k.
- The signature is (r, s).
- 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 = r ∙ w mod q.
- Calculate v = ((gu1 ∙ yu2) 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 only line contains integers N, L, q, p, g, y, H(m). The following limitations are applied:
- 3 ≤ N ≤ 36;
- 6 ≤ L ≤ 60; L ≥ N + 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.
Output the integers r and s separated with space. The pair (r, s) must be a 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
Problem Author: Prepared by Vladimir Yakovlev. Text by Wikipedia, the free encyclopedia.