4. cvičení z MIN401 — soustavy kongruencí,
Příklad 1:   Vyřešte následující kongruence:
(i) 210x = 40 (mod 212).
(ii) 325x = 694 (mod 471).
Příklad 2:   Vyřešte následující soustavy kongruenci:
(i) 2x = 3 (mod 7), x = 8 (mod 15).
(ii) x = 3 (mod 10), x = 8 (mod 15), x = 5 mod 84.
(iii) 21a: = 27 (mod 24), 26x = 10 (mod 25), 27x = 30 (mod 17).
Příklad 3:   Najděte inverzní prvek k číslu 157 modulo 2475.
Příklad 4:   [10.32, 10.33] Najděte primitivní kořeny modulo 8, 11, 20, 26, 41 a 412.
Příklad 5: Šifrou RSA s veřejným klíčem n = 95 a e = 55 bylo posláno číslo Z = 42. Šifru prolomte a určete zaslanou zprávu M G {1,2,..., 94}.
Příklad 6: Veřejný klíč Honzy pro RSA šifru je (91, 23). Zachytili jste jemu určenou zprávu 3. Dekódujte ji.
Příklad 7: V šifrovacím systému RSA s veřejným klíčem skládajícím se z modulu n = 2021 a exponentu e = 11 došlo k prozrazení faktorizace n = p ■ q = 43 • 47. S její pomocí dešifrujte zprávu c = 21. Při výpočtu mocniny cd mod 2021 počítejte zvlášť modulo 43 a modulo 47 a tyto mezivýsledky pak dejte dohromady.
[Řešeni: d = 527, cd = 11 mod 43, cd = 34 mod 47, zpráva je 269. ]
Příklad 8: V ElGamalově šifrovacím systému si Alice zvolila veřejný klíč sestávající z prvočísla p = 41, primitivního kořene g = 11 a jeho mocniny ga (kde exponent a = 10 je soukromý). Bob poslal Alici svůj veřejný klíč gb = 22 a zašifrovanou zprávu c = 6. Pomozte Alici zprávu dešifrovat?
[Řešeni: gab = 22" = 2210 = 32 mod 41. Inverze k 32 mod AI je d = 9. Zpráva je m = 6 • 9 = 13 mod 41. ]
Příklad 9: V ElGamalově šifrovacím systému si Alice zvolila veřejný klíč sestávající z prvočísla p = 997, primitivního kořene g = 11 a jeho mocniny gx (kde exponent x = 23 je soukromý). Bob si pro komunikaci s Alicí zvolil soukromý klíč y = 25 a poslal jí svůj veřejný klíč gy. Pomocí společného soukromého klíče gxy pak zašifroval zprávu m a výslednou zprávu c = 20 poslal Alici. Jak ji bude Alice dešifrovat?
[Řešení: Při počítání mod 997 je gx = ll23 = 659, gy = ll25 = 976, gxy = (gy)x = 97623 = 950, inverze k němu je —297, m = c ■ (—297) = 42. ]