© Teguh Jati Prasetyo/Shutterstock.com
Variationen der Caesar-Verschlüsselung, implementiert mit JavaScript

Der passende Schlüssel zur Verschlüsselung


Wir sind weiter auf der Suche nach einer „unknackbaren“ Verschlüsselungsmethode. Im letzten Teil haben wir die Caesar-Verschlüsselung vorgestellt, die auf der Basis zweier gegeneinander rotierter Alphabete arbeitet. Wir haben dann eine sehr einfache klassische Chiffriermaschine, die Chiffrierscheibe, mit JavaScript implementiert und festgestellt, dass das Verfahren auch ohne maschinelle Unterstützung mit wenig Aufwand durch einfaches Durchprobieren geknackt werden kann und daher hochgradig unsicher ist. In der Folge soll es nun darum gehen, die Ursache dieser Unsicherheit zu ermitteln und das Verfahren sicherer zu machen.

Warum ist die Caesar-Verschlüsselung so unsicher? Der Hauptgrund ist, dass die verschiedenen Geheimtextalphabete durch Rotation des normalen Alphabets gebildet werden. Das bewirkt, dass nur 25 mögliche Geheimalphabete existieren, sodass der Schlüsselraum sehr klein ist. Wie bereits im letzten Teil beschrieben, beträgt die Schlüssellänge lediglich 5 Bit, das ist sehr wenig.

Monoalphabetische Verschlüsselung oder warum Schlüssellänge nicht alles ist

Das Verfahren könnte sicherer gemacht werden, wenn nicht nur die Verschiebung, sondern auch das Geheimtextalphabet variiert werden könnte. Als Geheimtextalphabet könnte etwa "YUFBCDHEGIPKZLMANOQSTVJWRX" verwendet werden. Wir können unsere Implementierung der Chiffrierscheibe mit zwei Zeilen Code so anpassen, dass dieses Alphabet verwendet wird. Dazu definieren wir einfach eine Zeichenkette für das Geheimalphabet: let ciphered = "YUFBCDHEGIPKZLMANOQSTVJWRX";. Wir greifen bei der Erstellung des CharDiv-Elements für den Geheimbuchstaben statt auf das Ursprungsalphabet auf das Geheimalphabet in ciphered zu: <CharDiv theChar={ciphered[(i + theKey - 1) % 26]}. Listing 1 zeigt die Implementierung der CharDiv-Klasse mit den genannten Anpassungen.

Listing 1

class CharRings extends React.Component { render() { let {theKey,} = this.props; let charDivs = []; let chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; let ciphered = "YUFBCDHEGIPKZLMANOQSTVJWRX"; for (let i = 0; i < chars.length; i++) { let radian = (2 * Math.PI) / 26 * i + 0.5 * Math.PI; let deg = 360/26.0 * i; let transform = "rotate(" + deg + "deg)"; let r1 = 100; let x = 200 - (Math.cos(radian) * r1) - 8; let y = 240 - (Math.sin(radian) * r1) - 8; charDivs.push(<CharDiv theChar={chars[i]} x={x} y={y} transform={transform} /> ); let r2 = 140; let cipheredX = 200 - (Math.cos(radian) * r2) - 8; let cipheredY = 240 - (Math.sin(radian) * r2) - 8; charDivs.push( <CharDiv theChar={ciphered[(i + theKey - 1) % 26]} x={cipheredX} y={cipheredY} transform={transform} /> ); } ...

Abbildung 1 zeigt die angepasste Chiffrierscheibe; die beiden Alphabete sind in der dargestellten Stellung nicht gegeneinander verschoben. Wir können ablesen, dass mit dieser Stellung „CAESAR“ zu „DBEVBT“ verschlüsselt würde. Die Tatsache, dass ein Buchstabe durch die Verschlüsselung hier nicht geändert wurde, weil für den Buchstaben „E“ Klartext- und Geheimtextbuchstabe identisch sind, nützt dem Anwender wenig, da er das dem Geheimtext nicht ansehen kann.

schmidt_enigma_2_1.tif_fmt1.jpgAbb. 1: Chiffrierscheibe mit geändertem Geheimalphabet

Auch in der Grundstellung würde dieses Alphabet also bereits zur Verschlüsselung verwendet werden können. Damit erhöht sich die Anzahl der möglichen Stellungen auf 26. Nun gut, das ist lediglich eine weitere Stellung, die durchprobiert werden muss. Aber wie steht es mit dem Durchprobieren der möglichen Geheimtextalphabete? Dazu müssen wir uns überlegen, wie viele Möglichkeiten es gibt, die Buchstaben des Alphabets anzuordnen. In der Mathematik spricht man hier von Permutationen ohne Wiederholung [1]. Die Anzahl der möglichen Permutationen von n Elementen ohne Wiederholung kann dabei durch die Formel Anzahl Permutationen = fac(n) berechnet werden. Wie groß ist diese Zahl? Wir können die Fakultät mit ein paar Zeilen JavaScript rekursiv berechnen. Listing 2 berechnet die Fakultät von 26, gibt sie aus, multipliziert diese Zahl mit der Anzahl der möglichen Stellungen (26), gibt das Ergebnis als Dezimalzahl aus, wandelt diese dann in eine Binärzahl um und berechnet daraus die Schlüssellänge. Wir können dieses Programm jetzt mit node aufrufen:

node calculate_key_length.js Number of permutations: 4.0329146112660565e+26 Total number to check: 1.0485577989291747e+28 Key length in bit: 94

94 bit! Das klingt doch ziemlich sicher, oder? Ja, aber das Verfahren hat zwei Nachteile:

  • Caesar müsste nun neben der Rotation der Scheibe auch noch das Alphabet übermitteln. Er müsste statt 1 Buchstaben 27 Buchstaben als Code für den Empfänger versenden. Das ist erst einmal nicht so tragisch.

