Diskussion:Affine Chiffre

Index

M.E. ist der Index des Alphabetes null-basierend, also $x_{0},x_{1},\ldots$. So errechnet sich die Verschlüsselung des 1. Buchstabens A in dem im Artikel genannten Beispiel durch ((15 * 0) + 10) mod 26 = 10, womit der 11. Buchstabe K bezeichnet wird. Analog der 23. Buchstabe W: ((15 * 22) + 10) mod 26 = 2, also C. --Escla ^¿! 21:40, 2. Dez. 2007 (CET)

Du hast recht. Ich habe es entsprechend korrigiert. --Stefan Birkner 09:12, 3. Dez. 2007 (CET)

Geheimer Schlüssel

In den folgenden zwei Sätzen wird b zweimal unterschiedlich definiert. Falls das unterschiedliche b sind sollte man eins umbenennen, ansonsten klarer erklären wie b definiert ist. "Dieser Schlüssel ist ein Zahlenpaar (a,b), wobei a eine der Zahlen 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 oder 25 und b eine beliebige Zahl von 0 bis 25 ist. Für a gilt dabei a < b und ggT(a,b) = 1 und b ist die Anzahl der Buchstaben des Alphabets."

Absatz nennt eine schnellere Methode ohne Erklärung

Eine schnellere Methode kann angewandt werden, wenn zu zwei Buchstaben des Geheimtextes die jeweiligen Klartextbuchstaben bekannt sind. Dann lässt sich der geheime Schlüssel in wenigen Schritten berechnen.

Hier sollte man erwähnen wie diese "schnellere Methode" tatsächlich funktioniert oder zu einem entsprechenden Artikel verweisen. (nicht signierter Beitrag von 2A02:8070:46CB:5700:651F:BB6B:657D:C1BA (Diskussion | Beiträge) 20:26, 6. Nov. 2016 (CET))

Fehlerhafte Definition

Das affine Chiffre braucht zwei Zahlen sowie die Gesamtlänge des Alphabets, die Aussagen "und k {\displaystyle k} k eine beliebige Zahl von 0 bis 25 ist" sowie " k {\displaystyle k} k ist die Anzahl der Buchstaben des Alphabets." wiedersprechen sich schon. Hier wurden b und k offensichtlich schon früh durcheinander geworfen. Das dann unreflektiert zu vereinheitlichen macht leider auch nix besser, es hätte korrekt getrennt werden sollen. Wenn ich das Ganze bald verstanden haben sollte, versuche ich gerne das gerade zu ziehen, ob ich das aber soweit durchblicken werde muss sich erst herausstellen. (nicht signierter Beitrag von 93.204.215.103 (Diskussion) 15:31, 8. Feb. 2017 (CET))

Schlüssel (a, b)

Im dem schon sehr informativen Artikel zur affinen Chiffre findet man folgende Feststellung : "Der geheime Schlüssel ist ein Zahlenpaar (a, b) , wobei a als auch b Zahlen von 0 bis (m - 1) sind. Die Zahl a muss zusätzlich noch teilerfremd zu m sein." Das trifft so aber nicht zu, da a keinesfalls Null sein darf. Denn dann erhielte jeder der m chiffrierten Alphabeteinträge konstant den Wert b. Was nicht sein kann. Es gilt vielmehr [ 1 <= a < m ] sowie [ 0 <= b < m ]. Für den Zeichensatz m = 29 (prim !) gibt es somit (m -1) * m = 28 * 29 = 812 verschiedene Schlüssel (a, b), da alle denkbaren a und b hier automatisch relativ prim zu m sind. Es wäre hilfreich generell einmal darauf hinzuweisen, dass die affine Chiffre sich NICHT auf die Klartextzeichen (bei Verschlüsselung) bzw. die Geheimtextzeichen (bei der Dechiffrierung) sondern stattdessen vielmehr auf die POSITIONEN (0 bis (m - 1)) INNERHALB EINES ALPHABETES BEZIEHT, DESSEN ZEICHEN DARIN BELIEBIG PERMUTIERT SEIN KÖNNEN. Das bedeutet dann auch, dass sich mit Hilfe affiner Chiffren beliebige Klartextlängen mathematisch permutieren lassen, solange die verwendeten a und b der Schlüssel legitim (s.o.) sind. Hat ein Klartext die Länge k, dann lassen sich falls erforderlich l Zufallszeichen am Ende ergänzen, sodass dann (k + l) prim ist. In dem Fall existieren dann (k + l) * (k + l - 1) verschiedene affine Schlüssel (a, b) bzw. (a^-1, b), also die maximal mögliche Anzahl, mit denen sich dann ein Klartext einer Transposition über die gesamte Länge (k + l) unterziehen lässt, bzw. sich ein transponierter Geheimtext wieder in Klartext dechiffrieren lässt. Ein Klartext mit 1000 Buchstaben bzw. Zeichen lässt sich dabei z.B. mit l Zufallszeichen bis zur nächsten Primzahl ergänzen (hier k + l = 1009, l = 9). Dann existieren bereits 1009 * 1008 = 1.017.072 verschiedene nutzbare Transpositionsschlüssel (a, b) bzw (a^-1, b) über die gesamte Klartextlänge ! Stark verwürfelte Alphabete bzw. Klartexte ("Anagramme") sind besonders dann erreichbar, wenn ein Alphabet oder Klartext hintereinander mehrmals mit verschiedenen Schlüsseln (a1, b1), (a2, b2),........(an, bn) chiffriert wird. Eine Kryptanalyse wird dadurch ERHEBLICH erschwert. Dafür sind dann nämlich die entsprechenden Dechiffrierschlüssel (an^-1, bn)..... (a2^-1, b2), (a1^-1, b1) erforderlich, in der korrekten, umgekehrten Reihenfolge der Dechiffrierung ! --46.114.106.164 22:45, 4. Mär. 2024 (CET)

