[disc] Veiligheid op internet in gevaar door prime-testing?

[drm]

De International Herald Tribune meldt:

Many of the world's foremost mathematicians will gather in Palo Alto, California, this month to investigate a recent breakthrough in number theory that could have enormous implications for cryptography and the security of communications and economic transactions on the Internet...
» Lees verder

In dit artikel wordt gemeld dat er aan de Indian Institute of Technology in Kanpur een stukje code is ontwikkeld waarmee het heel eenvoudig wordt om priemgetallen te vinden.

Mathematici over de hele wereld denken er verschillend over.
• De ene groep is blij, omdat het een aanwinst voor cryptologie zou zijn, als priemgetallen zo eenvoudig te vinden zijn.
• De andere groep is bang, dat er in het ontbinden in factoren (factoring) ook een stuk eenvoud over het hoofd gezien is, zodat het juist veel eenvoudig wordt om missende sleutels (zoals van de RSA encryptie, die op zowel factoring als primes gebaseerd is) te kraken.

Wat zou dit voor gevolgen hebben voor de cryptologie? Sluit je je aan bij de eerste groep of de tweede?

[mbravenboer]

Zoals je op deze pagina kan vinden dateert dit nieuws al van Augustus 2002. Niet echt nieuw dus eigenlijk. Als we ons echt grote zorgen moeten gaan maken, hadden we het afgelopen half jaar zeker wel iets gemerkt.

Security.nl vond het nodig om nav dit artikel in de Tribune hier gisteren wat over te gaan schrijven, waardoor het allemaal heel erg recent en problematisch lijkt. Alle mogelijke problemen zijn echter gebaseerd op speculaties. Op webgoeroe schreef ik al dit:

Ik ben niet zo goed thuis in de cryptografie en kan het dus niet heel erg goed beoordelen, maar volgens mij wordt de zaak wel een klein beetje overdreven. Er is inderdaad wel een zeer interessant resultaat (met name vanwege de eenvoud), maar er werd al enige tijd richting deze oplossing gewerkt. De looptijd van dit algoritme kon al bereikt worden onder bepaalde voorwaarden en deze wiskunde knobbels hebben het voor elkaar gekregen om de voorwaarden weg te nemen.

Het essentiele is echter dit:

Moreover, they have said, if primality testing turned out to have such a simple solution, maybe they have overlooked a simple solution to factoring as well.

De hele paniek is dus gebaseerd op het idee dat het misschien wel eens zo zou kunnen zijn dat factorisering toch niet zo duur en lastig is als we nu denken, nu we weten hoe eenvoudig je kan testen of iets een priemgetal is met deze looptijd.

Er kan dus nu nog absoluut niets gedaan worden met het nieuwe algoritme was erg schokkend is. De looptijd is ook niet schokkend, de eenvoud is wellicht schokkend. Als factorisering ook eenvoudig en (relatief!) goedkoop gedaan kan worden, zou dat een volgende enorme schok zijn, maar volgens mij wijst niets heel direct op deze mogelijkheid.

[mbravenboer]

Zie trouwens ook hun eigen FAQ:

Q13. Does this result have any impact in cryptography at all?

Not in any obvious ways. Certain algorithms need to generate prime numbers in order to construct cryptographic keys, but algorithms to accomplish this which can be executed very efficiently already existed before the result in [1]. The most commonly used ones have a probability of error, but this error can be made to be arbitrarily small (see question 9) and thus they give us practically the same assurance as the algorithm proposed in P. These algorithms that are commonly used in practice are actually faster than the ones proposed in [1]. The result in [1] is a very important one in complexity theory, but probably have no (practical) impact in cryptography.

[1] is uiteraard hun publicatie.

Q12. Could this result break cryptographic algorithms?

No. As mentioned above, fast randomized algorithms for primality testing were already known, and in fact they are necessary just to make most known public key cryptosystems feasible!

Some people confuse the factorization problem with the problem of distinguishing prime numbers from composite numbers. The factorization problem is: given an integer n, try to find the prime numbers which when multiplied together give n. The fundamental theorem of arithmetic states that every integer n can indeed be factored into prime numbers, and in a unique way, so the problem makes sense for any integer. If one could efficiently factor large integers, then certain cryptographic algorithms would be broken (such as the famous RSA encryption and signature schemes). The fact that PRIME has been found to be in P cannot be used to break any cryptographic algorithms.

[ Voor 37% gewijzigd door mbravenboer op 11-03-2003 16:20 ]

[dusty]

Priem getallen berekenen op een snelle en makkelijke manier is een aanwinst voor cryptografie.

Echter zodra men erachter komt dat er een makkelijke manier is om een getal heel makkelijk in zijn factoren te berekenen zal weer negatief zijn voor cryptografie.