ECC a problém diskrétního logaritmu

  • Využití problému diskrétního logaritmu

  • Pro určitý bod na křivce postupně vypočítáme body

  • Křivka má konečný počet bodů - řád křivky (počet bodů na křivce), označíme

  • V kroku se nám začne posloupnost bodů opakovat

  • V bodě opakování tak platí , kde je některý z předešlých bodů

  • existuje nějaké takové, že

  • V posloupnosti se vždy dostaneme k bodu a poté cyklus začíná znovu od bodu protože

  • ! Nejmenší takové , pro které je nazýváme řád bodu (lze také označit )

  • Řád bodu dělí řád křivky

  • V kryptografii volíme takové body, jejichž řád je roven největšímu prvočíslu v rozkladu čísla nebo jeho násobku

  • ! Kofaktor = řád křivky / řád počátečního bodu, měl by být malý (protože vybírám největší prvočíslo z rozkladu)

Problém diskrétního logaritmu

  • Zvolme jako privátní klíč číslo

  • Vypočteme

  • Potom body a lze zveřejnit jako součást VK

  • Nikdo z nich pak není schopen dopočítat číslo

  • (Pro malá je úloha triviální, pro velká nelze řešit v polynomiálním čase)

  • (Pokud máme , dostáváme kroků (tj. zhruba na úrovni symetrické blokové šifry se 128b klíčem))

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