Verschlüsseln und Codieren: Kryptologie

Die Kryptologie ist die Wissenschaft von Geheimschriften. Sie hat zwei Seiten: Die Kryptographie entwickelt Verfahren, um Nachrichten zu verschlüsseln, und die Kryptoanalyse versucht, sie ohne Schlüssel zu lesen. Das Wort kommt aus dem Griechischen: kryptos heißt „verborgen“. Heute steckt Kryptologie in jeder Messenger-App, in jedem Onlinekauf und auf jedem Strichcode. Mathematisch sind es erstaunlich einfache Ideen: Verschieben, Zählen und Rechnen mit Resten.

Du gehst den Weg von einfachen zu modernen Verfahren: von Caesar über Vigenère bis zum öffentlichen Schlüssel mit RSA. Als Grundlage helfen das Rechnen mit Resten (Modulare Arithmetik) und Primzahlen.

Codieren und Verschlüsseln: zwei verschiedene Dinge

Im Alltag werden beide Wörter oft verwechselt. Dabei ist der Unterschied wichtig, denn er entscheidet, ob ein Verfahren etwas geheim hält.

Ein wichtiger Grundsatz stammt von dem niederländischen Sprachwissenschaftler Auguste Kerckhoffs (1883): Ein Verfahren darf öffentlich bekannt sein, geheim muss nur der Schlüssel bleiben. Wer sich auf ein geheimes Verfahren verlässt, ist verloren, sobald jemand es entdeckt.

Prüfziffern: Fehler entdecken statt Geheimnisse hüten

Eine Prüfziffer ist eine zusätzliche Ziffer, die aus den anderen berechnet wird. Vertippt sich jemand, stimmt die Rechnung nicht mehr, und der Fehler fällt auf. Das ist Codieren mit Fehlererkennung. Wie die Rechnung mit Resten dahintersteckt, steht im Abschnitt Prüfziffern der Seite zur modularen Arithmetik. Hier siehst du ein Beispiel für den Strichcode EAN-13.

Die Prüfziffer findet viele Fehler, aber nicht alle. Ein Tippfehler an einer Stelle ändert die Summe um die Differenz der Ziffern mal 1 oder 3. Das ist nie ein Vielfaches von 10, also fällt der Fehler auf. Bei vertauschten Nachbarziffern ist die Lage anders, siehe das Kästchen unten.

Die Caesar-Verschlüsselung

Julius Caesar soll in vertraulichen Briefen jeden Buchstaben um drei Stellen im Alphabet verschoben haben, so berichtet es der römische Schriftsteller Sueton. Aus A wird D, aus B wird E und so weiter, und nach Z geht es wieder bei A weiter. Der Schlüssel ist die Zahl der Stellen (hier 3). Das Verfahren hängt mit dem römischen Alltag zusammen, ist aber heute nur noch ein Lernbeispiel.

Die Caesar-Chiffre hat einen großen Nachteil: Es gibt nur 25 sinnvolle Schlüssel. Wer eine Nachricht abfängt, probiert einfach alle durch. Das heißt Brute-Force-Angriff (rohe Gewalt) und dauert hier ein paar Minuten, ganz ohne Computer.

Häufigkeitsanalyse: Geheimschriften mit Zählen knacken

Es geht noch schneller. In jeder Sprache kommen manche Buchstaben viel öfter vor als andere. Im Deutschen ist das E mit etwa 17 Prozent der häufigste Buchstabe, es folgt das N mit etwa 10 Prozent, danach I, S, R, A und T mit je 6 bis 8 Prozent. Bei der Caesar-Chiffre wird jeder Buchstabe immer durch denselben anderen ersetzt, also ist der häufigste Buchstabe des Geheimtexts sehr wahrscheinlich das verschlüsselte E. Daraus liest du den Schlüssel ab. Diese Häufigkeitsanalyse beschrieb im 9. Jahrhundert der arabische Gelehrte al-Kindi, ein Beispiel für das Wissen der Mathematik der islamischen Welt.

Bei kurzen Texten kann die Vermutung danebenliegen. Dann probierst du den zweithäufigsten Buchstaben.

Die Vigenère-Chiffre: ein Schlüsselwort statt einer Zahl

Um die Häufigkeitsanalyse auszutricksen, verschlüsselt man nicht jeden Buchstaben gleich. Bei der Vigenère-Chiffre, benannt nach dem französischen Diplomaten Blaise de Vigenère (1523–1596), dient ein Schlüsselwort. Jeder Buchstabe des Schlüsselworts steht für eine Verschiebung (A = 0, B = 1, …), und die Verschiebungen werden der Reihe nach angewendet, bei Bedarf wiederholt. Beschrieben hatte ein ähnliches Verfahren schon 1553 der Italiener Giovan Battista Bellaso.

