|
|
Složitost některých faktorizačních algoritmů
Štěpánek, Vilém ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent)
Práce se věnuje odhadu složitosti běhu algoritmu pro faktorizaci celého čísla použitím metody ECM. Nejprve jsou nastíněny základní vlastnosti eliptických křivek nad konečným tělesem a uvedeny dvě věty, na kterých se daná problematika zakládá. Následně jsou provedeny potřebné odhady různými konstantami a nastíněn princip fungování algoritmu ECM pro faktorizaci celého čísla. Poté je ukázána odhadovaná složitost algoritmu ECM a na závěr je rozvedena implementace faktorizačního algoritmu ECM.
|
|
|
Útoky na RSA založené na redukci mřížky
Vaněček, Jaromír ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent)
Diplomová práce má za cíl podrobně prostudovat Coppersmithův algoritmus pro hledání malých kořenů polynomiálních kongruencí, který je založen na re- dukci báze mřížky. Z tohoto algoritmu vychází celá řada útoků na nejrozšířenější asymetrickou šifrovací metodu RSA, a proto se práce dále zaměřuje na popis vybraných útoků. Jako jeden ze zásadních a aktuálních útoků můžeme zmínit tak zvaný ROCA, který umožňuje faktorizovat RSA modulus, pokud jsou prvo- čísla určitého tvaru. Nakonec je v práci Coppersmithův algoritmus, stejně jako útok ROCA, implementován a je provedena celá řada měření a experimentů. Z nasbíraných dat je možné vyčíst například, jak závisí doba běhu algoritmu na různých parametrech nebo jaké hodnoty parametrů jsou optimální v konkrétních situacích. 1
|
|
|
Generické algoritmy
Snítilá, Jitka ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent)
Práce se zaměřuje na odhad složitosti generických algoritmů pro problém dis- krétního logaritmu a Diffie-Hellmanových problémů. Pro tento účel práce zavádí dva rozdílné modely Black-Box. Na těchto modelech pak práce odhaduje a po- rovnává úspěšnost generických algoritmů pro uvedené problémy včetně takzvané Maurerovy redukce. Tato redukce řeší problém diskrétního logaritmu za pomoci vhodné eliptické křivky a orákula pro výpočet Diffie-Hellmanovy funkce. V zá- věru práce zkoumá generické algoritmy v souvislosti s vybranými identifikačními schématy, která jsou založená na problému diskrétního logaritmu. 1
|
|
|
Složitost některých faktorizačních algoritmů
Štěpánek, Vilém ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent)
Práce se věnuje odhadu složitosti běhu algoritmu pro faktorizaci celého čísla použitím metody ECM. Nejprve jsou nastíněny základní vlastnosti eliptických křivek nad konečným tělesem a uvedeny dvě věty, na kterých se daná problematika zakládá. Následně jsou provedeny potřebné odhady různými konstantami a nastíněn princip fungování algoritmu ECM pro faktorizaci celého čísla. Poté je ukázána odhadovaná složitost algoritmu ECM a na závěr je rozvedena implementace faktorizačního algoritmu ECM.
|
|
|
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
|
|
|
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.
|
|
| |
|
|
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.
|
host ::
RSS.