Messias. zei:
De kracht van public-key cryptografie ligt inderdaad in de veronderstelling dat priemfactorisatie een "moeilijk" probleem is. Het is een FNP-probleem, een complexiteitsklasse waarvan men, gegeven een oplossing, vrij eenvoudig de juistheid kan verifiëren, maar waarvoor tot nu toe nog geen efficiënte algoritmes gevonden zijn om die oplossingen te vinden.
Met efficiënte algoritmes wordt overigens bedoeld: een algoritme dat het probleem oplost in een polynomiaal aantal stappen in functie van de inputgrootte. Heel informeel wordt hiermee bedoeld dat als men de uitvoeringstijd van het algoritme in functie van de grootte van het probleem n uitzet, dat er dan een zekere waarde p bestaat zodat de uitvoeringstijdscurve onder de curve van n^p blijft naarmate de probleemgrootte nadert tot oneindig (over de hele as van probleemgroottes).
Met andere woorden, er bestaat een polynomiale functie (i.e. iets van de vorm n tot een zekere macht) die een bovengrens vormt voor de uitvoeringstijd voor grote probleemgroottes.
Een voorbeeld van een probleemgrootte is bijvoorbeeld het aantal bits in het getal waarvan men de factoren wilt kennen. Voor de complexiteitsanalyse van algoritmes is men enkel geinteresseerd in het gedrag van de uitvoeringstijd naarmate de inputgrootte tot oneindig nadert.
Er bestaan ook functies die sneller stijgen dan polynomiaal. Voor een algoritme waarvan de uitvoeringstijd bijvoorbeeld exponentiëel stijgt in functie van de probleemgrootte tijd vraagt bestaat er geen curve van de vorm n^p, omdat er altijd een punt zal zijn waarop uw exponentiële uitvoeringstijdscurve boven de n^p zal uittorenen en naarboven schieten. Het punt op de x-as waarop dat gebeurt zal wel verschuiven naar rechts naarmate ge p groter neemt, maar de exponentiële zal er vroeg of laat toch bovenuitschieten ongeacht hoe groot ge p ook kiest.
Daarom zegt men dat de exponentiële functie "sneller stijgt" dan de polynomiale functie, omdat exponentiële functies vroeg of laat altijd boven een polynomiale zullen uitschieten. Algoritmes die exponentiële tijd vragen zijn dus minder efficiënt dan diegene die polynomiale tijd vragen.
Problemen worden opgedeeld in verschillende klassen volgens hun eigenschappen. Zo is de klasse "P" de verzameling van alle problemen die in polynomiale tijd opgelost kunnen worden, maw. waarvoor een algoritme bestaat met uitvoeringstijd
O(n^p) voor zekere waarde van p.
De klasse van "NP"-problemen zijn dan weer die problemen waarvoor, als men een kandidaat-oplossing heeft, men in polynomiale tijd kan verifiëren of die kandidaat ook effectief een oplossing is van het probleem of niet. Het klassiek voorbeeld hierbij is het
subset-sum probleem:
Gegeven een lijst getallen, bestaat er een subset die samen sommeren tot 0?
bv. input: { −7, −3, −2, 5, 8}.
Het is uiteraard eenvoudig om, gegeven een mogelijke oplossing (bv. { −3, −2, 5}), te controleren of die getallen sommeren tot 0. Als ge k getallen hebt in uw kandidaat-oplossing (hier dus 3) is dat dus gewoon k-1 optellingen; duidelijk polynomiale tijd want dat ligt overal onder k^1. Subset-sum ligt dus in NP.
Veel minder eenvoudig is om die subset van getallen ook te vinden (althans in polynomiale tijd). Tot nog toe is niemand erin geslaagd om hier een algoritme voor te vinden dat in polynomiale tijd werkt.
In de loop der jaren heeft men een hele hoop van dergelijke problemen gevonden; dus die in NP zitten maar waarvoor nog niemand polynomiale algoritmen heeft kunnen vinden. Men heeft kunnen aantonen dat bepaalde van die problemen karakteristiek zijn voor de klasse NP. Deze problemen zijn karakteristiek in die zin dat men ontdekt heeft dat alle andere problemen in NP er naar kunnen omgevormd worden. Deze problemen noemt men NP-compleet.
Zowat hét belangrijkste onopgeloste probleem in de complexiteitstheorie is nu de vraagstelling of P = NP. Dit is met andere woorden de vraag:
kan elk probleem dat in polynomiale tijd geverifieerd kan worden ook opgelost worden in polynomiale tijd?
Men weet triviaal dat P een deelverzameling is van NP; dit is logisch, want elke oplossing van een P-probleem kan men uiteraard in polynomiale tijd verifiëren want men kan hem gewoon berekenen in polynomiale tijd. Om aan te tonen dat P = NP volstaat het dus om aan te tonen dat een NP-compleet probleem in polynomiale tijd opgelost kan worden.
Dit is overigens ook een van de
Millenniumprijsproblemen, zowat de lijst met de moeilijkste openstaande wiskundige problemen. Los dit probleem op en u wint $1M en wereldwijde academische faam
Hele reden van dit verhaal: integer-factorisatie is een (F)NP-probleem waarvan niet geweten is of het in (F)P ligt. Het is NP want gegeven een kandidaatoplossing (ie. een verzameling priemgetallen) kunnen we makkelijk kijken of het een oplossing is: gewoon vermenigvuldigen. Het effectief ook vinden van die priemgetallen is echter heel wat moeilijker.
Om moderne cryptografie onderuit te halen, volstaat dus een bewijs dat P = NP. Algemeen wordt aangenomen dat P != NP omdat niemand er vooralsnog in geslaagd is om polynomiale algoritmes te vinden voor NP-complete problemen.
Wees dus enigszins gerust: cryptografie steunt op een van de moeilijkste wiskundige problemen die er zijn en waar men al meer dan 40 jaar tevergeefs op zoekt. Als men kan bewijzen dat P != NP dan is cryptografie aantoonbaar inherent veilig (voor voldoende grootte inputgroottes).
Anderzijds, als men kan aantonen dat P = NP, dan is cryptografie ook nog altijd niet compleet verloren. Moderne cryptografie steunt voor een groot deel op het groot genoeg maken van de priemgetallen om brute-forcing tegen te gaan. Zelfs al geldt P = NP, dan nog is het perfect mogelijk dat een algoritme om priemfactoren te bepalen een complexiteit van O(n^(10^10^10^...^10)) heeft. Theoretisch polynomiaal, maar praktisch nog altijd even nutteloos wegens veel te lange uitvoeringstijd.
