Kryptosysteme auf Basis imaginärquadratischer Nichtmaximalordnungen

Die vorliegende Arbeit behandelt die Konstruktion und effiziente Implementierung von Kryptosystemen auf Basis imaginärquadratischer Nichtmaximalordnungen. Während die bisher bekannten Kryptosysteme in der Klassengruppe imaginärquadratischer Ordnungen [BW88], verglichen mit vielen populären Verfahren, ein höheres Maß an Sicherheit versprechen, so fanden sie in der Praxis bislang kaum Beachtung, da die benötigte Arithmetik nur vergleichsweise ineffiziente Implementierungen erlaubt. Deshalb wurde in [HJPT98] vorgeschlagen, anstatt der bislang verwendeten Maximalordnungen nunmehr imaginärquadratische Nichtmaximalordnungen zur Konstruktion von Verschlüsselungssystemen mit effizienterer Entschlüsselung zu verwenden. Neben der etwa fünffach beschleunigten Entschlüsselung führte dieser Vorschlag insbesondere zur Entwicklung einer völlig neuartigen Klasse von Kryptosystemen – den Verfahren auf Basis imaginärquadratischer Nichtmaximalordnungen. So führte eine weitere Variation des Systemaufbaus zur Entwicklung der NICE-Kryptosysteme [PT00, HM00b], die bei Verwendung der hier vorgestellten Algorithmen [Hüh00, Hüh01] eine sehr effiziente Signaturerzeugung und Entschlüsselung erlauben. Entgegen aller populärer Verschlüsselungsverfahren, benötigt NICE zur Entschlüsselung nur quadratische Laufzeit. Die Signaturerzeugung bei den NICE-Schnorr- und NICE-Guillou-Quisquater-Signaturverfahren in Ker(Phi) ist bei vermutlich gleicher Sicherheit etwa doppelt so schnell wie bei entsprechenden Analogen zu [Sch90, GQ90] in (Z / dp^2 Z). Schließlich kann die in dieser Arbeit vorgestellte Verallgemeinerung der – in [HT99] für einen Spezialfall vorgeschlagenen – Reduktion des DL-Problemes von der Klassengruppe der Nichtmaximalordnung auf die kleinere Klassengruppe der Maximalordnung und einigen endlichen Körpern zur Konstruktion eines nichtinteraktiven ElGamal-Verschlüsselungsverfahren [HJW01] verwendet werden. Der Vorteil dieses Verfahrens ist, dass gewisse Sicherheitsprobleme der bekannten Verfahren vermieden werden können und die Arbeitslast für die zentrale Schlüsselerzeugungsinstanz vergleichsweise gering ist. Neben der Diskussion dieser Kryptosysteme samt zugehörigen Sicherheitsaspekten, enthält diese Arbeit die zur effizienten Implementierung benötigten Algorithmen und erste Laufzeitergebnisse.

The present work deals with the construction and efficient implementation of cryptosystems based on non-maximal imaginary quadratic orders. While previously known cryptosystems using class groups of imaginary quadratic orders [BW88] promise to be more secure than many popular schemes, they have not been widely used in practice because the required arithmetic only allows fairly inefficient implementations. Therefore it was proposed in [HJPT98] to use non-maximal imaginary quadratic orders, instead of maximal orders, to construct cryptosystems with efficient decryption. Besides the approximately five-fold speedup of the decryption process this proposal lead to an entirely new class of schemes - the cryptosystems based on non-maximal imaginary quadratic orders. Another variation of the system setup lead to the development of the NICE-cryptosystems [PT00, HM00b], which allow a very efficient decryption and signature generation, by using the algorithms presented here [Hüh00, Hüh01]. Unlike all popular encryption schemes, NICE only has quadratic decryption time. For the same alleged level of security, the signature generation in the NICE-Schnorr- and NICE-Guillou-Quisquater-signature schemes in Ker(Phi) is about twice as fast as an analogue of [Sch90, GQ90] in (Z / dp^2 Z). Finally it is possible to use the generalization of the - for a special case introduced in [HT99] - reduction of the DL-problem from the class group of the non-maximal order to the smaller class group of the maximal order and a small number of finite fields to construct a non-interactive ElGamal encryption scheme [HJW01]. The advantage of this scheme is that it is possible to avoid some security problems of known schemes and that the workload for the central key generation service is relatively small. Besides the discussion of these cryptosystems and the related security issues, this work covers algorithms for an efficient implementation and first run time results.