Schnelle modulare Exponentiation

Bachelorarbeit aus dem Jahr 2005 im Fachbereich Informatik - Sonstiges, Note: 1,3, FernUniversität Hagen (Informatik), Sprache: Deutsch, Abstract: Inhaltsangabe:Zusammenfassung: In dieser Arbeit werden Algorithmen dargestellt und analysiert, die die in kryptographischen Verfahren häufig vorkommende modulare Exponentiation a^e mod m möglichst schnell berechnen. Nach der Einleitung in Kapitel 1 werden in Kapitel 2 einige wichtige mathematische Grundlagen vorgestellt. Dabei handelt es sich um den euklidischen Algorithmus, den erweiterten euklidischen Algorithmus, um die modulare Arithmetik, Primzahlen und die für die Beurteilung der Komplexität von Algorithmen wichtige O-Notation. In Kapitel 3 werden einige kryptographische Verfahren, in denen die modulare Exponentiation eine große Rolle spielt, beschrieben. Zur Beurteilung der Komplexität wird für jedes Verfahren aufgeführt, wie oft und mit welchen Bitlängen die modulare Exponentiation berechnet wird. Die modulare Multiplikation ist Thema des Kapitels 4. Algorithmen für die Multiplikation und für die Reduktion nach der Schulmethode werden dargestellt. Es wird gezeigt wie mit einem speziellen Algorithmus für die Quadrierung eine Beschleunigung um ca. 25% erzielt werden kann. Ein rekursiver Multiplikationsalgorithmus, der für sehr große Zahlen schneller als der klassische Algorithmus arbeitet, wird vorgestellt. Den Schluss des Kapitels 4 bildet ein Abschnitt über die Montgomerymultiplikation. In Kapitel 5 werden Methoden zur modularen Exponentiation behandelt, die ohne Vorberechnungen auskommen. Hierbei handelt es sich um die Binär-Methode, die m-ary-Method und die Fenstertechnik. Neben der Anzahl der Multiplikationen ist auch die Anzahl der während der Berechnung zu speichernden Zwischenergebnisse ein wichtiger Parameter für die Ausführungsgeschwindigkeit. Beide Parameter werden für die jeweiligen Verfahren diskutiert. Die modulare Exponentiation mit Vorberechnungen wird in Kapitel 6 behandelt. Dort wird zunächst auf die Additionsketten eingegangen. Es wird gezeigt, dass das mathematische Problem des Findens einer möglichst kurzen Additionskette, gleichbedeutend mit dem Finden eines möglichst schnellen Exponentiationsalgorithmus ist. Im Unterabschnitt 6.1.1 wird auf die Möglichkeit eingegangen, durch mehrere parallel arbeitende Multiplizierer die Exponentiation zu beschleunigen. Es folgt ein Abschnitt über Divisionsketten, ein Verfahren, das nicht nur auf die Reduzierung der Multiplikationen abzielt. Durch Verringerung von zu speichernden Zwischenergebnissen werden langsame Speicherzugriffe verhindert und so eine Beschleunigung der Berechnung erzielt. In Abschnitt 6.3 wird ein Algorithmus für die Berechnung modularer Exponentiationen mit fester Basis und variablen Exponenten vorgestellt (BMGW-Algorithmus). Beendet wird Kapitel 6 mit einem Abschnitt über die Exponentiation mit dem chinesischen Restsatz beim RSA-Verfahren. In Kapitel 7 werden die Ergebnisse der vorangegangenen Kapitel zusammengefasst. Die Arbeit endet mit Kapitel 8. Hier wird die beispielhafte Implementierung eines Verfahrens zur modularen Exponentiation beschrieben. Implementiert wird das Divisionskettenverfahren. Inhaltsverzeichnis:Inhaltsverzeichnis: ErklärungIII InhaltsverzeichnisV AbbildungsverzeichnisVII TabellenverzeichnisIX ListingsX SymbolverzeichnisXI KurzfassungXII 1.Einleitung1 2.Grundlagen3 2.1Euklidischer Algorithmus3 2.2Erweiterter euklidischer Algorithmus3 2.3Modulare Arithmetik, Restklassen4 2.3.1Rechenregeln der modularen Arithmetik5 2.4Primzahlen6 2.5Chinesischer Restsatz7 2.6O-Notation7 3.Kryptographische Verfahren8 3.1Digital Signature Algorithm9 3.2ElGamal10 3.3Pohlig Hellman12 3.4Rabin12 3.5RSA14 3.6Zusammenfassung16 4.Modulare Multip...