Vnitrosemestrální písemka - MIN401 - jaro 2022 - 6. 4. 2022
Veškeré odpovědi musí být zdůvodněny a výpočty musí být doprovozeny komentářem. (Řešení sestávající pouze z odpovědí budou považována za opsaná a hodnocena 0 body.)
1. (3 body) Najděte všechna celá čísla, která vyhovují soustavě kongruencí
5x = 1    (mod 14), 17a: = 2    (mod 35), 5a; = 15    (mod 18).
2. (3.5 bodu) V Rabínově kryptosystému je soukromým klíčem dvojice prvočísel p = 7, q = 23. Veřejným klíčem je n = 161. Dešifrujte obdrženou zprávu C = 116 (tj. najděte všechny možnosti pro poslanou zprávu).
3. (3.5 bodu) Julie a Romeo komunikují šifrou Elgamal. Oba se dohodli na prvočísle p = 19 a na primitivním kořenu g = 10. Julie si za svůj tajný klíč zvolila číslo a = 11, Romeo má svůj tajný klíč b.
(a) Ověřte, že 10 je skutečně primitivní kořen modulo 19. [5 bodů]
(b) Jaký údaj poskytla Julie Romeovi? [5 bodů]
(c) Romeo posléze poslal Julii jako zprávu dvojici čísel (gb = 7, 4). Pomozte Julii s dešifrováním zprávy. [15 bodů]
Řešení a bodování:
1. [3 body] Třetí rovnici lze podělit pěti. Dostáváme jednodušší
x = 3    (mod 18).
Vezmeme jednu rovnici, vyřešíme, dosadíme do druhé, vyřešíme, dosadíme do třetí a dostaneme celkový výsledek. Prvně počítejme modulo 35:
Í7x=2   (mod 35), 34x = 4   (mod 35), x = 31   (mod 35).
Proto x = 35a + 31 dosadíme do prvé rovnice a počítáme modulo 14:
5(35a + 31)x = 1   (mod 14), 5(7a + 3) = l   (mod 14), 7a + 1 = 1   (mod 14),
7a = 0   (mod 14), dělení 7, a=0   (mod 2).
Tedy a = 26 a x = 35(26) + 31. Dosadíme do třetí kongruence a počítáme modulo 18:
35(26)+31 = 3 (mod 18),
706 + 31 = 3 (mod 18),
-26=8 (mod 18),
-6=4 (mod 9), dělení 2,
6=5 (mod 9).
Odtud 6 = 9c + 5 a dosazením do x dostaneme
x = 35(2(9c + 5)) + 31 = 630c + 350 + 31 = 630c + 381.
Bodování: Počítání modulo 35 za [0.8], počítání modulo 14 za [0.8], počítání modulo 18 za [0.8] a správný výsledek [0.6b]. Za každé chybné dělení strhnout [0.5b].
2. [3.5 bodu] Dešifrovaná zpráva M splňuje Z2 = C mod n. Takové jsou 4 a jsou ve tvaru
M = ázapQ ± bqP   mod n,
kde a, 6, P,Q jsou celá čísla splňující
1. ap + bq = 1,
2. P = mod p,
3. Q = mod q.
Pomocí algoritmu spočítáme a = 10, 6 = —3. Dále počítáme modulo 7
1162 = 42 = 16 = 2   mod 7.
Tedy P = 2. Počítáním modulo 23
1166 = l6 = 1   mod 23.
Tedy Q = 1. Proto
M = ±10 • 7 • 1 ± 3 • 23 • 2 = ±70 ± 138.
Dešifrovaná zpráva je jedna z následujících: 47, 68, 93, 114.
O správnosti výpočtu se můžeme přesvědčit tím, že ověříme platnost kongruencí
M2 = 116 = 4   mod 7, M2 ee 116=1   mod 23.
Bodování: Správný vzorec pro M [lb], výpočet čísel a, b [0.4b], výpočet P = mod p [0.2], výpočet
Q = M 4    mod q [lb], správné hodnoty M [0.5b]. Ověření správnosti není třeba provádět.
3. [3.5 bodu] (a) if(19) = 18 = 2 • 32. Proto 1018 = 1 mod 19. Počítáme modulo 19
106 ee 1003 ee 53 ee 6 • 5 ee 11,
109 ee 106 • 100 • 10 ee 11 • 5 • 10 ee 11 • 12 ee 8 • 7 ee 18.
Tedy 10 je primitivní kořen.
(b) Julie poskytla údaj
ga ee 1011 ee 109 • 100 ee (-1) • 5 ee 14,   mod 19.
(c) Romeo zašifroval zprávu M jako dvojici (gb,M(ga)b) = (7,4). Proto dešifrujeme takto
M ee M(ga)b • (ff6)°)_1 = 4 • (711)"1 ee 4 • (li)"1 ee 4 • 7 ee 9   mod 19.
Výpočet
711 = 495 • 7 ee ll5 • 7 ee (-8)5 • 7 ee -642 • 56 ee -72(-l) ee 11   mod 19.
Inverze k 11 mod 19 se najde jako číslo a takové, že lla+196 = 1 pro nějaké b. Jednoduše (a, b) = (7, —4). Inverze je tedy 7.
Bodování: (a) Za ip(19) a jeho rozklad [0.2], za každou mocninu [0.2b], celkem [0.4b]. (b) Postup [0.4b], mocnina [0.2]. (c) Správný vzorec [lb], mocnina [0.4b], inverze [0.4b], správný výsledek [0.5b].