Genau das macht die Häufigkeitsanalyse schwer: Der Buchstabe E erscheint im Geheimtext nicht mehr als ein einziger Buchstabe. Das Verfahren galt über Jahrhunderte als „le chiffre indéchiffrable“, die unentzifferbare Chiffre. Dann fanden Mathematiker einen Weg: Charles Babbage knackte sie um 1854, ohne es zu veröffentlichen, der preußische Offizier Friedrich Kasiski veröffentlichte 1863 ein Verfahren. Es sucht Buchstabenfolgen, die sich im Geheimtext wiederholen, und leitet aus ihrem Abstand die Länge des Schlüsselworts ab. Dann zerfällt der Text in mehrere Caesar-Texte, die man einzeln mit Häufigkeiten knackt.

Öffentlicher Schlüssel und RSA

Bei allen bisherigen Verfahren haben Absender und Empfänger denselben Schlüssel (symmetrische Verfahren). Wie tauscht man ihn sicher aus, wenn man sich nie getroffen hat? Die Lösung kam in den 1970er Jahren: asymmetrische Verfahren mit zwei Schlüsseln. Der öffentliche Schlüssel zum Verschlüsseln darf jeder kennen, der private Schlüssel zum Entschlüsseln bleibt geheim. Man kann es sich wie einen Briefkasten vorstellen: Jeder kann einen Brief einwerfen, aber nur du hast den Schlüssel zum Öffnen.

Das bekannteste Verfahren ist RSA, benannt nach Ron Rivest, Adi Shamir und Leonard Adleman, die es 1977 veröffentlichten. Es rechnet mit Resten und Potenzen. So funktioniert es im Kleinen:

1. Wähle zwei Primzahlen, hier p = 3 und q = 11. Ihr Produkt ist n = 33.
2. Berechne (p − 1) · (q − 1) = 2 · 10 = 20.
3. Wähle eine Zahl e, die zu 20 teilerfremd ist, hier e = 3. Der öffentliche Schlüssel ist (n, e) = (33, 3).
4. Bestimme d mit e · d ≡ 1 (mod 20). Wegen 3 · 7 = 21 ist d = 7. Der private Schlüssel ist d = 7.
5. Verschlüsseln: Aus einer Zahl m (kleiner als 33) wird c = m^e mod n.
6. Entschlüsseln: Aus c wird m = c^d mod n.

Dass das immer klappt, folgt aus dem Satz von Euler, einer Verallgemeinerung des kleinen Satzes von Fermat. Wichtig ist die Sicherheit: Aus n = 33 erkennt jeder sofort 3 · 11 und kann d ausrechnen. Echte Schlüssel verwenden Primzahlen mit hunderten Stellen. Das Produkt zweier solcher Zahlen kann ein Computer in Sekundenbruchteilen bilden, es wieder zu zerlegen, dauert nach heutigem Wissen viel zu lange (Primzahlen und Verschlüsselung). Eine ausführlichere Geschichte mit größeren Zahlen erzählt der Beitrag Primzahlen im Handy: wie Verschlüsselung funktioniert.

Typische Fehler

Übungen

Geschichte: von Caesar bis zur Enigma

Geheimschriften sind uralt. Caesar kennt man wegen seiner Verschiebung, die erste bekannte Anleitung zum Knacken stammt von al-Kindi im 9. Jahrhundert. In der Renaissance entstanden Verfahren mit mehreren Alphabeten, im 19. Jahrhundert entzifferten Babbage und Kasiski sie.

Im 20. Jahrhundert wurde Verschlüsselung maschinell. Die deutsche Enigma verwendete drehbare Walzen und galt als sicher. Polnische Mathematiker um Marian Rejewski brachen die frühe Enigma ab 1932, und in Großbritannien setzte Alan Turing in Bletchley Park diese Arbeit fort.

Mit dem Computer kam 1976 der nächste Schritt. Whitfield Diffie und Martin Hellman zeigten, wie man einen Schlüssel über eine offene Leitung vereinbart, ein Jahr später folgte RSA. Britische Geheimdienstmitarbeiter hatten ähnliche Ideen schon früher, das wurde erst 1997 bekannt. Die Zahlentheorie, die dahintersteckt, ist älter: Pierre de Fermat, Leonhard Euler und Carl Friedrich Gauß legten die Grundlagen, ohne an Verschlüsselung zu denken.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Kryptologie
• Wikipedia: Caesar-Verschlüsselung
• Wikipedia: Häufigkeitsanalyse (al-Kindī als Entdecker)
• Wikipedia: Vigenère-Chiffre
• Wikipedia: RSA-Kryptosystem
• R. L. Rivest, A. Shamir, L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM 21 (1978), S. 120–126.
• Simon Singh: Geheime Botschaften. Die Kunst der Verschlüsselung von der Antike bis in die Zeiten des Internet, Hanser, München.