Dostawca urzadzen uzywa schematu podpisu DSA do cyfrowego podpisywania aktualizacji konfiguracji. Parametry systemu to:

p = 0x8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5
d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
q = 0xc773218c737ec8ee993b4f2ded30f48edace915f
g = 0x626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e
71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
a klucz publiczny dostawcy to

y = 0xeb772a91db3b69af90c5da844d7733f24270bdd11aac373b26f58ff528ef2678
94b1e746e3f20b8b89ce9e5d641abbff3e3fa7dedd3264b1b313d7cd569656c

Urzadzenie otrzymalo nastepujace trzy wiadomosci z nastepujacymi podpisami: 

H(m0) = SHA-1("Sunday") = 0xbc5dd045b8623ddfc4bd0bce98ca5fda42accf88
r0 = 0x8f4378d1b2877d8aa7c0687200640d4bba72f2e5
s0 = 0x105018fcef21539e573a54109f927ebae7c93416
H(m1) = SHA-1("Monday") = 0x932eeb1076c85e522f02e15441fa371e3fd000ac
r1 = 0x8f4378d1b2877d8aa7c0687200640d4bba72f2e5
s1 = 0x696de4ffb102249aef907f348fb10ca704a4b186
H(m2) = SHA-1("Tuesday") = 0x42e43b612a5dfae57ddf5929f0fb945ae83cbf61
r2 = 0x8f4378d1b2877d8aa7c0687200640d4bba72f2e5
s2 = 0x25f87cbb380eb4d7244963e65b76677bc968297e

(a) Sprawdz, ktore z tych wiadomosci pochodza od dostawcy (wskazowka: tylko dwie z nich).

(b) Jaki blad popelnil dostawca, generujac te podpisy? Uzyj tego bledu, aby sfalszowac podpis dla wiadomosci:
H(m3) = SHA-1("Wednesday")
Wskazowka: odejmij od siebie rownania definiujace s1 oraz s2.

##################
Uwaga:
w powyzszym zadaniu uzywamy oznaczen z https://en.wikipedia.org/wiki/Digital_Signature_Algorithm.
Skrot algorytmu:

**Algorytm podpisu DSA - etapy i wzory:**

**1. Generowanie kluczy DSA:**

* Wybierz: liczby pierwsze p, q, gdzie q \mid (p - 1)
* Wybierz: g = h^{(p-1)/q} mod p, gdzie 1 < h < p-1, g > 1
* Wybierz: klucz prywatny x < q
* Oblicz: klucz publiczny y = g^x mod p


**2. Generowanie podpisu:**

* Losuj: k \in \{1, \dots, q-1\}
* Oblicz: r = (g^k mod p) mod q
* Oblicz: s = k^{-1} * (H(m) + x * r) mod q

Podpis: (r, s)

---

**3. Weryfikacja podpisu:**

* Sprawdz: 0 < r < q i 0 < s < q
* Oblicz: w = s^{-1} mod q
* Oblicz: u_1 = H(m) * w mod q
* Oblicz: u_2 = r * w mod q
* Oblicz: v = ((g^{u_1} * y^{u_2}) mod p) mod q

Podpis poprawny gdy: v = r