Princíp asymetrickej kryptografie a RSA

          Problémom výmeny kľúčov sa zaoberali viacerí odborníci z oblasti kryptografie. Pre ďalšie vysvetlenia budeme používať nasledujúcu trojicu účastníkov komunikácie: Alica - odosielateľ správy, Bob - príjemca správy, Eva - narušiteľ. Eva sa snaží nejakým spôsobom odchytiť správu a previesť ju do čitateľnej podoby (prelomiť ju). Existuje spôsob ako môže Alica poslať Bobovi predmet alebo správu bezpečnou formou. Alica vloží predmet do bezpečnostnej skrinky a zamkne ju kladkou. Zanedbajme to, že sa môže skrinka jednoducho rozbiť, alebo že môžeme kladku odpilovať. Pošle skrinku poštou Bobovi. Ten na ňu pridá svoju kladku a pošle skrinku späť Alici. Alica pomocou svojho kľúča odoberie zo skrinky svoju kladku a pošle skrinku späť Bobovi. Bob jednoducho otvorí skrinku pomocou svojho kľúča (na skrinke ostane iba jeho kladka). Alica s Bobom si nemusia vymeniť žiadny kľúč. Ak by to platilo aj pri symetrickom šifrovaní, bez problémov by sa vytvoril systém, ktorý by dané šifrovanie uskutočnil. Problém je v tom, že ak zašifrujeme niečo prvým kľúčom, potom druhým a následne to dešifrujeme prvým a až potom druhým, nedostaneme otvorený text. Proti tomu je odolná Caesarova šifra, ale ostatné symetrické šifry už nie. V prípade Caesarovej šifry sa iba spočítajú posunutia. Napr. prvé posunutie by bolo 3, druhé posunutie by bolo 4. Celkové posunutie by teda bolo 6, čo je v skutočnosti stále iba Caesarova šifra s jedným kľúčom. V prípade ostatných symetrických šifier to už, ako sme spomínali, neplatí. Riešenie prinášajú matematické funkcie. Rozdeľujeme ich na jednosmerné a dvojsmerné. Jednosmerné sa dajú ľahko vykonať jedným smerom, ale len ťažko druhým. Dvojsmerné sú analogické v oboch smeroch. Napr. 2+x=5 (x je v tomto prípade 3) je dvojsmerná funkcia, lebo ju ľahko obrátime a vypočítame potrebné hodnoty. Príkladom jednosmernej funkcie môže byť 3^x (mod 4) = 1. Zápis tejto funkcie nám hovorí o tom, že zvyšok po delení čísla 3^x číslom 4 je 1. Ide o príklad z modulárnej aritmetiky. Jediný možný spôsob ako určiť hodnotu x je zostaviť si tabuľku možností pre x=1, x=2 atď. V tomto prípade je riešením práve číslo 2, ale v mnohých funkciách tohto typu sa výsledky nedajú tak skoro vyvodiť z tabuľky. Práve táto vlastnosť sa dá využiť pri šifrovaní. Zapíšme rovnicu všeobecne ako Y^x (mod P). Predstavme si, že Alica a Bob chcú použiť šifrovací systém založený na tejto funkcii. Určitými matematickými operáciami dostanú spoločné číslo. V prípade RSA sa to deje tak, že Bob si zvolí dve obrovské prvočísla (p a q), ktoré si uchová v tajnosti ako svoj súkromný kľúč. Následne ich medzi sebou vynásobí a dostane číslo P. Ďalej si zvolí číslo x. Obe čísla (P a x) zverejní v zozname ako verejný kľúč (čísla (p-1)*(q-1) a x by nemali mať žiadneho spoločného deliteľa). Číslo Y predstavuje znak (jeho desiatkový zápis v ASCII kóde), ktorý chce Alica Bobovi zašifrovať a poslať. Alica má všetky potrebné premenné potrebné na to, aby vypočítala hodnotu funkcie Y^x (mod P). Y predstavuje znak správy a čísla x a P Bobov verejný kľúč, ktorý Alica vyhľadá v spomínanom zozname verejných kľúčov. Hodnotu tejto funkcie označme C, teda C = Y^x (mod P). Číslo C Alica pošle Bobovi. Eva nemá možnosť zistiť hodnotu znaku kvôli vlastnostiam tejto funkcie (z čísel C, x a P Eva nie je schopná kvôli vlastnostiam použitej funkcie vypočítať hodnotu Y, ak by poznala Y, x a P, nemala by s výpočtom C problém, rovnako ako s ním nemá problém Alica. To Eve bohužiaľ nepomôže. Jej cieľom je získať Y). Bobovi sa však podarí správu dešifrovať, pretože pozná pôvodné hodnoty p a q, z ktorých pozostáva číslo P. Bobov dešifrovací postup začína tým, že vypočíta hodnotu čísla d, pomocou vzťahu:

x*d = 1 (mod (p-1) * (q-1)).

Bob na to použije rozšírený euklidov algoritmus. Posledný krok, ktorý musí Bob urobiť je vypočítať hodnotu Y podľa vzťahu:

Y = C^d (mod P).

          Y je hľadaný desiatkový zápis znaku v ASCII. Ďalšia možnosť využitia vlastností šifry RSA je použiť ju pri aplikovaní digitálneho podpisu. Bližšie o digitálnom podpise hovorí piata časť s názvom PGP. Šifra RSA je v súčasnosti bezpečná. Dôvodom je problém faktorizácie. Zatiaľ neexistuje spôsob ako rozložiť číslo P na súčin dvoch prvočísel. Jedinou možnosťou je vyskúšať všetky možnosti a to pri použití čísel väčších ako 10³⁰⁸ je pre všetky počítače sveta stále neriešiteľná úloha. Bezpečnosť RSA závisí od výkonnosti súčasných počítačov. Ak sa nájde skratka na výpočet prvočísel, vynásobením ktorých dostaneme číslo P, bezpečnosť RSA sa vytratí a svet bude potrebovať novú šifru, ktorá bude dočasne bezpečná. A možno existuje aj iný spôsob ako k problému pristupovať. O možnom budúcom vývoji hovorí posledná časť tohto projektu. A možno nejde ani tak o budúcnosť...