Null ist nicht teilerfremd zu irgendeiner Zahl n >= 2, denn es ist ggT(0,n) = n. Durch die Forderung, dass a teilerfremd zu m sein muss, ist a=0 also ausgeschlossen.--Megatherium (Diskussion) 13:24, 5. Mär. 2024 (CET)

@Megatherium D'accord ! Mir ging es nur um die missverständliche Formulierung "Der geheime Schlüssel ist ein Zahlenpaar (a, b) , wobei a als auch b Zahlen von 0 bis (m - 1) sind." : a ist eine Zahl von 1 bis (m - 1), nicht von 0 bis (m - 1). --46.114.110.53 23:40, 6. Mär. 2024 (CET)

Wenn man die Klartextzeichen frei permutiert, ist das ein zusätzlicher Verschlüsselungsschritt, der nicht zur Affinen Chiffre gehört, also eine Überschlüsselung. Dann ist auch die gewählte Permutation ein Teil des Schlüssels für die gesamte Verschlüsselung.--Megatherium (Diskussion) 13:44, 5. Mär. 2024 (CET)

@Megatherium Da haben Sie mich missverstanden, oder ich habe das unzureichend erklärt : es gibt nur eine Verschlüsselung, keine Überschlüsselung.

Es ist nicht so gedacht, dass man mit einer affinen Chiffre des Zeichensatzes 26 (311 verschiedene Schlüssel, der 312. Schlüssel (a=1, b=0) lässt den Klartext unverändert) zunächst den gesamten Klartext monoalphabetisch substituiert, und danach noch eine beliebige Transposition zur Überschlüsselung folgen lässt.

Stattdessen führt man eine affine Verschlüsselung über die gesamte Textlänge durch.

Beispiel :

Der erste Satz aus J. Cäsars "De Bello Gallico" (120 Zeichen, Wortabstände werden ignoriert) wird durch sieben Zufallszeichen am Ende zu 127 Zeichen ergänzt (nächstgrößere Primzahl). Die affine Chiffre über 127 Zeichen lässt somit 126 * 127 = 16.002 verschiedene Schlüssel (a,b) zu, wovon einer (1,0) den Klartext unverändert lässt.

Als Beispiel wählen wir (a,b) = (97; 73).

Mit (a * x + b) mod 127 berechnet man nun, in welche Position y des Geheimtextes ein Zeichen in der ursprünglicher Position x des Klartextes wechselt.

Die Zeichen auf den Klartext-Positionen x = 0, 1, 2, 3,......., 126 werden dadurch auf die Geheimtext-Positionen y = 73, 43, 13, 110, 80, 50, 20, ......, 6, 103 verschoben.

Man kann bei bekanntem Schlüssel (a,b) und bekannter Textlänge (m = 127) ein Array mit 127 Feldern anlegen, und diese von x = 0 bis 126 durchnummerieren. Durch Berechnung füllt man die Felder mit den entsprechenden y-Werten. a^-1 zur Dechiffrierung (in diesem Fall ist a^-1 = 55) eignet sich hier nicht, da einem Textzeichen anders als in einem beliebigen Alphabet keine eindeutige Position zugeordnet werden kann, denn es existieren zahlreiche Buchstaben mehrfach im Klartext und Geheimtext.

Aus

GALLI AESTO MNISD IVISA INPAR TESTR ESQUA RUMUN AMINC OLUNT BELGA EALIA MAQUI TANIT ERTIA MQUII PSORU MLING UACEL TAENO STRAG ALLIA

