Affine Chiffre

Verschlüsselungsverfahren
(Weitergeleitet von Affine Chiffrierung)

Die affine Chiffre ist ein Verschlüsselungsverfahren, das jeden einzelnen Buchstaben des Klartextes nach einer linearen mathematischen Formel substituiert. Die affine Chiffre lässt sich zwar ohne größeren Aufwand berechnen, dafür ist sie allerdings nicht besonders sicher. Einerseits gibt es nur eine begrenzte Anzahl geheimer Schlüssel, sodass diese alle durchprobiert werden können. Andererseits kann der Geheimtext auch ohne Probieren entschlüsselt werden, sobald die Verschlüsselung von nur zwei Zeichen bekannt ist.

Verfahren

Bearbeiten

Lateinisches Alphabet

Bearbeiten

Dieser Abschnitt zeigt die Verwendung der affinen Chiffre für das lateinische Alphabet mit seinen 26 Buchstaben.

Geheimer Schlüssel

Bearbeiten

Sender und Empfänger müssen sich vor Verwendung der affinen Chiffre auf einen geheimen Schlüssel verständigen. Dieser Schlüssel ist ein Zahlenpaar  , wobei

  •   eine zu  , der Anzahl der Buchstaben des Alphabets (hier 26), teilerfremde Zahl zwischen 0 und   ist (hier also eine der Zahlen 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 oder 25); und
  •   eine beliebige Zahl von 0 bis   ist.

Wenn   nicht teilerfremd zu   ist, also  , dann ist die Abbildung nicht invertierbar, und der Geheimtext kann nicht eindeutig entschlüsselt werden. Das wäre hier bei geraden   und bei   der Fall.

Als Beispiel wird im Folgenden die Ver- und Entschlüsselung mit dem Schlüssel   beschrieben.

Verschlüsselung

Bearbeiten

Zur Verschlüsselung werden die Buchstaben des Alphabets fortlaufend durchnummeriert: A=0, B=1, …. Man verschlüsselt jeden Buchstaben einzeln, indem man seinen Zahlenwert   mit   multipliziert und anschließend   addiert. Das Ergebnis teilt man dann durch  .

 

Der bei dieser Division auftretende Rest ist die Nummer des verschlüsselten Buchstabens.

Will man beispielsweise den Buchstaben S, dem die Zahl 18 zugeordnet ist, mit dem Schlüssel   verschlüsseln, so berechnet man

 

Das S wird also durch das L (den Buchstaben mit der Nummer 11) ersetzt.

Entschlüsselung

Bearbeiten

Zu jeder Zahl   des Schlüssels gibt es eine zweite Zahl  , die der folgenden Tabelle entnommen werden kann.

 : 1 3 5 7 9 11 15 17 19 21 23 25
 : 1 9 21 15 3 19 7 23 11 5 17 25

Mit den Zahlen   und   des Schlüssels lässt sich der Geheimtext wieder entschlüsseln. Man nimmt dazu den Zahlenwert   des Geheimtextbuchstabens, berechnet   und teilt das Ergebnis wieder durch  .

 

Auch bei dieser Division tritt ein Rest auf, der die Nummer des Buchstabens vor der Verschlüsselung angibt.

Um beispielsweise den Buchstaben L wieder zu entschlüsseln, schlägt man in der Tabelle   nach und berechnet

 

Der Rest 18 zeigt, dass der ursprüngliche Buchstabe ein S war. (Anstatt durch 26 zu teilen kann man bei negativen Zahlen auch so oft 26 addieren, bis man eine positive Zahl erhält. Diese Zahl ist mit dem Rest der Division identisch.)

Anzahl gültiger Schlüssel

Bearbeiten

Für ein Alphabet mit   Zeichen gibt es   mögliche Schlüssel für die affine Chiffre, wobei   die Eulersche Phi-Funktion bezeichnet. So gibt es insgesamt   verschiedene Schlüssel bei Verwendung des lateinischen Alphabets mit 26 Buchstaben.

Beliebiges Alphabet

Bearbeiten

Anstatt des lateinischen lässt sich jedes andere Alphabet verwenden. Auch hier werden die einzelnen Buchstaben beginnend mit der Null durchnummeriert. Im Weiteren bezeichnet   die Anzahl der Zeichen des Alphabets.

Der geheime Schlüssel ist ein Zahlenpaar  , wobei sowohl   als auch   Zahlen von 0 bis   sind. Die Zahl   muss zusätzlich noch teilerfremd zu   sein.

Zur Verschlüsselung verwendet man den Modulo-Operator, der dem Rest bei der Division entspricht. Ist   das zu verschlüsselnde Zeichen, dann berechnet sich das zugehörige Zeichen   des Geheimtexts nach der Formel

 

Zur Entschlüsselung berechnet man das multiplikativ inverse Element   mit Hilfe des erweiterten euklidischen Algorithmus. Anschließend erhält man das ursprüngliche Zeichen aus dem Zeichen des Geheimtexts nach der Formel

 [1]

Verschiebechiffre

Bearbeiten

Wenn   ist, wird die Affine Chiffre als Verschiebechiffre bezeichnet. Bei einer Verschiebung um   handelt es sich um die Caesar-Chiffre.

Sicherheit

Bearbeiten

Die affine Chiffre ist für längere Texte ein sehr schwaches Verschlüsselungsverfahren. Es gibt zwei Methoden, um sie zu brechen. Am einfachsten ist es, alle möglichen geheimen Schlüssel auszuprobieren. Eine schnellere Methode kann angewandt werden, wenn zu zwei Buchstaben des Geheimtextes die jeweiligen Klartextbuchstaben bekannt sind (Klartextangriff). Dann lässt sich der geheime Schlüssel in wenigen Schritten berechnen. Zu den beiden notwendigen Buchstabenpaaren gelangt man beispielsweise durch eine Häufigkeitsanalyse.

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Referenz zum gesamten Abschnitt „Verfahren“: Christof Paar, Jan Pelzl: Understanding Cryptography - A Textbook for Students and Practitioners. Springer-Verlag, ISBN 978-3-642-04100-6, S. 19–20 (springer.com).