Přejít k navigační liště

Zdroják » Různé » P vs. NP – reálne dopady na webovú bezpečnosť

P vs. NP – reálne dopady na webovú bezpečnosť

Články Různé

Taktiež vás postaršili, že ak sa nájde dôkaz známeho problému z teoretickej informatiky P = NP, internet padne na kolená? V tomto článku si rozoberieme čo je pravda, a čo skôr „novinárska kačica“.

Miliónový problém ohrozujúci ľudstvo

Problém P vs. NP je veľmi známy medzi ľudmi z oboru a nedávny neúspešný pokus o jeho riešenie (august 2017) od nemeckého profesora Norberta Bluma sa dostal aj do novín určených pre širšiu verejnosť. Tieto články tu a tam sprevádzali úvahy o apokalyptickom konci webu ako ho poznáme v prípade, že P sa rovná NP. Tvrdia, že zverejnený dôkaz by viedol k prakticky okamžitému prelomeniu všetkého šifrovania, ktoré je v súčasnosti používané.

K sláve problému prispieva aj jeho relatívne jednoduchá definícia kontrastujúca so zdanlivo náročným riešením – pre pochopenie problému stačí poznať niečo málo o výpočetnej zložitosti, riešenie zatiaľ ľudstvo nepozná. Popularizátorom je aj Clayov inštitút, ponúkajuci za korektný dôkaz milión amerických dolárov.

Čo to tie písmenká vlastne znamenajú?

Do množiny problémov P patria všetky programy, ktoré sa dajú vyriešiť svojim spôsobom rýchlo. Hovoríme, že majú polynominálnu časovú zložitosť – dĺžka výpočtu je nanajvýš rovná (dĺžka vstupu)^x, pričom x je fixné (a konečné!) číslo. Príkladom by bolo napríklad vyhľadanie prkvu v poli (prejdeme celým poľom nanajvýš raz – (počet prvkov)^1) alebo aj jeho utriedenie (napríklad v select sorte manipulujeme s každým prvkom nanajvýš toľko krát, koľko to pole obsahuje prvkov – (počet prvkov)^2).

No a množina NP je množina P rozšírená o problémy pre ktoré polynominálny algoritmus nepoznáme, za to výsledok vieme v polynominálnom čase overiť. Známym príkladom je problém Hamiltonovskej cesty – nájdenie takej cesty grafom, aby sme navštívili každý vrchol práve raz (a každú hranu nanajvýš raz). Pozrieť sa či sa v ceste neopakujú vrcholy je veľmi jednoduché. Ale jediný spôsob, čo poznáme na jej hľadanie, je vyskúšať skoro každú jednu cestu – a jednu po druhej ju overovať. To nám potom ale vyjde zložitosť celého problému v rádoch 2^(počet vrcholov) – to už polynóm nie je, keďže počet vrcholov nie je fixné číslo, ale závisí od vstupu.

A o čom teda je P vs. NP? Pre ani jeden NP problém ešte nebolo dokázané, že určite neexistuje polynominálny algoritmus čo by ho riešil. A tak sa nevie či množnina P je vlastne od NP nejak odlišná. Ak nie, znamenalo by to, že každý problém, ktorý dokážeme rýchlo overiť, dokážeme aj rýchlo vyriešiť. Možno je ľudstvo iba hlúpe a tieto jednoduché riešenia nám unikajú. A presne to je situácia s potenciálne katastrofickými následkami.

Naozaj nie šachová hádanka

Bohužial, nie každý novinár si plní domácu úlohu z teoretickej informatiky. P vs. NP je bol v médiách opakovane zle interpretovaný – od zámeny za šachovú hádanku po silné tvrdenia, že vyriešenie P vs. NP má okamžitý dopad na kryptografiu.

Problémom sa v minulosti zaoberal aj americký seriál Elementary, kde hlavný hrdina (moderné podanie Sherlocka Holmesa) riešil prípad vraždy dvoch vedcov, ktorí sa dostali k riešeniu veľmi blízko. Ako sa ukázalo, vrah taktiež disponoval dôkazom P = NP a využil ho – mimo iného – na vniknutie do bezpečnostného systému hotela.

Tento názor sa objavuje veľmi často – ľudia majú pocit, že ak niekto ukáže že P = NP, nastane okamžitý koniec bezpečného internetu. Nepreháňajú to náhodou?

Čo ak je P rovné NP?

Je pravda, že prakticky všetka kryptografia využívaná na internete stojí na predpoklade že P sa nerovná NP. Ak ukážeme opak, znamenalo by to nutne jej koniec? Nie každý dôkaz si je rovný – ak by sme dokázali P = NP, môžeme tak spraviť konštruktívne alebo existenčne.

