Vorlesung
Algorithmen für die Kryptographie
(Wintersemester 2014/15)

Veranstalter: Dr. Manfred Kufleitner

Termin: Do. 10:15-13:45 mit 30 Minuten Pause in F-132

Aktuelles und Inhalte der Vorlesung

• 29.01.15: Elliptische Kurven über den reellen Zahlen und über endlichen Körpern; die Anzahl der Punkte einer elliptischen Kurve über einem Körper mit q Elementen ist höchstens 2q; Hasse-Schranke; Schnitte von Geraden mit elliptischen Kurven; die Verknüpfung auf elliptischen Kurven; Diffie-Hellman-Schlüsselaustausch mit elliptischen Kurven; Pseudokurven; ist eine Addition von Punkten definiert, so liefert dies auch wieder einen Punkt auf der Kurve; die modulo-Operation auf Punkten ist mit der Verknüpfung der Kurve verträglich; Faktorisierung mit elliptischen Kurven.
  
  
• 22.01.15: Charakterisierung von Primzahlen durch Polynomidentitäten; der AKS-Algorithmus für das Testen der Primzahleigenschaft in deterministischer Polynomialzeit: Laufzeit, Korrektheit.
  
  
• 15.01.15: Kombinatorische Interpretation von Binomialkoeffizienten, ungeordnete Auswahl mit Wiederholung, das kleinste gemeinsame Vielfache kgV(n) der Zahlen 1,...,n, Binomialkoeffizienten als Teiler von kgV(n), untere und obere Schranken für kgV(n), untere und obere Schanken für die Anzahl der Primzahlen kleiner oder gleich n, das Bertrand'sche Postulat, untere Schranke für die Anzahl der Primzahlen zwischen n und 2n.
  
  
• 08.01.15: Diffie-Hellman-Schlüsselaustausch, Wahl von Elementen mit großer Ordnung, diskreter Logarithmus, Diffie-Hellman-Problem, ElGamal-Kryptosystem, Vor- und Nachteile gegenüber RSA, Shanks' Babystep-Giantstep-Algorithmus, Pollards rho-Methode für den diskreten Logarithmus, Reduktion der Gruppenordnung nach Pohlig-Hellman: Reduktion auf Primzahlpotenzen sowie Reduktion auf Primzahlen, Laufzeitabschätzung von Pohlig-Hellman, Index-Calculus
  
  
• 18.12.14: Wiederholung Fourier-Transformation, schnelle Berechnung der Fourier-Transformation mittels Divide-and-Conquer, elementare arithmetische Operationen, primitive Einheitswurzeln in Körpern, primitive Einheitswurzeln modulo 2^m+1, Übersicht zu Multiplikationsverfahren, Vergleich von Schönhage-Strassen mit Fürer, Ablauf des Schönhage-Strassen-Algorithmus, Laufzeitabschätzung des Schönhage-Strassen-Algorithmus
  
  
• 11.12.14: Das Quadratische Sieb: das Verfahren, ein Zahlenbeispiel; die diskrete Fourier-Transformation; primitive b-te Einheitswurzeln in Ringen, Invertierbarkeit der Fourier-Transformation mittels Matrxinvertierung, Schema zur Multiplikation von Polynomen
  
  
• 27.11.14: Aufgabe: Summe der Potenzen einer Einheitswurzel (ungleich 1) ergibt 0; Wurzelziehen in endlichen Körpern, Spezialfälle: gerade Anzahl von Elementen, Anzahl von Elementen ist kongruent -1 modulo 4; Cipollas Algorithmus: Erfolgswahrscheinlichkeit, Korrektheit, Laufzeit; das Geburtstagsparadoxon; Pollards rho-Methode zur Faktorisierung; Pollards (p-1)-Methode
  
  
• 20.11.14: Charakteristik eines Rings; die Charakteristik eines nullteilerfreien Rings ist null oder eine Primzahl; Frobeniushomomorphismus; Körperhomomorphismen sind injektiv; Ableitung eines Polynoms; Ableitungsregeln für Summen und Produkte; ggT von Polynomen; Nullstelle ist genau dann einfach, wenn Ableitung an dieser Stelle nicht Null ist; es sind genau dann alle Nullstellen von f einfach, wenn f und f' teilerfremd sind; irreduzible Polynome; Test auf Irreduzibilität bei Polynomen von Grad höchstens 3 mittels Nullstellen; Rechnen in K[X]/f mit Beispiel; K[X]/f ist genau dann ein Körper, wenn f irreduzibel ist; K[X]/f hat genau |K|^deg(f) Elemente; Erweiterungskörper; zu jedem Polynom f in K[X] gibt es einen Erweiterungskörper, in dem f in Linearfaktoren zerfällt (genannt: Zerfällungskörper von f über K); algebraischer Abschluss; Kreisteilungspolynome und Kreisteilungskörper; wenn K ein endlicher Körper ist, dann hat K genau pⁿ Elemente für eine Primzahl p und eine natürliche Zahl n; Ausblick auf Existenz und Eindeutigkeit eines Körpers mit pⁿ Elementen; Ausblick auf Korrektheit des Cipolla-Algorithmus zum Wurzelziehen.
  
  
• 13.11.14: Notizen zum Miller-Rabin-Primzahltest (Version vom 18.12.14)
  
  
• 13.11.14: Die Fehlrewahrscheinlichkeit des Miller-Rabin-Primzahltests bei Carmichael-Zahl ist höchstens 1/4, das Master-Theorem (ohne Beweis), schnelle modulare Exponentiation, Additionsketten, Multiplikation nach Karatsuba, Division mittels Newton-Verfahren, Eulerkriterium, in einem endlichen Körper mit einer ungeraden Anzahl an Elementen gibt es genau so viele Quadrate wie Nicht-Quadrate, das Rabin-Kryptosystem, Korrektheit des Rabin-Verfahrens, Sicherheit des Rabin-Verfahrens, Aufgabe: Wenn phi(n) nur kleine Primteiler hat, dann lässt sich n leicht faktorisieren, Wahl von sicheren Primzahlen für RSA- und Rabin-Verfahren
  
  
• 06.11.14: Aufgabe zu Gruppenhomorphismen, Binomialkoeffizienten, Additionstheorem, Binomialsatz, endliche Untergruppen der multiplikativen Gruppe eines Körpers sind zyklisch, die Struktur von Z/p^eZ für p prim, die Fehlerwahrscheinlichkeit des Miller-Rabin-Primzahltests bei Primzahlpotenzen, Carmichael-Zahlen, quadratfreie Zahlen, jede Carmichael-Zahl ist quadratfrei, jede Carmichael-Zahl hat mindestens drei Primteiler, die Fehlerwahrscheinlichkeit des Miller-Rabin-Primzahltests bei Nicht-Carmichael-Zahlen ist höchstens 1/4.
  
  
• 30.10.14: Einfache Eigenschaften von neutralen und inversen Elementen, Gruppen von Primzahlordnung sind zyklisch, Untergruppen von zyklischen Gruppen sind zyklisch, teilerfremde Ordnungen in kommutativen Gruppen, Satz von Cauchy, Nullteiler, nullteilerfrei, Körper sind nullteilerfrei, Z/nZ Körper gdw n prim, Polynome, Grad, Gradformel, das Rechnen modulo Polynomen, s ist genau dann Nullstelle von Polynom p(X) wenn (X-s) ein Teiler von p(X) ist, ein Polynom über einem nullteilerfreien Ring hat höchstens so viele Nullstellen (mit Vielfachheiten) wie es der Grad vorgibt, der Miller-Rabin-Primzahltest, Korrektheit des Miller-Rabin-Tests.
  
  
• 23.10.14: Aufgabe zu Teilbarkeitsregeln, Wiederholung RSA, Beispielrechnung zu RSA, Multiprime-RSA, kgV(p-1,q-1) anstelle von (p-1)(q-1), decodieren modulo p und modulo q mit anschließendem CRT (Chinese Remainder Theorem), Aufgabe: öffentliche Schlüssel (n,e) und (n,f) mit ggT(e,f)=1, Aufgabe: n⁵ ≡ n mod 30, Definitionen: Gruppe G, Untergruppe H ≤ G, Erzeugnis ⟨X⟩, (Links-)Nebenklasse gH, Nebenklassen sind entweder gleich oder disjunkt, Index einer Untergruppe, Satz von Lagrange, Ordnung eines Elements, Eigenschaften der Elementordnung, zyklische Gruppen, kommutative/abelsche Gruppen, Sicherheit des geheimen Schlüssels bei RSA
  
  
• 16.10.14: Etwas Historie und einige Querbezüge zu anderen wissenschaftlichen Disziplinen, Informationstheoretische Sichtweise auf die Kryptographie, Teilbarkeitsrelation, modulare Kongruenzen, größter gemeinsamer Teiler, Lemma von Bézout, der Erweiterte Euklidische Algorithmus und seine Rekursionstiefe, multiplikativ invertierbare Elemente, Eulersche phi-Funktion, Satz von Euler, Kleiner Satz von Fermat, Chinesischer Restsatz, Berechnung der Eulerschen phi-Funktion, das RSA-Verfahren, Korrektheit des RSA-Verfahrens

