Diskrétní matematika - cvičení 6. týden
Lukáš Vokřínek
Masarykova univerzita Fakulta informatiky
jaro 2020
Demonstrujte protokol výměny klíčů Diffie-Hellman pro zvolené prvočíslo p = 61 a primitivní kořen g = 7 s různými volbami a a b.
Řešení
Protokol probíhá tak, že si účastníci zvolí soukromé klíče -exponenty a a b a pošlou si navzájem příslušné mocniny ga (mod p) a gb (mod p), přičemž se (zatím?) neumí efektivně z těchto mocnin získat exponent a = \oggga (mod(^(p)), tedy tzv. diskrétní logaritmus.
Společný souromý klíč se pak stanoví jako gab (mod p). Druhý účastník jej spočítá jako {ga)b z obdržené mocniny ga a svého soukromého klíče b, první symetricky jako (gb)a.
Príklad
Demonstrujte protokol výměny klíčů Diffie-Hellman pro zvolené prvočíslo p = 61 a primitivní kořen g = 7 s různými volbami a a b.
Řešení
Při této příležitosti si ukážeme další způsob počítání mocnin (jde vpodstatě jen o jiný zápis), vhodný k algoritmizaci: mocninu ga budeme v krocích výpočtu zapisovat ve tvaru x • yz (začneme tedy s 1 • ga) a postupně budeme zmenšovat exponent z - když dojdeme k z = 0, výpočet končí s výsledkem x. V každém kroku snížíme exponent na polovinu: pokud je z = 2zf, upravíme
x • yz = x • (y2)z/ = x • (y )
J\z'
kde y' = y2 spočítáme explicitně. Pokud z = 2z' + 1, upravíme
x.y* = x.y (y2)*W.(/)
J\z'
kde x; = x • y a / = yz spočítáme explicitně.
,/ — .,2
Demonstrujte protokol výměny klíčů Diffie-Hellman pro zvolené prvočíslo p = 61 a primitivní kořen g = 7 s různými volbami a a b.
Řešení
Budeme volit a = 7, 6=11 (lepší volit čísla nesoudělná s <£>(61), jinak bychom například mohli dospět k a = 6, b = 10 =>■ yafc = y60 = ^ (mod 61)). Alice tedy spočítá a pošle
#a = 77 = 1 • 77
= l-7-(72)3 = 7-(-12)3
= 7 • (-12) • ((-12)2)1 = (-23) • 221
= 43.
Příklad
Demonstrujte protokol výměny klíčů Diffie-Hellman pro zvolené prvočíslo p = 61 a primitivní kořen g = 7 s různými volbami a a b.
Řešení		
Bob pak spočítá a	pošle	
	711 = 1 • 711	
—	l-7-(72)5 = 7-(-12)5	
—	7 • (-12) • ((-12)2)2 = (-23) • 222	
—	(-23) • (222)1 = (-23) • (-4)1	
—	31.	
Demonstrujte protokol výměny klíčů Diffie-Hellman pro zvolené prvočíslo p = 61 a primitivní kořen g = 7 s různými volbami a a b.
Řešení
Tedy
(7)
Alice
43
Bob
31
(H)
Bob spočítá společný soukromý klíč jako
gab = (g3}b = 43ii = : . (_i8)n
= 1 • (-18) • ((-18)2)5 = (-18) • 195 = (-18) • 19 • (192)2 = 24 • (-5)2 = 24 • ((-5)2)1 = 24 • 251 = 51.
Demonstrujte protokol výměny klíčů Diffie-Hellman pro zvolené prvočíslo p = 61 a primitivní kořen g = 7 s různými volbami a a b.
Řešení
Tedy
7        Alice í=± Bob 11
31
Alice spočítá společný soukromý klíč jako
gab = (gby = 317 = 1. 317
= 1 • 31 ■ (312)3 = 31 • (-15)3
= 31 • (-15) • ((-15)2)1 = 23 • (-19)1
= 51.
Martin a Honza chtějí komunikovat šifrou EIGamal navrženou egyptským matematikem Taherem Elgamalem podle protokolu Diffieho a Hellmana na výměnu klíčů. Martin si zvolil prvočíslo p = 41 a jemu příslušný primitivní kořen g — 11 a dále si zvolil soukromý klíč - exponent a = 10. Zveřejnil tedy trojici čísel p = 41, g — 11, g3 = 9. Honza mu poslal veřejným kanálem dvojici čísel gb = 22, c = 6. Jakou zprávu Honza poslal?
Řešení
První poslané číslo g slouží pouze ke stanovení společného klíče podle protokolu Diffie-Hellman; Martin jej spočítal jako gab = (gb)a = 2210 (jak jej spočítal Honza se nedozvíme, protože neznáme Honzův soukromý klíč - exponent b). Vlastní šifrování pak probíhá snadno jako násobení tímto společným klíčem, tedy:
c = g   • m (mod p).
Spočítame prvně gab = (gb)a = 2210:
gab = (^gby _ 22io = i . 2210
= 1 • (222)5 = 1 • (-8)5
= l-(-8)-((-8)2)2 = (-8)-(-18)2
ee (-8) • ((-18)2)1 ee (-8) • (-4)1 ee 32.
Dostávame tak kongruencii
6 = c = g3b • m = 32 • m (mod 41). Nyní tuto kongruenci vyřešíme a tím bude dešifrovaní hotové.
■v
Řešení
41 • m = O 32 • m = 6
9 • m = -6
5 • m = 24 = -17
4- m = 11
1 • m = 13
Poslaná zpráva tedy byla m = 13 (mod41).
V Rabínově kryptosystému Alice zvolila za svůj soukromý klíč p = 23, q — 31, veřejným klíčem je pak n — p - q — 713. Zašifrujte pro Alici zprávu m = 327 (mod713) a ukažte, jak bude Alice tuto zprávu dešifrovat.
Řešení
1
V Rabínově kryptosystému je šifrování dané umocňováním na druhou, tj. c = m2 (mod713). Budeme počítat zvlášť modulo 23 a modulo 31,
c = 3272 = 52 = 2 (mod23)
c = 3272 = (-14)2 = 10 (mod 31)
nyní dáme výsledky dohromady:
Řešení
Nyní dáme částečné výsledky c = 2 (mod 23), c = 10 (mod 31) dohromady modulo 713:
31 • c = 2 • 31
23 • c = 10-23
8 • c = 2 • 31 - 10 • 23
7 • c = -4 • 31 - 1 • 23
c = 6 • 31 - 9 • 23 = 692 (mod 713)
(samozrejme to šlo spočítat přímo a to se opravdu děje při realizaci tohoto kryptosystému).
Řešení
Nyní se zabývejme dešifrováním. Potřebujeme vlastně spočítat odmocninu z 692 (mod713). Opět počítáme zvlášť modulo 23 a 31, pak dáme výsledky dohromady (odmocnina už se přímo neumí). Modulo 23 platí:
1 = m22 =4> m2 = m24
m2 = (c6)2       m = ±c°(mod23)
_  i ^6
.12
(poslední implikace platí jen modulo prvočíslo!). Podobně
1 = m30       mz =       =      mz = (c*f       m = ±ctí (mod 31)
2 — _32
2      / 8\2
_  i ^8
P+i
Obecně odmocninu z c (mod p) lze spočítat jako ±c 4   (mod p)
■v
Číselně:
m = ±6926 = ±26 = ±18 (mod 23) m = ±6928 = ±108 = ±14 (mod 31)
■v
Řešení
|
m = ±6926 = ±26 = ±18 = ±5 (mod 23) m = ±6928 = ±108 = ±14 (mod 31)
Vyšly 4 možnosti a opravdu všechny jsou odmocniny z c. V realizaci kryptosystému je potřeba zaručit, aby vždy pouze jediná odmocnina byla přípustná (např. ta kladná/menší), případně dodatečnou informací specifikovat, která z odmocnin je správně. Ke všem čtyřem možnostem dopočítejme výsledek, začneme s m = 5 (mod 23), m = U (mod 31).
Řešení
Začneme s m = 5 (mod 23), m = 14 (mod 31):
31 • m = 5 • 31
23 • m = 14-23
8 • m = 5 • 31 - 14 • 23
7 • m = -10 • 31 + 11 • 23
m = 15 • 31 + 6 • 23 = 603 (mod 713)
Pro m = —5 (mod 23), m = —14 (mod 31) by bylo vše pouze s opačným znaménkem, dostaneme tedy dvě odmocniny ±603 = ±110 (mod 713).
■v
Řešení
Zbylé dvě dostaneme z m = 5 (mod 23), m = —14 (mod 31):
31 • m = 5 • 31
23- m= -14-23
8 • m = 5 • 31 + 14 • 23
7 • m = -10 • 31 - 11 • 23
m = 15 • 31 - 6 • 23 = 327 (mod 713)
a podobně pro opačná znaménka opačný výsledek, tedy
±327 (mod 713). Poznamenejme, že tímto postupem vlastně
můžeme dospět rovnou ke všem čtyřem výsledkům naráz
±15 • 31 ± 6 • 23 (mod 713) (ale bacha na znaménka, nejlepší když
už tak vypočítat s jednou sadou znamének a pak předělat na ±).
Poznámka
Kdy můžeme z kongruence x2 = y2 (mod m) odvodit x = ±y? Přepišme první kongruenci jako
0 = x2 — yz = (x — y)(x + y) (mod m)
tedy m | (x — y)(x + y). Pokud je m prvočíslo, můžeme z toho usoudit, že m | x — y (a tedy x = y) nebo m | x + y (a tedy x = —y). Zkuste si rozmyslet, kdy obecně toto funguje.
2 _
Poznámka
Bezpečnost Rabínova kryptosystému: Předpokládejme, že existuje algoritmus počítající nějakou z odmocnin c (modr?), budeme ji značit \fč. Náhodně zvolíme m a pomocí algoritmu spočítáme \fnc-. S pravděpodobností 1/2 se nebude jednat o ±m. V takovém případě je rozdíl m —        násobkem p, ale nikoliv q (jeden ze zbytků modulo p a q je stejný, druhý má opačné znaménko). Můžeme tedy jedno z prvočísel získat jako největší společný dělitel (n. m — \frrp-).