imported>Alabasterstein: Änderung 246036726 von 176.6.19.174 rückgängig gemacht; 1. Beleg fehlt 2. bitte mathematische Formeln in WP:TeX setzen

2024-06-19T09:01:04Z

Änderung 246036726 von 176.6.19.174 rückgängig gemacht; 1. Beleg fehlt 2. bitte mathematische Formeln in WP:TeX setzen

Neue Seite

Die '''affine Chiffre''' ist ein [[Verschlüsselungsverfahren]], das jeden einzelnen Buchstaben des [[Klartext (Kryptographie)|Klartextes]] nach einer [[Lineare Funktion|linearen]] mathematischen Formel [[Monoalphabetische Substitution|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 ==
=== Lateinisches Alphabet ===
Dieser Abschnitt zeigt die Verwendung der affinen Chiffre für das [[Lateinisches Alphabet|lateinische Alphabet]] mit seinen 26 Buchstaben.

==== Geheimer Schlüssel ====
Sender und Empfänger müssen sich vor Verwendung der affinen Chiffre auf einen [[Geheimer Schlüssel|geheimen Schlüssel]] verständigen. Dieser Schlüssel ist ein Zahlenpaar <math>(a,b)</math>, wobei
* <math>a</math> eine zu <math>k</math>, der Anzahl der Buchstaben des Alphabets (hier 26), [[teilerfremd]]e Zahl zwischen 0 und <math>k</math> ist (hier also eine der Zahlen 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 oder 25); und
* <math>b</math> eine beliebige Zahl von 0 bis <math>k-1</math> ist.

Wenn <math>a</math> nicht teilerfremd zu <math>k</math> ist, also <math>\operatorname{ggT}(a,k) > 1</math>, dann ist die Abbildung nicht invertierbar, und der Geheimtext kann nicht eindeutig entschlüsselt werden. Das wäre hier bei geraden <math>a</math> und bei <math>a=13</math> der Fall.

Als Beispiel wird im Folgenden die Ver- und Entschlüsselung mit dem Schlüssel <math>(7, 15)</math> beschrieben.

==== Verschlüsselung ====
Zur Verschlüsselung werden die Buchstaben des Alphabets fortlaufend durchnummeriert: A=0, B=1, …. Man verschlüsselt jeden Buchstaben einzeln, indem man seinen Zahlenwert <math>x</math> mit <math>a</math> multipliziert und anschließend <math>b</math> addiert. Das Ergebnis teilt man dann durch <math>k</math>.
: <math>(a \cdot x + b) : k</math>
Der bei dieser [[Division mit Rest|Division]] auftretende [[Division mit Rest|Rest]] ist die Nummer des verschlüsselten Buchstabens.

Will man beispielsweise den Buchstaben S, dem die Zahl 18 zugeordnet ist, mit dem Schlüssel <math>(7, 15)</math> verschlüsseln, so berechnet man
: <math>(7 \cdot 18 + 15) : 26 = 141 : 26 = 5 \, \operatorname{Rest} \, 11</math>
Das S wird also durch das L (den Buchstaben mit der Nummer 11) ersetzt.

==== Entschlüsselung ====
Zu jeder Zahl <math>a</math> des Schlüssels gibt es eine zweite Zahl <math>a^{-1}</math>, die der folgenden Tabelle entnommen werden kann.

{| class="wikitable"
|-
|class="hintergrundfarbe6" | <math>a</math>: || 1 || 3 || 5 || 7 || 9 || 11 || 15 || 17 || 19 || 21 || 23 || 25
|-
|class="hintergrundfarbe6" | <math>a^{-1} </math>: || 1 || 9 || 21 || 15 || 3 || 19 || 7 || 23 || 11 || 5 || 17 || 25
|}

Mit den Zahlen <math>a^{-1}</math> und <math>b</math> des Schlüssels lässt sich der Geheimtext wieder entschlüsseln. Man nimmt dazu den Zahlenwert <math>y</math> des Geheimtextbuchstabens, berechnet <math>a^{-1} \cdot (y-b)</math> und teilt das Ergebnis wieder durch <math>k</math>.
:<math>a^{-1} \cdot (y-b) : k</math>
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 <math>a^{-1} = 15</math> nach und berechnet
: <math>15 \cdot (11 - 15) : 26 = -60 : 26 = -3 \, \operatorname{Rest} \, 18</math>
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 ====

Für ein Alphabet mit <math>n</math> Zeichen gibt es <math>\varphi(n) \cdot n</math> mögliche Schlüssel für die affine Chiffre, wobei <math>\varphi(\cdot)</math> die [[Eulersche Phi-Funktion]] bezeichnet. So gibt es insgesamt <math>12 \cdot 26 = 312</math> verschiedene Schlüssel bei Verwendung des lateinischen Alphabets mit 26 Buchstaben.

=== Beliebiges Alphabet ===
Anstatt des lateinischen lässt sich jedes andere [[Alphabet]] verwenden. Auch hier werden die einzelnen Buchstaben beginnend mit der Null durchnummeriert. Im Weiteren bezeichnet <math>m</math> die Anzahl der Zeichen des Alphabets.

Der geheime Schlüssel ist ein Zahlenpaar <math>(a, b)</math>, wobei sowohl <math>a</math> als auch <math>b</math> Zahlen von 0 bis <math>m-1</math> sind. Die Zahl <math>a</math> muss zusätzlich noch [[Teilerfremdheit|teilerfremd]] zu <math>m</math> sein.

Zur Verschlüsselung verwendet man den [[Division mit Rest|Modulo-Operator]], der dem Rest bei der Division entspricht. Ist <math>x</math> das zu verschlüsselnde Zeichen, dann berechnet sich das zugehörige Zeichen <math>y</math> des Geheimtexts nach der Formel
: <math>y = (a \cdot x + b) \mod m</math>

Zur Entschlüsselung berechnet man das [[Prime Restklassengruppe|multiplikativ inverse Element]] <math>a^{-1}</math> mit Hilfe des [[Erweiterter Euklidischer Algorithmus|erweiterten euklidischen Algorithmus]]. Anschließend erhält man das ursprüngliche Zeichen aus dem Zeichen des Geheimtexts nach der Formel
: <math>x = \left[ a^{-1} \cdot (y - b) \right] \mod m</math><ref>Referenz zum gesamten Abschnitt „Verfahren“: {{Literatur|Autor=Christof Paar, Jan Pelzl|Titel=Understanding Cryptography - A Textbook for Students and Practitioners|Hrsg=|Sammelwerk=|Band=|Nummer=|Auflage=|Verlag=Springer-Verlag|Ort=|Datum=|Seiten=19–20|ISBN=978-3-642-04100-6|Online=https://www.springer.com/de/book/9783642041006|Abruf=}}</ref>

== Verschiebechiffre ==
Wenn <math>a=1</math> ist, wird die Affine Chiffre als [[Verschiebechiffre]] bezeichnet. Bei einer Verschiebung um <math>b=3</math> handelt es sich um die ''Caesar-Chiffre''.

== Sicherheit ==
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 [[Brute-Force-Methode|auszuprobieren]]. Eine schnellere Methode kann angewandt werden, wenn zu zwei Buchstaben des Geheimtextes die jeweiligen Klartextbuchstaben bekannt sind ([[Kryptoanalyse#Known Plaintext|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 ==
* [[Johannes Buchmann]]: ''Einführung in die Kryptographie.'' 2. erweiterte Auflage. Springer, Berlin u. a. 2001, ISBN 3-540-41283-2, S. 73–74.

== Einzelnachweise ==
<references />

[[Kategorie:Klassische Kryptologie]]
[[Kategorie:Kryptologisches Verfahren]]

Affine Chiffre - Versionsgeschichte

imported>Alabasterstein: Änderung 246036726 von 176.6.19.174 rückgängig gemacht; 1. Beleg fehlt 2. bitte mathematische Formeln in WP:TeX setzen