P vs. NP – reálne dopady na webovú bezpečnosť
Publikováno: 4.12.2017
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 do množiny NP patria všetky tie ostatné 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 potencioná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.