Kryptographische Anwendungen verallg. Lucas-Folgen, II

Forschungsprojekt P 14472Krypotographische Anwendungen verallg. Lucas-Folgen, IIWinfried B. MÜLLER26.06.2000 Eines der schwierigsten Probleme in der modernen Kryptography besteht darin, möglichst rasch, sehr große, "zufällige" Primzahlen zu generieren. Viele der heutzutage verwendeten Kryptomechanismen und deren Sicherheit beruhen auf den zugrundeliegenden Primzahlen, insbesondere deren Größe und Struktur. Wenn die Primzahlen zu klein sind, oder eine zu spezielle Bauart aufweisen, dann gibt es eine Reihe von Möglichkeiten, das System zu attackieren und dessen Sicherheit zu gefährden. Aus praktischen Gründen sind die meisten Mechanismen zur Generierung von Prixnzahlen "nur" probabilistisch. Obwohl diese weitaus schneller als die deterministischen sind, führen sie zum Problem der sog. Pseudoprimzahlen. Dies sind zusammengesetzte Zahlen, die fälschlicherweise von einem Pseudoprimzahltest als prim identifiziert werden. Die zuverlässigsten und effizientesten Pseudoprimzahltests verwenden Lucas Folgen. Im FWF Projekt P13088-MAT wurden wesentliche Eigenschaften solcher Folgen analysiert, die Aufschluss darüber geben, warum diese so hervorragend für Pseudoprimzahltests verwendet werden können. Es konnte sowohl eine genaue Charakterisierung von Lucas-artigen Pseudoprimzahlen, als auch eine Verbesserung einiger Tests basierend auf Lucas-Folgen angegeben werden. Jedoch haben die erbrachten Ergebnisse zu einer Reihe von neuen und interessanten Fragestellungen in diesem Zusammenhang geführt. Die Hauptziele des beabtragten Projektes bestehen darin, die Resultate des Projektes P 13088-MAT zu erweitern. und zu verbessern. Ein wesentliches Ziel ist es, die bisherigen Resultate auf möglichst effiziente Art zu vereinen um dadurch weitere Verbesserungen von Pseudoprimzahltests, aber auch eine noch detailliertere Charakterisierung der damit zusammenhängenden Pseudoprimzahlen zu erreichen. Weiters sollen die Resultate des Projektes P 13088-MAT auch auf andere geeignete algebraische Strukturen verallgemeinert werden. Durch die genaue Analyse der Lucas-Folgen im Projekt P 13088-MAT konnten auch wesentliche zahlentheoretische und algebraische Resultate von verallgemeinerten Lucas-Folgen erbracht werden. Diese ermöglichen eine detaillierte Charakterisierung. der wesentlichen zugrundeliegenden Eigenschaften solcher Folgen. Die erbrachten Resultate sind nicht nur von theoretischem. Interesse, sondern konnten auch in verschiedenen kryptographischen Anwendungen verarbeitet werden. Ein weiteres Ziel des beantragten Projektes besteht darin die wichtigsten zahlentheoretischen und kryptographischen Algorithmen zu optimieren und eine Verbesserung und noch genauere Kryptoanalyse der Systeme zu erstellen, welche auf Rekursionsfolgen beruhen.

Entwicklung eines neuen probabilistischen Primzahltests, welcher in Theorie und Praxis effizienter als alle bisher bekannten Verfahren zur Ermittlung großer Primzahlen ist. Eines der schwierigsten Probleme der modernen Kryptographie besteht darin, möglichst rasch, sehr große, "zufällige" Primzahlen zu generieren. Viele der heutzutage verwendeten Kryptomechanismen und deren Sicherheit beruhen auf den zugrundeliegenden Primzahlen, insbesondere deren Größe und Struktur. Wenn die Primzahlen zu klein sind, oder eine zu spezielle Bauart aufweisen, dann gibt es eine Reihe von Möglichkeiten, das System zu attackieren und dessen Sicherheit zu gefährden. Während theoretische Studien über Primzahlen bereits Jahrhunderte, ja sogar Jahrtausende, zurückgehen, wurde das Problem der praktischen Bestimmung von Primzahlen erst durch die jüngsten Anwendungen in der Kryptologie zu einem zentralen Thema der mathematische Forschung. Aus praktischen Gründen sind die meisten Algorithmen zur Generierung von Primzahlen "nur" probabilistisch. Diese sind zwar wesentlich schneller als die bekannten deterministischen Algorithmen, führen aber zum Problem der sogenannten Pseudoprimzahlen. Dies sind zusammengesetzte Zahlen, die fälschlicherweise von einem probabilistischem Primzahltest als prim identifiziert werden. Hauptziel des Projektes war die Entwicklung neuer und besserer probabilistischer Primzahltests und die Ermittlung von oberen Schranken für ihre Fehlerwahrscheinlichkeit. Dazu wurden die wichtigsten bekannten Pseudoprimzahltests analysiert und Eigenschaften von Pseudoprimzahlen untersucht. Als Hauptergebnis wurde ein neuer probabilistischer Primzahltest auf Basis der sogenannten Lucas Folgen entwickelt, welcher alle bisher bekannten Tests an Effizienz übertrifft.