  • Genauso wie die vorherigen Verfahren ist dieses monoalphabetisch. Das bedeutet, dass jeder Klartextbuchstabe durchgängig immer mit demselben Geheimtextbuchstaben verschlüsselt wird.

Kann man eine entsprechende Verschlüsselung ohne Kenntnis des Schlüssels knacken? Die Chancen dafür stehen gut, wenn ein paar Voraussetzung gegeben sind:

  • Der Anwender kommt auf die Idee, dass er es mit einer monoalphabetischen Verschlüsselung zu tun hat.

  • Der Angreifer weiß, in welcher Sprache der Klartext verfasst wurde. Jede Sprache hat statistisch unterschiedliche Häufigkeiten für einzelne Buchstaben, im Deutschen etwa ist der Buchstabe „E“ der mit Abstand häufigste Buchstabe. Darüber hinaus hat jede Sprache Charakteristika, die verwendet werden können. Taucht in einem englischen Geheimtext etwa sehr oft ein Wort auf, das aus derselben Sequenz dreier Buchstaben besteht, ist die Wahrscheinlichkeit groß, dass es sich entweder um das Wort „THE“ oder das Wort „AND“ handelt.

  • Der Text ist hinreichend lang, damit die Verteilung der Buchstabenhäufigkeiten im Text sich der statistischen Verteilung annähert. Je kürzer der Text ist, desto größer die Abweichung. Besteht der Klartext etwa nur aus dem Wort „CAESAR“, wäre hier das A statt dem „E“ der häufigste Buchstabe.

Betrachten wir dazu einen Text, der mit einem unbekannten Geheimalphabet verschlüsselt wurde:

CWS LA JGTS RQH ILILFLW SGAA LA SLH FRMSL SLA DRLTA SLW ILRAD IGF SGAA SLA

DRLTA FRMS TLSLDL CWS HGEQDL SGAA GMML JLMEQL WREQD SLA DRLTA FRMS GWFLDLDLW

ILDPLDLD JCLTSLW CWS LA HGEQD SGAA SRL VMLRWLW CWS SRL ITPAALW SRL TLREQLW CWS

SRL GTHLW SRL NTLRLW CWS SRL VWLEQDL GMMLAGHD AREQ LRW HGMZLREQLW ILFLW GW RQTL

TLEQDL QGWS PSLT GW RQTL ADRTW SGAA WRLHGWS VGCNLW PSLT ULTVGCNLW VGWW LT QGFL

SLWW SGA HGMZLREQLW WGLHMREQ SLW WGHLW SLA DRLTA PSLT SRL ZGQM ALRWLA WGHLWA

QRLT RAD JLRAQLRD JLT ULTADGWS QGD SLT CLFLTMLIL SRL ZGQM SLA DRLTA SLWW LA RAD

LRWLA HLWAEQLW ZGQM CWS ALRWL ZGQM RAD ALEQAQCWSLTDALEQACWSALEQZRI

Zur Entschlüsselung machen wir uns die bekannte statistische Buchstabenhäufigkeit in deutschen Texten zunutze. Zunächst zählen wir von Hand oder maschinell die Häufigkeiten der enthaltenen Buchstaben und erhalten folgende Verteilung:

A: 47 (9 %)

C: 13 (3 %)

D: 26 (5 %)

E: 15 (3 %)

F: 9 (2 %)

G: 34 (7 %)

H: 13 (3 %)

I: 9 (2 %)

J: 5 (1 %)

L: 103 (20 %)

M: 17 (3 %)

N: 3 (1 %)

P: 5 (1 %)

Q: 28 (6 %)

R: 41 (8 %)

S: 46 (9 %)

T: 27 (5 %)

U: 2 (0 %)

V: 5 (1 %)

W: 52 (10 %)

Z: 7 (1 %)

Wie wir sehen, kommt der Buchstabe „L“ mit einer Häufigkeit von 20 Prozent mit Abstand am Häufigsten vor. Unter [2] befindet sich die Aufstellung der Buchstabenhäufigkeiten in deutschen Texten. Der häufigste Buchstabe ist dabei statistisch „E“ mit 17,4 Prozent. Die Wahrscheinlichkeit ist daher sehr groß, dass „L“ den Buchstaben „E“ repräsentiert. Zum Entschlüsseln reicht das wahrscheinlich noch nicht. Deswegen berechnen wir noch die Buchstabenhäufigkeit am Wortanfang:

A: 5 (5 %)

C: 8 (7 %)

D: 5 (5 %)

F: 3 (3 %)

G: 6 (6 %)

H: 5 (5 %)

I: 6 (6 %)

J: 5 (5 %)

L: 7 (7 %)

N: 1 (1 %)

P: 3 (3 %)

Q: 4 (4 %)

R: 6 (6 %)

S: 25 (23 %)

T: 3 (3 %)

U: 2 (2 %)

V: 4 (4 %)

W: 5 (5 %)

Z: 4 (4 %)

Mit 25 Ausprägungen ist „S“ der häufigste Anfangsbuchstabe. Laut der Aufstellung der Buchstabenhäufigkeit ist der häufigste Anfangsbuchstabe „D“, wir ersetzen also „S“ durch „D“. In gleicher Weise ermitteln wir, dass „W“ der häufigste Endbuchstabe ist, und daher wahrscheinlich dem Buchstaben „N“ entspricht. Das Einsetzen ergibt dann diesen Klartext:

_ND E_ ___D ___ _E_E_EN D___ E_ DE_ ___DE DE_ __E__ DE...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Teams

Für Firmen haben wir individuelle Teamlizenzen. Wir erstellen Ihnen gerne ein passendes Angebot.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang