Vytisknout celou knihuVytisknout celou knihu

Asymetrické šifrování

Stránky: Moodle ZČU
Kurz: KVD/UIN Úvod do informatiky pro vzdělávání - šablona
Kniha: Asymetrické šifrování
Vytiskl(a): Nepřihlášený host
Datum: neděle, 8. listopadu 2026, 20.19

Obsah

1. Matematika pro kryptology



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:

šipka

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(pk) = (p - 1)*(pk-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.





2. Asymetrické šifrování



Asymetrické šifrování


Od symetrických šifer a vysvětlených pojmů matematiky se podíváme na asymetrický způsob šifrování.


Odlišnosti symetrického a asymetrického šifrování

Zásadní rozdíl mezi symetrickým a asymetrickým šifrování je v použití klíče.


Vzpomenete si ještě, jaký je rozdíl mezi symetrickým a asymetrickým způsobem šifrování?

  • symetrické šifrování obr. 1 užívá stejného klíče pro kryptografii (šifrování) i kryptoanalýzu (dešifrování), proto je důležité, aby se klíč vyměnil ještě před vzájemnou komunikací a první výměnou dat. Tato výměna může být právě onou krizovou záležitostí, neboť při předání může dojít k odposlouchávání. Pokud se klíč dostane do nepovolaných rukou, data nejsou v bezpečí a daný špion, který klíč získal, se bez problému dostane i k ukrytým údajům.

Obr. 1


  • asymetrické šifrování obr. 2 je založeno na použití odlišných klíčů. Jiný klíč je zapotřebí pro šifrování, další pro dešifrování.

Obr. 2



Nový princip

Transport veřejného klíče se obešel tak, že jej může znát kdokoli. Systém však vedle tohoto veřejného (public key) má i klíč tajný (private key). A pouze ten, kdo zná tajný klíč, může rozšifrovat text.


Princip funguje jako krabička se zámky a dvěma klíči. Určitě si vzpomenete na příklad s Pepou a Jarmilkou z úvodních studijních článků tohoto kurzu.

šipka

- Nejprve komunikace mezi Pepou a vámi ztroskotala na tom, že Jarmilka slyšela, co si říkáte...- Potom jste byl rafinovanější a zprávu zašifroval. Použil jste symetrickou šifru, kde je problematický bezpečný přenos klíče, a důsledkem toho by mohlo být, že se Jarmilka ke klíči propracuje znovu...

Asymetrické šifrování spočívá v tom, že vy pošlete Pepovi samotný otevřený zámek. Pepa vloží data do krabičky a zámek zamkne svým klíčem. Vy poté můžete zámek odemknout svým klíčem, ale pokud chcete Pepovi odpovědět, musíte mít opět jeho otevřený zámek, kterým zamknete krabičku s daty.

Tuto ideu poprvé implementovali v algoritmu RSA jeho autoři obr. 3. Metoda bude podrobně rozebrána v následujících studijních článcích.

Obr. 3 Ronald Rivest, Adi Shamir a Leonard Adleman - autoři algoritmu RSA


Obecně přínos asymetrického šifrování spočívá v použití matematických operací pro ukrytí klíče. Algoritmy blokových šifer, jejichž bezpečnost nebyla prozatím prolomena, máme. Nyní je potřeba vyřešit problém s transportem klíče.

Pro transport klíče si představíme některé algoritmy, které byly vymyšleny. Takovýmito představiteli mohou být D-H Protokol či již zmiňovaný šifrovací algoritmus RSA.


Shrnutí

Po představení a důkladném probrání některých algoritmů z rodiny symetrických šifer se nyní díváme na asymetrické šifry. Zopakovali jsme si hlavní rozdíly mezi symetrickým a asymetrickým šifrováním a představili některé zástupce.


Zdroje

DOSTÁLEK, Libor a Marta VOHNOUTOVÁ. Velký průvodce infrastrukturou PKI a technologií elektronického podpisu. vyd. 1. Brno: Computer Press, 2006, 534 s. ISBN 80-251-0828-7.

JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.





3. Diffie & Hellman



Diffie & Hellman


Poprvé formulovaná myšlenka, která odhalila jinou možnost šifrování, byla popsána v článku New Directions in Cryptography v roce 1976. Autoři tohoto článku byli Whitfield Diffie obr. 1 a Martin Hellman obr. 2.

Obr. 1 Whitfield Diffie



Obr. 2 Martin Hellman



D-H protokol

Tento protokol, pojmenovaný po svých autorech (W. Diffie a M. Hellman; někdy také algoritmus Diffie-Hellman, či Diffie-Hellmanův protokol) není klasický algoritmus šifrování, ale spíše bezpečná varianta transportu klíče mezi komunikujícími osobami.

Celá hlavní myšlenka spočívá v tom, že zjištění klíče pro šifrování či dešifrování je umožněno každému účastníkovi komunikace za použití informací, které jsou zaslány nezabezpečeným kanálem. Pro případného útočníka je však dopočítání klíče, při znalosti těchto veřejných informací v současné době, nemožné. Vtip je v použití jednosměrné matematické funkce, která využívá mocnin a oblíbené funkce modulo.


Komunikace probíhá následujícím způsobem:


šipka

  • všichni se veřejně domluví na použitém modulu m a počátečním základu z; m a z jsou tedy veřejným klíčem; dobré je, když tato čísla jsou prvočísla
  • každý sám za sebe si zvolí svůj exponent e; exponent nesmí být soudělný s modulem - exponent je tedy soukromý klíč každého
  • dále pak každý umocní základ modulárně na svůj exponent a výsledek pošle dalšímu
  • algoritmus protokolu končí, když je každý z původních základů zpracován každým účastníkem - kolo se uzavře

Přehledně a srozumitelně je to zobrazeno na obrázku obr. 3. Protokol je součástí většiny algoritmů určených pro digitální podpis.

Obr. 3 Princip D-H protokolu


Shrnutí

Představili jsme si jeden z prvních protokolů, který umožňuje bezpečný transport klíče mezi zainteresovanými osobami.

Zdroje

JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.SINGH, Simon. Kniha kódů a šifer: tajná komunikace od starého Egypta po kvantovou kryptografii. 2. vyd. v českém jazyce. Praha: Dokořán, 2009. ISBN 978-807-3632-687.





4. RSA



RSA


Roku 1977 přišli Ron Rivest obr. 1, Adi Shamir obr. 2 a Joe Adleman obr. 3 s implementací D-H protokolu pro svůj algoritmus. Asymetrická šifra RSA byla první tohoto typu. Zkratka RSA je tvořena počátečními písmeny příjmení autorů. Celý systém je založen na jednoduché myšlence.

Obr. 1 Ron Rivest



Obr. 2  Adi Shamir



Obr. 3  Leonard Adleman




šipka

Je snadné vynásobit dvě dlouhá prvočísla, ale bez jejich znalosti je prakticky nemožné zpětně provést rozklad výsledku na původní prvočísla.

Princip

Pro pochopení algoritmu slouží schéma, představující obecný algoritmus       obr. 4. Schéma ukazuje jak šifrování, tak dešifrování.


Obr. 4 Obecné schéma algoritmu RSA



Princip

Pro pochopení algoritmu slouží schéma, představující obecný algoritmus. Schéma ukazuje jak šifrování, tak dešifrování.Princip:
  • Zvolíme dvě různá velká náhodná prvočísla p a q (my volíme prvočísla, která umíme relativně rychle spočítat a jsou v řádu desítek či stovek, v praxi se používají 100 i více ciferná čísla).
  • spočítáme jejich součin m = p × q (dokážete si představit dvě 100ciferná čísla, která máte spolu vynásobit?).
  • najdeme dvě čísla i a j tak, aby platilo (i × j) mod [(p − 1) × (q − 1)] = 1.

Pro šifrování čísla x potom volíme veřejný klíč složený z (m;i), který použijeme ve vzorečku y = xi mod m. Pro dešifrování čísla y volíme soukromý klíč složený z (m;j), který použijeme ve vzorečku x = yj mod m.

Příklad: Šifrujte pomocí algoritmu RSA zprávu. Zadané máme x = 3. Na obrázku 5 vidíme opět šifrování i dešifrování. (Pro šifrování známe tedy x = 3, pro dešifrování musíte znát y = 12)


Obr. 5 Příklad šifrování pro x = 3 a dešifrování pro y = 12

Kompletní ukázka šifrování RSA pro p = 3, q = 7, x = 3 a y = 12.

Kryptoanalýza

Fakt, že není znám algoritmus, jenž dokáže vytvořit k veřejnému klíči klíč soukromý, tvoří základ každého asymetrického kryptosystému. Není ani dokázáno, že je nutné prolomit šifru pomocí modulární matematiky - čili hledáním prvočísel. Je možné, že existuje algoritmus, který rozluští zašifrovaný text jinak, než pomocí znalosti čísel. Dostupnými prostředky ale zatím není možné RSA prolomit. Teoreticky, pokud by se někomu podařilo najít čísla p a q, poté je na základě matematických znalostí možné, že přijde i na čísla i a j, která představují exponenty, a dopočítá se správného výsledku - klíče.Dnešní dostupná počítačová technika umožňuje rozložit číslo, které bude mít kolem 100 cifer. Poslední informace pocházející z RSA Challenge z roku 2003 říká, že nejmenší číslo vložené do algoritmu mělo 174 cifer.[1] Sami si můžete vyzkoušet dvě cvičení. V prvním jsou prvočísla malá a dopočítáte se velmi rychle, u druhého jsou volena čísla větší. A představte si, jak by vypadalo počítání s řádově 100- cifernými čísly. V praxi se totiž nepoužívají čísla jako 3, 7, 87, 141, ale několikaset násobná. Proto je i pro výpočetní techniku složité rozložit tolika místné číslo. Na obrázku můžete vidět rozklad 174- místného čísla, které bylo v již zmiňované soutěži RSA Challenge obr. 6.

Obr. 6  RSA-Challenge 2003



Použití

Systém RSA je hojně využíván při digitálním podpisu. Představte si, že chcete podepsat svá data a vyslat je do světa tak, aby každý věděl, že autorem jste vy.Napadlo by vás, jak toto realizovat?
  • použijeme digitální podpis

RSA je také užíváno jako součást PGP. Nyní jsou připravena cvičení sloužící k upevnění jednotlivých funkcí, které algoritmus RSA používá.

Shrnutí

Představili jsme si jednoho z dalších představitelů asymetrického šifrování, kterým je algoritmus RSA. Používali jsme prvočísla, která by v praxi ani omylem neuspěla, ovšem pro vysvětlení principu šifrování a dešifrování, jsou dostačující.

Zdroje

DOSTÁLEK, Libor a Marta VOHNOUTOVÁ. Velký průvodce infrastrukturou PKI a technologií elektronického podpisu. vyd. 1. Brno: Computer Press, 2006, 534 s. ISBN 80-251-0828-7.JIROUŠEK, Radim. Principy digitální komunikace. Vyd. 1. Voznice: Leda, 2006, 309 s. ISBN 80-733-5084-X.





5. Cvičení: RSA s „malými“ prvočísly

Zadání

Stojí před vámi nelehký úkol, zde je jeho zadání, které je rozděleno do tří bodů.


1. Šifrujte algoritmem RSA, za předpokladu, že víte:

šipka

  • x = 5
  • m = 55
  • i = 3
  • chceme znát hodnotu y

2. Dešifrujte algoritmem RSA, pokud znáte:

  • y = 15
  • j = 67
  • m = 55
  • chceme znát hodnotu x

3. Porovnejte hodnoty x a y a zjistěte, jestli došlo k manipulaci se zprávou během jejího transportu.




Tipy pro řešení

  • vzpomeňte si, co jsme si říkali o algoritmu RSA
  • doporučené je použít vědeckou kalkulačku v počítači (zobrazuje na více míst než klasická kalkulačka)
  • neztrácejte trpělivost




Návrh řešení





6. Cvičení: RSA s „velkými“ prvočísly

Zadání

Nyní tedy podobné zadání jako u minulého cvičení. Úloha je rozdělena do tří bodů.


1. Šifrujte algoritmem RSA, za předpokladu, že víte:

šipka

  • x = 45
  • m = 3233
  • i = 11
  • chceme znát hodnotu y

2. Dešifrujte algoritmem RSA, pokud znáte:

  • y = 2354
  • j = 851
  • m = 3233
  • chceme znát hodnotu x

3. Porovnejte hodnoty x a y a zjistěte, jestli došlo k manipulaci se zprávou během jejího transportu.




Tipy pro řešení

  • princip je pořád stejný, velkých čísel se nebojte
  • doporučené je použít vědecké kalkulačky (či některého ze specializovaných programů pro matematické operace)




Návrh řešení