kopf
brlogo
fensterobenrechts
   
   
fensteruntenblau
   
 

 

Grundlagen der Kryptologie

 

4. Polyalphabetische Substitution

 

Die polyalphabetische Substitution, die auch als Vigenere-Chiffrierung bezeichnet wird, beruht auf der Idee, gleiche Buchstaben in der Reihenfolge ihres Auftretens unterschiedlich zu verschlüsseln. Bei unbekanntem Schlüssel hilft die Analyse der Häufigkeiten nicht weiter. Zur Dechiffrierung muss durch Suchen periodisch auftretender Muster aus Buchstabenpaaren, -trippeln usw. auf die Periodenlänge der Verschlüsselung geschlossen werden. Danach kann man entsprechend der mono-alphabetschen Codierung fortfahren. Diese Suche ist in [1] beschrieben.

Es gibt eine Reihe von Variationen von diesem Verfahren.

 

a)  Von Zeile zu Zeile verschobenen permutiertem Alphabete

 

 

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

0

D

L

G

A

Z

E

N

B

O

S

F

C

H

T

Y

Q

I

X

K

V

P

J

M

U

W

V

1

L

G

A

Z

E

N

B

O

S

F

C

H

T

Y

Q

I

X

K

V

P

J

M

U

W

V

D

2

G

A

Z

E

N

B

O

S

F

C

H

T

Y

Q

I

X

K

V

P

J

M

U

W

V

D

L

...

                                                   

N

                                                   

 

b)  Permutationen mit Hilfe eines Schlüsselwortes

 

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

 

Die Auswahl des Tauschalphabets wird über ein Schlüsselwort "WAFFEN" gesteuert. Jeder Buchstabe des Textes wird nun mit Hilfe eines anderen Tauschalphabets verschlüsselt.

Für den i-ten Buchstaben nimmt man i-te Tauschalphabet.

Aus ALBIN wird WLGNR

 

Analyse eines Vigenere-chiffrierten Textes

Auch ein solch chiffrierten Text kann geknackt werden. Ist ein Geheimtext genügend lang, so weist er einige statistische Regelmäßigkeiten auf, die es ermöglichen, das Schlüsselwort zu ermitteln.

Es stehen im wesentlichen zwei Methoden zur Kryptoanalyse von Vigenere-Chiffrierungen zur Verfügung.

 

Der Kasiski-Test (preußischer Infanteriemajor 1863)

Der Test beruht auf folgender Idee:

Treten im Klartext zwei Folgen aus gleichen Buchstaben auf (z.B. ein), so werden im allgemeinen die entsprechenden Folgen im Geheimtext verschieden ausfallen. Werden aber die beiden Anfangsbuchstaben der Folgen mit Hilfe desselben Schlüsselwortbuchstabens verschlüsselt, so sind auch die beiden Geheimtextbuchstaben gleich.

Dieser Fall tritt genau dann auf, wenn das Schlüsselwort zwischen sie genau einmal, genau zweimal usw. passt. Also genau dann, wenn der Abstand der beiden Klartextbuchstaben ein vielfaches der Schlüsselwortlänge ist.

 

substitution_10

 

Nun geht man umgekehrt vor: Wenn man im Geheimtext zwei Folgen aus gleichen Buchstaben findet, so ist ihr Abstand wahrscheinlich ein vielfaches der Schlüssel-wortlänge. Gleiche Buchstaben oder Paare sagen nicht viel über die Schlüsselwort-länge aus, aber aus Folgen aus drei oder mehr Buchstaben kann man schon ziemlich zuverlässig auf die Schlüsselwortlänge schließen.

 

substitution_20

substitution_25

 

Folge

Abstand

Primfaktorzerl. des Abstandes

JTD

50

2*5*5

VIQM

265

5*53

TDMHZGNMWK

90

2*3*5

MWK

75

3*5*5

 

Der höchste gemeinsame Faktor ist 5. Dies ist ein starkes Indiz dafür, dass die Schlüsselwortlänge 5 ist.

Dies ist nur ein Indiz. Es könnte sein, dass wir auch Folgen aus drei oder mehr gleichen Buchstaben finden, die einen nicht durch 5 teilbaren Abstand haben. Dann würde sich der ggT = 1 ergeben. (KAH tritt zweimal auf mit dem Abstand 128). Man muss u.U. auch solche Ausreißer berücksichtigen.

Es kann auch sein, dass die Schlüsselwortlänge ein Vielfaches von 5 also 10, 15 oder 30 ist; denn die Faktoren 2 und 3 kommen recht häufig vor.

Der Kasiski-Test liefert die Schlüssellänge nur bis auf Vielfache oder Teiler.

Ein anderer Test (Friedman-Test) wird in [1] oder [4] besprochen.

 

Weitere Beispiele zur Verschlüsselung

