Kryptographie

• Kryptographie, die Verschlüsselung von Information, war lange Zeit eine Sache
der Geheimdienste. Mit der Verbreitung des Internet wurde die Nutzung von
Kryptographie eine Sache von jedermann.

• Kryptographie ist die Wissenschaft der Verschlüsselung von Information durch

Geheimschriften bzw. Chiffren (griechisch: kryptós „verborgen“ und gráphein
„schreiben“). Dabei werden meist geheime Schlüssel benutzt.

• Die Kryptographie umfasst nicht nur die Anwendung, sondern auch die
Entwicklung von Verfahren mit Verschlüsselung.

• Daneben bezeichnet die Krypto-Analyse (auch: Kryptanalyse) sowohl die

Untersuchung von Verschlüsselungsverfahren auf ihre Resistenz gegenüber
Sicherheitsangriffen als auch das Herausfinden von geheimen Schlüsseln.

• Kryptoanalyse wird auch Brechen oder Knacken einer Verschlüsselung genannt.

Die Kryptographie bildet mit der Kryptoanalyse zusammen die Kryptologie.
 Die ältesten Chiffren

• Chiffren wurden bereits in Sparta (die Skytale) und dem alten Rom (Caesar-
Chiffre) benutzt. Gaius Julius Caesar (100 – 44 v.Chr.) hat die nach ihm benannte
Caesar-Chiffre zur geheimen Kommunikation für seine militärische
Korrespondenz verwendet.

• Heutzutage benutzte Verfahren der Kryptographie haben meist eine mathematische

Basis und sind meist standardisiert.

• Die Sicherheit der Verfahren beruht darauf, dass die Verfahren weltweit von
Kryptologen untersucht und eventuelle Schwächen öffentlich bekannt gemacht
werden.

• Falls neue Verfahren der Kryptographie erforderlich werden, hat es sich

neuerdings besonders bewährt, dass zur Entwicklung eines neuen Verfahrens
weltweit aufgerufen wird, die Vorschläge veröffentlicht werden und ihre Qualität
weltweit untersucht wird.
 Sicherheit der Kryptographie

• Die Sicherheit eines kryptographischen Verfahrens liegt also gerade nicht darin,
sich ein skurriles Verfahren auszudenken und dieses geheim zu halten, sondern
darin, dass die Menge der möglichen Schlüssel für ein Verfahren so groβ ist,
dass ein Angreifer sie nicht durchprobieren kann.

