Hlavní navigace

Názor k článku Mají i dnes smysl otevřené validující resolvery? od Vít Šesták - Ona se vůbec těžko dokazuje výpočetní náročnost. Doufáme...

  • Článek je starý, nové názory již nelze přidávat.
  • 19. 5. 2017 20:36

    Vít Šesták

    Ona se vůbec těžko dokazuje výpočetní náročnost. Doufáme a věříme, že pro RSA ani ECC neexistuje algoritmus pro prolomení v lineárním čase na klasickém (nekvantovém) počítači. Ale kdyby se to někomu povedlo dokázat, dokáže tím zároveň P≠NP.

    Taky se čeká, že prolomení RSA ani ECC není NP-complete. Opět, kdyby se to někomu povedlo dokázat, dokáže tím P≠NP. A kdyby to náhodou bylo NP-complete, znamenal by Shorův algoritmus s příchodem kvantových počítačů hrozbu nejen pro dnes převládající asymetrické algoritmy, ale i pro symetrické algoritmy a postkvantové algoritmy – vlastně by zbyly unconditionally secure algoritmy (Vernamova šifra, Shamir Secret Sharing Scheme, …) a vše ostatní by rozluštil kvantový počítač v polynomiálním čase.

    A dokázat relativní sílu ECC vůči RSA bude asi ještě vetší oříšek než dokazovat asymptotickou složitost, kde můžete zanedbat některé konstanty…