Konštruktívny dôkaz by nám dal postup, ako NP ťažký problém vyriešiť v polynominálnom čase, zatiaľ čo existenčný by nám iba oznámil, že takéto riešenie existuje. To by si akademická obec mohla ďalej trieskať hlavu o stôl, neschopná rovnosti využiť k urýchleniu známych algoritmov. Dôkaz by to ale bol stále korektný, milión dolárov vyplatených. Čakalo by sa naďalej, kým niekomu napadne, ako teda tie NP-ťažké problémy rozumne riešiť.

Stačí teda pre sľubovanú apokalypsu aby dôkaz bol konštruktívny? Nie tak celkom.

Ani všetky konštrukčné dôkazy nemusia viesť k praktickému riešeniu. Konštanty sprevádzajúce riešenie nejakého NP ťažkého problému musia byť tiež rozumne veľké. 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*.

n^300 je už polynóm o niečo vačší, 300 je však konečné číslo a tak problém by ale stále v bol v P – môžme sa však rozlúčiť s výpočtom na osobných počítačoch. To isté platí pre algortmus bežiaci v n^30 00 000. To, že vykonanie takého algoritmu by ľudstvu mohlo trvať stovky rokov – aj na najvýkonnejších superpočítačoch – už opomíname. Pokiaľ by konštrukcia popísaná v dôkaze mala zložitosť takýchto n^(veľmi veľa), nebola by prakticky využiteľná na dostatočne silných kľúčoch.

Dôkaz P = NP, ktorý by lámal šifry, teda musí byť konštruktívny, rozumne implementovateľný a vykonateľný.

Tu sa to už stáva zaujímavým – 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. A symetrická kryptografia na tom nie je o toľko lepšie. Jediné súčasne známe, prakticky použiteľné a P = NP-odolné kryptografické metódy sú tie z princípu odolné voči všetkým útokom – napríklad Vermanova šifra, kde je ale neprakticky potrebné mať tajný kľúč aspoň tak veľký ako správu, ktorú šifrujete. Predstavte si, že heslo k vášmu počítaču by muselo zaberať aspoň polovicu miesta na disku… Nastal by pravdepobodobne sľúbený koniec bezpečného internetu – vo svete, kde P je rovné NP, by bezpečná výmená informácií znamenala USB kľúč prevážaný v pancierovom vozidle s ozbrojenými ochrankármi.

Čo ak P nie je rovné NP?

Čo naopak – sú naše súčasné šifry v absolútnom bezpečí, ak sa dokáže nerovnosť? Ani tu to nie je také jednoznačné, aspoň z matematického pohľadu. Algoritmus RSA – dlho utajovaný americkou vládou, dnes používaný v PGP či TSL – je jedným z nich. Nikdy totiž nebolo dokázané, že na dešifrovanie správy bez kľúča je potrebné vyriešiť nejaký NP problém. Áno, je to jediné riešenie, aké zatiaľ poznáme, hneď zajtra však môže vyjsť článok demonštrujúci niečo iné.

Veľmi veľa iných algoritmov by bolo naopak dokázateľne bezpečných, aspoň pokiaľ nepríde niečo ako univerzálny kvantový počítač. P != NP je ten nudnejší výsledok, ktorý by nám iba poskytol utvrdenie v tom, že naša predstava o bezpečnej komunikácií je naozaj správna.

Záverom

Najbližšie roky asi nie je potrebné panikáriť, k rozhodutiu P vs. NP sme ďaleko a internety sú v bezpečí. A nejaký akademický papier – aj keby bol hodný milióna dolárov – to stále nemusí zmeniť. Je však potrebné sa zmieriť s tým, že skoro celá informačná bezpečnosť a kryptografia stojí na „tušáku“, a že je to tak v poriadku.

Komentáře

Subscribe
Upozornit na
guest
9 Komentářů
Nejstarší
Nejnovější Most Voted
Inline Feedbacks
View all comments
atamiri

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í.

atamiri

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.

Martin Hassman

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.

atamiri

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

Martin Hassman

Chybu jsme opravili. O tom žádná.

brkerez

Tady se zastanu autora i redakce. Hodnocení typu „OMG“ mi v tomhle případě přijde rozhodně víc nekorektní a přehnané, než to, že si dovolil napsat „(a konečné!)“ – přesně sem díky tomu pochopil co tím myslel i když sem matematickou hantýrku dávno zapomněl. A to byl myslím v případě tohoto článku účel.

v6ak

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.

v6ak

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í.

Enum a statická analýza kódu

Mám jednu univerzální radu pro začínající programátorty. V učení sice neexistují rychlé zkratky, ovšem tuhle radu můžete snadno začít používat a zrychlit tak tempo učení. Tou tajemnou ingrediencí je statická analýza kódu. Ukážeme si to na příkladu enum.

Pocta C64

Za prvopočátek své programátorské kariéry vděčím počítači Commodore 64. Tehdy jsem genialitu návrhu nemohl docenit. Dnes dokážu lehce nahlédnout pod pokličku. Chtěl bych se o to s vámi podělit a vzdát mu hold.