Hamdy, Safuat (2002)
Über die Sicherheit und Effizienz kryptographischer Verfahren mit Klassengruppen imaginär-quadratischer Zahlkörper.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

In dieser Arbeit beschreiben wir asymmetrische Kryptoverfahren, deren Sicherheit auf der Schwierigkeit des DL-, des DH- oder des Wurzelproblems in Klassengruppen imaginär-quadratischer Zahlkörper beruht; diese Kryptoverfahren werden im folgenden als IQ-Kryptoverfahren oder einfach nur IQ-Verfahren bezeichnet. Bislang sind über IQ-Kryptographie nur vereinzelte Arbeiten erschienen, in denen einzelne Aspekte der IQ-Kryptographie beschrieben werden. So wurden z.B. in [Buchmann/Williams, 1988] Klassengruppen für den Diffie-Hellman-Schlüsselaustausch vorgeschlagen und eine erste Analyse zur Schwierigkeit des DL-Problems in Klassengruppen imaginär-quadratischer Zahlkörper gegeben, und in [Hafner/McCurley, 1989], [Duellmann, 1991] und [Jacobson, 1999] wurden subexponentielle Methoden zur Berechnung diskreter Logarithmen in Klassengruppen vorgestellt. Die folgenden Fragestellungen waren aber noch offen geblieben: Es war unklar, welche Signaturverfahren für Klassengruppen verwendet werden sollen, denn die Ordung der Klassengruppe oder eines Teilers davon (außer Potenzen von 2) ist i.allg. nicht effizient berechenbar. Daher können Signaturen vom ElGamal-Typ (z.B. DSA) nicht ohne weiteres auf Klassengruppen übertragen werden, da für Signaturen diesen Typs die Gruppenordnung bekannt sein muß. Weiterhin existierte bisher keine Untersuchung darüber, wie eine Klassengruppe ausgewählt werden sollte, so daß die Berechnung diskreter Logarithmen oder Wurzeln darin selbst mit den besten bekannten Algorithmen hierzu nicht effizient möglich ist. Es existierten bisher auch keine Implementierungen von IQ-Kryptoverfahren, weder experimentelle Implementierungen, noch Implementierungen für den praktischen Gebrauch. Letztendlich existierten daher bisher auch keine Untersuchungen über die Effizienz von IQ-Kryptoverfahren. Mit dieser Arbeit soll diese Lücke geschlossen werden: Wir stellen eine Reihe von IQ-Kryptoverfahren zur Signatur, zur Verschlüsselung und zum Schlüsselaustausch vor, und wir beschreiben detailliert, wie diese Kryptoverfahren implementiert werden sollten. Wir gehen dabei in einer Weise vor, wie es sich bei diversen Standards für Public-Key-Kryptographie eingebürgert hat, z.B. ANSI X9.62, ANSI X9.63, IEEE P1363 oder SEC; wir haben uns für unsere Spezifikation konkret den Standard SEC als Vorbild genommen. Wir zeigen, daß die IQ-Kryptoverfahren sicher sind unter der Annahme, daß die Berechnung diskreter Logarithmen und Wurzeln in Klassengruppen nicht effizient möglich ist. Wir zeigen dazu, wie die Diskriminante ausgewählt werden soll, damit diese Annahme mit sehr hoher Wahrscheinlichkeit erfüllt ist, und wir zeigen darüberhinaus, wie eine Diskriminante gewählt werden soll, so daß etwa die Berechnung diskreter Logarithmen in der entsprechenden Klassengruppe so aufwendig ist wie andere bekannte Berechnungsprobleme mit bestimmten Parametern (z.B. Faktorisierung einer ganzen Zahl mit 1024 Bit). Schließlich untersuchen wir die Effizienz der IQ-Kryptoverfahren und der darunter liegenden Arithmetik für Klassengruppen zu Diskriminanten, die für mittelfristigen Gebrauch kryptographisch geeignet sind, und wir zeigen, daß IQ-Kryptoverfahren so effizient sind, daß sie mit "`traditionellen"' Kryptoverfahren wie RSA oder DSA konkurrieren. Wir weisen damit nach, daß IQ-Kryptoverfahren eine sinnvolle und taugliche Alternative in der Familie der asymmetrischen Kryptoverfahren sind.

Frage zum Eintrag

Redaktionelle Details anzeigen