Das RSA-Verfahren ist eines der international gebräuchlichsten Verfahren für digitale Signaturen und Verschlüsselungen. Es wird u.a. beim Homebanking (z.B. Bank24), im Internet (z.B. Netscape) und für sichere elektronische Post (z.B. PGP) eingesetzt. Dabei wird ein öffentlicher (d. h. allgemein zugänglicher) und ein privater (d.h. geheimer) Schlüssel verwendet. Mit dem einen Schlüssel wird die Nachricht codiert und mit dem anderen decodiert. Beide Schlüssel müssen für einen Nachrichtenaustausch eingesetzt werden. Der öffentliche Schlüssel ist das Produkt zweier großer Primzahlen.
Die einzige bisher bekannte Methode, das RSA-Verfahren zu brechen, ist die Faktorisierung des RSA-Modulus, d.h. die Berechnung der Primfaktoren des öffentlichen Schlüssels. Die Vorhersage der für die Faktorisierung von Schlüsseln üblicher Größe (384 Bit, 448 Bit, 512 Bit, 576 Bit, usw.) benötigten Rechenzeit ist daher die einzige Möglichkeit, die Sicherheit in der Praxis benutzter RSA-Systeme zu beurteilen.
Während die Probedivision schon bei Zahlen von 20 Dezimalstellen (ca. 70 Bit) an ihre Grenze stößt, können mit neuen Algorithmen (Quadratisches Sieb 1986, Zahlkörpersieb 1993) Zahlen mit mehr als 100 Dezimalstellen zerlegt werden. Beide Verfahren haben asymptotisch eine subexponentielle Laufzeit. Die theoretischen Analysen geben jedoch wenig Auskunft über die tatsächlich benötigte Rechenzeit für reale Instanzen. Zuverlässige Extrapolationen von erfolgreich zerlegten Zahlen sind nur über ca. zehn weitere Dezimalstellen möglich.
Das quadratische Sieb und das Zahlkörpersieb enthalten eine Siebphase und
die Lösung eines Gleichungssystems über GF(2), das Zahlkörpersieb
darüber hinaus die Bestimmung einer Quadratwurzel in einem Zahlkörper. Die
Siebphase ist mit mehreren Jahren Rechenzeit
auf einer Workstation bei einem 384-Bit-Modulus
der bei weitem zeitaufwendigste Teilschritt
und wurde auf einer Vielzahl von Parallelrechnern
implementiert (Workstation-Cluster, Parsytec GCel, PowerXplorer, IBM
SP1, usw.). Den Engpaß der Siebphase bilden Speicherarchitektur und
Speicherverwaltung der jeweiligen Maschine. Hier haben wir für
RISC-Maschinen eine schnelle Umsetzung entwickelt. U.a. gelang uns die
Faktorisierung einer 116-stelligen Zahl aus dem Cunningham-Projekt
- ein Europarekord (siehe Abb. 
).
Abbildung: Faktorisierung einer 116-stelligen Zahl
Die zu lösenden 0-1-Gleichungssysteme der Faktorisierungsalgorithmen aus dem letzten Abschnitt beinhalten Matrizen mit mehreren hunderttausend Zeilen und Spalten. Die auftretenden Matrizen sind sehr dünn besetzt (weniger als 0,1% Nichtnulleinträge), im Gegensatz zu ähnlichen Problemen aus der Numerik jedoch unstrukturiert. Gewöhnliche Gauß-Elimination ist wegen der entstehenden Zeit- und Platzprobleme indiskutabel.
Die jüngste Entwicklung stellt das Block-Lanczos-Verfahren von P. L. Montgomery für GF(2) dar, das explizit die Wortgröße der benutzten Maschine (32 Bit, 64 Bit) einbezieht. Hier haben wir eine Shared-Memory Parallelisierung auf der SGI Power Challenge-Maschine des Rechenzentrums begonnen. Erste parallele Ergebnisse konnten bereits nach nur einer Woche erzielt werden, da - im Gegensatz zu einer Distributed Memory Parallelisierung - nur zeitkritische Teile parallelisiert werden müssen. Auf acht Prozessoren haben wir einen (vorläufigen) Speedup von 4,8 erzielt.
Mit kryptographischen Hashfunktionen können ,,Fingerabdrücke`` elektronischer Dokumente effizient berechnet werden. Der Fingerabdruck wird dann zeitaufwendiger verschlüsselt und dient als elektronische Unterschrift des jeweiligen Dokumentes. Gute kryptographische Hashfunktionen müssen sicher sein: So darf es z.B. keine praktische Möglichkeit geben, zwei verschiedene Nachrichten mit demselben Fingerabdruck zu konstruieren. Notwendigerweise müssen kryptographische Hashfunktionen dazu eine Reihe von statistischen Tests passieren.
Ein in Kooperation mit der debis Systemhaus GmbH, Bonn, entwickeltes Programmpaket für statistische Tests kryptographischer Hashfunktionen wurde im Januar 1995 erfolgreich abgenommen. Neben klassischen Standardverfahren lagen hier die Schwerpunkte bei algebraischen Zykeltests und der effizienten Suche nach Linear- und Pseudolinearfaktoren.
Mit den implementierten Zykeltests können für eine Funktion mit identischem Definitions- und Wertebereich Eigenschaften wie Abgeschlossenheit, Injektivität und Fixpunktfreiheit entschieden werden. Darüber hinaus kann beurteilt werden, ob das von der Größe der Schlüsselmenge suggerierte Sicherheitsmaß realistisch ist oder nicht.
Ziel der in der Literatur zuvor nur wenig dokumentierten Linear- und Pseudolinearfaktortests ist die Suche nach (pseudo-)linearen Abhängigkeiten innerhalb der Ausgabestellen bei gleichzeitiger Änderung einer bestimmten Menge von Eingabestellen. Dazu wurden neue Verfahren zur Bestimmung von Linear- und Pseudolinearfaktoren entwickelt und implementiert, die u.a. alle Pseudolinearfaktoren mit einer Wahrscheinlichkeit oberhalb einer vorgegebenen Schranke bestimmen.
Zu einer vollständigen Beurteilung der Qualität der kryptographischen Hashfunktion müssen die Ergebnisse im allgemeinen um eine manuelle Analyse der Funktion erweitert werden.