Kryptografia | 14.4.2020 9:15 | RSA

Zhrnutie prednášky

Prednáška sa venuje generovaniu kľúčov v šifrovacom systéme RSA na konkrétnom príklade s p = 7 a q = 17. Eulerova funkcia φ(m) sa pre súčin dvoch prvočísel počíta ako (p−1)(q−1) = 96, pričom p a q už nie je potrebné poznať. Šifrovací kľúč e sa volí menší ako φ(m) a nesúdeliteľný s ním, čo sa overuje cez najväčší spoločný deliteľ; zvolené je e = 13. Dešifrovací kľúč d je multiplikatívny inverzný prvok k e modulo φ(m), teda platí e·d ≡ 1 (mod φ(m)). Na jeho výpočet sa používa Euklidov algoritmus a jeho rozšírená verzia, ktorej postup lektor začína rozpisovať spätným dosadzovaním zvyškov.

• - Pre súčin dvoch prvočísel platí φ(m) = (p−1)(q−1); v príklade φ(m) = 6·16 = 96.
• - Po výpočte m a φ(m) už nie je potrebné poznať prvočísla p a q.
• - Šifrovací kľúč e musí byť menší ako φ(m) a nesúdeliteľný s ním, teda gcd(e, φ(m)) = 1.
• - V príklade je zvolené e = 13 (overené cez Wolfram Alpha) a je to verejný kľúč.
• - Dešifrovací kľúč d je multiplikatívny inverzný prvok k e, platí e·d ≡ 1 (mod φ(m)).
• - Na nájdenie d sa používa rozšírený Euklidov algoritmus pre čísla 13 a 96.
• - RSA potrebuje verejný kľúč m, verejný kľúč e a súkromný kľúč d.

Zhrnutie pripravené s pomocou AI z prepisu videa.