Řešení domácích úloh z minulého týdne Návodné úlohy ooo MB104 - 5. demonstrovaná cvičení RSA algoritmus Masarykova univerzita Fakulta informatiky 27.3. 2012 Řešení domácích úloh z minulého týdne Návodné úlohy ooo Řešení domácích úloh z minulého týdne Návodné úlohy • RSA algoritmus • Algoritmus EIGamal Řešení domácích úloh z minulého týdne Návodné úlohy ooo Přikladl. Zakódujte zprávu 10011 pomocí(8,5) kódu generovaného polynomem 1 + x + x3. Řešení. 11110011. □ Řešení domácích úloh z minulého týdne Návodné úlohy ooo Příklad 2. Určete generující matici a matici kontroly parity pro lineární kód generovaný polynomem z předchozího příkladu. Řešení. G = 0 1 1 1\ 1 1 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 \o 0 0 0 1/ /l 0 0 1 0 1 1 1\ H=01011100 \0 0 1 0 1 1 1 0/ Příklad 3. Metodou vedoucích reprezentantů dekódujte slovo 10001111 přijaté v kódu z předchozích příkladů za předpokladu, že došlo k minimálnímu počtu chyb při přenosu. Řešení, syndrom S = 001 vedoucí reprezentant: 00100000, pravděpodobně posílané kódové slovo 10101111. □ Řešení domácích úloh z minulého týdne Návodné úlohy ooo Řešení domácích úloh z minulého týdne Návodné úlohy • RSA algoritmus • Algoritmus EIGamal Řešení domácích úloh z minulého týdne Návodné úlohy •OO Martin zveřejnil svoje RSA klíče N=143 a e=17. Honza mu chce poslat zprávu 3. Jak to pomocí RSA algoritmu provede? Jak Martin posléze zprávu dešifruje? Řešení. Martin zná rozklad čísla 143 = 11-13 (faktorizace je těžký problém pro velká N). Řešení domácích úloh z minulého týdne Návodné úlohy •OO Martin zveřejnil svoje RSA klíče N=143 a e=17. Honza mu chce poslat zprávu 3. Jak to pomocí RSA algoritmu provede? Jak Martin posléze zprávu dešifruje? Řešení. Martin zná rozklad čísla 143 = 11-13 (faktorizace je těžký problém pro velká N). Díky tomuto rozkladu spočítá (p(N) = 120 a dopočítá inverzi k číslu 17 v okruhu Z120: [17]^2o = [H3]. Řešení domácích úloh z minulého týdne Návodné úlohy •OO Martin zveřejnil svoje RSA klíče N=143 a e=17. Honza mu chce poslat zprávu 3. Jak to pomocí RSA algoritmu provede? Jak Martin posléze zprávu dešifruje? Řešení. Martin zná rozklad čísla 143 = 11-13 (faktorizace je těžký problém pro velká N). Díky tomuto rozkladu spočítá (p(N) = 120 a dopočítá inverzi k číslu 17 v okruhu Z120: [17]^2o = [H3]. Honza pošle 317 = 9 (mod 143) Řešení domácích úloh z minulého týdne Návodné úlohy •OO Martin zveřejnil svoje RSA klíče N=143 a e=17. Honza mu chce poslat zprávu 3. Jak to pomocí RSA algoritmu provede? Jak Martin posléze zprávu dešifruje? Řešení. Martin zná rozklad čísla 143 = 11-13 (faktorizace je těžký problém pro velká N). Díky tomuto rozkladu spočítá (p(N) = 120 a dopočítá inverzi k číslu 17 v okruhu Z120: [17]^2o = [H3]. Honza pošle 317 = 9 (mod 143) Martin dešifruje 9113 = 3 (mod 143). □ Řeše :ní domácích úloh z mi nulého týdne Návodné úlohy 0*0 • Odesílatel zvolí cyklickou grupu G spolu s generátorem g. Řešení domácích úloh z minulého týdne Návodné úlohy 0*0 • Odesílatel zvolí cyklickou grupu G spolu s generátorem g. • Odesílatel zvolí tajný klíč x, spočítá h = gx a zveřejní veřejný klíč (G,g,h). Řešení domácích úloh z minulého týdne Návodné úlohy 0*0 • Odesílatel zvolí cyklickou grupu G spolu s generátorem g. • Odesílatel zvolí tajný klíč x, spočítá h = gx a zveřejní veřejný klíč (G,g,h). • Šifrování zprávy Z: Bob zvolí náhodně y a vypočte Si = gy a S2 = Z • /7y a pošle (Si, S2). Řešení domácích úloh z minulého týdne Návodné úlohy 0*0 • Odesílatel zvolí cyklickou grupu G spolu s generátorem g. • Odesílatel zvolí tajný klíč x, spočítá h = gx a zveřejní veřejný klíč (G,g,h). • Šifrování zprávy Z: Bob zvolí náhodně y a vypočte Si = gy a S2 = Z • /7y a pošle (Si, S2). • Dešifrování zprávy: m = Ss/Sf = z-/py(^T = z-hy/(gxy = z-w/{w) = z. Řešení domácích úloh z minulého týdne Návodné úlohy 00» Příklad Martin a Honza chtějí komunikovat šifrou EIGamal Domluvili se na cyklické grupě a Martin si náhodně zvolil generátor grupy Ha číslo 10 a zveřejnil trojici (Z41,11,9), (9 = ll10 (mod 41)). Honza mu pošle veřejně dvojici (22,6). Jakou zprávu Honza poslal? Řešení domácích úloh z minulého týdne Návodné úlohy 00» Příklad Martin a Honza chtějí komunikovat šifrou EIGamal Domluvili se na cyklické grupě a Martin si náhodně zvolil generátor grupy Ha číslo 10 a zveřejnil trojici (Z41,11,9), (9 = ll10 (mod 41)). Honza mu pošle veřejně dvojici (22,6). Jakou zprávu Honza poslal? Řešení. Zprávu Z dostaneme jako Z = (6/2210) (mod 41). Řešení domácích úloh z minulého týdne Návodné úlohy 00» Příklad Martin a Honza chtějí komunikovat šifrou EIGamal Domluvili se na cyklické grupě a Martin si náhodně zvolil generátor grupy Ha číslo 10 a zveřejnil trojici (Z41,11,9), (9 = ll10 (mod 41)). Honza mu pošle veřejně dvojici (22,6). Jakou zprávu Honza poslal? Řešení. Zprávu Z dostaneme jako Z = (6/2210) (mod 41). Spočtěme nejprve 2210 = 222 • (222)2 • ((222)2) = (-8) • (-8)2 • (-8)2 = (-8) • 23 • 23 = -9 (mod 41), Řešení domácích úloh z minulého týdne Návodné úlohy 00» Příklad Martin a Honza chtějí komunikovat šifrou EIGamal Domluvili se na cyklické grupě a Martin si náhodně zvolil generátor grupy Ha číslo 10 a zveřejnil trojici (Z41,11,9), (9 = ll10 (mod 41)). Honza mu pošle veřejně dvojici (22,6). Jakou zprávu Honza poslal? Řešení. Zprávu Z dostaneme jako Z = (6/2210) (mod 41). Spočtěme nejprve 2210 = 222 • (222)2 • ((222)2) = (-8) • (-8)2 • (-8)2 = (-8) • 23 • 23 = -9 (mod 41), (-9)^ = 9, Řešení domácích úloh z minulého týdne Návodné úlohy 00» Příklad Martin a Honza chtějí komunikovat šifrou EIGamal Domluvili se na cyklické grupě a Martin si náhodně zvolil generátor grupy Ha číslo 10 a zveřejnil trojici (Z41,11,9), (9 = ll10 (mod 41)). Honza mu pošle veřejně dvojici (22,6). Jakou zprávu Honza poslal? Řešení. Zprávu Z dostaneme jako Z = (6/2210) (mod 41). Spočtěme nejprve 2210 = 222 • (222)2 • ((222)2) = (-8) • (-8)2 • (-8)2 = (-8) • 23 • 23 = -9 (mod 41), (-9)^ = 9, Z = 9-6 = 13 (mod 41). □