SKS 2022 cvicenie 4

Zhrnutie prednášky

Cvičenie z Kryptografických systémov sa venuje príprave na útok typu Certificate Manipulation, ktorý sa bude demonštrovať na protokole príbuznom Diffie-Hellmanovmu. Prednášajúci preto najprv zopakoval problém diskrétneho logaritmu: v cyklickej grupe Z_p* s generátorom g treba nájsť exponent x, pre ktorý g^x ≡ β (mod p). Tento problém je pre klasické počítače ťažký, čo umožňuje jeho využitie v asymetrickej kryptografii, napríklad v ElGamalovom kryptosystéme. Z_p* má však podgrupy, ktoré by útočníkovi uľahčili úlohu, preto sa často používa podgrupa prvočíselného rádu q, ktorá už podľa Lagrangeovej vety ďalšie podgrupy nemá. Problém možno formulovať pre ľubovoľnú konečnú cyklickú grupu, no napríklad v aditívnej grupe Z_n je ľahký, lebo sa rieši rozšíreným Euklidovým algoritmom. Na záver prednášajúci začal vysvetľovať Diffie-Hellmanov protokol na výmenu kľúča medzi Alicou a Bobom.

• - Problém diskrétneho logaritmu: nájsť x také, že g^x ≡ β (mod p), kde g je generátor cyklickej grupy.
• - Pre klasické počítače nie je známy efektívny algoritmus, efektívne by ho vyriešil až výkonný kvantový počítač.
• - Z_p* má podgrupy, ktoré útočníkovi uľahčujú útok, preto sa používa podgrupa prvočíselného rádu q bez ďalších podgrúp (Lagrangeova veta).
• - V aditívnej grupe Z_n je problém diskrétneho logaritmu ľahký, rieši sa rozšíreným Euklidovým algoritmom.
• - Ťažký je aj v grupách eliptických kriviek, ktoré sa využívajú napríklad v ElGamalovi.
• - Diffie-Hellmanov protokol slúži na vytvorenie spoločného tajomstva medzi Alicou a Bobom v konečnej cyklickej grupe.
• - Tieto základy slúžia ako príprava na demonštráciu útoku Certificate Manipulation.

Zhrnutie pripravené s pomocou AI z prepisu videa.