Substitution (Kryptographie)

Grundprinzip und Bedeutung

Die Substitution ist neben der Transposition eine der beiden grundlegenden Verschlüsselungsklassen der Kryptographie. Kryptographie ist der Teil der Kryptologie, der sich mit Geheimschriften befasst.

Bei einer Substitution werden Buchstaben, andere Zeichen oder Gruppen davon durch sogenannte Geheimtextzeichen ersetzt. So verlieren die Zeichen des Klartextes ihr ursprüngliches Aussehen und sind für Unbefugte zumindest auf den ersten Blick nicht erkennbar. Claude Shannon bezeichnete diese Wirkung als Konfusion.

Einfache und polygraphische Verfahren

Substitutionsverfahren lassen sich danach unterscheiden, wie viele Klartextzeichen gemeinsam ersetzt werden:

• Einfache oder monographische Verfahren ersetzen einzelne Zeichen. Ein Beispiel ist die Caesar-Verschlüsselung.
• Polygraphische Verfahren ersetzen Gruppen aus mehreren Zeichen gemeinsam.
• Werden jeweils Zeichenpaare, also Zweiergruppen, ersetzt, heißt das Verfahren bigraphisch. Ein Beispiel ist die Playfair-Chiffre.

Monoalphabetische und polyalphabetische Substitution

Bei einer monoalphabetischen Substitution wird nur ein einziges festes Alphabet als Schlüssel verwendet. „Alphabet“ bezeichnet dabei die Ersetzungstabelle, die festlegt, welches Klartextzeichen durch welches Geheimtextzeichen ersetzt wird. Ein Zeichen oder eine Zeichengruppe erhält deshalb immer denselben Ersatz, beispielsweise wird ein A stets durch ein D ersetzt.

Bei einer polyalphabetischen Substitution kommen dagegen mehrere verschiedene Ersetzungsalphabete zum Einsatz. Welches Geheimtextzeichen einen Buchstaben ersetzt, hängt von dessen Position im Text ab. Beispiele sind die Vigenère-Verschlüsselung und die Schlüsselmaschine ENIGMA.

Beispiele und Abgrenzung

Ein sehr einfaches Beispiel ersetzt jeden Buchstaben durch den im lateinischen Alphabet folgenden: A wird zu B, B zu C und so weiter. Gaius Iulius Caesar verwendete ein entsprechendes Verfahren mit einer Verschiebung um drei Alphabetplätze; nach ihm heißt es Caesar-Verschlüsselung.

Die Transposition unterscheidet sich von der Substitution dadurch, dass sie Zeichen nicht ersetzt, sondern ihre Positionen im Text verändert. Beide klassischen Techniken bilden auch heute in vielfältigen Kombinationen die Grundlage moderner, computerbasierter Verschlüsselungsverfahren. Dort wird die Substitution als S-Box bezeichnet. Im Advanced Encryption Standard ersetzt eine solche S-Box jeweils ein Byte beziehungsweise Oktett durch ein anderes.