8 komentářů k článku P vs. NP – reálne dopady na webovú bezpečnosť:

  1. atamiri

    OMG
    Nechápu, jak tento článek prošel přes editora, je to dost ostudná vizitka redakce a někdo by se měl vážně zamyslet.

    “pričom x je fixné (a konečné!) číslo”

    Každé číslo je z definice konečné, chtěl-li autor mermomocí explicitně specifikovat, jaká čísla jsou relevantní, mohl napsat “reálné.”

    “do množiny NP patria všetky tie ostatné, pre ktoré polynominálny algoritmus nepoznáme”

    To je špatně, NP je nadmnožina P (plyne přímo z definice, že jde o problémy řešitelné v polynomiálním čase nedeterministickým TS) a P=?NP je otázka, jde-li o nadmnožinu vlastní.

    1. Filip OpálenýAutor příspěvku

      Re: OMG
      Ahoj,

      čo sa týka „konečných“ čísel, prívlastok bol pridaný čisto ako dovysvetlenie. Článok je určený aj pre menej zbehlých ľudí a nie každý musí vedieť že „nekonečno“ v bežnom kontexte číslo nie je. Okrem toho, existujú aj pojmy „kardinálne číslo“ či „hyperreálne číslo“, označujúce práve nekonečná.

      S druhou vetou máš samozrejme pravdu, pôvodne som sa snažil vysvetliť NP vs. NP-hard vs. NP-complete, čo som ale škrtol aby som neodbiehal pridaleko od témy. No a pri škrtaní vzniklo toto. Napíšem editorovi nech to pozmení.

      1. atamiri

        Re: OMG
        Jo, vypadalo to jako kiks po úpravě, proto jsem psal, že to je primárně chyba editora/korektora.
        Článku by asi prospělo vysvětlení vztahů mezi NP, NP-hard a NP-complete.

    2. Martin Hassman

      Re: OMG

      Díky, tu větu s množinami jsem změnil, viz komentář autora.

      Jinak si dovolím připomenout, že tohle není akademický text, ale článek pro širší publikum. Na slovíčkaření si tu nehrajeme.

      1. atamiri

        Re: OMG
        Právě proto, že je pro širší publikum, by neměl obsahovat takové zjevné chyby. Korektní vyjadřování není slovíčkaření.

  2. v6ak

    O(n^3) není až tolik

    Vezmime si algoritmus zložitosti rádovo n^3 – dĺžka výpočtu nanajvýš rovná tretej mocnine dĺžky vstupu – v takom čase funguje napríklad algoritmus Bellman-Ford pre hľadanie najkratšej cesty grafom. n^3 je polynóm (najkratšia cesta teda patrí do P) pomerne malý, ale pre niektoré praktické aplikácie je už tento algoritmus príliš pomalý. Je potrebné siahnuť po rýchlejších algoritmoch ako Dijkstra či A*.

    S obecným principem (polynom dostatečně velkého stupně by mohl stačit) souhlasím, ale zrovna O(n^3) není v kryptografii až tak moc – vždyť třeba u RSA se používají algoritmy, které šifrují a dešifrují v O(n^3). Pokud bychom měli algoritmus, ktrerý v O(n^3) spočítá privátní RSA klíč z veřejného, byl by na tom útočník asymptoticky stejně jako legitimní uživatel a zachránit by to mohly už jen konstanty. Což v situaci, kdy legitimní uživatel chce rychlou funkčnost na mobilu (omezené CPU a baterie) a útočník má k dispozici grid a čas třeba i několik let, by muselo znamenat fakt monstrózní konstanty. Navíc konstanty lze někdy „umlátit“, třeba pomocí FPGA nebo ASIC. Nebo pomocí GPU, pokud je algoritmus dobře paralelizovatelný.

    A to jsem uvažoval RSA a ne třeba AES-128, který má řádově kratší klíče. U RSA se dnes doporučuje minimálně 2028b klíč (což je jen délka modulu, ne délka celého klíče), u AES-128 se používá 128b klíč. A v tomto světle by na tom nebyl až tak dobře ani AES-256…

    Ale pokud to bude O(n^19), měl nevyplatilo by se to (z hlediska počtu operací) pro 128b klíče, u O(n^32) ani pro 256b klíče. (Ten exponent 19 by mohl být ještě o trochu menší, ale pak by nebyl celočíselný…) Samozřejmě, ještě hraje roli cena operace (tedy ony konstanty), ale v případě symetrické operace už dnes tyto operace pro known-plaintext bruteforce jsou dost levné (což chce i legitimní uživatel, aby kryptografie nepřinášela velkou režii) a nedal by se moc čekat průlom, který by zde útočníkovi pomohl.

  3. v6ak

    NP vs. NP-complete
    Základní sdělení článku OK, ale chtělo by si to po sobě více přečíst…

    Nikdy totiž nebolo dokázané, že na dešifrovanie správy bez kľúča je potrebné vyriešiť nejaký NP problém.

    Pokud myslíte NP-úplný problém, pak souhlas. (Nebo aspoň o tom není známo, přesněji řečeno.) Ale tak, jak je to napsané, to není pravda. Nějaký problém vyřešit musíme, a určitě se vejde do třídy NP, dost možná i do nižší.

    Proč je potřeba rozlišovat NP a NP-úplné problémy lze vidět kousek výše. Ve článku potřebujeme oba pojmy. Kdybychom všechny výskyty „NP“ nahradili za „NP-úplný“, opravili bychom sice výše uvedený úryvek, ale pak by byl zase problém tady:

    všetky používané algoritmy na asymetrickú kryptografiu (využívané v TSL, S/MIME, Tor…) závisia nejakým spôsobom na NP probléme ako faktorizácia na prvočísla či diskrétny logaritmus

    Tady nemám problém s doslovným zněním (až na „TSL“, což asi mělo být „TLS“), ale ukazuje to, proč nelze míchat „NP“ a „NP-úplný“ do jednoho pojmu. Jak faktorizace tak diskrétní logatirmus jsou v NP, ale dost možná nejdou NP-úplné. To není snadné dokázat (kdybych to uměl, dokázal bych zároveň, že P≠NP), ale je tu pár vodítek. Oba problémy patří do BQP, protože je díky Shorovu algoritmu můžeme na kvantovém počítači vyřešit s určitou ohraničenou pravděpodobností úspěchu v polynomiálním čase. To u problémů, o kterých víme, že jsou NP-úplné, neumíme. A nejspíš ani umět nebudeme – NP-úplné algoritmy umí na kvantovém počítači řešit Groverův algoritmus, o kterém bylo dokázáno (zřejmě za podmínky P≠NP), že je optimální. Jenže Groverův algoritmus není polynomiální, dovede „jen“ s ohraničenou chybovostí prohledat N možností v O(sqrt(N)), tedy bruteforce původně v O(n^2) zkrátí na O(n^(n/2)).

    Ono v tom článku není až tak podstatné, že faktorizace zřejmě není NP-complete, jen jsem chtěl ukázat, že článek zmiňuje jak třídu NP, tak NP-complete, a měl by pro obojí používat jiný pojem, jinak je to matoucí.

Napsat komentář

Zdroj: https://www.zdrojak.cz/?p=20630