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ň