Cryptography and Computational Number Theory
K.-Y. Lam, I. Shparlinski, H. Wang, C. Xing (Herausgeber)
Birkhäuser Verlag, Boston, Basel, Berlin, 2001, 392 Seiten, 155 $
ISBN 3-7643-6510-2
Die beiden im Titel genannten Gebiete und ihre wechselseitigen Beziehungen waren Gegenstand des CCNT Workshops im November 1999 in Singapur. Die Entwicklung in diesen Bereichen verläuft gerade in den letzten Jahren sehr rasant, so dass es Ziel des Workshops war, einerseits einen Überblick über den Stand der Forschung zu geben und andererseits neue Aspekte zu benennen und darzustellen und so die Forschung weiter voranzutreiben. Der Workshop war Treffpunkt für Mathematiker, Informatiker, Programmierer und Ingenieure. In den Tagungsband aufgenommen wurden 27 Arbeiten aus den verschiedensten Gebieten, was natürlicherweise zur Folge hat, dass bei der Besprechung eine Auswahl zu treffen war. Diese wiederum muss nach persönlichen Vorlieben geschehen, was der Leser entschuldigen möchte. So steht bei den ausgewählten Artikeln der zahlentheoretische Aspekt und dessen Bedeutung für die kryptographischen Anwendungen im Vordergrund.
A. Conflitti: On Elements of High Order in Finite Fields.
In den endlichen Gruppen mit kryptographischer Relevanz spielt speziell die Ordnung eines Elementes eine Rolle; so ist es von Bedeutung, Elemente hoher Ordnung zu konstruieren (wie etwa speziell Basispunkte auf elliptischen Kurven). In diesem Artikel werden endliche Körper Fqn betrachtet, und es wird eine Abschätzung für die Ordnung eines Elementes α ∈ Fqn vom Grad n, die auf S. Gao zurückgeht, verbessert. Betrachtet werden Elemente α, die einer speziellen Gleichung Xm - g(X) genügen, wobei m eine q-Potenz ist und der Grad von g beschränkt ist. Dabei wird, ähnlich wie bei Gao, eine Sequenz multiplikativ unabhängiger Hilfspolynome konstruiert. Die Abschätzung ist in extremen Fällen quadratisch in der alten unteren Schranke. Conflitti schlägt vor, auch Wurzeln α von Gleichungen Xmh(X)- g(X) zu betrachten und hier analoge Aussagen zu machen.
D. Kohel: Rational Groups of Elliptic Curves Suitable for Cryptography.
Die Arbeit von Kohel gibt einen guten Überblick über die verschiedenen Methoden, elliptische Kurven zu konstruieren, die für kryptographische Zwecke geeignet sind, das bedeutet konkret, deren Ordnung einen großen Primfaktor enthält. Die beiden hauptsächlichen Methoden hierfür sind einerseits die Zufallsmethode (also Bestimmen der Ordnung "zufällig'' gewählter Kurven) und andererseits die Methode der komplexen Multiplikation (CM-Methode, Konstruktion einer geeigneten Kurve zu vorgegebener Diskriminante). Es werden beide Methoden vorgestellt und Varianten gegeben. Ein bisschen zu sehr betont wird die bekannte Tatsache, dass bei der Konstruktion von Kurven nach der CM-Methode bei Festlegung der Charakteristik des zu Grunde liegenden Körpers der Zufallsaspekt natürlich zu kurz kommt. Übrigens ist angesichts der Tatsache, dass mit Hilfe der Zufallsmethode heute die Punkteanzahl einer elliptischen Kurve sehr schnell berechnet werden kann, die CM-Methode ohnehin in den Anwendungen nicht übermäßig relevant. Der Artikel eignet sich gut für "Einsteiger'', die sich einen Überblick verschaffen wollen.
R. Peralta: Elliptic Curve Factorization Using a "Partially Oblivious'' Function.
Es geht um die Faktorisierung großer ganzer Zahlen N = P ⋅ R, wobei P eine Primzahl ist, die R nicht teilt. Der Autor beschreibt eine Variation von Lenstra's Elliptic Curve Method, die mit Hilfe einer speziellen Klasse von Funktionen, den "teilweise vergesslichen'' Funktionen (im Deutschen klingt es nicht besser als im Englischen) schneller als die herkömmliche Methode ist. Dabei handelt es sich um Funktionen f : Z/NZ → Z, die, grob gesprochen, die Periode P haben und einer Wahrscheinlichkeitsbedingung genügen. Solche Funktionen existieren für den Fall, dass R ein perfektes Quadrat ist. Es gibt Kryptosysteme, in denen solche Zahlen benutzt werden, doch ist der hier vorgestellte Algorithmus nicht schnell genug, um diese ernsthaft anzugreifen.
A. De Bonis, A. De Santis: New Results on the Randomness of Visual Cryptography Schemes.
In kryptographischen Anwendungen ist es stets notwendig, "gute'' Zufallszahlen zu erzeugen. Da dies sehr schwer ist, besteht eine Alternative darin, Verfahren zu konstruieren, die mit möglichst wenigen Zufallszahlen auskommen. In dieser Arbeit werden diese Fragen bei Verfahren behandelt, die auf visueller Kryptographie beruhen. Der Artikel ist auch ohne Vorkenntnisse zu verstehen, wenn auch Grundkenntnisse in visueller Kryptographie das Verständnis natürlich enorm erleichtern.
Abschließend möchte ich betonen, dass dieser Tagungsband überraschend weit gefächert ist und - wie es auch schon Anspruch der Tagung war - sicher neben dem anwendungsinteressierten Mathematiker auch viele Wissenschaftler aus anderen Gebieten anspricht.
Rezension: Markus Wessler (Kassel) aus Computeralgebra-Rundbrief, Nr. 29 - Oktober 2001