Stránka 1 z 1

Zkouška - Úvod do kryptografie (Mareš, 2020)

Napsal: 18. 6. 2020 18:02
od Quake
Ahoj, zde přidávám nějaké postřehy ze zkoušky. Zkouška sestává ze dvou částí, jednou je teoretická otázka a tou druhou příklad.
Teoretická otázka je nejspíš zpravidla nějaké větší téma nebo případně přímo nějaká šifra, pokud je o ní trochu více informací. Já dostala Diffieho-Hellmana, ke kterému chtěl vědět základní verzi, různé útoky a pak i to, proč volíme grupu kvadratických zbytků. Dále chtěl vědět, jakým způsobem se najde generátor v multiplikativní grupě. Spolužák dostal jako otázku módy blokových šifer, ten měl napsat všechny příklady, které jsme si říkali, útoky na módy, jaké informace, který mód propouští a jak se vyhnout paddingu.
Příklad byl následující:
Máme certifikační autoritu, která plní dvě funkce. První funkcí je klasické podepisování certifikátů, tedy vy uživateli pošlete váš veřejný klíč, CA ho ověří a pokud je vše v pořádku, tak pošle E(hash(cert) | 0). Druhou službou, kterou nabízí je timestampování zpráv, to probíhá tak, že pošlete CA libovolnou zprávu, která však nesmí být příliš dlouhá a CA vám pošle nazpět: E(zpráva | 1). CA používá k podepsání obou služeb RSA, kde e je tajný šifrovací klíč a d je veřejný klíč. Šifrovací klíč je pro obě služby stejný. Vaším úkolem je podepsat si libovolný klíč.
Řešení: Tady je potřeba uvědomit si, že chceme využít multiplikativnosti RSA (což nám Mareš napověděl, když jsme si nevěděli rady). Tedy, že E(x*y) = E(x)*E(y). To využijeme tak, že si uvědomíme, že ten podepsaný klíč, který chceme získat, bude vlastně nějaké sudé číslo (protože nakonec se přilepí nula) a to můžeme rozepsat jako součin dvou lichých čísel. Tato čísla najdeme tak, že nejdříve najdeme jedno - budeme prostě zkoušet lichá čísla. A to druhé umíme dopočítat přes multiplikativní inverzy. Pokud by to bylo soudělné s n, tak jsme právě našli faktor n a můžeme si podepsat cokoliv. Jakmile jsme našli naše dvě lichá čísla, tak si prostě obě zvlášť necháme podepsat a součin těch podpisů nám dá podpis našeho klíče a opět jsme vyhráli. CA tohle může opravit tak, že zahešuje i tu zprávu, kterou timestampuje, protože najít dva heše, který dají sudé číslo, je už příliš obtížné.

Na příklad i teoretickou otázku máte v podstatě neomezeně času (alespoň na našem termínu, který jsme si s Marešem domluvili a nebyl ani vypsán to tak bylo). Mareš nám zadal teoretickou otázku a příklad a pak jsme mohli psát. Jakmile to už máte, tak za ním jen přijdete a on vám buď dá známku nebo chce, aby jste ještě něco připsali. V případě příkladu vám poradí, pokud si nevíte rady a přišlo mi, že na něm až tak nebazíroval.