Prečo 1 nie je prvočíslo.

V 70tych rokoch keď som chodil do školy boli všetky čísla rovnaké. Prvočísla som vôbec nevnímal, ako keby ani neexistovali. Nemali pre ľudí žiadny význam a nestálo zato strácať s nimi čas. Samozrejme vtedy som netušil, že v Amerike sa práve rodí objav, ktorý pozdvihol prvočísla nad všetky ostatné.

Na počítanie sme v škole ešte stále používali logaritmické pravítko, ale v apríli 1977 už niektorí žiaci mali aj kalkulačky. Práve vtedy prišiel Ron Rivest na nápad využiť prvočísla na šifrovanie správ, ktoré sa v Amerike posielali už elektronickou poštou. Princíp spočíval v tom, že nie je ťažké vynásobiť medzi sebou dve prvočísla, ale ak poznáte len ich súčin je takmer nemožné zistiť ktoré to boli. Napríklad číslo 143 budem postupne deliť číslami 1, 2, 3... až kým nedostanem celočíselný výsledok. Ak poznáte triky s delitelnosťou čísel môžete si ušetriť prácu, pretože toto číslo delia bez zvyšku okrem fyzika/meracie-jednotky/" class="wiki-link" title="Viac o: jednotky">jednotky len dve prvočísla 11 a 13. Prvočísla sú bez zvyšku deliteľné len jednotkou a samým sebou. Číslo 143 teda nie je prvočíslo, ale nie je deliteľné žiadnym číslom od 1 do 10. Keď prvočísla zvolím väčšie bude sa ich súčin správať tak isto, ale čas na ich zistenie bude oveľa dlhší. Skúste 323 a to sme stále len pri dvojciferných prvočíslach. Pre šifrovanie sa prvočísla volia viac ako 100 ciferné a nájsť ich, ak poznáte len ich súčin je úctyhodný proces, ktorý sa volá faktorizácia.

Veľmi obtiažne je už len samotné vyhľadanie takýchto veľkých prvočísel, pretože neexistuje jednoduchý vzorec ktorý ich nájde. Najstarším postupom na ich vyhľadávanie je Eratostenove sito ešte z čias Antiky. Za dvetisíc rokov sa však v tejto oblasti veľa nezmenilo, ak sa vôbec dá niečo zmeniť. Ani modernejšie metódy nevedia v krátkom čase preveriť či náhodne zvolené veľké číslo je prvočíslom, alebo nie. Zrejme preto sa prvočísla tak zaľúbili Ronovi Rivesovi, ktorý vďaka ním vyhral závod o nájdenie jednosmernej funkcie potrebnej pre asymetrické šifrovanie. Aj keď samotný postup asymetrickej šifry je o niečo zložitejší, jednosmerná funkcia ktorú pritom využíva je vlastne jednoduchá. Ak zverejním súčin mojich dvoch tajných prvočísel, môže mi každý posielať správy zašifrované práve týmto číslom, ktoré je mojim verejným kľúčom. Tajné prvočísla, ktoré poznám len ja, sú mojim súkromným kľúčom a len pomocou nich môžem správu dešifrovať.

Asymetrická šifra vďaka jednosmernej funkcii zaručuje, že ani ten kto správu zašifroval ju nedokáže bez súkromného kľúča dešifrovať. To je zásadný rozdiel oproti symetrickému šifrovaniu, ktoré nepoužívalo jednosmerné funkcie a obráteným postupom umožňovalo dešifrovať správy. Pri symetrickej šifre je nevyhnutné doručenie dešifrovacieho kľúča ešte pred odoslaním správy, čo spôsobovalo obrovské problémy najmä bankám, ktoré v Amerike 70tich rokov už so svojimi klentami komunikovali šifrovanou elektronickou poštou. Stovky kuriérov roznášalo dešifrovacie kľúče v zapečatených obálkach tisíckam klientov, ktorý pri bankových prevodoch zadávali čísla svojich kreditných kariet šifrované symetrickou šifrou. Asymetrická šifra umožnila aj ďalšiu geniálnu vec a tou je elektronický podpis. Nach už je vaša predstava akákoľvek elektronický podpis neexistuje. Najčastejšie sa zaň vydáva takzvaný odtačok prsta (zmes čísel a písmen dlhá cca. na 1 riadok), ktorý je však len kontrolným súčtom súkromného kľúča.

Podpísať dokument elektronicky vlasne znamená zašifrovať ho vlastným súkromným kľúčom. Každý ho môže následne dešifrovať verejným kľúčom, pretože ten je voľne prístupný na sieti. Ak je výsledkom dešifrovania zrozumiteľný text, potom musel byť zašifrovaný príslušným súkromným kľúčom a pretože ten je tajný, nikto nemôže pochybovať že ho šifroval majiteľ súkromného kľúča. Aké jednoduché a hneď dve muchy jednou ranou. Takto podpísanú správu však môže čítať hocikto a preto sa preto sa tajné správy šifrujú dvakrát. Raz verejným kľúčom príjemcu kvôli utajeniu a druhý krát vlastným súkromným kľúčom, ktorý garantuje odosielateľa a to že správa na svojej ceste nebola zmenená. Aj keď sa to na prvý pohľad zdá veľmi zložité, v programe PGP , ktorý poskladal Phil Zimmermann už v roku 1991, to beží takmer automaticky. Napíšete správu a vyberiete z ponuky PGP čo s ňou chcete urobiť. Zašifrovať, podpísať, alebo oboje súčasne. Všetko ostatné urobí program až na odoslanie šifrovaného súboru. To musíte zvládnuť. Príjemca na druhej strane klikne na tlačítko dešifrovať a overiť podpis. To je vlastne celé a len vďaka prvočíslam.

Takže, už viete prečo 1 nie je prvočíslo?

POUŽITÁ LITERATÚRA A ZDROJE

Simon Singh - THE CODE BOOK -