Bei der Diskussion mit Schülern ergaben sich weitere einfache Methoden der Verschlüsselung. So ergaben sich im Zusammenhang mit ARRAYS und Zeichenketten die folgenden Verfahren, die beliebig ergänzt werden können. Sie sind jedoch als Spezialfälle in den bereits besprochenen Verfahren enthalten. Ich erwähne sie deshalb hier, da es interessante Beispiele zur Arbeit mit ARRAYS bzw. Zeichenketten sind.

Die Idee beruht darauf die Zeichenkette in ein ARRAY einzulesen. Der Text kann dann umgekehrt zeilenweise, reihenweise oder diagonal ausgelesen werden.

 

D

I

E

I

S

T

E

I

N

S

P

Z

I

A

L

F

A

L

L

D

E

R

P

O

L

Y

A

L

P

H

A

B

E

T

I

S

C

H

E

N

K

O

D

I

E

R

U

N

G

 

Verschlüsselter Text bei reihenweiser Kodierung:

DILRPSDINFPHCIESAOAHESZLY usw.

umgekehrter zeilenausgabe

ETSIEIDAIZPSNI usw.

 

Beispiel für die Polyalphabetische Substitution

In diesem Programm werden in dem Text alle Satzzeichen, Leerzeichen und Umlaute entfernt. (loesche_sonderzeichen(neu,zk);)

Danach wird der Text in entsprechende gleiche Blöcke eingeteilt. Die Anzahl der Zeichen werden in der Variablen "schlüssel1" (schl1) festgelegt. Der letzte Block kann auch weniger Zeichen enthalten.

Die einzelnen Blöcke werden mit dem Schlüssel2 (schl2) permutiert. Mit diesem Verfahren ist eine Entschlüsselung mit der Häufigkeitsverteilung fast nicht mehr möglich.

 

Zugehörige Algorithmen und ein Programmierbeispiel in Pascal//Delphi-Notation:  Substitution1

 

Dekodierung

Die Dekodierung verläuft entsprechend. Eine systematische Entschlüsselung kann man dann vornehmen, wenn man sämtliche Möglichkeiten der beiden Schlüssel in einem Programm realisiert. Bei einem langen Text und entsprechenden Schlüssel ist dies kaum in einer annehmbaren Zeit realisierbar.

 

Zugehörige Algorithmen und ein Programmierbeispiel in Pascal//Delphi-Notation:  Substitution2

 

 

Beispielprogramm zu Permutation mit Hilfe eines Schlüsselwortes

In diesem Beispielprogramm wird die Kodierung mit dem Schlüsselwort "WAFFEN" durchgeführt.

 

Zugehörige Algorithmen und ein Programmierbeispiel in Pascal//Delphi-Notation:  Substitution3

 

Im Zusammenhang mit den bisher besprochenen Kryptosystemen sollten im Unterricht folgende Fragen diskutiert werden:

 

  • Die Schlüssel müssen geheim übertragen bzw. verteilt werden. 
  • Wurde ein Schlüssel dechiffriert, kann ein nichtberechtigter Nutzer Nachrichten lesen und gegebenenfalls recht einfach fälschen. 
  • Wenn n Personen das System nutzen wollen, so benötigt man  Schlüssel.
  • Wie ist die Periode zu wählen, damit optimale Sicherheit gewährleistet wird?
  • Wie kann ein Programm geschrieben werden, um Vigenere-Chiffren zu knacken?
  • Welche Punkte sollte man bei der Konstruktion eines solchen Systems beachten?
  • Welche Eigenschaften der deutschen Sprache können bei der Entschlüsselung helfen?
  • Was können Benutzer tun, um eine Dechiffrierung ihrer Nachrichten zu erschweren?

 

 

DES (Data Encryption Standard)

 

DES wurde 1977 vom National Bureau of Standards (NBS) in den USA genormt. Das Verfahren liefert eine Blockchiffrierung. Eine Folge von festen Tranpositionen und von schlüsselabhängigen, multipartiten, nichtlinearen Substitutionen sorgt für eine sehr gründliche Durchmischung. Der Schlüssel war ursprünglich 8 Byte lang, wovon noch 8 Paritätsbits abzuziehen sind. Die effektive Schlüssellänge ist also 56 Bit. Neuere Verfahren haben eine Schlüssellänge von 128 Bit.

 

Eine Skizze des Verfahrens

Im Detail kann man das Verfahren im Anhang aus Spektrum der Wissenschaft Januar 1989 nachlesen.

 

substitution_30

 

Am 18. Juni 1997 gelang es einer Gruppe von Internet-Aktivisten DES (256 Möglichkeiten) zu knacken. Tausende von Rechnern waren weltweit verbunden. Begonnen hat die Aktion am 18, Februar 1997.

Ein Pentium Rechner kann etwa 200.000 Schlüssel pro Sekunde testen.

Die Funktion f ist der zentrale Teil des Verfahrens:

 

substitution_40

 

weiter:  Asymmetrische Verschlüsselung

 

 
 
Thursday, 23. November 2017 / 00:47:20