• Bei einer Schlüssellänge von z.B. 80 Bit gibt es insgesamt 2!" mögliche
Schlüssel. Wenn ein Angreifer je Sekunde eine Milliarde (10# ) Schlüssel
durchprobieren kann, dann benötigt er 2!" /10# sec ≈ 38 Millionen Jahre.

• Diese Aufgabe ist praktisch nicht durchführbar. Jede Verlӓngerung des

Schlüssels um 1 Bit verdoppelt den Aufwand für den Angreifer, d.h. bei 10 Bit
Verlӓngerung vergröβert sich der Aufwand für den Angreifer jeweils ca. um den
Faktor 1000.
 Symmetrische und asymmetrische Verfahren

• Historische Verfahren der Kryptographie sind symmetrisch, d.h. Sender und

Empfӓnger benutzen den gleichen Schlüssel für die Verschlüsselung und die
Entschlüsselung.

• In den 1970er Jahren wurden asymmetrische Verfahren der Kryptographie erfunden.

Sie benutzen ein Schlüsselpaar, das aus einem öffentlichen Schlüssel und einem
dazugehörigen privaten Schlüssel besteht. Der private Schlüssel ist geheim, nur sein
Besitzer hat Zugang zu ihm.

• Asymmetrische Verfahren der Kryptographie brachten — nach Jahrtausenden der

symmetrischen Kryptographie — völlig neue Möglichkeiten:

• Zum Verschlüsseln braucht kein geheimer Schlüssel mehr übertragen zu

werden. Der Sender benutzt dazu den öffentlich bekannten öffentlichen
Schlüssel des Empfängers.

• Asymmetrische Schlüssel erlauben digitale Signaturen bzw. digitale

Unterschriften. Dazu benutzt die unterschreibende Person ihren privaten
Schlüssel. Mit seinem öffentlichen Schlüssel kann jeder diese digitale Signatur
nachprüfen. Die digitale Signatur ist also verbindlich.
 Sicherheitsdienste

• Die Ziele, die man durch kryptographische Verfahren erreichen will, werden als
Sicherheitsdienste bezeichnet.

• Die Verbindlichkeit einer digitalen Signatur ist ein solches Ziel.

• Das bekannteste Ziel ist die Vertraulichkeit, d.h. nur ein bestimmter Adressat
kann eine verschlüsselte Botschaft lesen.

• Weitere Sicherheitsdienste sind Authentizität, Integrität, Anonymität und

Zugriffskontrolle.

• Sicherheitsdienste werden durch Sicherheits-Mechanismen bereitgestellt. Z.B.

bietet Verschlüsselung (ein Sicherheitsmechanismus) den Sicherheitsdienst der
Vertraulichkeit.

• Sicherheits- Mechanismen sind die prinzipiellen technischen Mittel, welche die

spezielle Wahl noch offen lassen, z.B. Caesar-Chiffre als Verschlüsselungs-
Algorithmus.
 Historische Verfahren

Im Lauf der Geschichte ist eine groβe Vielfalt von Verschlüsselungsverfahren

erdacht und benutzt worden. Hier werden nur einige der bekanntesten Vertreter
angesprochen;

Skytale

Die Skytale wurde seit ca. 500 v.Chr. in Sparta benutzt. Das Gerät für die
Verschlüsselung und Entschlüsselung ist ein Holzstab mit je gleichem Umfang.
Um diesen wird ein Band aus Pergament oder Leder gewickelt und die geheime
Botschaft in Längsrichtung des Stabes geschrieben. Im abgewickelten Zustand
zum Transport der Botschaft steht auf dem Band eine unsinnige Folge von
Buchstaben. Der Empfänger kann die Botschaft entschlüsseln, indem er das Band
auf seinem Stab mit dem gleichen Umfang wieder aufwickelt.
• Bei der Skytale handelt es sich um eine Transpositions-Chiffre. D.h. die Zeichen
selbst sind unverändert, sie befinden sich nur in anderen Positionen.

• Eine Transpositions-Chiffre lässt sich verallgemeinern, indem in der genannten

Matrix ihre Elemente zeilen- oder spaltenweise vertauscht werden. Diese
Permutation der Matrixelemente ist dann der Schlüssel.

• Ein Angreifer kann bei einer Transpositions-Chiffre versuchen, aus dem Vorrat
der Zeichen der verschlüsselten Botschaft vermutete Wörter zu bilden und sie in
eine sinnvolle Reihenfolge zu bringen.

• Ein Angriff kann beliebig erschwert werden, wenn die Matrix genügend groß
gewählt wird.

• Bei einer Transpositions-Chiffre kann die Häufigkeitsverteilung der Zeichen

nicht für einen Angriff genutzt werden, wie dies bei der Caesar-Chiffre der Fall
ist, denn die Häufigkeit der Zeichen entspricht genau der des ursprünglichen
Klartextes (und damit der der verwendeten Sprache), da nur die Reihenfolge des
Zeichen vertauscht wurde.
 Caesar-Chiffre

• Die Caesar-Chiffre arbeitet zeichenweise, wobei jeder Buchstabe durch den

drittnächsten Buchstaben im Alphabet ersetzt wird.

• Ein Klartext-Buchstabe „a“ wird beim Verschlüsseln durch einen Chiffretext-

Buchstaben „D“ ersetzt, ein Klartext „b“ durch ein Chiffre-Text „E“ usw. In
Tabelle steht unter jedem der 26 Klartext-Buchstaben der zugehörige
Chiffretext- Buchstabe. In der unteren Zeile sind die Chiffretext-Buchstaben
gegenüber der oberen Zeile um 3 Positionen zyklisch nach links verschoben,
d.h. auf „Z“ folgen „A“, „B“ und „C“.
• Beim Entschlüsseln wird die Tabelle in umgekehrter Weise benutzt, d.h. Ein
Chiffretext- Buchstabe wird durch den darüber stehenden Klartext-Buchstaben
ersetzt.

• Für Klartext bzw. Chiffretext wird Klein- bzw. Großschreibung benutzt. Dies ist
für die Verschlüsselung unerheblich und dient nur der leichten Unterscheidung.

• Alternativ zu Tabelle kann die Caesar-Chiffre durch Chiffrier-Scheiben

mechanisiert werden. Die 26 Buchstaben stehen zyklisch in 26 Sektoren. Die
zwei Scheiben für Input und Output sind um 3 Buchstabenpositionen
gegeneinander verdreht und fixiert. Auf der Input-Scheibe sind außen zusӓtzlich
Nummern den Buchstaben zugeordnet.
• Die Caesar-Chiffre wird entsprechend der Verschiebung der Scheiben als
Verschiebe-Chiffre- (displacement cipher) sowie als monoalphabetische
Substitutions-Chiffre bezeichnet: Es wird ein Klartext-Buchstabe durch einen
Chiffretext-Buchstaben ersetzt bzw. „substituiert“. Dabei wird eine einzige
Alphabet-Zuordnungsliste benutzt („monoalphabetisch“).
Verallgemeinerung der Caesar-Chiffre

• Die Caesar-Chiffre kann verallgemeinert werden, indem statt einer fest

eingebauten Verschiebung um 3 Buchstaben jeder Wert aus [0, 25] als Verschiebe-
Schlüssel k gewӓhlt wird.

• Zur formalen Beschreibung einer allgemeinen Verschiebung k ist es zweckmӓßig,

den Buchstaben eine Buchstaben-Nummer zuzuordnen:

• Durch die Modulo-Bildung (mod 26), wird der ganzzahlige Rest bei Division
durch 26 gebildet, oder alternativ, das Ergebnis durch „+26“ oder „26“ in den
Bereich [0,25] gebracht. Anschaulich gesprochen sorgt die Modulo-Bildung für
die zyklische Zuordnung, wie sie von der Chiffrier-Scheibe direkt realisiert wird.
• (Beispiele: Verschlüsselung von „y“: „y“+“k“=24+3=27≡1=“B“ (mod 26);
Entschlüsselung von „C“: „C“-“k“=2-3=1 ≡ 25=“z“ (mod 26). Das Zeichen „ ≡“
wird als Kongruenz bezeichnet. Sie bedeutet eine Gleichheit in einem Zyklus
mit n=26 Werten. Die Nummerierung der Buchstaben mit [0, 25] statt mit [1,
26]) vereinfacht die formale Darstellung.
Kryptoanalyse der Caesar-Chiffre

• Eine Verschiebe-Chiffre ist aus heutiger Sicht sehr einfach zu brechen. Sie hat
ihren Dienst erfüllt, als zu Zeiten Caesars die meisten Menschen Analphabeten
waren.

• Eine Verschiebe-Chiffre kann gebrochen werden, indem der Angreifer die 26

Möglichkeiten für den Schlüssel k durchprobiert, bis ein sinnvoller Klartext
erscheint. Noch schneller geht es, wenn man von den unterschiedlichen
Hӓufigkeiten der Buchstaben in einem natürlich sprachlichen Text Gebrauch
macht.

• In der deutschen Sprache tritt der Buchstabe „e“ mit 17,4 % auf gegenüber einer
mittleren Hӓufigkeit für alle Buchstaben von 1/26 = 3,8 %. (In der englischen
Sprache hat „e“ die Hӓufigkeit von 12,7 %).

• Bei einer Verschiebe-Chiffre braucht ein Angreifer nur den hӓufigsten

Buchstaben im Klartext ermitteln. Der Abstand zwischen dem Buchstaben „e“
und dem hӓufigsten Buchstaben im Chiffretext ergibt mit hoher Sicherheit den
Schlüssel k.
Ein Beispiel für die Hӓufigkeit der Buchstaben, die für eine natürliche Sprache
charakteris:sch ist, findet sich in Abbildung unten. Das Histogramm wurde
gewonnen aus einem Text in deutscher Sprache, der mit dem Werkzeug CrypTool
analysiert wurde.
 Vigenére-Chiffre

• Die Vigenére-Chiffre ist eine Verallgemeinerung der Caesar-Chiffre, wobei staJ

eines Schlüssels k eine Folge von Schlüsseln k: 𝑘$ , 𝑘% , ... 𝑘& periodisch benutzt
wird.

• Bei einer Periode von z.B. r=5 lautet die Schlüsselfolge k: 𝑘$ 𝑘% 𝑘' 𝑘( 𝑘) | 𝑘$ 𝑘%
𝑘' 𝑘( 𝑘) | 𝑘$ 𝑘% 𝑘' 𝑘( 𝑘) | ... | ... . Der 1. Buchstabe des Klartextes wird mit 𝑘$ ,
der zweite Buchstabe mit 𝑘% usw. verschlüsselt.

• Die Vigenére-Chiffre ist, wie die Caesar-Chiffre, eine Verschiebe-Chiffre

(displacement cipher), denn Klartextbuchstabe und Chiffretextbuchstabe sind
um 𝑘* Buchstaben im Alphabet zyklisch verschoben.

• Darüber hinaus ist die Vigenére-Chiffreine polyalphabe:sche Subs:tu:on,

denn es gibt, entsprechend den Werten der Schlüssel 𝑘* , 26 verschiedene
Alphabet-Zuordnungslisten.
• Neben der Chiffrier-Scheibe und der Formel ist als HilfsmiJel für die
Verschlüsselung und Entschlüsselung das sog. Vigenére-Quadrat bekannt. Es
ist eine Verallgemeinerung der Tabelle für die Caesar-Chiffre, wobei staJ der
2. Zeile in Caesar-Chiffre Tabelle wo alle 26 Möglichkeiten der Verschiebungen
aufgelistet sind.

• In dem Vigenére-Quadrat enthӓlt die linke Spalte die Schlüssel, die oberste
Zeile die Klartextbuchstaben und der Kreuzungspunkt den
Chiffretextbuchstaben.

• Beispiel: Schlüssel 𝑘* =13=n, Klartextbuchstabe 𝐵+ =“e“, Chiffretextbuchstabe

𝐵, =“R“.
 Vigenére-Quadrat

Links: der Schlüssel 𝑘* , oben: der Klartexbuchstabe, im Kreuzungspunkt: der

Chiffretextbuchstabe. Der Chiffretext ist durch Großbuchstaben dargestellt.
• Auf den Klartext (hier „this is...“) wird eine Folge von Schlüsseln (hier „cxg go...“)
angewendet. Der verschlüsselte Text (hier „VENC OG...“) wird auf der
Empfӓngerseite mit der gleichen Schlüsselfolge („cxg go...“) wieder korrekt
entschlüsselt.

• Das Blockschaltbild ist im Prinzip eine bildliche Darstellung, wobei als Schlüssel k
eine Folge k: 𝑘$ 𝑘% 𝑘' 𝑘( ... von Schlüsseln benutzt wird. Für die Verschlüsselung
und Entschlüsselung muss die Schlüsselfolge nicht nur gleich, sondern auch
synchron zu Klar- und Chiffretext sein.

• In dem Beispiel sind die Leerzeichen in dem Chiffretext zwischen den Wörtern zu
erkennen. Man kann dies vermeiden, indem entweder die Leerzeichen
weggelassen werden oder indem man das Leerzeichen als 27. Buchstaben
auffasst und die Opera:onen modulo 27 durchführt.
 Angriff auf die Vigenère-Chiffre

• Für einen Angriff auf die Vigenère-Chiffre sind die von der Caesar-Chiffre
bekannten Methoden nicht direkt anwendbar. Bei einem Durchprobieren aller
Schlüssel sind bei der Vigenère-Chiffre nicht nur die 26 Möglichkeiten von 𝑘$ ,
sondern 26& Möglichkeiten für eine Schlüsselperiode zu prüfen. Wenn die
Schlüsselperiode r genügend groß gewählt wurde, ist diese Aufgabe prak:sch
nicht durchführbar.

• Auch ist eine Häufigkeitsanalyse der Buchstaben im Chiffretext nicht direkt

anwendbar. Denn bei den unterschiedlichen Teilschlüsseln 𝑘* (i=1...r) der
Schlüsselfolge k: 𝑘$ 𝑘% 𝑘' 𝑘( 𝑘) ... 𝑘& vermischen sich die charakteris:schen
Häufigkeiten im Chiffretext und ein Rückschluss auf einen bes:mmten
Teilschlüssel 𝑘* ist nicht möglich.

• Ein erfolgreicher Angriff kann gefahren werden, wenn die Schlüsselperiode r

bekannt ist. Für die Buchstabenposi:onen i-j.r (i=1...r, j=0, 1, 2, ...), d.h. die
Posi:onen, die zueinander den Abstand der Schlüsselperiode r haben, wurde
für die Verschlüsselung jeweils der gleiche Teilschlüssel 𝑘* verwendet.
 Vernam-Chiffre

• Gilbert S. Vernam (1890-1960) arbeitete als Ingenieur bei AT&T (Bell Labs)
und erfand 1917 die nach ihm benannte Chiffre. Sie kann als Spezialisierung
/ Erweiterung der Vigenère-Chiffre angesehen werden:

• Die Spezialisierung betrir das Alphabet, das nicht mehr mit 26 Buchstaben,
sondern mit nur 2 Buchstaben {0, 1} arbeitet. Aus heu:ger Sicht ist uns die
binӓre Arbeitsweise vertraut. Die Erweiterung betrir die Schlüsselfolge, die
ebenso lang ist wie die Nachricht und nur ein einziges Mal verwendet
werden darf (one-:me pad). Die polyalphabe:sche Subs:tu:on der Vernam-
Chiffre wird auch als Strom-Chiffre bezeichnet.

Die Folge der Schlüssel ist zufallsmӓßig gewӓhlt, sie ist bei Sender und Empfӓnger gleich,
und sie wird nur ein einziges Mal benutzt.
• StaJ modulo 26 wird hier die Addi:on und Subtrak:on, den 2 Buchstaben {0, 1}
entsprechend, modulo 2 ausgeführt. Die Addi:on mod 2 ist iden:sch der
bitweisen XORVerknüpfung. Addi:on und Subtrak:on modulo 2 sind iden:sch
und müssen nicht unterschieden werden.

• Die Schlüsselfolge wird zufallsmӓßig und gleich verteilt gewӓhlt, d.h. jede
Binӓßrstelle der Schlüsselfolge wird gewürfelt. Die Werte „0“ und „1“ sollen die
gleiche Wahrscheinlichkeit von 1/2 haben.

• Die Schlüsselfolge muss als Geheimnis vor ihrer Benutzung auf einem
vertraulichen Wege zu Sender und Empfӓnger übertragen werden.
• Die Vernam-Chiffre liefert perfekte Sicherheit: Ein Wert „1“ im Chiffretext
kann entstanden sein durch eine „0“ im Klartext und eine „1“ in der
Schlüsselfolge oder durch eine „1“ im Klartext und eine „0“ in der
Schlüsselfolge. In der Schlüsselfolge haben die Werte „1“ und „0“ die gleiche
Wahrscheinlichkeit, und somit haben im Klartext die Werte „0“ und „1“ für
einen Angreifer die gleiche Wahrscheinlichkeit.

• Die Schlüsselfolge darf nur ein einziges Mal verwendet werden. Andernfalls
könnte ein Angreifer Schlüsselfolgen ausprobieren. Wenn sich für
verschiedene Chiffretexte, die mit der gleichen Schlüsselfolge erzeugt
wurden, jeweils sinnvolle Texte ergeben, dann war die angenommene
Schlüsselfolge offenbar die rich:ge.
 Enigma

• Die Enigma (griechisch: „Rӓtsel“) ist eine Chiffrier-Maschine, die im 2.

Weltkrieg (1939-1945) von der deutschen Wehrmacht benutzt wurde. Sie
gehört zu dem Typ der Rotor-Maschinen und entspricht technologisch einer
elektrischen Schreibmaschine.

• Technisch enthӓlt eine Rotor-Maschine mehrere Rotorscheiben R1, R2, R3 und

eine Umkehrscheibe U. Die Rotorscheiben sind links und rechts jeweils mit 26
Kontakten versehen. Je ein linker Kontakt ist mit je einem rechten Kontakt
elektrisch verbunden, wobei das Verbindungsschema einer Zufalls-ӓhnlichen
Permuta:on entspricht. Die Rotorscheiben sind drehbar gelagert und können
26 Drehposi:onen einnehmen. Die Umkehrscheibe U steht fest. Sie hat nur auf
der rechten Seite Kontakte, die paarweise ebenfalls Zufalls- ӓhnlich verbunden
sind.
• In Abbildung ist dargestellt, wie ein Buchstabe „e“ des Klartextes in einen
Buchstaben „M“ für den Chiffretext verschlüsselt wird. Die Verschlüsselung
wird manuell durchgeführt, d.h. in dem dargestellten Beispiel wird die Taste „e“
gedrückt und für „M“ leuchtet ein Lӓmpchen auf, was dann abgelesen werden
muss.

• Verschlüsselung und Entschlüsselung sind symmetrisch. Wenn man für die

Entschlüsselung die Taste „m“ drückt, werden die Leitungen und Kontakte in
umgekehrter Richtung durchlaufen und es erscheint wieder „E“ als
Klartextbuchstabe.
Bei jedem Betӓ:gen einer Eingabetaste wird die Rotorscheibe R1 um 1/26 einer
Umdrehung weitergedreht. Nach 26 Eingaben, d.h. nach einer vollen Umdrehung von
R1 wird wie bei einem Übertrag die nӓchste Rotorscheibe R2 um 1/26 Umdrehung
weitergestellt. Entsprechendes gilt für R2 und R3.

Mit jedem Weiterstellen der Rotorscheiben wird ein anderes Zuordnungsschema

zwischen den linken und den rechten Kontakten einer Rotorscheibe wirksam.
Dadurch verӓndert sich die Zuordnung zwischen Eingabe und Ausgabe. Bei 3
Rotorscheiben können diese 26' verschiedene Rota:ons-Zustӓnde einnehmen. Für
jeden Zustand gilt eine unterschiedliche Zuordnung zwischen Eingabe und Ausgabe.

Nach jeder Verschlüsselung eines Buchstabens ӓndert sich die Stellung der
Rotorscheiben und damit die Zuordnung für das Ersetzen der Buchstaben. Als
Verschlüsselung ergibt sich eine polyalphabe:sche Subs:tu:on. Die Folge der
Alphabet-Zuordnungslisten hat eine Periode von 26' . Übertragene Botschazen sind
kurz gegenüber dieser Periode.