Veřejná kryptografie
Veřejná kryptografie způsobila veliký zlom v historii šifer
a šifrování. Řeší totiž problém s distribucí klíčů. Se staršími typy
šifer je totiž problém v tom, že když se prozradí klíč nebo princip
šifry, musí se vydat nový. Ale jak se na novém klíči domluvit? To je
celkem problém. Zprávu nemůžeme poslat nezašifovaně, ani zašifrovanou
starou šifrou. Co s tím udělat? Tímto problémem se zabývali už pánové
W.Diffie, M.E. Hellman a R.Merkle v roce 1945. Ti přemýšleli nad
podobnou těžko řešitelnou situací. Představte si totiž místnost
(síť) plnou vědců(hackerů), z nichž si 2 chtějí poslat zašifrovanou
zprávu, aniž by si předem domluvili klíč. Zkusíte-li vymyslet řešení,
asi se vám to nepovede. Všechno, co totiž řeknete tomu druhému, slyší
všichni, všechno, co řekne on, taky. Takže co s tím? Je to řešitelné
nebo ne? Teoreticky tato úloha řešitelná není, ale prakticky ji
vyřešit můžete. Fígl je v tom, že se oni dva dozvědí onu informaci
mnohem dříve než ostatní. Nejprve si ukážeme řešení od pana Merkla.
Takže máme odesílatele Oldu, příjemce Pepu a hackera Honzu.
Upozornění tento příklad je náhodný, číselné konstanty můžou být
jiné (tyto bych doporučoval). Používají nějakou dohodnutou šifru
např. DES
+--+---------------------------+------------------------------+
| |Olda |Pepa |
+--+---------------------------+------------------------------+
|a)|N (2^20) klíčů (náhodně) | |
| |s délkou 56 bitů doplněné | |
| |44 nulami na 100 bitů | |
+--+---------------------------+------------------------------+
|b)|vygeneruje 20bitový klíč | |
| |a zašifruje všech N klíčů | |
| |na ŠK | |
+--+---------------------------+------------------------------+
|c)| pošle všechny ŠK Pepovi |NxŠK |
+--+---------------------------+------------------------------+
|d)| |vybere si jeden ŠK |
| | |a vyzkouší na něm všech |
| | |2^20 klíčů dokud mu nevyjde |
| | |44 nul na začátku, druhých |
| | |56 bitů je klíč->K |
+--+---------------------------+------------------------------+
|e)| |Pošle dohodnutý řetězec |
| | |(např. samé nuly), zašifruje |
| | |ho klíčem K a pošle ho Oldovi |
+--+---------------------------+------------------------------+
|f)|Na K vyzkouší všech N klíčů| |
| |dokud mu nevyjde dohodnutý | |
| |řetězec samé nuly. Klíč pro| |
| |který to platí je klíč, | |
| |který nikdo jiný nezná | |
+--+---------------------------+------------------------------+
A teď se na situaci koukneme z Honzovy strany. Koukneme-li se na
tabulku, všimneme si dvou "slabých" míst, kde se přenášejí informace.
tzn. c) a e). V bodě c) posílá Olda N šifrovaných klíčů, takže Pepa
i Honza mají stejné informace. Fígl je v tom, že Pepa si VYBERE JENOM
JEDEN klíč, pro který zkouší 2^20 možnosti, jenže Honza jich musí
vyzkoušet N*2^20, což je jen milionkrát víc. Takže když bude Pepa
zkoušet svejch 2^20 možností 1 minutu, bude Honza testovat 694 dní
a ještě k tomu nebude vědět, kterej z těch 2^20 klíčů je ten pravej.
Takže si musí počkat na krok e) a udělat to samé co Olda v kroku f).
Takže Oldovi s Pepou bude určení společného klíče trvat 2 minuty a
Honzovi asi 2 roky. (Ve skutečnosti to bude všem třem trvat mnohem
déle.)
---------------------------------------------------------------------
Další řešení této úlohy je už založeno na vyšší matematice, přesněji
na tom, že pro všechna velká čísla x a prvočísla a a p (asi 200
cifer) můžeme X = a^x mod p spočítat jen na 2*log(2)p (dvojkovej
logaritmus z p) násobení, zatímco na výpočet x z X potřebujeme asi
druhou odmocninu z p násobení. Zase je v tom finta. Mocnina se totiž
dá rozložit pomocí binárního rozkladu exponentu na pár jednodušších
mocnin, které násobíte navzájem.
Např. a^17 = a^(b00010001) = a^(16+1) = (((a²)²)²)²*a
8^17 = (((8²)²)²)²*8
+--+---------------------------+------------------------------+
| |Olda |Pepa |
+--+---------------------------+------------------------------+
|a)|veřejné číslo p a a<p a je |a, p |
| |prvočíslo | |
| | | |
|b)|tajný koeficient x |tajný koeficient y |
| | | |
|c)|zveřejní X (X=a^x mod p) |zveřejní Y (Y=a^y mod p) |
| | | |
|d)|spočítá K = Y^x mod p = |spočítá L = X^y mod p = |
| |=a^(xy) mod p |=a^(xy) mod p |
+--+---------------------------+------------------------------+
K=L
Honza nemá x a y, takže by je musel určit z X = a^x mod p, což je,jak
jsme si řekli, hrozně paměťově a časově náročné.
HIPP
(příště si řekneme něco o praktickém použití a RSA)
výheň