Kryptoanalyse: Unterschied zwischen den Versionen
Thomas (Diskussion | Beiträge) |
Keine Bearbeitungszusammenfassung |
||
| (Eine dazwischenliegende Version von einem anderen Benutzer wird nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
Wie sicher ein Verschlüsselungsverfahren ist, zeigt sich erst, wenn jemand ernsthaft versucht, es zu brechen. Genau das untersucht die Kryptoanalyse. | |||
==Definition== | |||
Die '''Kryptoanalyse''' ist die Lehre von den Methoden, mit denen man aus einem Geheimtext ohne Kenntnis des Schlüssels den Klartext oder den Schlüssel gewinnt. Zusammen mit der [[Kryptographie]] bildet sie die Kryptologie. | |||
Ein Angriff geht nach dem [[Kryptographie#Prinzip von Kerckhoffs|Prinzip von Kerckhoffs]] davon aus, dass der Angreifer das Verfahren kennt. Geheim ist nur der Schlüssel. Angriffe unterscheiden sich darin, was der Angreifer außerdem weiß: | |||
Ein | * '''nur den Geheimtext''' (englisch: ciphertext-only): Der Angreifer hat lediglich mitgelesen. | ||
* '''Klartext und Geheimtext''' (englisch: known-plaintext): Der Angreifer kennt zu einem Teil des Geheimtextes den Klartext. | |||
==Schlüsselraum== | |||
Der '''Schlüsselraum''' ist die Menge aller Schlüssel, die bei einem Verfahren möglich sind. Seine Größe ist die Anzahl dieser Schlüssel. | |||
* Besteht der Schlüssel aus <math>b</math> Bit, enthält der Schlüsselraum <math>2^b</math> Schlüssel. | |||
* Besteht der Schlüssel aus <math>l</math> Buchstaben, enthält der Schlüsselraum <math>26^l</math> Schlüssel. | |||
Ein großer Schlüsselraum ist notwendig, damit ein Verfahren sicher ist. Er reicht allein aber nicht aus: Die [[Monoalphabetische Substitution|monoalphabetische Substitution]] hat einen riesigen Schlüsselraum und wird trotzdem mit der [[Häufigkeitsanalyse]] in kurzer Zeit gebrochen. | |||
==Brute-Force-Angriff== | |||
Bei einem '''Brute-Force-Angriff''' (englisch für „rohe Gewalt“) probiert der Angreifer alle Schlüssel des Schlüsselraums der Reihe nach aus, bis ein sinnvoller Klartext entsteht. Mit genug Zeit gelingt der Angriff bei fast jedem Verfahren. Im ungünstigsten Fall muss der Angreifer alle Schlüssel prüfen, im Durchschnitt die Hälfte. Die Ausnahme ist das [[One-Time-Pad]]: Dort liefert das Durchprobieren jeden denkbaren Klartext und damit keine Information. | |||
Schutz bietet nur ein Schlüsselraum, der so groß ist, dass das Durchprobieren auch mit den schnellsten Rechnern viel zu lange dauert. | |||
== | ==Known-Plaintext-Angriff== | ||
Bei einem '''Known-Plaintext-Angriff''' kennt der Angreifer zu einem Stück Geheimtext den zugehörigen Klartext, zum Beispiel eine Anrede oder einen festen Dateianfang. Daraus berechnet er den Schlüssel oder einen Teil davon und versucht, damit den Rest zu entschlüsseln. | |||
Besonders gefährdet sind Verfahren, bei denen sich der Schlüssel direkt aus Klartext und Geheimtext ausrechnen lässt und auch für den Rest des Textes gilt, weil er sich wiederholt. Das trifft auf die [[Caesar-Verschlüsselung]], das [[Vigenère-Verfahren]] und die [[XOR-Verschlüsselung]] mit wiederholtem Schlüssel zu. Beim [[One-Time-Pad]] verrät ein bekanntes Stück Klartext dagegen nur den Schlüssel an dieser Stelle. | |||
==Wörterbuchangriff== | |||
Bei einem '''Wörterbuchangriff''' probiert der Angreifer nicht alle Möglichkeiten aus, sondern nur wahrscheinliche: Wörter aus Wörterbüchern, Namen, Tastaturmuster und bekannte Passwörter. Menschen wählen selten zufällige Schlüssel, deshalb ist dieser Angriff oft viel schneller als ein Brute-Force-Angriff. | |||
Der wichtigste Einsatz ist der Angriff auf Passwörter, die als Hashwerte gespeichert sind (siehe [[Hashfunktion#Passwörter|Hashfunktion]]). | |||
==Weitere Angriffe== | |||
* Die [[Häufigkeitsanalyse]] nutzt aus, dass Buchstaben in einer Sprache unterschiedlich oft vorkommen. | |||
* Der [[Kasiski-Test]] und der [[Koinzidenzindex]] ermitteln die Schlüssellänge beim Vigenère-Verfahren. | |||
* Beim [[Man-in-the-Middle-Angriff]] schaltet sich der Angreifer unbemerkt zwischen zwei Partner. | |||
* Angriffe auf das [[RSA-Verfahren]] versuchen, den RSA-Modul in seine Primfaktoren zu zerlegen (siehe [[Primfaktorzerlegung]]). | |||
==Beispiele== | |||
===Schlüsselraum und Dauer eines Brute-Force-Angriffs berechnen=== | |||
Angenommen, ein Rechner prüft eine Milliarde Schlüssel pro Sekunde. Die Tabelle zeigt, wie lange er im ungünstigsten Fall braucht. Ein Jahr hat rund 31,5 Millionen Sekunden. | |||
{| class="wikitable" | |||
! Verfahren !! Schlüssel !! Größe des Schlüsselraums !! Dauer bei einer Milliarde Schlüsseln pro Sekunde | |||
|- | |||
| [[Caesar-Verschlüsselung]] || Verschiebung 0 bis 25 || <math>26</math> || sofort | |||
|- | |||
| [[Vigenère-Verfahren]] mit einem Schlüsselwort aus 6 Buchstaben || 6 Buchstaben || <math>26^6 = 308\,915\,776</math> || 0,309 Sekunden | |||
|- | |||
| Schlüssel aus 56 Bit || 56 Bit || <math>2^{56} \approx 7{,}2 \cdot 10^{16}</math> || etwa 2,3 Jahre | |||
|- | |||
| [[Monoalphabetische Substitution]] || Ersetzungstabelle für 26 Buchstaben || <math>26! \approx 4{,}0 \cdot 10^{26}</math> || etwa <math>1{,}3 \cdot 10^{10}</math> Jahre | |||
|- | |||
| Schlüssel aus 128 Bit || 128 Bit || <math>2^{128} \approx 3{,}4 \cdot 10^{38}</math> || etwa <math>1{,}1 \cdot 10^{22}</math> Jahre | |||
|} | |||
Die monoalphabetische Substitution zeigt, dass diese Rechnung nur eine obere Grenze liefert: Mit der Häufigkeitsanalyse gelingt der Angriff trotz des großen Schlüsselraums in Minuten. | |||
===Schlüssel aus bekanntem Klartext ermitteln=== | |||
Eve fängt diesen Geheimtext ab: <code>DWHHK XKXSE NOADA JQJOI KNCAJ</code> | |||
Sie weiß, dass er mit der [[Caesar-Verschlüsselung]] entstanden ist und dass jede Nachricht mit <code>HALLO</code> beginnt. Ein einziges Buchstabenpaar genügt: | |||
* erster Geheimtextbuchstabe <code>D</code> mit dem Wert 3 | |||
* erster Klartextbuchstabe <code>H</code> mit dem Wert 7 | |||
* Schlüssel: <math>k = (3 - 7) \bmod 26 = -4 \bmod 26 = 22</math> | |||
Mit <math>k = 22</math> entschlüsselt Eve die ganze Nachricht: <code>HALLO BOBWI RSEHE NUNSM ORGEN</code> | |||
Dasselbe gelingt bei der XOR-Verschlüsselung, siehe [[XOR-Verschlüsselung#Schlüssel aus bekanntem Klartext berechnen|Schlüssel aus bekanntem Klartext berechnen]]. | |||
===Passenden Angriff auswählen=== | |||
{| class="wikitable" | |||
! Lage !! Geeigneter Angriff | |||
|- | |||
| Geheimtext einer Caesar-Verschlüsselung, Schlüssel unbekannt || Brute-Force-Angriff: Der Schlüsselraum ist winzig. | |||
|- | |||
| Langer Geheimtext einer monoalphabetischen Substitution || Häufigkeitsanalyse | |||
|- | |||
| Langer Geheimtext des Vigenère-Verfahrens || Kasiski-Test für die Schlüssellänge, danach Häufigkeitsanalyse je Teiltext | |||
|- | |||
| Geheimtext und ein Stück des Klartextes sind bekannt || Known-Plaintext-Angriff | |||
|- | |||
| Gestohlene Tabelle mit Hashwerten von Passwörtern || Wörterbuchangriff | |||
|- | |||
| Schlüsselaustausch über einen Kanal, den der Angreifer kontrolliert || Man-in-the-Middle-Angriff | |||
|} | |||
[[Kategorie:Kryptologie]] | |||
[[Kategorie:AHR I Informatik LK]] | |||