ADFGVX

Billy Duong

Inhalt

Allgemein

Verfahren

Kryptoanalyse

Allgemein

Geschichtlicher Hintergrund

Charakteristika

  • Wahl “A, D, G, F, (V,) X”* um Signalstörungen zu vermeiden

    A | · −
D | − · ·
G | − − ·
F | · · − ·
V | · · · −
X | − · · −

  • Verwendet Substitution und Transposition

  • fraktionierendes Verfahren

Verfahren

Krytoverfahren 101

Alice        | UNSAFE COMMUNICATION TUNNEL |         Bob

m --E(k,m)-->           c                   --D(k,c)--> m

             | Eve                         |


---------------------------------------------------------
m : message
c : ciphertext
k : key
E : encryption function
D : decryption function

Nachricht - m

  • keine Leerzeichen, Buchstaben großgeschrieben

  • Satzzeichen werden ersetzt (zB. X) oder ausgelassen

  • Bei ADFGX muss ein Buchstabe gleich sein (zb. I = J)

  • Bei ADFGX müssen Zahlen ausgeschrieben werden

  • Beispiel:

    GEHEIMENACHRICHT

Verschlüsselte Nachricht - c

  • Besteht nur aus A, D, F, G, (V, ) X

  • Wird in 5er Blöcken übertragen

  • Beispiel:

    DFFAD GAADX DFFVV DVFDD DGGAD FDVDD AA

Schlüssel - k

  • 2 Wörter oder Zeichenketten (A-Z)

  • 1. Wort: 1-25 (ADFGX) bzw. 1-36 (ADFGVX)

  • 2. Wort: beliebig lang

  • Beispiel:

    KRYPTOGRAPHIE, FLUSS


Anmerkung: Schlüssel wurde in Praxis einmal täglich gewechselt.

Verschlüsselung - E (I)

1. Substitution über Polybios Quadrat

 |A D F G V X        - 1. Wort als Schlüssel:
-·-----------          "KRYPTOGRAPHIE"
A|K R Y P T O
D|G A H I E B        - Dopplungen im Schlüssel werden
F|C D F J L M          ausgelassen: "KRYPTOGAHIE"
G|N Q S U V W
V|X Z 0 1 2 3        - Ersetzungstabelle bilden
X|4 5 6 7 8 9


m = G  E  H  E  I  M  E  N  A  C  H  R  I  C  H  T

 => DA DV DF DV DG FX DV GA DD FA DF AD DG FA DF AV

Verschlüsselung - E (II)

2. Spaltentransposition

m' = DA DV DF DV DG FX DV GA DD FA DF AD DG FA DF AV

12534               12345   - in Spalten aufschreiben
-----               -----     (#Spalten = Länge 2. Wort)
DADVD           |   DAVDD
FDVDG           v   FDDGV   - Spalten nach 2. Wort
FXDVG     =>        FXVGD     anordnen FLUSS = 12534
ADDFA               ADFAD
DFADD               DFDDA   - Spalten von OBEN nach UNTEN
GFADF               GFDFA     ablesen (* ignorieren)
AV***               AV***

c = DFFADGAADXDFFVVDVFDDDGGADFDVDDAA
 => DFFAD GAADX DFFVV DVFDD DGGAD FDVDD AA


Alternativ: Statt * mit zB. X (VA) auffüllen.

Entschlüsselung - D

1. Spaltentransposition

12345               12534   - Spalten aufstellen (#Spalten 
-----               -----     = Länge 2. Wort)
DAVDD               DADVD
FDDGV               FDVDG   - * anhand von Länge setzen
FXVGD     =>        FXDVG
ADFAD               ADDFA   - Nachricht eintragen und Spalten
DFDDA               DFADD     nach 2. Wort anordnen
GFDFA               GFADF     
AV***               AV***   - Zeilen ablesen

 => DADVDFDVDGFXDVGADDFADFADDGFADFAV

2. Substitution

 => GEHEIMENACHRICHT

Kryptoanalyse

Werkzeuge (I)

Transposition

  • zB. allgemeine Spaltentransposition
  • Known Plaintext
  • Bigramme + Trigramme
  • Heuristische Verfahren

Werzeuge (II)

Monoalphabetische Substitution

  • zB. Cäsar-Chiffre
  • Häufigkeitsanalyse


Koinzidenzindex *

\(\displaystyle \mathbf {IC} ={\frac {\sum _{i=A}^{Z}n_{i}(n_{i}-1)}{N(N-1)}}\)

Probleme

  • Häufigkeitsanalyse nicht direkt möglich

    • Transposition “zerreißt” die Doppelzeichen

  • Heuristische Verfahren benötigen…

    • Nachbarschaftsfunktion
    • Kostenfunktion

  • (Transpositions) Schlüssellänge ist sehr wichtig!

Ansätze (I)

SOLUTION OF THE ADFGVX SYSTEM *

  • “Special solution by means of identical endings” (98)

  • “Special solution by means of identical beginnings” (105)

  • “Special solution by the exact factor method” (123)

  • “Basic principles of the general solution” (125)

Ansätze (II)

Heuristischer Ansatz *

  • Transponieren und über Koinzidenzindex testen
    • \(n_i\) steht für Buchstabenpaare
    • Korrekte Transposition ergibt guten Koinzidenzindex für Sprache
  • Algorithmen: Hill Climbing, Simulated Annealing, Tabu Search, Genetische Algorithmen

Weiterführendes

Allgemein

* Empfehlungen

Vertiefung

* Empfehlungen

Danke für Zuhören!