Substitution (Kryptographie)

Als Substitution (von lateinisch: substituere = „ersetzen“) bezeichnet man in der Kryptographie eine der beiden grundlegenden Verschlüsselungsklassen neben der Transposition. Die Kryptographie ist der Wissenschaftszweig der Kryptologie, der sich mit Geheimschriften befasst.^[1]

Kennzeichen der Substitution ist, dass Buchstaben oder Zeichen oder auch Buchstabengruppen oder Zeichengruppen eines zu verschlüsselnden Klartextes durch andere Zeichen, genannt Geheimtextzeichen, ersetzt (substituiert) werden.

Dadurch, dass Klartextzeichen durch Geheimtextzeichen substituiert werden, verlieren sie ihren „Charakter“, das heißt ihr Aussehen, und sind somit für unbefugte Blicke, zumindest auf den ersten Blick, nicht mehr zu erkennen. Claude Shannon bezeichnete dies mit dem Wort „Konfusion“.^[2]

Ein einfaches Beispiel für eine Substitution wäre das Ersetzen jedes Buchstabens dieses Textes durch den im Alphabet auf ihn folgenden, also Ersetzen von A durch B, B durch C, und so weiter. Diese besonders simple Verschlüsselungsmethode, allerdings mit Verschiebung um drei statt nur um einen Alphabetplatz, wurde bereits von Gaius Iulius Caesar verwendet und heißt ihm zu Ehren Caesar-Verschlüsselung.

Von der Klassifizierung der unterschiedlichen Substitutionsverfahren her, gehört die Caesar-Verschlüsselung zu den einfachen (das heißt: monographischen) monoalphabetischen Substitutionen. Monographisch deshalb, weil Einzelzeichen ersetzt werden, und monoalphabetisch, weil nur ein einziges festes Alphabet als Schlüssel verwendet wird. Ein Beispiel für eine bigraphische Substitution, bei der also nicht Einzelzeichen, sondern Zeichenpaare substituiert werden, ist das Playfair-Verfahren.

Im Gegensatz zu den monoalphabetischen Substitutionen stehen die polyalphabetischen Substitutionen, bei denen zur Verschlüsselung mehrere (viele) verschiedene Alphabete verwendet werden. Beispiele hierfür sind die Vigenère-Verschlüsselung und die Schlüsselmaschine ENIGMA.

Bei der Transposition, der zweiten grundlegenden Verschlüsselungsklasse neben der Substitution, verändern die Zeichen nicht ihren „Charakter“, sondern ihren Platz, also ihre Position im Text. Substitution und Transposition sind klassische Verschlüsselungsverfahren, die aber auch heute noch in vielfältig kombinierter Form die Grundlage moderner Verschlüsselungsverfahren bilden, wie beispielsweise des Advanced Encryption Standards (von und nach seinen Entwicklern auch Rijndael genannt).

• Terminologie der Kryptographie
• Homophone Verschlüsselung – Die Klartextzeichen können durch unterschiedliche Geheimtextzeichen substituiert werden.
• One-Time-Pad – Perfekte Form der Substitutionsverschlüsselung
• Polygrammsubstitution (auch: polygraphische Substitution) – Statt einzelner Klartextzeichen werden Zeichen-N-Gramme (beispielsweise Buchstabengruppen) substituiert.

• Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, ISBN 3-540-67931-6.
• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography. CRC Press, Boca Raton FL u. a. 1996, ISBN 0-8493-8523-7, S. 17.
• Fred B. Wrixon: Codes, Chiffren & andere Geheimsprachen. Von den ägyptischen Hieroglyphen bis zur Computerkryptologie. Könemann, Köln 2000, ISBN 3-8290-3888-7, S. 168ff.

• CrypTool.de Freies Kryptologie-Lernprogramm CrypTool
• CrypTool-Online: Online-Verschlüsselung von Caesar und weiteren klassischen Verfahren
• Kryptographiespielplatz: Online-Verschlüsselung von Caesar und etlichen weiteren klassischen Verfahren

1. ↑ Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 46 ff.
2. ↑ Claude Shannon: Communication Theory of Secrecy Systems. In: Bell System Technical Journal. Band 28, Nr. 4, 1949, S. 708, doi:10.1002/j.1538-7305.1949.tb00928.x (englisch).