ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1598. DSA Attack

Time limit: 1.0 second
Memory limit: 64 MB

Background

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.

Problem

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).

Input

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.

Output

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.

Sample

inputoutput
3 6 5 41 10 16 2
3 3
Problem Author: Prepared by Vladimir Yakovlev. Text by Wikipedia, the free encyclopedia.