Über die Sicherheit und Effizienz kryptographischer Verfahren in algebraischen Zahlkörpern

In dieser Arbeit leisten wir einen Beitrag zur Suche nach alternativen sicheren und effizienten Kryptoverfahren. Wir befassen uns mit dem Entwurf, der Sicherheit und der praktischen Effizienz von Public Key-Kryptoverfahren, deren Sicherheit auf der Schwierigkeit des diskreten Logarithmusproblems, des Diffie-Hellman-Problems oder des Wurzelproblems in Klassengruppen algebraischer Zahlkörper (number fields) vom Grad größer 2 basiert. (Solche Kryptoverfahren nennen wir NF-Kryptoverfahren.) Die Verwendung von algebraischen Zahlkörpern in der Kryptographie (NF-Kryptographie) wurde zwar in [Buchmann:1991] und [Buchmann/Paulus:1997] vorgeschlagen, jedoch blieben die Details offen. Bislang wurde in einer Reihe von Arbeiten lediglich die Verwendung des einfachsten Spezialfalls der quadratischen Zahlkörper analysiert. Die oben genannten mathematischen Basisprobleme, die zum Brechen der Kryptoverfahren gelöst werden müssen, sind für Zahlkörper vom Grad größer 2 noch schwieriger als für quadratische Zahlkörper. Zudem erscheint deren Lösung selbst dann schwierig, wenn die heute in der Praxis in Kryptoverfahren verwendeten Basisprobleme effizient gelöst würden, z.B. das Faktorisierungproblem ganzer Zahlen oder das diskrete Logarithmusproblem in endlichen Körpern oder der Punktegruppe einer elliptischen Kurve über endlichen Körpern. Das macht Zahlkörper höheren Grades für die Kryptographie besonders interessant. Die vorliegende Arbeit löst die zahlreichen Problemstellungen, die bzgl. NF-Kryptographie noch offen waren: Wir zeigen, dass man überhaupt kryptographische Protokolle über Klassengruppen algebraischer Zahlkörper entwerfen kann, obwohl hier die Gruppenordnung unbekannt und nicht effizient berechenbar ist. Hierzu stellen wir einige NF-Kryptoverfahren zur Signatur, zur Verschlüsselung, zum Schlüsselaustausch, zur Identifikation und für weitere Anwendungen vor. Wir zeigen, dass die NF-Kryptoverfahren sicher sind unter der Annahme, dass die Berechnung diskreter Logarithmen und Wurzeln in Klassengruppen nicht effizient möglich ist. Wir erläutern, wie der algebraische Zahlkörper ausgewählt werden soll, damit diese Annahme nach heutigem Kenntnisstand mit sehr hoher Wahrscheinlichkeit erfüllt ist. Mittels theoretischer Resultate und praktischer Untersuchungen zeigen wir ferner, wie groß die Parameter (die Diskriminante und der Grad eines Zahlkörpers) ausgewählt werden müssen, damit das Brechen der NF-Kryptoverfahren nach heutigem Kenntnisstand genauso schwierig ist wie das Brechen heute in der Praxis verwendeter Kryptoverfahren wie RSA (mit z.B. 2048 Bit Schlüssellänge). Zudem untersuchen wir die Effizienz der NF-Kryptoverfahren und der darunter liegenden Arithmetik für Klassengruppen algebraischer Zahlkörper. Wir zeigen, dass NF-Kryptoverfahren schon hinreichend effizient sind, um auf modernen Computern eingesetzt werden zu können. In unserer Implementierung des R-Fiat-Shamir-Identifikationsprotokolls in der Klassengruppe kubischer Stender-Körper mit 404 Bit-Diskriminante benötigen beispielsweise Beweiser und Verifizierer auf einem 433 MHz PC jeweils 528 ms. Auf dem gleichen PC bräuchte der Beweiser bei vergleichbarer Sicherheit im RSA-Verfahren (4096 Bit Schlüssellänge) bei Verwendung einer anerkannt effizienten Referenzimplementierung 640 ms