|
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:
- Beschreibung des Verfahrens [PDF-Datei].
- Der binäre Potenzalgorithmus [PDF-Datei].
- Der EUKLIDische Algorithmus [PDF-Datei].
- Analyse des EUKLIDischen Algorithmus [PDF-Datei].
- Kongruenzdivision [PDF-Datei].
- Der chinesische Restalgorithmus [PDF-Datei].
- Die EULERsche j-Funktion
[PDF-Datei].
- Die CARMICHAEL-Funktion [PDF-Datei]
- Geeignete RSA-Parameter [PDF-Datei].
Die drei Algorithmen
- binärer Potenzalgorithmus,
- EUKLIDischer Algorithmus,
- chinesischer Restalgorithmus,
sind die grundlegenden Algorithmen der algorithmischen Algebra und
Zahlentheorie (»Computer-Algebra«), aber von großer Bedeutung auch in der numerischen
Mathematik - immer dann, wenn es nicht um näherungsweises Rechnen mit Gleitkomma-Zahlen
sondern um exaktes Rechnen mit ganzen oder rationalen Zahlen oder symbolischen
Ausdrücken geht.
Wer an Quellcode für RSA oder an Computeralgebra-Systemen interessiert ist,
sei auf folgende WWW-Ressourcen verwiesen:
- Kryptographische Software-Bibliotheken:
- Ganzzahl-Arithmetik:
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.
- Freie Computeralgebra-Systeme:
- Kommerzielle Computeralgebra-Systeme:
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 (nicht Ausführen!) von Mathematica-Notebooks kann man sich
im WWW den kostenlosen
MathReader
besorgen.
- Relevante Kategorien im
Google-Verzeichnis:
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.
Autor: Klaus Pommerening, 21. Mai 2000;
letzte Änderung: 31. Juli 2003.
E-Mail an
Pommerening@imsd.uni-mainz.de.