Diffie Hellman - praktické výpočty

Základem je vzorec
\$\mathbf{g^t mod p}\$ (na kalkulačce se tento vzorec píše g^t mod p)
kde g je generátor (nemusí to být moc velké číslo), p je velké prvočíslo a t je tajné číslo.
Funkce mod p počítá zbytek po celočíselném dělení číslem p. (\$13 mod 5 = 3\$)
Generátor g a prvočíslo p jsou veřejné. Alice a Bob se na nich dohodnou a vymění si je mezi sebou.
t je tajné číslo, které si volí každý sám a nikam se nepřenáší.
U Alice budeme toto tajné číslo označovat a a u Boba b.

Alice	Bob
\$g=4, p=17\$	\$g=4, p=17\$
zvolí tajné číslo \$a=11\$	zvolí tajné číslo \$b=14\$
spočítá \$A=g^a mod p=4^11 mod 17=13\$ a pošle Bobovi	spočítá \$B=g^b mod p=4^14 mod 17=16\$ a pošle Alici
výměna výsledků: \$B=16\$	výměna výsledků: \$A=13\$
výpočet tajemství: \$s_A=B^a mod p=16^11 mod 17=16\$	výpočet tajemství: \$s_B=A^b mod p=13^14 mod 17=16\$

Alice

Bob

\$g=4, p=17\$

zvolí tajné číslo \$a=11\$

zvolí tajné číslo \$b=14\$

spočítá \$A=g^a mod p=4^11 mod 17=13\$ a pošle Bobovi

spočítá \$B=g^b mod p=4^14 mod 17=16\$ a pošle Alici

výměna výsledků: \$B=16\$

výměna výsledků: \$A=13\$

výpočet tajemství: \$s_A=B^a mod p=16^11 mod 17=16\$

výpočet tajemství: \$s_B=A^b mod p=13^14 mod 17=16\$

Jak to, že to funguje?

\$s_A=B^a mod p=(g^b mod p)^a mod p=g^{b^a} mod p=g^{b*a} mod p=g^{a*b} mod p=g^{a^b} mod p=(g^a mod p)^b mod p=A^b mod p = s_B\$

Pokud by Eva chtěla zjistit \$s_A\$ nebo \$s_B\$, tak musí řešit rovnici \$13=4^a mod 17\$ nebo rovnici \$16=4^b mod 17\$, s neznámými \$a\$ nebo \$b\$, tedy problém diskrétního logaritmu, což je velmi těžké, prakticky neřešitelné.

Problém diskrétního logaritmu je považován za výpočetně neřešitelný. To znamená, že není znám žádný účinný klasický algoritmus pro výpočet diskrétních logaritmů obecně.

Poznámka: Pokud byste počítali g^t mod p na kalkulačce pro velká čísla, tak může dojít k přetečení a dostanete nesmysly.

Výpočet pro jiná čísla

Alice	Bob
\$g=7, p=111\$	\$g=7, p=111\$
zvolí tajné číslo \$a=38\$	zvolí tajné číslo \$b=51\$
spočítá \$A=g^a mod p=7^38 mod 111=49\$ a pošle Bobovi	spočítá \$B=g^b mod p=7^51 mod 111=100\$ a pošle Alici
výměna výsledků: \$B=100\$	výměna výsledků: \$A=49\$
výpočet tajemství: \$s_A=B^a mod p=100^38 mod 111=\mathbf{10}\$	výpočet tajemství: \$s_B=A^b mod p=49^51 mod 111=\mathbf{10}\$

Alice

Bob

\$g=7, p=111\$

zvolí tajné číslo \$a=38\$

zvolí tajné číslo \$b=51\$

spočítá \$A=g^a mod p=7^38 mod 111=49\$ a pošle Bobovi

spočítá \$B=g^b mod p=7^51 mod 111=100\$ a pošle Alici

výměna výsledků: \$B=100\$

výměna výsledků: \$A=49\$

výpočet tajemství: \$s_A=B^a mod p=100^38 mod 111=\mathbf{10}\$

výpočet tajemství: \$s_B=A^b mod p=49^51 mod 111=\mathbf{10}\$

Výpočet pro jiná čísla

