kopf
brlogo
fensterobenrechts
   
   
fensteruntenblau
   
 

 

Grundlagen der Kryptologie

 

2. Zyklische Permutationen (Cäsarverschlüsselung)

 

Die einfache Substitution (die Reihenfolge der Zeichen wird nicht verändert, sondern es werden diese Zeichen durch andere Zeichen ersetzt) von Zeichen eines Textes V, durch ein Zeichen des Geheimtextes der Menge W, lässt sich folgendermaßen formulieren:

 

krypto2.gif (1135 Byte)

 

Für eine eindeutige Entschlüsselung muss die Abbildung umkehrbar eindeutig sein, also |V| = |W|. Einfache und zur Einführung Geeignete Spezialfälle sind die Permutationen auf einem Alphabet.

 

Zyklische Permutationen (Cäsarverschlüsselung)

 

V sei das deutsche Alphabet. V = {A,B, ...,Z,Ä,Ö,Ü,ß}

Ein Text, der mit der folgenden Permutation

krypto3.gif (1182 Byte)

verschlüsselt wurde, lässt sich folgendermaßen wieder entschlüsseln:

krypto4.gif (1265 Byte)

Eine derartige Verschlüsselung lässt sich mittels einer kreisförmigen Zuordnungstabelle veranschaulichen (jeder Buchstabe wird durch den s-ten Nachfolger im Alphabet ersetzt, für s = 3 ergibt sich aus ALBIN BUHL: DOELQ EXKO.

Statt W = V zu wählen, kann man auch den ASCII-Zeichensatz verwenden. In diesem Fall sollte man die Umlaute und ß entsprechend umsetzen. Die entsprechenden Algorithmen sind recht einfach.

Im Unterricht sollte man in diesem Zusammenhang folgende Punkte erarbeiten:

  

  • Eine Verschlüsselung muss ohne Zwischenräume und Satzzeichen durchgeführt werden.
  • Eine zweifache Substitution entspricht einer einfachen Substitution.
  • Die Kenntnis eines einzigen Buchstabens genügt zur Decodierung.
  • Ein genügend langer Text (ca. 1000 Buchstaben) lässt sich über die Häufigkeit, mit der die Buchstaben auftreten, entschlüsseln.

  

Den letzten Punkt kann man teilweise dadurch kompensieren, wenn häufig auftretenden Zeichen, wie Vokalen mehrere Zeichen des Geheimalphabets zugeordnet werden. Hier bieten sich umfangreiche Experimentiermöglichkeiten für den Unterricht, so dass auch schwächere Schüler zu Ergebnissen kommen können.

 

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

 

An dieser Stelle kann man im Unterricht noch weiter experimentieren, wenn man ein Programm zur Verfügung stellt oder mit den Schülern entwickelt, mit dem sie weiter experimentieren können:

Eingabe eines Schlüssels

Eingabe anderer Verschlüsselungsalphabete

Derartig verschlüsselte Texte kann man auch durch eine Ermittlung der relativen Häufigkeiten entschlüsseln. Voraussetzung ist eine hinreichende Länge des Geheimtextes. Solche relative Häufigkeiten sind in [2] S 46. ff zusammengestellt. Einige Häufigkeiten sind auf der folgenden Seite aufgeführt. Unter Umständen kann man solche Tabellen im Unterricht auch selbst erstellen, um auf die Problematik der relativen Häufigkeiten aufmerksam zu werden. Bei kurzen Texten ergeben sich große Unterschiede.

 

Monoalphabetische Chiffrierungen

 

Eine Chiffrierung heißt monoalphabetisch, falls jeder Buchstabe des Alphabets stets zu demselben (Geheimtext-) Buchstaben chiffriert wird. Eine monoalphabetische Chiffrierung kann man immer so darstellen, dass man ein "Geheimtextalphabet" (ASCII, bel. andere Alphabete) unter das Klartextalphabet schreibt.

Damit ergeben sich für das obige gewählte Alphabet mit 30 Zeichen 30 Fakultät monoalphabetische Chiffrierungen.

Wie die obigen Überlegungen zeigen, sind diese Chiffrierungen bei weitem nicht so sicher, wie die große Zahl von Möglichkeiten andeutet.

Analyse:

  

  1. Häufigkeit der Buchstaben ermitteln. Dadurch kann man die entsprechenden Buchstaben von e usw. ermitteln
  2. Paare aufeinanderfolgenden Buchstaben ermitteln
  3. Der Computer kann die erkannten Buchstaben im Text ersetzen

  

Verschleierung der Häufigkeiten

Bei einer Chiffrierung kann man die Häufigkeiten der Buchstaben durch eine einfache Zuordnung verschleiern.

Man ordnet jedem Buchstaben eine Menge von Zeichen oder Zahlen entsprechend der Häufigkeit zu.

 

A

10, 21, 52, 59, 71

B

20, 34

C

26, 06, 80

D

19, 58, 70, 81, 87

E

09, 18, 29, 33, 38, 40, 42, 54, 55

F

00, 41

G

08, 12, 97

H

01, 07, 24

I

 

J

 

 

Beim Chiffrieren ordnet man jedem Buchstaben zufällig ein Zeichen aus diesem Bereich zu.

Der Empfänger der Nachricht kann den Text mit der obigen Tabelle dechiffrieren.

Es ist jetzt wesentlich schwieriger den Code zu dechiffrieren. Die Analyse dieser Methode basiert auf der Beobachtung, dass zwar die Häufigkeiten der Geheimtextzeichen gleich sind, aber aus der Betrachtung von Paaren von Geheimtextzeichen Informationen gewinnen kann.

 

Wahrscheinlichkeiten für das Auftreten der Buchstaben in der deutschen Sprache

 

Buchstabe

p(b)

Buchstabe

p(b)

A

0,0433

P

0,0050

B

0,0160

Q

0,0001

C

0,0267

R

0,0686

D

0,0439

S

0,0539

E

0,1470

T

0,0473

F

0,0136

U

0,0319

G

0,0267

V

0,0074

H

0,0436

W

0,0142

I

0,0638

X

0,0001

J

0,0016

Y

0,0002

K

0,0096

Z

0,0142

L

0,0293

Ä

0,0049

M

0,0213

Ö

0,0025

N

0,0884

Ü

0,0058

O

0,0136

Leerz, *

0,1515

 

Einige Häufigkeiten aus zwei Buchstabenkombinationen

 

EN

0,0447

GE

0,0168

BE

0,0096

NA

0,0069

ER

0,0340

ST

0,0124

SS

0,0094

RA

0,0069

CH

0,0280

IC

0,0119

NS

0,0093

EL

0,0068

ND

0,0258

HE

0,0117

AN

0,0092

WI

0,0068

EI

0,0226

NE

0,0117

SI

0,0083

HT

0,0067

IN

0,0214

SE

0,0117

UE

0,0082

SC

0,0066

ES

0,0204

NG

0,0107

DA

0,0081

WE

0,0065

TE

0,0181

RE

0,0107

AS

0,0078

HA

0,0064

IE

0,0178

AU

0,0104

NI

0,0070

IS

0,0064

UN

0,0176

DI

0,0102

AE

0,0069

LI

0,0064

 

Einige Häufigkeiten aus drei Buchstabenkombinationen

 

EIN

0,0122

DER

0,0086

CHT

0,0061

UNG

0,0048

ICH

0,0111

CHE

0,0075

DEN

0,0057

DAS

0,0047

NDE

0,0089

END

0,0075

INE

0,0053

HEN

0,0047

DIE

0,0087

GEN

0,0071

NGE

0,0052

IND

0,0046

UND

0,0087

SCH

0,0066

NUN

0,0048

ENW

0,0045

 

weiter:  Verallgemeinerung

 

 
 
Saturday, 18. November 2017 / 03:45:16