6. procvičení z MB 154, podzim 2023
Příklad 1. Najděte primitivní kořen modulo 19 a demonstrujte DH protokol pro a = 5 a 6 = 7. (Vyjde hned g = 2, Alice pošle 25 = 13, Bob pošle 27 = 14, společný soukromý klíč 25'7 = 10.)
Příklad 2. Tomáš a Petr chtějí komunikovat šifrou ElGamal. Tomáš si zvolil prvočíslo p = 29, primitivní kořen g = 10 a číslo x = 7. Zveřejnil pak trojici (29,10, h), kde /i = 107 (mod 29). Petr mu poslal dvojici (2,27). Jakou zprávu poslal Petr Tomášovi? (Společný soukromý klíč 27 = 12, dešifrovaná zpráva M = (12)_1 • 27 = 24.)
Příklad 3. V Rabínově kryptosy stému Alice zvolila za svůj soukromý klíč p=ll,g = 19, veřejným klíčem je pak n = p ■ q = 209. Zašifrujte pro Alici zprávu m = 42 (mod 209) a ukažte, jak bude Alice tuto zprávu dešifrovat. (Zašifrování C = 92, dešifrování M = ±42, ±53.)
Příklad 4. Vyřešte diofantickou rovnici 23x + Aly = 1693, prvně nad z, pak se pokuste odpovědět nad No. (Vyjde x = —Alt + 54, y = 23t ±11; nezáporné pro t = 0,1.)
Příklad 5. Vyřešte diofantickou rovnici 36x±60í/±352; = 973, prvně nad z, pak se pokuste odpovědět nad N0. (Například x = -5s - 15* ± 28, y = 3s ± 2t, z=Ylt- 1; nad N0 čtyři řešení (13,2,11), (8,5,11), (3,8,11), (3,1, 23).)
i