Alice	Bob
\$g=15, p=1217\$	\$g=15, p=1217\$
zvolí tajné číslo \$a=46\$	zvolí tajné číslo \$b=94\$
spočítá \$A=g^a mod p=15^46 mod 1217=853\$ a pošle Bobovi	spočítá \$B=g^b mod p=15^94 mod 1217=1185\$ a pošle Alici
výměna výsledků: \$B=1185\$	výměna výsledků: \$A=853\$
výpočet tajemství: \$s_A=B^a mod p=1185^46 mod 1217=\mathbf{1213}\$	výpočet tajemství: \$s_B=A^b mod p=853^94 mod 1217=\mathbf{1213}\$

Alice

Bob

\$g=15, p=1217\$

zvolí tajné číslo \$a=46\$

zvolí tajné číslo \$b=94\$

spočítá \$A=g^a mod p=15^46 mod 1217=853\$ a pošle Bobovi

spočítá \$B=g^b mod p=15^94 mod 1217=1185\$ a pošle Alici

výměna výsledků: \$B=1185\$

výměna výsledků: \$A=853\$

výpočet tajemství: \$s_A=B^a mod p=1185^46 mod 1217=\mathbf{1213}\$

výpočet tajemství: \$s_B=A^b mod p=853^94 mod 1217=\mathbf{1213}\$

Pro nějaké větší prvočíslo \$p=9973\$

Výpočet pro jiná čísla

Alice	Bob
\$g=26, p=9973\$	\$g=26, p=9973\$
zvolí tajné číslo \$a=151\$	zvolí tajné číslo \$b=94\$
spočítá \$A=g^a mod p=26^151 mod 9973=335\$ a pošle Bobovi	spočítá \$B=g^b mod p=26^94 mod 9973=9702\$ a pošle Alici
výměna výsledků: \$B=9702\$	výměna výsledků: \$A=335\$
výpočet tajemství: \$s_A=B^a mod p=9702^151 mod 9973=\mathbf{5022}\$	výpočet tajemství: \$s_B=A^b mod p=335^94 mod 9973=\mathbf{5022}\$

Alice

Bob

\$g=26, p=9973\$

zvolí tajné číslo \$a=151\$

zvolí tajné číslo \$b=94\$

spočítá \$A=g^a mod p=26^151 mod 9973=335\$ a pošle Bobovi

spočítá \$B=g^b mod p=26^94 mod 9973=9702\$ a pošle Alici

výměna výsledků: \$B=9702\$

výměna výsledků: \$A=335\$

výpočet tajemství: \$s_A=B^a mod p=9702^151 mod 9973=\mathbf{5022}\$

výpočet tajemství: \$s_B=A^b mod p=335^94 mod 9973=\mathbf{5022}\$

Výpočet pro větší čísla

Alice	Bob
\$g=67, p=131071\$	\$g=67, p=131071\$
zvolí tajné číslo \$a=455\$	zvolí tajné číslo \$b=514\$
spočítá \$A=g^a mod p=67^455 mod 131071=53284\$ a pošle Bobovi	spočítá \$B=g^b mod p=67^514 mod 131071=93865\$ a pošle Alici
výměna výsledků: \$B=93865\$	výměna výsledků: \$A=53284\$
výpočet tajemství: \$s_A=B^a mod p=93865^455 mod 131071=\mathbf{51349}\$	výpočet tajemství: \$s_B=A^b mod p=53284^514 mod 131071=\mathbf{51349}\$

Alice

Bob

\$g=67, p=131071\$

zvolí tajné číslo \$a=455\$

zvolí tajné číslo \$b=514\$

spočítá \$A=g^a mod p=67^455 mod 131071=53284\$ a pošle Bobovi

spočítá \$B=g^b mod p=67^514 mod 131071=93865\$ a pošle Alici

výměna výsledků: \$B=93865\$

výměna výsledků: \$A=53284\$

výpočet tajemství: \$s_A=B^a mod p=93865^455 mod 131071=\mathbf{51349}\$

výpočet tajemství: \$s_B=A^b mod p=53284^514 mod 131071=\mathbf{51349}\$