PPELL ANTUR VNCQJ TB

wird dann die Transposition

INSPP BITIL SJLIA ITRMN IINSA METCC QQLOT NOLQL VLRGA VUMEG ENMSG ACDPS ENUNI TTTTR ARTII AITAN LAEQE UULSE AMLUU ILUAR NAASA NIUTA

MOIEO LPRGA RBAAU EA

welche durch Berechnung des Arrays (s.o.) leicht wieder dechiffriert werden kann : das erste Zeichen des Geheimtextes kommt an Position 73. des Klartextes, das zweite Geheimtextzeichen an Position 43. des Geheimtextes usw., alle folgenden Positionen werden bei diesem (a, b) zyklisch (mod 127) durch jeweils weitere Subtraktion von 30 berechnet.

Natürlich ist eine solche Transposition nicht wirklich sicher. sie wird aber zunehmend sicherer, wenn man den Geheimtext wieder und wieder mit anderen Schlüsseln (a,b) überschlüsselt. Schon bei fünf Durchgängen mit verschiedenen Schlüsseln (a, b) existieren dann 16.001^ 5 = 1,05*10^21 mögliche verschiedene Klartexte zu einem bestimmten Geheimtext. Ein Schlüsselraum mit 22 Ziffern Länge. --46.114.104.220 13:31, 7. Mär. 2024 (CET)

Verstehe, das soll eine Anwendung der affinen Abbildung auf die Zeichenposition (eine Transposition) statt auf den Zeichenwert (Substitution der Zeichen) sein. Das ist eine interessante Idee, aber ich glaube, das läuft unter wp:Theoriefindung. Außerdem ist die Verkettung von zwei affinen Abbildungen ebenfalls affin, zwei aufeinanderfolgende können also durch eine einzige ersetzt werden, und der Schlüsselraum vergrößert sich nicht. Es sei denn, man verwendet beide Male einen anderen Modul (zumindest dann, wenn die beiden Module zueinander teilerfremd sind).--Megatherium (Diskussion) 15:37, 7. Mär. 2024 (CET)

@Megatherium Daran hatte ich nicht gedacht, das kann wirklich der Fall sein, eine Complication illusoire. Das ist vermutlich auch der Grund dafür, dass beim sogenannten Doppelwürfel (doppelte Spaltentransposition mit unterschiedlicher Anzahl an Spalten) die beiden Schlüsselwortlängen relativ prim zueinander sein sollten. Zumindest verhält es sich da ähnlich. --46.114.104.220 22:30, 7. Mär. 2024 (CET)

@Megatherium Zu Ihrem Hinweis auf die Verkettung zweier verschiedener affiner Chiffren noch folgender Hinweis :

Ein Standardalphabet möge zuerst mit der affinen Chiffre y1 = ((a1 * a) + b1) mod m (hier 26) verschlüsselt werden, danach das Chiffrat nochmals mit der anderen affinen Chiffre y2 = ((a2 * x) + b2) mod m.

Dann gilt allgemein, dass sich diese beiden affinen Chiffren ersetzen lassen durch nur eine andere affine Chiffre y3 = ((a3 * x) + b3) mod m, wobei a3 = (a1 * a2) mod m und b3 = ((a2 * b1) + b2) mod m.

Beispiel : a1 = 9, b1 = 17 und a2 = 15 sowie b2 = 21 lässt sich ersetzen durch a3 = 5 und b3 = 16.

Das heißt : beliebig viele affine Chiffren nacheinander verwendet kann man auch durch nur eine einzige ersetzen.

Das gilt aber nicht mehr dann, wenn man ZWISCHEN den affinen Verschlüsselungsschritten je einen Transpositionsschritt einfügt, der NICHT AFFIN IST. Z.B. könnte man die Nachricht in n Blöcke unterteilen, von denen der letzte geringfügig länger ist als die anderen (Klartextlänge prim !), und diese Blöcke nach Schlüssel permutieren und dabei teilweise auch invertieren. Wählt man die Blockanzahl 13, dann existieren 13! * 2^13 verschiedene Transpositionen, bei denen Blöcke nicht nur permutiert sind, sondern womöglich auch invertiert. Und jetzt macht sich der große Schlüsselraum von z.B. zehn nacheinander durchgeführten affinen Chiffren durchaus bemerkbar. Eine Verkettung tritt nicht mehr auf.

Eine solche Transposition über die volle Textlänge wäre für Computer schnell machbar, aber für Unbefugte kaum mehr mit akzeptablem Aufwand lesbar. --176.6.20.24 14:01, 18. Jun. 2024 (CEST)