Krypto-Wissenschaftler knacken Primzahlenproblem

Indische Informatiker haben eine Methode ausgearbeitet, mit der ein Computer eine Primzahl eindeutig identifizieren kann. Dies ist ein uraltes Problem der Mathematik und seine Lösung ein entscheidender Schritt nicht zuletzt für die Kryptografie.

Aktuelle Verschlüsselungstechniken setzen zwei Schlüssel ein: Einen öffentlichen und einen privaten. Dazu wird eine mathematische Funktion benötigt, die nicht umkehrbar sein darf. Eine solche Funktion wurde 1977 von Ronald Rivest, Adi Shamir und Leonard Adleman gefunden. Die nach ihren Initialen benannte Methode RSA beruht auf der Multiplikation von großen Primzahlen. Wenn sie ausreichend groß gewählt werden, kann auch ein Supercomputer die Verschlüsselung nur unter erheblichem Zeit- und Rechenaufwand knacken.

Das Problem: Die aktuell eingesetzten Algorithmen zum Test einer Primzahl können kein eindeutiges Ergebnis zeitigen. Die von Professor Manindra Agrawal und seinen Studenten Neeraj Kayal und Nitin Saxena vom Indian Institute of Technology in Kanpur präsentierte Funktion jedoch soll todsicher sein und stets ein konkretes Ergebnis liefern. Die Funktion trägt den Titel „Primes is in P“ und ist bislang nur als Arbeitspapier veröffentlicht worden.

Kollegen von Agrawal bezeichnen die Methode als bahnbrechend: „Die größte Schwachstelle herkömmlicher Kryptografiesoftware ist, dass sie eine Primzahl nicht mit Bestimmtheit als solche erkennen kann“, erläuterte beispielsweise Eric Allender, Informatik-Professor an der State University of New Jersey. „Der neue Algorithms beantwortet eine fundamentale Frage, der man seit mehreren Jahrhunderten auf der Spur ist.“

Allerdings ist mit einer sofortigen Nutzung der neuen Methode nicht zu rechnen. „Unser Algorithmus ist langsamer als die schnellsten bereits bekannten Testmethoden“, erläuterte Agrawal. Experten gehen davon aus, dass herkömmliche Verschlüsselungssoftware weiterhin eingesetzt wird. Mit der bestehenden vergleichsweise geringen Unsicherheit könnten viele Anwender gut leben. „Es handelt sich (beim neuen Algorithmus) um ein theoretisches Konzept und stellt als solches einen ersten Schritt dar“, erklärte Allender. „Wir sprechen hier von einem Türöffner. Nun sind Verfeinerungen und Verbesserungen von Nöten, um das ganze praktisch umsetzen zu können.“