Je vidět že Diffie Hellmanův algoritmus nám funguje docela dobře. Počítal jsem kalkulačkou na Linux Mint Cinnamon a funguje docela dobře. (Zřejmě ji programovali hoši, co znají Diffie-Hellmanův algoritmus :-)

Z výše uvedených výpočtů vidíte, že sdílené tajemství \$s_A = s_B\$ je vždy menší než prvočíslo \$p\$. Z toho je vidět následující: abychom dostali sdílený klíč pořádný, prvočíslo \$p\$ musí být hóóódně velké.

p je 31. Mersennovo prvočíslo:

Alice	Bob
\$g=121, p=2147483647\$	\$g=121, p=2147483647\$
zvolí tajné číslo \$a=824\$	zvolí tajné číslo \$b=416\$
spočítá \$A=g^a mod p=121^824 mod 2147483647=265734643\$ a pošle Bobovi	spočítá \$B=g^b mod p=121^416 mod 2147483647=1471934431\$ a pošle Alici
výměna výsledků: \$B=1471934431\$	výměna výsledků: \$A=265734643\$
výpočet tajemství: \$s_A=B^a mod p=1471934431^824 mod 2147483647=\mathbf{947767745}\$	výpočet tajemství: \$s_B=A^b mod p=265734643^416 mod 2147483647=\mathbf{947767745}\$

Alice

Bob

\$g=121, p=2147483647\$

zvolí tajné číslo \$a=824\$

zvolí tajné číslo \$b=416\$

spočítá \$A=g^a mod p=121^824 mod 2147483647=265734643\$ a pošle Bobovi

spočítá \$B=g^b mod p=121^416 mod 2147483647=1471934431\$ a pošle Alici

výměna výsledků: \$B=1471934431\$

výměna výsledků: \$A=265734643\$

výpočet tajemství: \$s_A=B^a mod p=1471934431^824 mod 2147483647=\mathbf{947767745}\$

výpočet tajemství: \$s_B=A^b mod p=265734643^416 mod 2147483647=\mathbf{947767745}\$

Bitově je číslo 947767745 ještě hodně malé, má hexadecimální hodnotu 0x387DC9C1 a vejde se do 32 bitů. Takže jako tajemství je to dost nepoužitelné.

Potřebovali bychom aspoň takovéto prvočíslo p abychom dostali použitelný klíč:
415368757628736598425938247569843765827634879128375827365928736
84273684728938572983759283475934875938475928475928739587249587
29873958729835792875982795837529876348273685729843579348795827
93857928739548772397592837592478593867045986792384737826735267
3547623568734869386945673456827659498063849024875809603947902
7945982730187439759284620950293759287049502938058920983945872
0948602984912837502948019371092480193581037995810937501938507913
95710937597019385089103951073058710393701934701938091803984091804
98109380198501398401983509183501983091079180395810395190395180935
8109385019840193580193840198340918093851098309180019

Tohle však obyčejná kalkulačka už asi nezvládne.

Dá se na to jít také takto:

Pravidla pro počítání s modulo a mocninami

\$\mathbf{(a*b) mod c= ((a mod c)*(b mod c)) mod c}\$
\$\mathbf{(a^b) mod c = ((a mod c)^b) mod c}\$
\$\mathbf{a^{b+c}=a^b*a^c}\$
\$\mathbf{a^{b*c}=(a^b)^c}\$

Pomocí těchto pravidel můžeme zjednodušit výpočet pro velká čísla tak, aby nám to nepřeteklo. Těmito pravidly se zabývá diskrétní matematika.

Zdroje:

Seznam prvočísel do 1000: https://cs.wikipedia.org/wiki/Seznam_prvo%C4%8D%C3%ADsel

Mersennova prvočísla: https://cs.wikipedia.org/wiki/Mersennovo_prvo%C4%8D%C3%ADslo

Kalkulačka na ověření prvočísla: Prime Numbers Chart and Calculator

Seznamy prvočísel: https://en.wikipedia.org/wiki/List_of_prime_numbers

Počítání s modulo: https://www.symbolab.com/solver/modulo-calculator (našel Dominik Krška)

Diskrétní matematika: https://math.fel.cvut.cz/cz/lide/habala/teaching/dma