
Kapitel 8
Kryptographie
Skript Informatik · Grundkurs
Notebooks in diesem Kapitel NB08
Alle Notebooks der Klasse · Das grüne Schild an einer Überschrift zeigt, zu welchem Notebook der Abschnitt gehört.
PDF zum Ausdrucken zusammenstellen
Kreuze an, welche Abschnitte du brauchst. Die PDF hat dasselbe Aussehen wie das gedruckte Skript, mit Platz zum Schreiben. Jeden Abschnitt gibt es auch einzeln unter seiner Überschrift, das ganze Kapitel unten auf der Seite.
Wenn Sie eine Nachricht verschicken, nimmt sie einen Weg, den Sie nicht kontrollieren: durch ein WLAN, über ein Dutzend Router, durch Leitungen, die weder Ihnen noch dem Empfänger gehören. An jeder dieser Stationen kann jemand mitlesen. Das lässt sich nicht verhindern. Verhindern lässt sich nur, dass der Mitleser etwas versteht.
Darum geht es in der Kryptographie. Sie ist längst keine Sache von Militär und Geheimdiensten mehr, sondern läuft ständig unbemerkt mit: beim Aufruf einer Webseite, beim Bezahlen, beim Entsperren des Handys, bei jeder Messenger-Nachricht.
Dieses Kapitel geht chronologisch vor, und das hat einen Grund: Jedes Verfahren ist die Antwort auf die Schwäche des vorigen, und jeder Angriff nutzt eine Eigenschaft aus, die die Erfinder für harmlos hielten. Wer diese Kette einmal verfolgt hat, versteht auch, warum heutige Verfahren so aussehen, wie sie aussehen.
Am Ende dieses Kapitels können Sie
- die Schutzziele Vertraulichkeit, Integrität und Authentizität unterscheiden und Angriffe darauf einordnen,
- klassische Verfahren (Transposition, mono- und polyalphabetische Substitution) erklären, anwenden und programmieren,
- eine Häufigkeitsanalyse und den Kasiski-Test durchführen und begründen, warum sie funktionieren,
- erklären, warum das One-Time-Pad sicher, aber unpraktisch ist,
- den Unterschied zwischen symmetrischen und asymmetrischen Verfahren erläutern,
- den Schlüsseltausch von Diffie und Hellman an kleinen Zahlen durchführen und seine Grundidee erklären,
- den Man-in-the-Middle-Angriff beschreiben und begründen, warum Mathematik allein ihn nicht verhindert,
- das RSA-Verfahren an kleinen Zahlen vollständig durchrechnen,
- beschreiben, wie Signatur, Hashfunktion und Hybridverfahren beim Aufruf einer Webseite zusammenwirken.
8.1Schutzziele und Angriffe
Diesen Abschnitt als PDF (S. 2–3)
Bevor man ein Verfahren auswählt, muss klar sein, wovor es eigentlich schützen soll. Die IT-Sicherheit unterscheidet drei Grundforderungen.
| Schutzziel | Leitfrage | Beispiel für eine Verletzung |
|---|---|---|
| Vertraulichkeit | Kann ein Dritter die Nachricht lesen? | Jemand liest im offenen WLAN die Bestellung mit. |
| Integrität | Ist die Nachricht unverändert angekommen? | Die Kontonummer in einer Überweisung wird unterwegs ersetzt. |
| Authentizität | Stammt die Nachricht wirklich vom angegebenen Absender? | Eine Mail gibt sich als Nachricht der Schulleitung aus. |
Häufig kommt als viertes Ziel die Verbindlichkeit hinzu: Der Absender soll später nicht abstreiten können, die Nachricht geschickt zu haben.
Angriffe auf diese Ziele teilt man in zwei Gruppen:
- Passiver Angriff. Der Angreifer liest nur mit. Er verletzt die Vertraulichkeit, verändert aber nichts. Solche Angriffe hinterlassen keine Spuren und sind darum kaum zu entdecken – man kann sie nur verhindern, indem man den Inhalt unlesbar macht.
- Aktiver Angriff. Der Angreifer verändert, wiederholt, verzögert oder unterdrückt Nachrichten oder gibt sich als jemand anderes aus (Maskerade). Solche Angriffe lassen sich nicht verhindern, denn die Leitung gehört dem Angreifer genauso wie uns. Man kann sie nur erkennbar machen.
Passive Angriffe muss man verhindern, aktive Angriffe muss man erkennen. Verschlüsselung allein schützt nur die Vertraulichkeit – für Integrität und Authentizität braucht es zusätzliche Werkzeuge (Abschnitt 8.11).
- Ordnen Sie zu, welches Schutzziel jeweils verletzt wird: (a) Ein Angreifer schneidet den Netzwerkverkehr mit. (b) Eine Bestellung wird von 1 auf 100 Stück geändert. (c) Ein Erpresser verschlüsselt alle Dateien einer Firma. (d) Eine gefälschte Absenderadresse verschickt Rechnungen.
- Begründen Sie, warum ein aktiver Angriff meist einen passiven voraussetzt.
- Nennen Sie für jedes der drei Schutzziele eine Situation aus Ihrem eigenen Alltag, in der Sie sich darauf verlassen.
8.2Grundbegriffe
Diesen Abschnitt als PDF (S. 4–5)
Die Wörter stammen aus dem Griechischen: kryptós (verborgen), gráphein (schreiben), lógos (Wort, Lehre).
- Kryptographie ist die Lehre vom Entwurf von Verschlüsselungsverfahren.
- Kryptoanalyse ist die Lehre vom Brechen dieser Verfahren.
- Kryptologie ist der Oberbegriff für beides. Wer gute Verfahren bauen will, muss angreifen können – beide Seiten gehören untrennbar zusammen.
Der Klartext ist die lesbare Nachricht, der Geheimtext (auch: Chiffrat) ihre verschlüsselte Form. Der Vorgang heißt Chiffrierung bzw. Dechiffrierung, das zugrunde liegende Verfahren Chiffre. Die Information, die Sender und Empfänger geheim halten, ist der Schlüssel.
Benutzen beide Seiten denselben Schlüssel, heißt das Verfahren symmetrisch. Gibt es getrennte Schlüssel zum Ver- und Entschlüsseln, heißt es asymmetrisch (Abschnitt 8.9).
8.2.1Das Prinzip von Kerckhoffs
Ein Anfängerfehler ist es, die Sicherheit auf die Geheimhaltung des Verfahrens zu gründen. Auguste Kerckhoffs formulierte 1883 die bis heute gültige Gegenregel.
Die Sicherheit eines Verschlüsselungsverfahrens darf allein auf der Geheimhaltung des Schlüssels beruhen, nicht auf der Geheimhaltung des Algorithmus.
Das klingt paradox, ist aber praktisch begründet: Algorithmen werden implementiert, verteilt, disassembliert, von Mitarbeitern weitergetragen. Ein Verfahren, das nur geheim funktioniert, ist genau einmal sicher – bis zum ersten Leck. Ein Schlüssel dagegen lässt sich austauschen, ohne dass alles Übrige neu gebaut werden muss. Moderne Verfahren wie AES sind vollständig veröffentlicht und werden weltweit öffentlich angegriffen; dass sie das aushalten, ist ihr Sicherheitsnachweis.
8.2.2Angriffsmodelle
Nach Kerckhoffs kennt der Angreifer das Verfahren. Unterschieden wird danach, welches Material ihm darüber hinaus vorliegt.
| Modell | Der Angreifer hat … | Realistisch, wenn … |
|---|---|---|
| Ciphertext-only | nur Geheimtexte | er Datenverkehr mitschneidet |
| Known-plaintext | Geheimtexte und zugehörige Klartexte | Formulierungen vorhersehbar sind (Briefköpfe, Protokolle) |
| Chosen-plaintext | er darf Klartexte seiner Wahl verschlüsseln lassen | er Zugang zum Verschlüsselungsgerät hat |
| Chosen-ciphertext | er darf Geheimtexte seiner Wahl entschlüsseln lassen | ein Server jede Anfrage beantwortet |
Beide Lehrpläne nennen als Angriffsarten nur Brute-Force, Known-Plaintext und Häufigkeitsanalyse. Die beiden unteren Zeilen der Tabelle — chosen plaintext und chosen ciphertext — gehen darüber hinaus. Sie stehen hier, weil ohne sie unklar bleibt, woran moderne Verfahren eigentlich gemessen werden.
Ein Verfahren gilt als gut, wenn es selbst im stärksten Modell standhält. Die Verfahren dieses Kapitels scheitern der Reihe nach immer früher, je weiter wir zurückgehen.
- Erklären Sie, warum das Prinzip von Kerckhoffs für Open-Source-Software besonders gut passt.
- Der Klassiker unter den Known-plaintext-Angriffen: Im Zweiten Weltkrieg enthielten viele deutsche Funksprüche das Wort „Wetter“. Erläutern Sie, welchen Vorteil das einem Angreifer verschafft.
8.3Klassische Verfahren
Diesen Abschnitt als PDF (S. 6–8)
Klassisch heißen Verfahren, die ohne Computer auskamen. Sie arbeiten mit zwei Grundoperationen, die – in ganz anderem Gewand – bis heute in jeder modernen Blockchiffre stecken.
- Transposition: Die Buchstaben bleiben, ihre Reihenfolge ändert sich.
- Substitution: Die Reihenfolge bleibt, die Buchstaben werden ersetzt.
8.3.1Transposition: die Skytala
Die älteste überlieferte Chiffre ist rund 2400 Jahre alt. Die Spartaner wickelten einen schmalen Lederstreifen um einen Stab bestimmter Dicke, die Skytala, und schrieben die Nachricht längs des Stabes. Abgewickelt ergab der Streifen eine sinnlose Buchstabenfolge; nur ein Stab desselben Durchmessers machte sie wieder lesbar. Der Schlüssel ist also die Dicke des Stabes.
Informatisch ist die Skytala nichts anderes als eine Tabelle: Man schreibt den Text zeilenweise in eine Tabelle mit Spalten und liest ihn spaltenweise wieder aus.
Klartext: ANGRIFFBEIMORGENGRAUEN, s = 4
A N G R Auslesen spaltenweise:
I F F B AIERGE NFIGRN GFMEA RBONU
E I M O
R G E N
G R A U
E N
Der Angriff ist einfach: Es gibt nur wenige sinnvolle Spaltenzahlen, man probiert sie durch. Die Skytala scheitert schon im Ciphertext-only-Modell.
8.3.2Substitution: die Cäsar-Chiffre
Bei der Cäsar-Chiffre wird das Alphabet zyklisch um Stellen verschoben. Nach Z folgt wieder A. Der Schlüssel ist die Zahl .
Klartext: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Geheim (k=4): E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
Rechnet man die Buchstaben in Zahlen um (A = 0, B = 1, …, Z = 25), wird daraus eine Addition mit Rest:
Dabei ist der Klartext- und der Geheimtextbuchstabe. Das „mod 26“ erledigt genau den Übergang von Z zurück zu A.
Weil es nur 25 brauchbare Schlüssel gibt, ist die Cäsar-Chiffre mit Bleistift und Papier in Minuten zu brechen: Man probiert alle durch (Brute-Force-Angriff). Ein Computer erledigt das in Mikrosekunden.
8.3.3Allgemeine monoalphabetische Substitution
Man kann jedem Buchstaben statt der Verschiebung eine beliebige Zuordnung geben – dann ist der Schlüssel eine vollständige Vertauschung des Alphabets. Davon gibt es
Stück. Eine Maschine, die eine Milliarde Schlüssel pro Sekunde prüft, wäre damit rund 13 Milliarden Jahre beschäftigt — ungefähr so lange, wie das Universum alt ist. Trotzdem ist das Verfahren unsicher, und diese Diskrepanz ist die wichtigste Lehre dieses Abschnitts.
Ein großer Schlüsselraum ist notwendig, aber nicht hinreichend für Sicherheit. Er schützt nur vor Brute Force, nicht vor einem klügeren Angriff.
8.3.4Kryptoanalyse durch Häufigkeitsanalyse
Der klügere Angriff nutzt die Statistik der Sprache. In deutschen Texten kommen die Buchstaben höchst ungleich vor:
| Buchstabe | E | N | I | S | R | A | T | D | H | U | L | C |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Anteil % | 17,4 | 9,8 | 7,6 | 7,3 | 7,0 | 6,5 | 6,2 | 5,1 | 4,8 | 4,4 | 3,4 | 3,1 |
Allein E und N machen gut ein Viertel jedes Textes aus, die zwölf häufigsten Buchstaben rund 80 %. Eine monoalphabetische Substitution verschiebt diese Verteilung nur, sie zerstört sie nicht: Der häufigste Geheimtextbuchstabe ist mit großer Wahrscheinlichkeit das E.
titel: Cäsar, Vigenère und die Häufigkeitsanalyse verfahren: caesar schluessel: 7 text: DIE HAEUFIGKEITSANALYSE BRICHT JEDE MONOALPHABETISCHE SUBSTITUTION SOBALD DER TEXT LANG GENUG IST
Probieren Sie es im Bedienfeld aus: Bei Cäsar wandert die Verteilung geschlossen um Stellen nach rechts — die Form bleibt erkennbar. Schalten Sie dann auf Vigenère um, und die Verteilung flacht ab. Genau deshalb braucht der Angriff auf Vigenère einen zweiten Gedanken, den Kasiski-Test aus dem nächsten Abschnitt.
Das untere Diagramm ist der ganze Angriff: Man sucht den höchsten Balken und weiß, dass er das E sein muss. Daraus ergibt sich der Schlüssel, und der Rest fällt von allein.
Hilfreich sind außerdem Bigramme (Buchstabenpaare). Im Deutschen sind ER, EN, CH, DE und EI besonders häufig; CH und SCH verraten sich schnell. Bei kurzen oder ungewöhnlichen Texten versagt die Methode allerdings – ein Text „über den Einfluss von Ozon auf die Zebras im Zentrum von Zaire“ hat eine ganz andere Statistik als die Zeitung von gestern.
- Verschlüsseln Sie
INFORMATIKmit der Cäsar-Chiffre und . - Entschlüsseln Sie den Geheimtext
OBXE LITLL UXBF XGMLVAENXLLXEG. Notieren Sie Ihren Weg. - Schreiben Sie ein Programm, das zu einem Text und einem Schlüssel den Geheimtext liefert, und ein zweites, das zurückrechnet. Buchstaben außerhalb von A–Z sollen unverändert bleiben.
- Erweitern Sie Ihr Programm so, dass es alle 25 Möglichkeiten ausgibt – der vollständige Brute-Force-Angriff.
- Schreiben Sie ein Programm, das die Häufigkeit aller Zeichen eines Textes zählt und als Balkendiagramm ausgibt. Testen Sie es an einem längeren deutschen Text.
- Begründen Sie, warum ein Brute-Force-Angriff auf die allgemeine monoalphabetische Substitution aussichtslos, das Verfahren aber trotzdem unsicher ist.
8.4Polyalphabetische Verschlüsselung: Vigenère
Diesen Abschnitt als PDF (S. 9–12)
Die Antwort auf die Häufigkeitsanalyse liegt nahe: Man benutzt nicht ein Geheimalphabet, sondern mehrere im Wechsel. Das bekannteste dieser Verfahren veröffentlichte der französische Diplomat Blaise de Vigenère 1586.
Unter den Klartext wird ein Schlüsselwort geschrieben und so oft wiederholt, bis der Text zu Ende ist. Jeder Buchstabe des Schlüsselworts gibt an, um wie viele Stellen der darüberstehende Klartextbuchstabe verschoben wird (A = 0, B = 1, …).
Klartext: K R Y P T O G R A P H I E
Schlüssel: H A L L O H A L L O H A L
Geheimtext: R R J A H V G C L D O I P
Von Hand liest man die Geheimtextbuchstaben im Vigenère-Quadrat ab: Die Zeile gibt der Schlüsselbuchstabe vor, die Spalte der Klartextbuchstabe; im Kreuzungspunkt steht der Geheimtextbuchstabe. Für das erste Zeichen des Beispiels sucht man also die Zeile H und darin die Spalte K und findet R.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
----------------------------------------------------
A | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B | B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C | C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D | D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E | E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F | F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G | G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H | H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I | I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J | J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K | K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L | L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M | M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N | N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O | O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P | P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q | Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R | R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S | S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T | T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U | U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V | V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W | W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X | X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y | Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z | Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
Jede Zeile des Quadrats ist nichts anderes als ein um eine Stelle weiter verschobenes Alphabet – also eine Cäsar-Chiffre. Das Vigenère-Verfahren besteht demnach darin, im Takt des Schlüsselworts zwischen 26 Cäsar-Chiffren hin- und herzuspringen. Genau diese Beobachtung wird uns beim Angriff in Abschnitt 8.4.1 wieder begegnen.
Rechnerisch ist es eine Addition mit Rest, nur dass sich der Summand von Buchstabe zu Buchstabe ändert:
Dabei ist die Länge des Schlüsselworts.
Der Gewinn ist deutlich: Gleiche Klartextbuchstaben werden je nach Position verschieden verschlüsselt, die Häufigkeitsverteilung des Geheimtextes wird flach. Drei Jahrhunderte lang galt das Verfahren als unknackbar – „le chiffre indéchiffrable“.
8.4.1Der Kasiski-Test
1863 zeigte der preußische Major Friedrich Wilhelm Kasiski, wo die Schwäche liegt: Der Schlüssel wiederholt sich. Trifft dieselbe Klartextstelle zufällig auf dieselbe Stelle des Schlüsselworts, entsteht dieselbe Geheimtextstelle. Der Abstand solcher Wiederholungen ist deshalb ein Vielfaches der Schlüssellänge.
Daraus ergibt sich der Angriff in drei Schritten:
- Im Geheimtext wiederholte Buchstabenfolgen (Länge 4 oder 5) suchen und ihre Abstände berechnen.
- Den größten gemeinsamen Teiler der Abstände bilden – das ist die vermutete Schlüssellänge . Ein einzelner Abstand genügt nicht, denn er ist nur ein Vielfaches von .
- Den Text in Spalten zerlegen. Jede Spalte ist mit einem festen Alphabet verschlüsselt, also eine gewöhnliche Cäsar-Chiffre – und gegen die hilft die Häufigkeitsanalyse aus 8.3.4.
Der folgende Text wurde mit einem Schlüsselwort verschlüsselt, dessen Länge wir nicht kennen:
0 VEXWZAWZDIWZFDCWGEVWDDUKZENRSEBLWAHFSEFWEEHOQRXWZDYKTAFTII
58 LVVEXWZAWZDIWZFVYJECBDGEMKQLNOQRXAQNUUTRCUTTFAQSNKUEBLZULT
116 GCBKFAVWZSUDMTQWDDYFECBDGEMKQLBSFSCWTTXAQNUUTRCUTTMGQIHXMC
174 BAETXWDGLMZDAWPAHCQUHVEOMUTWYJUSNKQIHWGMMWFZOFSIHVQRJJMXCK
Vier Folgen kommen doppelt vor:
| Folge | Positionen | Abstand |
|---|---|---|
VEXWZAWZDIWZF |
0 und 60 | 60 |
ECBDGEMKQL |
76 und 136 | 60 |
XAQNUUTRCUTT |
90 und 154 | 64 |
OQRX |
43 und 87 | 44 |
Der größte gemeinsame Teiler von 60, 64, 60 und 44 ist
4. Das Schlüsselwort hat also vier Buchstaben — es war
MAUS. Mit nur einem Abstand wäre man nicht weitergekommen:
60 allein lässt 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 und 60 zu.
Die Vigenère-Chiffre ist nur so stark wie die Periode ihres Schlüssels. Ein sich wiederholender Schlüssel zerlegt den Text in mehrere einfache Chiffren.
1922 ergänzte William F. Friedman den Friedman-Test: Er schätzt die Schlüssellänge über den Koinzidenzindex, also die Wahrscheinlichkeit, dass zwei zufällig gezogene Buchstaben eines Textes gleich sind. Für deutschen Klartext liegt dieser Wert bei etwa 0,076, für zufällige Buchstaben bei . Je länger der Schlüssel, desto näher rückt der Geheimtext an den Zufallswert.
- Verschlüsseln Sie
SICHERHEITmit dem SchlüsselwortMAUS. - Entschlüsseln Sie
DLGK TKQTmit dem SchlüsselwortTAG. - Erklären Sie, warum ein Schlüsselwort mit lauter gleichen Buchstaben
(z. B.
AAAA) die Vigenère-Chiffre auf ein bekanntes Verfahren zurückführt. Auf welches? - Schreiben Sie ein Programm zur Ver- und Entschlüsselung nach Vigenère.
8.4.2Werkstatt: ein Vigenère-Chiffrat knacken
Der folgende Text ist deutsch, mit einem unbekannten Schlüsselwort verschlüsselt und 509 Buchstaben lang. Umlaute stehen als AE/OE/UE, Satzzeichen und Leerzeichen sind entfallen. Die Zahl am Zeilenanfang gibt die Position des ersten Buchstabens der Zeile an – damit lassen sich Abstände ablesen, ohne nachzuzählen.
1 NIWKZ SNPRW DGXDS GWVWB MFEJA URTEE KAWVB TEVMF LCMHK BSLMX
51 MABWS VOMSV VOZON STHRI LELCF NDORO QKMPD SGLAO PKEMN AQSOI
101 LMFNM CKDIJ DMHTW AARZO SUPOK MMHWT AOODG WVSEL KRAVV KACSA
151 KZNIC SUPDE MCSWT OYZDW AMVOZ RODBO OZNIW TSOVQ EVMKC KRLMM
201 KCMVS CMFXB NEJHW BTOGL LWXBO XLQFC XKLLM FEVNK FIUUB TEVMW
251 SVJED VWCXK LLMES BNEJO WGWRN LMFRI OUXQY UMSTK IFKTI SWLWB
301 XBEMA KSAMH WWXPQ JIWZX BQODJ QURSK SAACS DORGM XPMXT DQURB
351 ODAMK OVKNY ZAPNL EJMAD ASMBI ZBIMH LHWRV RUFLW BBNRW QMXLC
401 EUPRS OORKC URBOI EKZSN PRSBF KKRWA MVOZR ODBWX JECZA LKJON
451 XWDQM XUFLT OADIE ULOIE SVMJO VKBKB SOVNE FLAOT KEFOW NMCSU
501 PDEMC SWTK
Dass die einfache Häufigkeitsanalyse hier nicht weiterhilft, zeigt schon ein Blick auf die Verteilung: Der häufigste Buchstabe des Chiffrats ist M mit 7,7 %, gefolgt von O mit 7,3 % und gleich drei Buchstaben mit 6,1 %. Im Deutschen läge das E dagegen bei 17,4 %. Die Verteilung ist flach – aber, wie Kasiski gezeigt hat, nicht strukturlos.
16 Suchen Sie im Chiffrat Buchstabenfolgen der Länge 5, die zweimal vorkommen, und notieren Sie mindestens vier Funde mit ihren Positionen und dem Abstand. Bestimmen Sie zu jedem Abstand alle Teiler und markieren Sie die Zahl, die in jeder Zeile vorkommt. Begründen Sie, warum ein einzelner Fund nicht genügt: Welche Schlüssellängen ließe Ihr kleinster Abstand noch offen?
Legen Sie dafür im Heft eine Tabelle mit den Spalten Fundstelle, Position 1, Position 2, Abstand und alle Teiler des Abstands an.
17 Zerlegen Sie das Chiffrat in Spalten und bestimmen Sie für jede Spalte den häufigsten Buchstaben. Nehmen Sie an, dass dies das verschlüsselte E ist, und berechnen Sie daraus den Schlüsselbuchstaben. Arbeiten Sie arbeitsteilig – je Gruppe eine Spalte.
Tabellenspalten: Spalte, Anzahl Buchstaben, häufigster Buchstabe, Verschiebung, Schlüsselbuchstabe.
18 Notieren Sie das Schlüsselwort. Fällt Ihnen an seinen Buchstaben etwas auf, das Ihre Rechnung bestätigt? Entschlüsseln Sie anschließend die ersten beiden Zeilen von Hand und setzen Sie Wortgrenzen. Der Klartext verrät, wem Sie dieses Verfahren verdanken.
19 Automatisieren Sie den Angriff im Notebook vigenere-info12.ipynb: Häufigkeiten zählen, Wiederholungen und Abstände finden, ggT bilden, Spalten auswerten, entschlüsseln.
20 Für Schnelle: Lassen Sie Ihr Programm alle Schlüssellängen von 1 bis 12 durchprobieren und jedes Ergebnis über die Abweichung von der deutschen Buchstabenverteilung bewerten (). Der Angriff läuft dann ganz ohne Vorwissen: Bei diesem Text schneidet die richtige Länge rund zwanzigmal besser ab als die nächstbeste. Beachten Sie dabei eine Falle — auch jedes Vielfache der richtigen Länge liefert einen guten Wert. Warum?
8.5Homophone Verschlüsselung
Diesen Abschnitt als PDF (S. 13)
Die Abschnitte 8.5 und 8.6 stehen in keinem der beiden Lehrpläne. Sie schließen aber die Lücke zwischen Vigenère und den modernen Verfahren: erst die Statistik verwischen, dann die Wiederholung des Schlüssels abschaffen.
Ein anderer Weg, die Statistik zu verwischen: Jedem Klartextbuchstaben wird nicht ein Zeichen zugeordnet, sondern eine Menge von Zeichen – und zwar so viele, wie es seiner Häufigkeit entspricht. Beim Verschlüsseln wählt man daraus zufällig aus.
A: 10, 21, 52, 59, 71, 84
B: 20, 34
C: 06, 28, 80
E: 09, 18, 33, 38, 40, 42, 53, 54, 55, 60, 66, 75, 85, 86, 92, 93, 99
Weil dem E siebzehn Zeichen zur Verfügung stehen, dem B nur zwei, kommt am Ende jedes Zeichen etwa gleich oft vor: Die Häufigkeitsanalyse läuft ins Leere. Der Preis ist ein längerer Geheimtext und eine große Tabelle als Schlüssel. Sicher ist auch dieses Verfahren nicht – Bigramme und Wortstrukturen bleiben erhalten und wurden historisch erfolgreich ausgenutzt.
8.6Das One-Time-Pad
Diesen Abschnitt als PDF (S. 14)
Aus den bisherigen Angriffen lassen sich zwei Forderungen ableiten: Der Schlüssel darf sich nicht wiederholen, er muss also so lang sein wie die Nachricht, und er darf nur ein einziges Mal benutzt werden. Genau das leistet das One-Time-Pad (Vernam-Chiffre, 1917).
Der Schlüssel ist eine echt zufällige Buchstaben- oder Bitfolge, von der Sender und Empfänger je ein identisches Exemplar besitzen. Jedes Zeichen wird mit genau einem Schlüsselzeichen verknüpft, danach wird der verbrauchte Teil vernichtet.
Das One-Time-Pad ist das einzige Verfahren, dessen Sicherheit bewiesen ist (Shannon, 1949). Der Grund lässt sich mit den Werkzeugen dieses Kapitels formulieren: Zu einem gegebenen Geheimtext existiert für jeden denkbaren Klartext gleicher Länge ein passender Schlüssel. Der Kasiski-Test findet keine Periode, die Häufigkeitsanalyse keine Spalten. Der Geheimtext verrät über den Klartext nichts außer dessen Länge.
Warum benutzen wir es dann nicht überall? Wegen der Praxis:
- Der Schlüssel ist so lang wie alle Nachrichten zusammen und muss vorab sicher ausgetauscht werden. Wer das kann, könnte auch die Nachricht selbst sicher austauschen.
- Er muss echt zufällig sein; Pseudozufallszahlen aus einem Programm genügen nicht.
- Jede Wiederverwendung bricht das Verfahren sofort. Die sowjetischen Funksprüche des Venona-Projekts wurden genau deshalb entziffert: Schlüsselblöcke waren aus Zeitnot doppelt verwendet worden.
- Begründen Sie, warum aus einem One-Time-Pad-Geheimtext prinzipiell kein Klartext ableitbar ist, obwohl der Angreifer das Verfahren kennt.
- Zwei Nachrichten wurden versehentlich mit demselben One-Time-Pad verschlüsselt. Zeigen Sie: Aus und lässt sich etwas berechnen, das den Schlüssel nicht mehr enthält. Was?
- Erklären Sie, warum das One-Time-Pad für den Betrieb einer Webseite ungeeignet ist.
8.7Moderne symmetrische Verfahren
Diesen Abschnitt als PDF (S. 15)
Heutige symmetrische Verfahren verschlüsseln keine Buchstaben, sondern Bitblöcke fester Länge (Blockchiffren). Der Standard ist seit 2001 AES (Advanced Encryption Standard) mit Schlüssellängen von 128, 192 oder 256 Bit. AES wendet auf jeden 128-Bit-Block mehrere Runden aus Substitution und Transposition an – dieselben zwei Ideen wie in Abschnitt 8.3, nur auf Bits und vielfach verschachtelt.
Bei 128 Bit gibt es Schlüssel. Eine Maschine, die eine Billion Schlüssel pro Sekunde prüft, wäre damit rund Jahre beschäftigt. Brute Force ist hier endgültig kein Weg mehr.
Ein Problem bleibt aber, und es ist kein mathematisches: Sender und Empfänger brauchen denselben geheimen Schlüssel. Bei Teilnehmern, die alle paarweise vertraulich kommunizieren wollen, sind das
Schlüssel – bei 1000 Teilnehmern also fast eine halbe Million, und jeder einzelne muss sicher ausgetauscht werden, bevor die erste Nachricht fließt. Das ist das Schlüsselverteilungsproblem.
- Berechnen Sie die Zahl der nötigen Schlüssel für eine Schule mit 900 Personen.
- Ein Angreifer kann eine Milliarde AES-Schlüssel pro Sekunde testen. Schätzen Sie die Dauer eines Brute-Force-Angriffs auf einen 128-Bit-Schlüssel und vergleichen Sie mit dem Alter des Universums (rund Jahre). Vergleichen Sie auch mit Abschnitt 8.3.3: Warum ist der Unterschied zur monoalphabetischen Substitution so gewaltig, obwohl beide Schlüsselräume „riesig” heißen?
8.8Schlüsseltausch nach Diffie und Hellman
Diesen Abschnitt als PDF (S. 16–18)
Das Schlüsselverteilungsproblem sieht aus wie ein Henne-Ei-Problem: Um sicher zu reden, braucht man einen gemeinsamen Schlüssel — und um den auszutauschen, müsste man schon sicher reden können. 1976 zeigten Whitfield Diffie und Martin Hellman, dass dieser Schluss falsch ist. Zwei Partner können sich auf einen gemeinsamen geheimen Schlüssel einigen, indem sie ausschließlich öffentlich miteinander sprechen. Niemand muss das Geheimnis jemals übertragen, weil es erst beim Rechnen entsteht.
Alice und Bob mischen Farben. Beide starten mit demselben, allen bekannten Gelb. Alice gibt heimlich etwas Rot dazu, Bob heimlich etwas Blau; die Mischungen tauschen sie offen aus. Nun gibt Alice ihr Rot in Bobs Mischung, Bob sein Blau in Alices — beide halten am Ende denselben Braunton in der Hand. Ein Beobachter hat Gelb, Orange und Grün gesehen und kommt damit nicht weiter: Mischen ist leicht, Entmischen ist schwer.
Die Rolle des Mischens übernimmt in der Mathematik das Potenzieren mit Rest. Öffentlich vereinbart werden eine Primzahl und eine Zahl mit , die Basis. Beide Werte dürfen alle kennen.
| Schritt | Alice | Bob |
|---|---|---|
| 1 | wählt geheim | wählt geheim |
| 2 | berechnet | berechnet |
| 3 | sendet an Bob | sendet an Alice |
| 4 | berechnet | berechnet |
Dass am Ende wirklich dieselbe Zahl herauskommt, ist nichts als ein Potenzgesetz:
Öffentlich: und .
- Alice wählt und berechnet .
- Bob wählt und berechnet .
- Sie tauschen und offen aus.
- Alice rechnet .
- Bob rechnet .
Beide haben , ohne dass die 2 jemals über die Leitung ging. Die Probe: .
Rechnen Sie
nicht mit dem Taschenrechner aus —
hat elf Stellen. Nehmen Sie nach jedem Schritt den Rest:
,
also
,
und damit
.
In Python genügt pow(5, 15, 23).
Warum ist das sicher? Ein Lauscher kennt , , und . Um zu berechnen, bräuchte er einen der beiden geheimen Exponenten, müsste also aus die Zahl zurückgewinnen. Diese Aufgabe heißt diskreter Logarithmus. Bei löst man sie in zwanzig Versuchen; bei einer Primzahl mit 600 Stellen ist kein Verfahren bekannt, das in vertretbarer Zeit zum Ziel kommt. Potenzieren mit Rest ist also eine Einwegfunktion — leicht vorwärts, praktisch unmöglich rückwärts.
Diffie-Hellman ist kein Verschlüsselungsverfahren. Es überträgt keine Nachricht, sondern erzeugt bei beiden Partnern dieselbe Zufallszahl. Verschlüsselt wird danach symmetrisch, etwa mit AES — der ausgehandelte Wert ist der Sitzungsschlüssel. Genau so arbeitet heute jede HTTPS-Verbindung.
Der Schlüssel entsteht bei jedem Verbindungsaufbau neu und wird danach verworfen. Das hat einen Namen und einen Zweck: Perfect Forward Secrecy. Wer den heutigen Datenverkehr mitschneidet und in zehn Jahren den privaten Schlüssel des Servers erbeutet, kann damit nichts anfangen — die Sitzungsschlüssel von damals stehen nirgends mehr.
Der Mittelsmann. Diffie-Hellman sichert zu, dass am Ende zwei Partner denselben Schlüssel besitzen. Es sichert nicht zu, wer diese beiden sind. Mallory kann sich in die Leitung setzen und mit jeder Seite einen eigenen Schlüsseltausch durchführen:
- Mallory wählt selbst ein geheimes und berechnet .
- Alice sendet los. Mallory fängt es ab und schickt Bob stattdessen .
- Bob sendet . Mallory fängt auch das ab und schickt Alice .
- Alice rechnet — und Mallory rechnet .
- Bob rechnet — und Mallory rechnet .
Mallory hat nun zwei Schlüssel: 6 für die Strecke zu Alice, 5 für die Strecke zu Bob. Er entschlüsselt jede Nachricht, liest sie, verschlüsselt sie neu und reicht sie weiter. Alice und Bob bemerken nichts, denn beide Verbindungen sind kryptographisch einwandfrei. Wie sich das abwehren lässt, steht im nächsten Abschnitt.
- Führen Sie den Schlüsseltausch mit , , und durch. Geben Sie , und an und prüfen Sie, dass beide Seiten dasselbe erhalten.
- Begründen Sie mit dem Potenzgesetz, warum und denselben Rest lassen müssen.
- Ein Lauscher kennt , und . Bestimmen Sie durch Probieren und notieren Sie, wie viele Versuche Sie gebraucht haben. Was sagt das über die Sicherheit kleiner Primzahlen?
- Warum darf nicht 1 sein? Was passiert, wenn Alice und Bob zufällig denselben geheimen Wert wählen?
- Berechnen Sie
von Hand, indem Sie nach jedem Schritt den Rest nehmen. Vergleichen Sie
mit
pow(7, 20, 11). - Erklären Sie in drei Sätzen, warum Diffie-Hellman das Schlüsselverteilungsproblem löst, das Problem der Echtheit eines Gegenübers aber nicht.
8.9Asymmetrische Verfahren
Diesen Abschnitt als PDF (S. 19–21)
1976 schlugen Whitfield Diffie und Martin Hellman eine Lösung vor, die zunächst unmöglich klingt: Jeder Teilnehmer besitzt zwei Schlüssel.
- Der öffentliche Schlüssel (public key) wird veröffentlicht. Mit ihm kann jeder eine Nachricht an den Besitzer verschlüsseln.
- Der private Schlüssel (private key) bleibt geheim und verlässt den Besitzer nie. Nur mit ihm lässt sich wieder entschlüsseln.
Damit verschwindet das Schlüsselverteilungsproblem: Es muss nie ein Geheimnis übertragen werden. Bei Teilnehmern genügen Schlüsselpaare.
Die Metapher dazu ist ein Briefkasten: Den Einwurfschlitz kann jeder benutzen, herausholen kann nur, wer den Schlüssel hat.
Mathematisch braucht man dafür Einwegfunktionen: Berechnungen, die in eine Richtung leicht, in die andere praktisch unmöglich sind. Das Standardbeispiel ist die Multiplikation von Primzahlen.
Für die Verschlüsselung braucht man etwas mehr, nämlich eine Falltürfunktion: eine Einwegfunktion, die sich doch umkehren lässt, wenn man eine Zusatzinformation besitzt – die Falltür ist der private Schlüssel.
Asymmetrische Verfahren beruhen nicht darauf, dass ein Angreifer den privaten Schlüssel nicht berechnen kann, sondern darauf, dass die Berechnung zu lange dauert. Sicherheit ist hier eine Frage des Aufwands, nicht der Unmöglichkeit.
8.9.1Der Haken: Man-in-the-Middle
Den Man-in-the-Middle-Angriff verlangt ausdrücklich nur der LK-Lehrplan („beschreiben den Man-in-the-middle-Angriff auf das Diffie-Hellman-Verfahren”). Dass die Lücke existiert, sollte aber auch im Grundkurs gesagt werden — sonst bleibt der falsche Eindruck zurück, Verschlüsselung allein genüge.
Oben stand, das Schlüsselverteilungsproblem verschwinde. Das stimmt nur halb. Übertragen wird zwar kein Geheimnis mehr — aber Alice muss immer noch wissen, dass der Schlüssel, den sie für Bobs öffentlichen hält, wirklich Bob gehört.
Genau hier setzt der Man-in-the-Middle-Angriff an (auch Mittelsmann-Angriff). Der Angreifer — traditionell Mallory genannt, von malicious — stellt sich nicht neben die Leitung, sondern hinein.
Der Ablauf:
- Alice fragt nach Bobs öffentlichem Schlüssel. Mallory fängt die Antwort ab und schickt stattdessen seinen eigenen.
- Alice verschlüsselt mit diesem Schlüssel und schickt los. Mallory kann entschlüsseln — es ist ja sein Schlüssel.
- Mallory liest mit, ändert nach Belieben, verschlüsselt mit Bobs echtem Schlüssel neu und schickt weiter.
- Bob antwortet, und dasselbe geschieht in der Gegenrichtung.
Beide merken nichts. Beide Verbindungen sind kryptographisch einwandfrei.
Ein Man-in-the-Middle bricht die Verschlüsselung nicht — er unterläuft sie. Die Mathematik bleibt unangetastet; was fehlt, ist die Zuordnung von Schlüssel zu Person.
Deshalb löst Kryptographie allein das Problem nie ganz. Es braucht einen zweiten Weg, über den sich ein Schlüssel überprüfen lässt: persönliche Übergabe, ein Fingerabdruck über das Telefon — oder eine dritte Stelle, der beide trauen. Das sind die Zertifikate aus Abschnitt 8.11.
Es ist derselbe Angriff, den Sie in Abschnitt 8.8 schon am Schlüsseltausch gesehen haben, und er hat denselben Grund: Beide Verfahren stellen sicher, dass am Ende zwei Partner einen Schlüssel teilen — aber nicht, wer diese beiden sind. Die Mathematik kann diese Lücke nicht schließen; dafür braucht es die Zertifikate aus Abschnitt 8.11.
- Erklären Sie, warum ein Man-in-the-Middle-Angriff kein Widerspruch zu der Aussage ist, RSA sei sicher.
- Sie bekommen den öffentlichen Schlüssel einer Mitschülerin per E-Mail. Nennen Sie zwei Wege, auf denen Sie prüfen können, ob er wirklich von ihr stammt.
- Begründen Sie, warum der Angriff auf einem Flughafen-WLAN leichter ist als im Schulnetz.
8.10Das RSA-Verfahren
Diesen Abschnitt als PDF (S. 22–24)
1977 fanden Ronald Rivest, Adi Shamir und Leonard Adleman eine solche Falltürfunktion. Das nach ihnen benannte RSA-Verfahren wird bis heute eingesetzt.
8.10.1Vorbereitung: Rechnen mit Resten
ist der Rest, den bei Division durch lässt. Beispiele: , , (denn ).
Die eulersche Phi-Funktion gibt an, wie viele Zahlen mit teilerfremd zu sind:
| teilerfremde | ||
|---|---|---|
| 5 | 1, 2, 3, 4 | 4 |
| 6 | 1, 5 | 2 |
| 15 | 1, 2, 4, 7, 8, 11, 13, 14 | 8 |
Für RSA genügen zwei Regeln:
- Ist eine Primzahl, so ist .
- Sind Primzahlen und , so ist .
Der Satz von Euler besagt: Sind und teilerfremd, so gilt . Daraus folgt die Idee von RSA: Man zerlegt den Exponenten geschickt in zwei Faktoren – einen zum Verschlüsseln, einen zum Entschlüsseln.
- Rechnen Sie: , , .
- Bestimmen Sie , und . Prüfen Sie bei und die zweite Regel nach, indem Sie zusätzlich abzählen.
8.10.2Schlüsselerzeugung
- Zwei verschiedene Primzahlen und wählen.
- berechnen.
- berechnen.
- Ein mit wählen, das teilerfremd zu ist.
- Das bestimmen mit (erweiterter euklidischer Algorithmus).
Schritt 5 ist LK-Stoff: Der GK-Lehrplan verlangt das RSA-Verfahren ausdrücklich „ohne die Berechnung des privaten Schlüssels”, der LK dagegen fordert den euklidischen und den erweiterten euklidischen Algorithmus. Im Grundkurs bekommen Sie also vorgegeben und prüfen nur die Bedingung nach — rechnen Sie Schritt 5 trotzdem einmal mit, er ist der schönste Teil.
Öffentlicher Schlüssel: . Privater Schlüssel: . Die Zahlen , und werden vernichtet – wer sie kennt, kann berechnen.
8.10.3Durchgerechnetes Beispiel
Wir wählen und .
- Wahl von . Probe: , also teilerfremd.
- Gesucht ist mit . Euklidischer Algorithmus: und , der ggT ist also 1.
- Rückwärts eingesetzt: . Also ist . Probe: .
Öffentlicher Schlüssel , privater Schlüssel .
Verschlüsselung der Nachricht :
Entschlüsselung:
titel: RSA-Rechner p: 7 q: 13 e: 5 nachricht: 3
Im Bedienfeld können Sie und verändern. Probieren Sie größere Primzahlen und beobachten Sie zweierlei: Die Rechnung bleibt gleich schnell, der Angriff durch Faktorisieren wird dagegen rasch mühsam.
Die zweite Rechnung führt man nicht mit dem Taschenrechner aus – hat 52 Stellen. Man rechnet modular, also nach jedem Schritt den Rest, oder nutzt die schnelle Exponentiation:
# Modulare Exponentiation - in Python eingebaut
print(pow(3, 5, 91)) # 61 Verschluesseln
print(pow(61, 29, 91)) # 3 Entschluesseln8.10.4Sicherheit von RSA
Die Sicherheit steht und fällt mit dem Faktorisierungsproblem: Wer in und zerlegen kann, berechnet und daraus – RSA ist gebrochen. Ein schnelles Faktorisierungsverfahren ist bis heute nicht bekannt, aber es ist auch nicht bewiesen, dass es keines gibt.
In der Praxis benutzt man deshalb sehr große Zahlen: Schlüssel unter 2048 Bit gelten als überholt, empfohlen werden heute 3072 Bit oder mehr. Unser ist 7 Bit lang.
Ein Nachtrag, den ältere Darstellungen noch nicht enthalten: Ein hinreichend großer Quantencomputer könnte mit dem Algorithmus von Peter Shor (1994) in Polynomialzeit faktorisieren und damit RSA brechen. Solche Rechner existieren bisher nicht in nutzbarer Größe. Trotzdem werden seit 2024 schrittweise post-quanten-sichere Verfahren eingeführt, die auf anderen mathematischen Problemen beruhen; Messenger und Browser setzen sie bereits parallel zu RSA ein.
- Führen Sie die Schlüsselerzeugung für und mit vollständig durch und bestimmen Sie über den erweiterten euklidischen Algorithmus.
- Verschlüsseln Sie mit Ihrem Schlüssel aus Aufgabe 37 die Zahl
und entschlüsseln Sie das Ergebnis wieder. Kontrollieren Sie mit
pow(...). - Erklären Sie, warum und nach der Schlüsselerzeugung gelöscht werden müssen.
- Warum darf nicht größer als sein? Was folgt daraus für längere Nachrichten?
- Schreiben Sie ein Programm, das zu gegebenen , und den privaten Schlüssel berechnet und einen Text zeichenweise ver- und entschlüsselt.
8.11Signaturen, Hashfunktionen und die Praxis
Diesen Abschnitt als PDF (S. 25)
Verschlüsselung schützt die Vertraulichkeit. Für Integrität und Authentizität kommen zwei weitere Bausteine hinzu.
Hashfunktionen berechnen aus einer beliebig langen Nachricht einen kurzen Wert fester Länge, den Fingerabdruck. Sie sind Einwegfunktionen: Aus dem Hashwert lässt sich die Nachricht nicht zurückgewinnen, und es soll praktisch unmöglich sein, zwei Nachrichten mit gleichem Hashwert zu finden (Kollision). Ändert sich ein einziges Bit der Nachricht, ändert sich der Hashwert vollständig. Aktuell ist SHA-256; ältere Verfahren wie MD5 und SHA-1 sind gebrochen – für sie lassen sich Kollisionen gezielt erzeugen – und dürfen für Sicherheitszwecke nicht mehr verwendet werden.
Alles Weitere in diesem Abschnitt — digitale Signatur, Zertifikate und hybride Verfahren — steht nur im LK-Lehrplan („erläutern die Idee der digitalen Signatur anhand des RSA-Verfahrens”, „erläutern die Idee hybrider Verschlüsselungsverfahren”). Die Hashfunktion oben gehört dagegen zum Schutzziel Integrität und damit in beide Kurse.
Digitale Signaturen drehen die asymmetrische Idee um. Der Absender verschlüsselt den Hashwert seiner Nachricht mit seinem privaten Schlüssel. Jeder kann diesen Wert mit dem öffentlichen Schlüssel prüfen und mit dem selbst berechneten Hashwert vergleichen. Stimmen beide überein, stammt die Nachricht vom Besitzer des privaten Schlüssels und wurde nicht verändert – Authentizität und Integrität in einem Schritt.
Offen bleibt: Woher weiß ich, dass ein öffentlicher Schlüssel wirklich zu der Person gehört, die draufsteht? Diese Lücke schließen Zertifikate. Eine Zertifizierungsstelle bestätigt mit ihrer eigenen Signatur die Zuordnung von Schlüssel und Inhaber. Ihr Zertifikat ist wiederum signiert – bis hinauf zu Wurzelzertifikaten, die im Betriebssystem und im Browser hinterlegt sind.
Hybride Verfahren verbinden schließlich beide Welten, denn asymmetrische Verfahren sind um Größenordnungen langsamer als symmetrische. Beim Aufruf einer Webseite über HTTPS läuft deshalb Folgendes ab:
- Der Server sendet sein Zertifikat mit dem öffentlichen Schlüssel.
- Der Browser prüft die Signaturkette bis zu einem Wurzelzertifikat.
- Beide handeln asymmetrisch einen gemeinsamen, zufälligen Sitzungsschlüssel aus.
- Die eigentlichen Daten werden symmetrisch mit diesem Sitzungsschlüssel verschlüsselt (AES).
- Nach der Sitzung wird der Schlüssel verworfen.
Asymmetrisch wird der Schlüssel ausgetauscht, symmetrisch werden die Daten verschlüsselt. Das Schloss im Browser bedeutet genau das – und nicht, dass die Seite vertrauenswürdig ist.
- Erklären Sie, warum beim Signieren der Hashwert und nicht die ganze Nachricht verschlüsselt wird.
- Ein Angreifer findet zwei verschiedene Verträge mit identischem MD5-Hashwert. Beschreiben Sie, welchen Schaden er damit anrichten kann.
- Rufen Sie im Browser das Zertifikat einer beliebigen Webseite auf. Notieren Sie Aussteller, Gültigkeitsdauer und Schlüssellänge und ordnen Sie die Angaben diesem Kapitel zu.
- Begründen Sie, warum das Schloss-Symbol nichts über die Seriosität des Anbieters aussagt.
8.12Exkurs: Blockchain, Kryptowährungen und Mining
Diesen Abschnitt als PDF (S. 26–29)
Ein Exkurs im Wortsinn: Kein Lehrplan verlangt ihn. Er benutzt ausschließlich Bausteine, die Sie schon kennen — Hashfunktion und Signatur — und zeigt, was sich daraus bauen lässt.
Über kaum eine Technik ist so viel geschrieben worden wie über die Blockchain, und kaum eine ist so einfach. Sie besteht fast nur aus dem Baustein des vorigen Abschnitts: der Hashfunktion. Wer verstanden hat, was SHA-256 tut, versteht in zwanzig Minuten eine Blockchain.
8.12.1Das Problem: ein Kassenbuch ohne Kassenwart
Eine Überweisung ist nichts Körperliches. Sie ist eine Zeile in einem Buch: Lena zahlt 10 an Jonas. Damit das funktioniert, muss jemand das Buch führen, dem alle vertrauen — eine Bank. Sie verhindert, dass Lena dieselben 10 Euro zweimal ausgibt, und sie verhindert, dass jemand nachträglich Zeilen ändert.
Kann man ein Kassenbuch führen, das alle besitzen, in das jeder schreiben darf — und in dem trotzdem niemand nachträglich etwas ändern kann?
Die erste Hälfte ist leicht: Man schickt das Buch an alle. Die zweite ist das Problem. Wer eine Kopie hat, kann darin radieren.
8.12.2Die Kette
Der Trick ist eine Kette aus Hashwerten. Die Zeilen werden zu Blöcken zusammengefasst, und jeder Block enthält — neben seinen eigenen Daten — den Hashwert seines Vorgängers.
Was das bewirkt, sieht man am besten beim Versuch zu betrügen. Angenommen, jemand ändert in Block 1 den Betrag von 10 auf 100. Dann ändert sich der Hashwert von Block 1 vollständig:
vorher: 0000daf462463140…
nachher: 3448594b61837fab…
Block 2 trägt aber noch den alten Wert als Vorgänger-Hash. Die Kette passt nicht mehr zusammen, und zwar sichtbar für jeden, der nachrechnet. Wer die Fälschung verbergen will, muss auch Block 2 neu berechnen — und dann Block 3, und alle weiteren.
Eine Blockchain macht Änderungen nicht unmöglich. Sie macht sie auffällig: Wer einen alten Block ändert, muss die gesamte Kette dahinter neu bauen.
8.12.3Mining: Arbeit als Bremse
Neu bauen wäre für einen Rechner eine Sache von Millisekunden. Deshalb kommt eine zweite Zutat hinzu: Ein Block gilt nur dann als gültig, wenn sein Hashwert eine Bedingung erfüllt — zum Beispiel, dass er mit mehreren Nullen beginnt.
Am Hashwert selbst lässt sich nicht drehen; er ergibt sich aus dem Inhalt. Also baut man ein Feld in den Block ein, das sonst keinen Zweck hat: die Nonce (von number used once). Man zählt sie hoch und rechnet jedes Mal den Hash neu, bis die Bedingung zufällig erfüllt ist. Dieses Suchen heißt Mining.
Gehasht wird jeweils die Zeichenkette aus Datensatz, einem
senkrechten Strich und der Nonce, also
Lena zahlt 10 an Jonas|0, dann
Lena zahlt 10 an Jonas|1 und so fort. Gesucht ist die
kleinste Nonce, bei der der SHA-256-Wert mit einer bestimmten Zahl von
Nullen beginnt:
| Bedingung | gefundene Nonce | Versuche | Rechenzeit |
|---|---|---|---|
0… |
7 | 8 | unmessbar |
00… |
370 | 371 | unmessbar |
000… |
9 815 | 9 816 | 0,01 s |
0000… |
10 021 | 10 022 | 0,01 s |
00000… |
4 728 918 | 4 728 919 | 3,4 s |
Jede zusätzliche Null macht die Suche im Mittel sechzehnmal teurer — eine Hexadezimal stelle hat sechzehn mögliche Werte. Das echte Bitcoin-Netz arbeitet derzeit mit einer Bedingung, für die ungefähr Versuche nötig sind.
Prüfen ist billig, Finden ist teuer. Diese Asymmetrie ist der ganze Mechanismus: Ein einziger Hashdurchlauf bestätigt, was Billionen Versuche gekostet hat. Man nennt das Proof of Work — Arbeitsnachweis.
8.12.4Was eine Kryptowährung daraus macht
Eine Kryptowährung ist dieses Kassenbuch, verteilt auf viele tausend Rechner.
- Wer eine Überweisung tätigen will, signiert sie mit seinem privaten Schlüssel (Abschnitt 8.11). Die „Kontonummer” ist der zugehörige öffentliche Schlüssel. Es gibt kein Konto, keinen Namen, keine Bank — nur ein Schlüsselpaar.
- Die Rechner im Netz sammeln Überweisungen und suchen nach einer gültigen Nonce. Wer zuerst eine findet, verbreitet seinen Block, und alle anderen hängen ihn an.
- Als Lohn darf der Finder sich selbst eine festgelegte Menge neuer Münzen gutschreiben. Daher der Name Mining: Es sieht aus, als würde Geld geschürft, tatsächlich wird eine Rechenleistung bezahlt.
- Gehen zwei Ketten auseinander, gilt die Regel: Die längste Kette zählt. Wer eine Fälschung durchsetzen will, muss also schneller rechnen als der gesamte Rest des Netzes zusammen.
Das Problem war nie die Verschlüsselung — die gab es längst. Gelöst wurde die Frage, wie sich Fremde, die einander nicht trauen und keine gemeinsame Instanz anerkennen, auf eine Reihenfolge von Ereignissen einigen. Der Preis dafür ist, dass diese Einigung Rechenarbeit kostet, und zwar absichtlich.
8.12.5Was es kostet
Die absichtliche Verschwendung ist kein Nebeneffekt, sondern das Sicherheitsmerkmal — und sie hat eine Größenordnung. Das Bitcoin-Netz verbrauchte zuletzt Strom in der Größenordnung eines mittleren europäischen Staates, für eine Zahl von Überweisungen, die ein einzelner Bankrechner nebenbei abwickelt. Neuere Netze wie Ethereum sind deshalb auf Proof of Stake umgestiegen: Dort entscheidet nicht Rechenarbeit, wer den nächsten Block anhängen darf, sondern ein hinterlegtes Pfand.
Dazu kommen Eigenschaften, die je nach Standpunkt Vorzug oder Mangel sind:
| Eigenschaft | Folge |
|---|---|
| keine zentrale Stelle | niemand kann Konten sperren — und niemand hilft bei Verlust |
| Schlüssel statt Konto | wer den privaten Schlüssel verliert, verliert alles, endgültig |
| unumkehrbare Buchungen | kein Rückruf bei Irrtum oder Betrug |
| öffentliche Kette | jede Überweisung ist für immer einsehbar, pseudonym, nicht anonym |
| Kurs ohne Deckung | der Wert folgt allein Angebot und Nachfrage |
Die Technik ist nachprüfbar, die Bewertung ist es nicht. Dieser Exkurs erklärt, wie eine Blockchain funktioniert — ob sie für eine bestimmte Aufgabe das richtige Werkzeug ist, ist eine wirtschaftliche und politische Frage, keine informatische.
- Berechnen Sie mit einem Programm die SHA-256-Werte von
Informatikundinformatik. Wie viele Stellen stimmen überein? Welche Eigenschaft einer Hashfunktion zeigt sich daran? - Schreiben Sie ein Programm, das zu einem Text die kleinste Nonce
sucht, deren SHA-256-Wert mit
000beginnt. Gehasht wird<Text>|<Nonce>wie in der Tabelle oben; in Python genügtimport hashlib. - Erweitern Sie es auf vier und fünf Nullen und messen Sie die Zeit. Vergleichen Sie mit der Tabelle oben. Warum weichen Ihre Nonce-Werte nicht ab, Ihre Zeiten aber schon?
- Bauen Sie eine Kette aus drei Blöcken nach. Ändern Sie dann den Inhalt von Block 1 und zeigen Sie an den Hashwerten, dass die Kette bricht.
- Begründen Sie, warum ein Angreifer mit 10 % der Rechenleistung des Netzes eine Fälschung praktisch nicht durchsetzen kann.
- Erläutern Sie den Unterschied zwischen pseudonym und anonym am Beispiel einer öffentlichen Blockchain.
Können Sie in zwei Sätzen erklären, warum eine Blockchain ohne Proof of Work nichts nützt — und was genau die Nonce mit Sicherheit zu tun hat?
8.13Zusammenfassung
Diesen Abschnitt als PDF (S. 30)
- Verschlüsselung schützt die Vertraulichkeit; Integrität und Authentizität brauchen Hashfunktionen und Signaturen.
- Nach Kerckhoffs darf nur der Schlüssel geheim sein, nie das Verfahren.
- Klassische Verfahren kombinieren Transposition und Substitution. Monoalphabetische Substitution fällt der Häufigkeitsanalyse zum Opfer, polyalphabetische dem Kasiski-Test.
- Ein großer Schlüsselraum schützt nur vor Brute Force.
- Das One-Time-Pad ist beweisbar sicher, aber praktisch kaum einsetzbar.
- Symmetrische Verfahren (AES) sind schnell, haben aber das Schlüsselverteilungsproblem.
- Der Schlüsseltausch von Diffie und Hellman löst es ohne jedes Geheimnis auf der Leitung: Beide Seiten potenzieren modular, und das Potenzgesetz sorgt dafür, dass dasselbe herauskommt. Rückwärts steht der diskrete Logarithmus im Weg.
- Asymmetrische Verfahren (RSA) gehen einen Schritt weiter und lösen es über Einweg- und Falltürfunktionen.
- Kein Schlüsselaustausch sichert, mit wem man spricht — das ist die Lücke, in die sich ein Man-in-the-Middle setzt und die erst Zertifikate schließen.
- Die Praxis kombiniert beides: asymmetrischer Schlüsselaustausch, symmetrische Datenverschlüsselung, Signaturen und Zertifikate für die Echtheit.
Wiederholungsaufgaben
- Erläutern Sie an einem selbst gewählten Beispiel den Unterschied zwischen einem passiven und einem aktiven Angriff.
- Vergleichen Sie Cäsar-, Vigenère- und One-Time-Pad-Chiffre in einer Tabelle nach Schlüssellänge, Schlüsselraum und bekanntem Angriff.
- Ein Mitschüler behauptet: „Ein Verfahren mit Schlüsseln kann niemand knacken.“ Nehmen Sie begründet Stellung.
- Skizzieren Sie den Ablauf einer HTTPS-Verbindung und markieren Sie, an welcher Stelle symmetrisch und an welcher asymmetrisch gearbeitet wird.
- Erklären Sie, warum RSA mit zwar rechenbar, aber vollkommen unsicher ist.