|
|
Prosívání ve faktorizačních algoritmech
Staško, Samuel ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent)
Kvadratické a číselné síto jsou dvě tradiční faktorizační metody. Uvádíme zde princip fungování obou těchto algoritmů, přičemž se zaměřujeme především na výpočet asympto- tické složitosti. Největší důraz klademe na rozbor prosívací fáze. Hlavním cílem práce je však popis různých modifikací, odhad jejich časové složitosti a porovnání praktické vyu- žitelnosti se základními verzemi. Kromě několika známých variant prezentujeme vlastní návrhy jak kvadratického, tak číselného síta a podrobně analyzujeme jejich výhody či nevýhody. 1
|
|
|
Prosívání ve faktorizačních algoritmech
Staško, Samuel ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent)
Kvadratické a číselné síto jsou dvě tradiční faktorizační metody. Uvádíme zde princip fungování obou těchto algoritmů, přičemž se zaměřujeme především na výpočet asympto- tické složitosti. Největší důraz klademe na rozbor prosívací fáze. Hlavním cílem práce je však popis různých modifikací, odhad jejich časové složitosti a porovnání praktické využi- telnosti se základními verzemi. Kromě toho prezentujeme vlastní variantu kvadratického síta, která má v některých oblastech oproti ostatním známým návrhům poměrně velké výhody. 1
|
|
|
O DSA
Čadová, Veronika ; Drápal, Aleš (vedoucí práce) ; Jedlička, Přemysl (oponent)
Bakalářská práce se věnuje problematice porovnávání bezpečnosti a složitosti digitalních podpisů DSA a Schnorr. Digitálni podpis je téměř plnohodnotnou, zákonem uznávanou alternativou k fyzickému podpisu, určenou pro využití v digitálním prostředí. Princip využívá asymetrických šifer a hašovacích funkcí, které jsou zde jednoduše popsány, stejně jako další základní pojmy, mezi něž patří problém diskrétního logaritmu a cyklické grupy. Práce se zabývá analýzou některých možných útoků na DSA a porovnáním DSA a Schnorrova algoritmu. Součásti textu je i pohled do historie a vlastní implementace digitálního podpisu.
|
|
|
Kryptoanalýza s využitím postranní informace
Primas, Martin ; Rosa, Tomáš (vedoucí práce) ; Jedlička, Přemysl (oponent)
V této práci útočíme pomocí postranní informace na implementaci schématu RSA, která využívá Montgomeryho aritmetiku a Čínskou větu o zbytcích. Náš útok vychází z již dříve předvedeného Tomoedova útoku, který je zde zkoumán exaktněji než v původním článku, je drobně upraven a zejména doplněn o teoretický odhad pravděpodobonosti jeho úspěchu. Dále je v práci vytvořen nový formální aparát k algoritmu na hledání aproximovaných největších společných dělitelů (ANSD), který využívá známý LLL algoritmus na hledání krátkých vektorů v mřížích. Hlavní obsah práce je ovšem v originálním spojení Tomoedova útoku a algoritmu na hledání ANSD, které přináší efektivnější útok proti představené implementaci RSA. Hledání optimálního spojení těchto algoritmů a popis konkrétních útoků je závěrečným vyústěním této práce.
|
|
|
Testování perfektních mocnin
Straková, Hana ; Stanovský, David (vedoucí práce) ; Jedlička, Přemysl (oponent)
Perfektní mocnina je takové přirozené číslo, které lze zapsat jako netriviální mocninu jiného přirozeného čísla. Přirozené číslo n tedy nazveme perfektní mocninou, pokud existují přirozená čísla x a k, obě větší než 2, taková, že n = x^k. Testy, zda je číslo perfektní mocnina, jsou důležité pro faktorizaci čísel nebo testy prvočíselnosti, které samy neumějí rozlišit, zda je vstupní číslo mocnina jiného čísla. Tato práce pojednává o dvou algoritmech na testování perfektních mocnin, prvním od E.Bacha & J. Sorensona a druhém od Daniela J. Bernsteina. Cílem práce je implementace algoritmů v jazyce C s pomocí knihovny GMP, srovnání teoretických výsledků pro jednotlivé algoritmy s praktickými měřeními a porovnání algoritmů mezi sebou z hlediska teoretického přístupu a rychlosti.
|
|
| |
|
| |
|
|
Pokročilé metody hledání diskrétního logaritmu
Matocha, Vojtěch ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent)
Mějme konečnou cyklickou grupu G generovanou prvkem g. Problém diskrétního logaritmu, tedy pro zadané y nalézt přirozené číslo x splňující g^x = y, představuje jeden ze základních pilířů moderních kryptografických transformací. Ve své práci podáváme přehled algoritmů, které se pro výpočet diskrétního logaritmu používají, včetně v současnosti nejrychlejšího známého algoritmu pro multiplikativní grupu konečného tělesa: funkčního síta. Kromě funkčního síta se podrobněji zabýváme index kalkulem a jeho optimalizacemi: Coppersmithovým algoritmem a polynomiálním sítem. Hlavním přínosem práce je implementace funkčního síta v jazyce C a její aplikace na konkrétní vstupy.
|
|
|
O DSA
Čadová, Veronika ; Drápal, Aleš (vedoucí práce) ; Jedlička, Přemysl (oponent)
Bakalářská práce se věnuje problematice porovnávání bezpečnosti a složitosti digitalních podpisů DSA a Schnorr. Digitálni podpis je téměř plnohodnotnou, zákonem uznávanou alternativou k fyzickému podpisu, určenou pro využití v digitálním prostředí. Princip využívá asymetrických šifer a hašovacích funkcí, které jsou zde jednoduše popsány, stejně jako další základní pojmy, mezi něž patří problém diskrétního logaritmu a cyklické grupy. Práce se zabývá analýzou některých možných útoků na DSA a porovnáním DSA a Schnorrova algoritmu. Součásti textu je i pohled do historie a vlastní implementace digitálního podpisu.
|
|
|
Number Field Sieve for Discrete Logarithm
Godušová, Anna ; Jedlička, Přemysl (vedoucí práce) ; Příhoda, Pavel (oponent)
Mnoho dnešních kryptografických systémů, jako například protokol Diffie- Hellman, je založených na problému diskrétního logaritmu. Síto v číselném tělese je algoritmus řešící faktorizaci velkých celých čísel, nové poznatky ale ukazují, že může být použit i na problém diskrétního logaritmu. V této práci studujeme síto v číselném tělese pro diskrétní logaritmus a porovnáváme ho se sítem v číselném tělese pro faktorizaci. Oba algoritmy jsou založeny na stejném principu, ale v jednotlivých krocích nalézáme velké rozdíly. 1
|
host ::
RSS.