PRVOČÍSLA – základ moderního šifrování

• Úvod

• Základní prvočíselné pojmy

Úvod

Svět, který nás dnes obklopuje, je plný elektroniky, dat, bezdrátových technologií, bezkontaktních plateb, internetových aplikací, a dokonce i virtuálních měn. Naše finance, osobní data, komunikaci nebo i fotky dnes chceme mít pod kontrolou, ale na druhou stranu stále po ruce a snadno dostupné. Těžko si umíme představit, že by všechny tyto informace a činnosti nebyly nějak zabezpečeny. S požadavky na vysokou míru bezpečnosti (šifrování/heslování) elektronické komunikace a uchovávání informací se setkáváme na každém kroku. Jenže šifrovaní informací nebo zpráv není pro lidstvo nic až tak novým. První důkazy o skrývání obsahu dopisů máme již z dob starého Egypta, Mezopotámie a Indie, tedy již z doby 3000 let př. n. l. Staří Řekové dokonce vynalezli první mechanické maskování zpráv a první šifrové systémy jsou dochované z doby 5. století př.n.l.

Tím, jak narůstala touha lidí ukrývat různé informace před nechtěnými čtenáři (kryptografie), tím narůstala touha je umět odkrývat a dešifrovat (kryptoanalýza). Tento souboj šel tisíciletí ruku v ruce a po každém prolomení důkladnějšího systému šifrování následovala touha po nové, ještě dokonalejší metodě šifrování. Některé systémy byly zapamatovatelné, pro jiné byly potřeba speciální pomůcky, šablony, jednoduché strojky. Obrovským milníkem v tomto oboru byl vynález Morseovy abecedy, jejímž prostřednictvím bylo uskutečněno v roce 1844 první telegrafické spojení, konkrétně mezi městy Washington a Baltimore v USA. Rádiová komunikace a její šifrování nabyla obrovského významu a rozmachu v době první a hlavně druhé světové války. Díky potřebě řešení složitějších matematických výpočtů a například i dekódování šifry Enigma vznikly mezi dvacátými až čtyřicátými lety dvacátého století první „digitální elektronické počítací stroje“, tedy základ dnešních počítačů.

S postupným rozmachem komunikace, elektroniky a počítačů narůstala potřeba šíření informací, ale zároveň i hledání stále bezpečnějšího způsobu šifrování šířené elektronické komunikace. Průlom nastal v roce 1977 vynálezem asymetrického šifrování RSA, jehož základem se stal rozklad velkých čísel na prvočísla.
Metod symetrického i asymetrického šifrování vzniklo postupně několik a jsou součástí veškeré dnešní elektronické komunikace. Jiné šifrování je potřeba pro bankovnictví, jiné má internetová síť HTTPS, jiná metoda se používá pro e-mailovou komunikaci, kryptoměny, elektronické klíčenky, navigační systémy, vesmírnou komunikaci, elektronický podpis, atd. Základním kamenem ale zůstávají prvočísla.

Bohužel s narůstajícím výkonem počítačů okolo nás a jejich snadnější dostupností, roste i potřeba používat pro šifrování stále větší prvočísla, a tedy i potřeba hledání nových, která ještě neznáme. Čím větší prvočísla jsou totiž při šifrování použita, tím náročnější je prolomení takové šifrované elektronické informace. Hledání prvočísel je tak základní činností pro naši všeobecnou bezpečnost v dnešním moderním světě, aniž by si toho většina lidí byla při každodenním využívání elektronických nástrojů vědoma.

Co je prvočíslo

Prvočíslo je přirozené číslo, které je beze zbytku dělitelné pouze jedničkou a sebou samým. Jednička samotná však prvočíslo není. Nejmenší prvočíslo je dvojka. Dvojka je totiž beze zbytku dělitelná pouze jedničkou a sama sebou (dvojkou). Je zároveň jediné prvočíslo, které je sudé. Ostatní sudá čísla jsou totiž vždy dělitelná i dvojkou = nejsou to prvočísla.

Základní vlastnosti prvočísel

• Prvočísel je nekonečně mnoho.
• Pro všechna celá čísla, která jsou větší než 1, platí, že v intervalu (z, 2*z) existuje minimálně jedno prvočíslo. Například: pro celé číslo 2 máme interval (2, 4). V tomto intervalu je jediným celým číslem trojka - ta je prvočíslo. Pro celé číslo 5 máme interval (5, 10) tedy čísla 6, 7, 8, 9. Z tohoto intervalu právě číslo 7 je prvočíslo. Podobně je to i s vyššími celými čísly.

Příklady

Nejmenšími prvočísly jsou: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, …
Největší známé prvočíslo je 2^{82 589 933} − 1. Jedná se o číslo, které má 24 862 048 číslic v desítkové soustavě. Číslo bylo objeveno v rámci projektu distribuovaných výpočtů GIMPS v prosinci 2018.

Hledání prvočísel

Nalezení velkého prvočísla není nikterak snadné, a i když je dnešní výpočetní technika na tak vysoké úrovni, hledání těch největších  znamená pro běžný počítač i dny práce. Přitom většina pokusů o jejich nalezení končí neúspěšně.