Kryptanalyse
- Einleitung
- Häufigkeitsanalyse (Character Entropie)
- Brute Force Attack
- Ciphertext Only Attack
- Known Plaintext Attack
- Chosen Plaintext Attack
- Adaptive Chosen Plaintext Attack
- Chosen Cyphertext Attack
- Links
Einleitung
Die Kryptanalyse befasst sich damit, entweder aus einem Chiffretext den Klartext
wiederherzustellen oder den Schüssel zu ermitteln.
Beides führt dazu, dass es dem Angreifer möglich ist verschlüsselte Nachrichten zu
lesen und im zweiten Fall auch zu schreiben (u.U. auch im ersten).
Es werden hier nur die gebräuchlichsten Verfahren dargestellt.
Weggelassen wurden z.B. Chosen Key Attack und Chosen Text Attack, die allerdings
entweder ungebräuchlich oder eine Kombination aus den hier vorgestellten Verfahren
sind.
Häufigkeitsanalyse - Redundanzen - Character Entropie
Durch Häufigkeitsanalyse vom Gemeintext lassen sich besonders bei den substitutions
Chiffren gute Ergebnisse für die Entschlüsselung ohne Rechner erziehlen. Bei der
Häufigkeitsanalyse wird einfach die Anzahl der einzelnen Zeichen aufsummiert. Im
deutschen ist z.B. bekannt, dass der Buchstabe 'e' eine Häufigkeit von 17,48%
aufweist. Wenn bei der Häufigkeitsanalyse eines Cäsar-Chiffre ein Buchstabe auch
mit etwa 17% auftritt, dann hat man prinzipiell schon den Schlüssel gefunden und
kann die Nachricht entschlüsseln.
Buchstabenhäufigkeiten der deutschen und englischen Sprache (Monogramme) in %:
| Zeichen: |
a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
| deutsch |
6.47 |
1.93 |
2.68 |
4.83 |
17.48 |
1.65 |
3.06 |
4.23 |
7.73 |
0.27 |
1.46 |
3.49 |
2.58 |
| englisch |
8.04 |
1.54 |
3.06 |
3.99 |
12.51 |
2.30 |
1.96 |
5.49 |
7.26 |
0.16 |
0.67 |
4.14 |
2.53 |
| Zeichen: |
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
| deutsch |
9.84 |
2.98 |
0.96 |
0.02 |
7.54 |
6.83 |
6.13 |
4.17 |
0.94 |
1.48 |
0.04 |
0.08 |
1.14 |
| englisch |
7.09 |
7.60 |
2.00 |
0.11 |
6.12 |
6.54 |
9.25 |
2.71 |
0.99 |
1.92 |
0.19 |
1.73 |
0.09 |
Shift-Chiffre, wo nur jeweils ein Zeichen substituiert wird, lassen sich also sehr
einfach durch Analyse der Monogramme der entsprechenden Sprache brechen, bei der
polygraphischen substitutions Chiffrierung (z.B. Playfair) werden jedoch die Monogramme
relativ gut "verschleiert", dort wird der Gemeintext auf andere Redundanzen geprüft, z.B.
auf Bi- und Trigramme. Das Prinzip ist das gleiche wie bei den Monogrammen, nur sind
die Tabellen entsprechend größer:
Bi- und Trigramme der deutschen Sprache in %%:
er 409
en 400
ch 242
de 227
ei 193
nd 187
te 185
in 168
ie 163
|
ge 147
es 140
ne 122
un 119
st 116
re 112
he 102
an 102
be 101
|
|
ein 122
ich 111
nde 89
die 87
und 87
der 86
che 75
end 75
gen 71
|
sch 66
cht 61
den 57
ine 53
nge 52
nun 48
ung 48
das 47
hen 47
|
ind 46
enw 45
ens 44
ies 44
ste 44
ten 44
ere 43
lic 42
ach 41
|
sse 39
aus 36
ers 36
ebe 35
erd 33
enu 33
nen 32
rau 32
ist 31
|
nic 31
sen 31
ene 30
nda 30
ter 30
ass 29
ena 29
ver 29
wir 29
| |
Für weitere Informationen über einfache Kryptanalyse siehe [1], insb. für ausführliche
Listen von Mono- Bi- Tri- Tetragrammen der englischen Sprache die Dateien appX.pdf.
Brute Force Attack
Beim Brute Force Angriff werden sämtliche mögliche Schüssel durchprobiert und es wird
verglichen ob ein sinnvoller Plaintext bei der Entschlüsselung entsteht.
Ein Algorithmus gilt als sicher wenn diese Methode die einzige ist um an den Schüssel
zu kommen.
Bei einem Schlüssel der Länge von 8 Bit gibt es 2^8 oder 256 mögliche Schüssel, dies ist
selbst ohne Computer einfach zu knacken.
Heutzutage sind Schlüssellängen von 64 Bit nicht mehr sicher und werden von einigen Rechnern
in wenigen Stunden geknackt. Um wirklich sicher zu sein, sollten es daher 128 Bit sein.
128 Bit sind selbst von den bekannten Geheimdiensten nicht zu knacken, Voraussetzung ist
natürlich, dass der verwendete Algorithmus sicher ist.
Ciphertext Only Attack
Bekannt sind mehrere verschlüsselte Nachrichten, die mit demselben Verschlüsselungs-
algorithmus chiffriert wurden.
Die Aufgabe des Kryptanalytiker ist es nun möglichst viele Klartexte zu entschlüsseln
oder den Schüssel, der zur Verschlüsselung benutzt wurde, abzuleiten, um dann die
Möglichkeit zu haben beliebige Nachrichten zu entschlüsseln.
Known Plaintext Attack
Es sind sowohl Chiffretext also auch Klartext mehrerer Nachrichten bekannt. Die
Aufgabe des Kryptanalytikers ist es nun, den zugehörigen Schlüssel herauszufinden
oder einen äquivalenten Algorithmus zu entwickeln, der die Nachrichten genau wie
der eingesetzte Verschlüsselungsalgorithmus ver- und entschlüsselt.
Chosen Plaintext Attack
Hier kann der Kryptanalytiker nun selber die zu verschlüsselnden Klartexte auswählen.
Zusätzlich zu den Möglichkeiten des Known Plaintext Angriffes ist es jetzt also
möglich gezielt Klartextblöcke zur verschlüsselung auszuwählen, die u.U. zu mehr
Informationen über den Schlüssel führen.
Die Aufgaben des Kryptanalytikers sind die gleichen wie beim Known Plaintext Angriff.
Adaptive Chosen Plaintext Attack
Dies ist ein Sonderfall des Chosen Plaintext Angriffes. Beim Chosen Plaintext Angriff
ist es nur möglich einen großen Block Klartext zu verwenden, es ist jedoch nicht möglich
diesen zu verkleinern bzw. zu variieren. Hier dagegen ist es möglich einen kleineren Block
zu nehmen, den zu verschlüsseln und dann darauf aufbauend einen zweiten Block auszuwählen.
Der Unterschied besteht also darin, dass es hier möglich ist die Auswahl des Klartextes
besser zu variieren, indem vorhergehende Verschlüsselungen berücksichtigt werden.
Chosen Cyphertext Attack
Hier hat der Kryptanalytiker die Möglichkeit selber Chiffretexte zu entschlüsseln, jedoch
kann er im Gegensatz zu dem Chosen Plaintext Angriffe keinen Text selber verschlüsseln.
Zum Beispiel wäre eine sichere Machine denkbar, die Chiffretexte enschlüsselt aber nicht
verschüsselt.
Die Aufgabe besteht nun darin den Schlüssel herauszufinden, damit es auch möglich ist zu
entschlüsseln.
Diese Methode wird meist gegen asymmetrische Algorithmen (RSA, Public-Key Verfahren) einge-
setzt. Sie kann jedoch auch in Kombination mit den anderen Angriffen gegen symmetrische
Algorithmen erfolgreich eingesetzt werden.
Links
[1] Basic Cryptoanalysis
|
