RSA

  • 1970 - Uveden Rivestem, Shamirem a Adlemanem

  • Používán dodnes

  • Šifrovací systém VK (veřejného klíče) založen na modulárním umocňování

  • Dvojice je veřejná část klíče (VK)

    • - exponent
    • - modul, součin dvou prvočísel a , tedy a
    • (aby existovala inverze , tedy )

  • Dvojice je tajná/soukromá část klíče (SK)

  • Šifrovací předpis totožný s exponenciální šifrou, jen je jiná podmínka pro

  • Dešifrovací předpis obdobný, musí existovat multiplikativní inverze

  • ! Čas cca 00:20:00 na tabuli z 6. přednášky bude chtít vysvětlit u zkoušky

    • Problém: Pokud vím faktorizaci - tedy zjistit a , pak umím udělat , tedy jsem schopen spočítat pomocí rozšířeného Euklidova algoritmu
      • Eulerova věta
      • Formátová věta
    • U exponenciální musí být šifrovací klíč utajený, jinak lze spočítat dešifrovací
    • U RSA šifrovací klíč lze zveřejnit, ale nesmím zveřejnit rozklad !!

  • ! V čem tkví bezpečnost? Porovnat s exponenciální šifrou

Příklad šifrování

    • Podmínka

  • Zpráva OT

  • Převedeme do číselných ekvivalentů

  • Rozdělíme do bloků o délce 4 číslic (protože je 4-ciferné)

  • Přidáme padding ()

  • Šifrujeme po blocích pomocí

  • Dostáváme ŠT

Příklad dešifrování

    • Podmínka

  • Najdeme multiplikativní inverzi

  • Zpráva ŠT

  • Dešifrujeme

  • Dostáváme OT

Formální definice

../Attachments/Pasted image 20230404150311.png

Bezpečnost RSA

  • Rabinův-Millerův pravděpodobnostní test prvočíselnosti
  • Doporučení: zvolit jako nějaké prvočíslo větší než a
  • Pokud znemožnění odkrytí bloku otevřeného textu následným jednoduchým odmocňováním celého čísla

../Attachments/Pasted image 20230404151901.png

Využití RSA

  • Šifrování
  • Autentizace (zpráva byla zašifrována (podepsána) privátním klíčem odesílatele, lze ověřit pomocí jeho veřejného klíče)

../Attachments/Pasted image 20230404152342.png

RSA-CRT

  • Urychlení šifrování - exponenty s malou Hammingovou váhou (málo nenulových bitů)

    • např.
    • Díky tomu např. u algoritmu Square&Multiply nemusíme dělat tolikrát krok Multiply

  • Urychlení dešifrování - Využívá Čínskou větu o zbytcích

    • Číslo od 0 do 102 lze reprezentovat nějakou kombinací zbytků

  • Dešifrovací proces rozkládá do více paralelních výpočtů (více vláken)

  • Veřejný klíč je stejný jako u RSA -

  • Soukromý klíč je složitější -

../Attachments/Pasted image 20230404153900.png

  • ! Jak urychlujeme šifrování
  • ! Proč dešifrování děláme s Čínskou větou o zbytcích

Šifrování

  • Stejné jako pro RSA, tedy

Dešifrování

  • Dešifrovací proces rozkládá do více paralelních výpočtů (více vláken)
  • Lze dosáhnout až 8x zrychlení

../Attachments/Pasted image 20230404154052.png

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25