Überblick

Die Vorlesung behandelt mathematische und algorithmische Aspekte der modernen Kryptographie. Hierzu zählen einige Public-Key-Verfahren sowie Techniken aus der algorithmischen Zahlentheorie. Wenn man beispielsweise beurteilen kann, welche Zahlen sich leicht faktorisieren lassen, dann kann man auch das RSA-Verfahren sicherer umsetzen. Im Einzelnen werden die folgenden Themen behandelt:

• Mathematische Grundlagen
• Public-Key-Kryptographie
• Das RSA-Verschlüsselungsverfahren
• Das Rabin-Verschlüsselungsverfahren
• Der Miller-Rabin-Primzahltest
• Wurzelziehen in endlichen Körpern
• Pollards (p-1)-Methode zur Faktorisierung
• Pollards rho-Methode zur Faktorisierung
• Das Quadratische Sieb
• Die schnelle Fourier-Transformation
• Multiplikation großer Zahlen
• Der Diffie-Hellman-Schlüsselaustausch
• Das ElGamal-Verschlüsselungsverfahren
• Shanks' Babystep-Giantstep-Algorithmus
• Pollards rho-Methode zur Berechnung des diskreten Logarithmus
• Der Pohlig-Hellman Algorithmus
• Index Calculus
• Elliptische Kurven
• Primzahltests für spezielle Primzahlen
• Primzahlerkennung in deterministischer Polynomialzeit

Literatur

• E. Bach, J. Shallit: Algorithmic number theory. MIT Press, 1996.
• J. Buchmann: Einführung in die Kryptographie. Springer, 2010.
• R. Crandall, C. Pomerance: Prime Numbers: A Computational Perspective. Springer-Verlag, 2005 (2nd edition)
• V. Diekert, M. Kufleitner, G. Rosenberger: Diskrete Algebraische Methoden. Walter de Gruyter, 2013. Campus Lizenz
• V. Diekert, M. Kufleitner, G. Rosenberger: Elemente der Diskreten Mathematik. Walter de Gruyter, 2013.
• J. von zur Gathen, J. Gerhard: Modern Computer Algebra. Cambridge University Press, 2003 (2nd edition).