Matematika pro kryptology

Algoritmy z rodiny asymetrických šifer jsou založeny na rozkladu přirozených čísel.

Než se však k principu algoritmů dobereme, sdělíme si něco málo z matematiky.

Rozklad na součin prvočísel

Vzpomínáte ze základní či střední školy na D(25, 5) či n(25, 5)???

Zkusili byste vymyslet, co tento zápis znamenal?

D(25, 5) značí, že hledáme největšího společného dělitele čísel 25 a 5
n(25, 5) nám říká, že hledáme nejmenší společný násobek čísel 25 a 5 obr. 1

Obr. 1 Rozklad na součin

hledání provádíme pomocí rozkladu na součin prvočísel
prvočíslo je takové číslo, které nemá jiného dělitele než samo sebe a jedničku obr. 2.

Obr. 2 Prvočísla do 400

Příklad:

Najděte největšího společného dělitele čísel 140 a 15. využijte rozkladu na součin prvočísel obr. 3

Obr. 3 Největší společný dělitel čísel 140 a 15

U rozkladu na součin prvočísel se předpokládá, že ačkoli je tento postup jednoduchý, u velkých čísel může být hledání dělitelů z řad prvočísel nadmíru složité a těžké a doposud není známý algoritmus, který by toto bez pochybení dokázal.Pro lepší pochopení tu máme upřesnění, které nám ukazuje historický vývoj zjišťování prvočíselných dělitelů. V roce 1970 byla úspěšně rozkládána 20- ciferná čísla. O desetiletí později se s rozvojem techniky a matematických operací umožnil rozklad 50- ciferných čísel. Rokem 1990 se prolomila 100- ciferná čísla a bylo umožněno jejich rozkládání na prvočinitele. V polovině devadesátých let s použitím internetové sítě bylo rozloženo 129 místné číslo. Kolem roku 1996 bylo rozloženo až 130- ciferné číslo.Pro zajímavost je zde uvedena i soutěž, která se konala v roce 2003. Jejímž cílem byl rozklad 174- ciferného čísla. Odměna se pohybovala v řádu tisíců dolarů a rozklad se ke konci roku podařil najít obr. 4.

Obr. 4 RSA-Challenge 2003

Otázka k zamyšlení... Je jednička prvočíslo?Diskuze na toto téma by mohla být velmi zajímavá, zkuste se ovšem zamyslet, jaké podmínky musí číslo splňovat, aby se mohlo nazývat prvočíslem...

jednička prvočíslem není
prvočíslo je definované tak, že musí být dělitelný dvěma různými čísly - jedničkou a samo sebou
jednička je dělitelná jedničkou a sama sebou, ovšem toto je pouze jeden dělitel

Problém diskrétního logaritmu

Vedle připomenutí pojmu prvočíslo se v následujících článcích setkáme s pojmem „neřešitelnost“ diskrétního logaritmu. Nebudeme zde zabíhat do složitých matematických definic tohoto pojmu.

Eulerova funkce

Eulerovu funkci nebudeme definovat jako správní matematici, ale spíše jen pro naše chápání a pochopení její aplikace v následujících studijních aktivitách.Eulerova funkce, kterou používá především algoritmus RSA, je dána takto: f(p^k) = (p - 1)*(p^k-1), kdy f je funkce, která nám říká, že p je prvočíslo a s k je navzájem nesoudělné.Tvoří jenom součást z mnoha výpočtů, které se například v algoritmu RSA musí vykonat.

Soudělnost x nesoudělnost

Vedle problému vysokoškolské matematiky se bezpečnost algoritmů opírá také a velice jednoduchý problém soudělnosti a nesoudělnosti dvou čísel.Dvě čísla jsou soudělná, pokud mají alespoň jednoho společného dělitele kromě čísla 1 (čísla 5 a 25 jsou soudělná, protože jejich společný dělitel je 5 a 1). Naopak čísla 3 a 13 jsounesoudělná, protože jediný společný dělitel je číslo 1.

Div a mod

Zkuste zapátrat v paměti... Kdo už jste někdy programoval, určitě jste k některým dílčím úkonům použil klíčová slova mod a div.Vzpomněli byste si, co znamenají?

div je celočíselné dělení
mod je potom zbytek po tomto dělení (respektive operace, která vrátí zbytek po celočíselném dělení)
operace mod je hojně využívána opět především u algoritmu RSA, kdy je zbytek (mod) využíván pro další výpočty
rozdíl mezi operaci ukazuje následující schéma obr. 5

Obr. 5 Dělení

Poznámka: operace mod provede dělení, celočíselný výsledek zahodí, a vrátí nám pouze hodnotu zbytku po celočíselném dělení.Se znalostí těchto pojmů se tedy můžeme pustit do vysvětlení principu asymetrického šifrování.

Shrnutí

Ujasnili jsme si pojmy, které budou v dalších studijních aktivitách hojně využívány. Probrali jsme soudělnost a nesoudělnost čísel, dotkli se problému prvočísel a jejich umocňování, které souvisí s Eulerovou funkcí. Řekli jsme si také, co je to mod a div. Nyní se tedy podíváme na aplikování těchto pojmů.

Zdroje

TESKOVÁ, Libuše. Lineární algebra. 3. vyd. Plzeň: Západočeská univerzita, 2010, 243 s. ISBN 978-80-7043-966-1.