Kryptologie III.1 Das RSA-Verfahren und seine algorithmischen Grundlagen

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Der ganze Abschnitt als PDF-Datei - oder in einzelne Unterabschnitte aufgeteilt:

1. Beschreibung des Verfahrens [PDF-Datei].
2. Der binäre Potenzalgorithmus [PDF-Datei].
3. Die CARMICHAEL-Funktion [PDF-Datei]
4. Geeignete RSA-Parameter [PDF-Datei].

Die drei Algorithmen

• binärer Potenzalgorithmus,
• EUKLIDischer Algorithmus,
• chinesischer Restalgorithmus,

Wer an Quellcode für RSA oder an Computeralgebra-Systemen interessiert ist, sei auf folgende WWW-Ressourcen verwiesen:

• Kryptographische Software-Bibliotheken:
  • libgcrypt (GNU Cryptographic Library)
  • OpenSSL
• Ganzzahl-Arithmetik:
  • gmp (GNU Multiprecision Library)
  • Pari-GP
  • LiDIA
  Achtung: Gewöhnliche Arithmetik-Bibliotheken sollten für kryptographische Software-Entwicklung nur mit äußerster Achtsamkeit verwendet werden. Z. B. sollte kryptographische Software stets dafür sorgen, dass geheime Schlüssel niemals, auch nicht in temporären Dateien oder Auslagerungsdateien, auf einer Festplatte oder anderen permanenten Speicherbereichen zwischengespeichert werden. Es gilt als schwerer Kunstfehler, kryptographische Software für den ernsthaften Gebrauch selbst zu entwickeln! Jeder macht dabei fatale Fehler.
• Freie Computeralgebra-Systeme:
  • Pari-GP
  • SIMATH, NZMATH
  • CoCoA
  • ARIBAS
  • SAGE (enthält PARI, GAP [ein Gruppentheorie-Programmsystem] und Singular [ein Programmsystem für Algebraische Geometrie und Polynomalgebra] sowie Schnittstellen zu Maple, Mathematica und anderen kommerziellen Systemen). Für Pari (und MAGMA) gibt es auch einen Online-Zugang.
• Kommerzielle Computeralgebra-Systeme:
  • Maple
  • Mathematica
  Diese sind sehr viel komfortabler als die freien Systeme, kosten aber dafür auch recht viel (Sonderkonditionen für Studenten). Sie sind aber auch im Software-Pool des Zentrums für Datenverarbeitung installiert und für Studenten und Mitarbeiter, die dort einen Account haben, bequem über einen Terminalserver nutzbar.
  Zum Ansehen von Mathematica-Notebooks kann man sich im WWW den kostenlosen Mathematica Player besorgen.
• Relevante Kategorien im Google-Verzeichnis:
  • Science > Math > Software
  • Science > Math > Number Theory > Software
  • Science > Math > Algebra > Software
  • Computer > Algorithms > Computational Algebra

Literatur zur Computer-Algebra:

• Joachim von zur Gathen, Jürgen Gerhard: Modern Computer Algebra. Cambridge University Press 1999, ISBN 0-521-64176-4. Information.
• Donald E. Knuth: The Art of Computer Programming, Vol. 2, Seminumerical Algorithms. Addison-Wesley, Reading Mass. 1969/1998.
  Deutsche Version von Chap 4: Arithmetik. Springer, Berlin 2001, ISBN 3-540-66745-8.
• Otto Forster: Algorithmische Zahlentheorie. Vieweg, Braunschweig 1996, ISBN 3-528-06580-X.
• Henri Cohen: A Course in Computational Algebraic Number Theory. Springer, Berlin 1993, ISBN 3-540-55640-0.
• John E. Cremona: Algorithms for Modular Elliptic Curves. Cambridge University Press 1992/1997. Online-Version.