Home > Kryptographie > Geschichte
Kryptographie
Seit Menschengedenken gibt es das Bedürfnis, vertrauliche Mitteilungen so zu verbergen, dass sie für unbefugte Augen unlesbar bleiben. Der einfachste Weg besteht darin, eine Nachricht an einem geheimen Ort zu verstecken, doch dies kann ja nun nicht der Weisheit letzter Schluss sein; denn wenn jemand die Mitteilung findet, ist das ganze "System" bereits gebrochen. Dies dachte sich wahrscheinlich auch die Regierung von Sparta vor 2500 Jahren und führte die sog. Skytale ein. Trotz der Einfachheit dieser Chiffrierung erfüllte die Skytale zu damaligen Zeiten sicherlich ihren Zweck – heute wäre sie schlichtweg nutzlos (wenn man nicht gerade seine Daten vor der kleinen Schwester schützen will ...). Doch die Skytale weist bereits einen guten kryptographischen Ansatz auf, und heute findet die Transposition, auf dessen Sicherheit sich die Skytale gründet, in modernen Verfahren (in verbesserter Form, versteht sich) Verwendung. Wie die Substitution ist sie ein grundlegender Baustein komplizierter Computeralgorithmen wie z. B. DES. Auch Imperator Gaius Julius Caesar soll auf Verschlüsselung zurückgegriffen haben, als es um private Briefe an Cicero und Bekannte ging. Hier können Sie mehr darüber nachlesen. Ein guter Ansatz war die Chiffrierung Vigenères aus dem Jahre 1586, auf der das unknackbare One-Time-Pad aufbaut. Hier gilt: Je länger und "zufälliger" der Schlüssel ist, desto schwerer wird ein Angriff auf das Verfahren. Sind Schlüssel und Klartext gleich lang und entstammt der Schlüssel einem "echten" Zufallsprozess, ist es unmöglich, das System zu brechen (vorausgesetzt, der Schlüssel wird nur ein einziges Mal benutzt).
Kryptographische Methoden kamen in zahllosen historischen Schlachten zum Einsatz, und man bemühte sich, die bekannten Techniken zu verbessern. Der alte Kampf zwischen Kryptographen und Kryptoanalysten motivierte dazu, neues Terrain auf dem Gebiet zu erforschen. Die verwendeten Methoden waren jedoch fast ausnahmslos alle recht einfache Verfahren, und so ist es nicht verwunderlich, dass sie oft geknackt werden konnten. Um den gnadenlosen Analysten ein Schnippchen zu schlagen, modifizierte man bekannte Verfahren, indem man einige Variablen änderte, das Grundprinzip jedoch beibehielt. Mehr dazu finden Sie in der diversen Literatur.
Wegbereiter der modernen Kryptographie war Kerckhoffs von Nieuwenhof, welcher bekundete, dass die Sicherheit eines kryptographischen Systems nicht von der Geheimhaltung des Algorithmus abhängen darf, sondern sich allein auf die Geheimhaltung des Schlüssels gründen muss. Dies ist ein wichtiges Prinzip, das heute als selbstverständlich gilt. Damit sichergestellt werden kann, dass ein Verfahren mit größter Wahrscheinlichkeit sicher ist, werden fast alle Algorithmen der Öffentlichkeit zugänglich gemacht – angefangen bei DES 1977. So können alle Kryptographen der Welt das Verfahren sorgfältig prüfen und testen. Werden nach einigen Jahren der Kryptoanalyse keine gravierenden Mängel entdeckt, wird es vermutlich als sicher anerkannt. Das heißt natürlich nicht, dass die Chiffrierung absolut sicher ist – irgendwann könnten bisher unentdeckte Schwachstellen gefunden werden, oder neuartige Analyse-Methoden könnten ein Knacken des Verfahrens ermöglichen. Seien Sie sich dessen bewusst!
In den zwanziger Jahren des 20. Jahrhunderts wurden mit sog. Rotormaschinen Verfahren entwickelt, die Chiffrierung zu automatisieren. Die Maschine besteht aus einer Tastatur und verschiedenen Walzen oder Rotoren, mit deren Hilfe man Substitution durchführen konnte. Die Anordnung der Walzen wurde ständig geändert, so dass Gegnern, die der Maschine habhaft werden konnten, potentielle verschlüsselte Nachrichten immer noch nicht zu knacken vermochten.
Bekannt geworden ist z. B. der legendäre "room 40", in den britische Kryptologen während des Ersten Weltkriegs einzogen. Als den Briten ein Signalbuch der deutschen Marine in die Hände fiel und die USA in den Krieg eintraten, entwickelte sich die Kryptographie als kriegsentscheidend.
Auch im Zweiten Weltkrieg nahm die Kryptographie einen hohen Stellenwert ein und beeinflusste den Ausgang des Krieges. Zur Verschlüsselung ihrer Kommunikation verwendeten die Deutschen die sog. Enigma (griech.: Rätsel), eine aus mehreren Walzen zusammengesetzte Rotormaschine. Die englischen Kryptologen waren nicht untätig und machten sich 1939 – diesmal im Betchley Park – an die Arbeit, allen voran der geniale Mathematiker Alan Turing. Er und seine Kollegen ersannen Methoden zum Brechen der mit den Enigmas verschlüsselten Nachrichten. Der Erfolg der Briten hinsichtlich der Enigmas währte jedoch nicht ewig, da ab 1943 neue Enigmas eingesetzt wurden und das Spiel von vorne begann. Im Gegensatz zu den Deutschen und den Japanern, die übrigens mit der später von den Amerikanern geknackten Purple ihre Nachrichten geheimzuhalten suchten, setzten die USA auf die Sprache der nordamerikanischen Ureinwohner, der Navahos. Sie zogen damit Vorteil aus ihren natürlichen Ressourcen, die allein ihnen zur Verfügung standen, da kein Deutscher oder Japaner der Sprache mächtig war. Zudem ist die Sprache äußerst komplex und für Erwachsene schwierig zu lernen. So arbeiteten schließlich über 400 Navahos in der amerikanischen Militärkommunikation.
Seitdem hat sich die Kryptographie zur eigenständigen Wissenschaft entwickelt. Sie mag wie ein bloßes Derivat der Mathematik anmuten (Korrelationen lassen sich wohl kaum abstreiten), aber sie ist noch mehr als das: Sie ist auch mit Strategien und "eiskalter Kalkulation" verbunden. Man bemüht sich zwar redlich, sichere kryptographische Verfahren zu entwickeln, aber es ist eben nicht nur das, was Kryptologie ausmacht: Wie kann ich Wege finden, ein System zu brechen? Wie kann ich sichere Systeme entwickeln? Kryptologie zeichnet sich auch durch den Versuch aus, Mittel und Wege zu finden, Krypto-Systeme vor Angriffen zu schützen – oder genau solche Angriffe zu finden! Der Kampf zwischen Kryptographen und Kryptoanalysten bedarf einiger Strategien und eiskaltem Kalkül. Denn sehr oft gestaltet sich die Praxis sehr viel schwieriger zu realisieren als von der Theorie vorhergesagt. Sinnvolle Sicherheitskonzepte sind also vonnöten, die auch auf die Theorie Einfluss nehmen sollten. Das alles ist auch Teil der Kryptologie – eben nicht nur Mathematik. Und schließlich haftet dieser Wissenschaft auch der Hauch des Mysteriösen an – man denke nur an James Bond, Mission Impossible und Konsorten. Ist es nicht das, was ihren wahren Reiz ausmacht?
Der sog. Quantenkryptographie gereicht die natürliche Ungewissheit der Quantenwelt zum Nutzen. Jeder Abhörversuch des Kommunikationskanals würde die Übertragung stören. Warum? Nun, in der Welt der Quanten kann sich ein Teilchen gleichzeitig an mehreren Orten befinden, wobei es für jeden Ort eine gewisse Wahrscheinlichkeit gibt. Der Heisenbergschen Unschärferelation zufolge kann man jedoch nicht alle Aspekte eines Teilchens zur gleichen Zeit messen (Ort und Geschwindigkeit). Es lässt sich also immer nur eine Größe auf einmal messen; es gibt eine grundlegende Unschärfe, die sich nicht vermeiden lässt. Eben diese Unschärfe kann man sich jedoch zum Generieren geheimer Schlüssel zunutze machen. In einem Kommunikationsmodell tauschen Alice und Bob Photonen (Lichtquanten) aus. Bob arbeitet mit sog. Filtern, die nur Photonen mit einer bestimmten Polarisation (Richtung, in der die Photonen schwingen) durchlassen. Zunächst sendet Alice Bob eine Reihe von Photonstößen zufälliger Polarisation. Bob kann seinen Polarisationsdetektor nun entweder auf gerade Polarisationen oder schräge Polarisationen ausrichten, jedoch nicht auf beides. Entspricht die Einstellung seines Filters der Polarisation der Photonen, so kann er feststellen, in welche Richtung die Photonen polarisiert wurden. Stellt er den Detektor so ein, dass er schräge Polarisation misst, die Photonen sind aber gerade polarisiert, erhält er zufällige Ergebnisse. Danach übermittelt Bob Alice seine benutzten Detektor-Einstellungen. Alice teilt ihm anschließend mit, welche Einstellungen korrekt waren. Sie behalten nur diese Polarisationsmessungen. Auf diese Weise lassen sich Schlüssel für symmetrische Algorithmen oder One-Time-Pads generieren, wenn die Ergebnisse in Bits konvertiert werden. Jeglicher Versuch eines Lauschers, die Kommunikation abzuhören, verändert die Polarisation der Photonen. Denn auch der Lauscher kann die Polarisation nur raten und seine Filter dementsprechend einstellen. Um Lauschangriffe zu vereiteln, vergleichen Alice und Bob daher einige Bits der Folge. Sind sie identisch, so können sie sich ziemlich sicher sein, dass sie nicht belauscht wurden. Sie verwerfen die zum Vergleich benutzten Bits und verwenden nur den Rest. Sind die Bits nicht identisch, wissen sie immerhin, dass sie belauscht wurden.
Diese Art der Kryptographie ist faszinierend, da es nicht möglich ist, passiv zu lauschen. Jede Messung der Polarisation beeinflusst wiederum die Polarisation der Photonen selbst, so dass die Kommunikation zwangsläufig gestört wird. Es gibt bereits ein funktionierendes Modell quantenbasierter Schlüsselverteilung.
Auf Grundlage der Forschung im Bereich der Quantenmechanik sind nicht nur Protokolle zur absolut sicheren (One-Time-Pad-ähnlichen) Ver- bzw. Entschlüsselung möglich geworden, sondern auch sog. Quantencomputer, die zum Brechen von modernen Verfahren wie RSA eingesetzt werden könnten. RSA findet mittlerweile in unzähligen Computer-Applikationen Verwendung. Die Sicherheit von RSA beruht bekanntlich auf der Schwierigkeit, das Produkt zweier Primzahlen p und q zu faktorisieren; das heißt, die Entschlüsselung ohne Kenntnis der Faktoren p und q ist ungleich schwerer als die nur relativ wenige Rechenoperationen erfordernde Verschlüsselung. Mit Hilfe der Quantenkryptographie versucht man nun, einen Algorithmus zu entwerfen, der eine Primzahl genauso leicht ermitteln kann wie zwei Faktoren, deren korrekte Multiplikarion eben diese Zahl ergeben würde. Gelänge es, eine derartige Möglichkeit zu finden, wären Verfahren wie RSA, denen das Faktorisierungs-Problem zugrunde liegt, nicht mehr ausreichend für das Verschlüsseln geheimer Botschaften.
Ein solcher Quantencomputer – wenn er denn je gebaut werden wird – macht sich ebenfalls die Prinzipien der Quantenmechanik zunutze. Ein Quanten-Teilchen wie ein Photon z. B. kann sich gleichzeitig in einer Vielzahl von Zuständen befinden; es verhält sich sowohl als Welle als auch als Teilchen, jedoch kann immer nur ein Zustand gemessen werden, da die Messung selbst das Photon beeinflusst. Ein Quantencomputer besitzt nun eine interne Wellenfunktion, die eine Überlagerung einer Kombination der möglichen Grundzustände ist. Berechnungen wandeln die Wellenfunktion um, wobei die gesamte Menge der Zustände in einer einzigen Operation geändert wird. Im Folgenden möchte ich Ihnen diese Vorgänge etwas genauer erklären.
Ein herkömmlicher Computer speichert Informationen in Bits, der kleinstmöglichen Informationseinheit. So wird die Zahl 13 beispielsweise als 1101 dargestellt, die Zahl 15 als 1111 und die Zahl 167 als 101100111. Da dieses Binärsystem, auf dem die Berechnungen mit Bits basieren, ein System zur Basis 2 ist (wie auch unser Dezimalsystem ein System zur Basis 10 ist), werden zur Darstellung einer Zahl N log2N Ziffern benötigt. Um jedoch sämtliche Zahlen von 0 bis N darzustellen, benötigt man N Speicherplätze mit einer Länge von je log2N Ziffern. Daher braucht man für die Speicherung aller Zahlen von 0 bis 255 (d. h. von 0 bis 28 − 1) 256 Speicherplätze à 8 Bit Länge (die "0" als eigene Zahl muss ebenfalls berücksichtigt werden; somit ergeben sich 256 Möglichkeiten für die Zahlen im Bereich 0 bis 255, und log2256 ist 8). Ein Quantencomputer dagegen kann alle 256 Zahlen mit nur einem Speicherplatz von 8 Bit Länge darstellen. Die Aneinanderreihung von Speicherplätzen für Bits bei herkömmlichen Computern nennt man Register; Register aus Qubits heißen entsprechend Quantenregister.
Ein sog. Quantenbit oder Qubit basiert auf dem Superpositionsprinzip in der Quantentheorie. Ein Gedankenexperiment auf Grundlage dieses Superpositionsprinzips ist das Paradoxon von Schrödingers Katze. Hierbei wird eine Katze zusammen mit einer Apparatur, welche von radioaktivem Zerfall gesteuert wird, in eine Kiste gesperrt, wobei die Apparatur die Katze mit einer Wahrscheinlichkeit von 50% innerhalb einer Stunde tötet. Tatsache ist, dass die Katze entweder tot oder lebendig ist, egal ob wir in die Kiste schauen oder nicht. Die Frage ist aber nun, in welchem sich die Katze befindet, wenn wir nicht in die Kiste schauen – analog zur Frage nach dem quantenmechanischen Zustand eines Systems, solange man keine Messung an ihm vornimmt. Nach den Prinzipien der Quantenmechanik befindet sich die Katze theoretisch in einem Überlagerungszustand zwischen tot und lebendig; tatsächlich ist die Katze mit einer gewissen Wahrscheinlichkeit tot und mit einer gewissen Wahrscheinlichkeit lebendig (Wahrscheinlichkeitsspanne). Erst wenn wir die Kiste öffnen, d. h. prüfen bzw. "messen", können wir mit 100%-iger Wahrscheinlichkeit eine tote oder lebendige Katze feststellen.
Selbstverständlich ist "Schrödingers Katze" ein reines Gedankenexperiment und lässt sich nicht auf die Realität übertragen. Erstens nämlich gibt es jenen Zustand zwischen tot und lebendig nicht, und zweitens wurden hier unzulässigerweise und ohne Überlegung die quantenmechanischen Gesetze auf ein makroskopisches Objekt übertragen.
Dennoch ist dieses Paradoxon eine Analogie für viele Phänomene in der Quantenmechanik. Übertragen auf die Idee der Qubits ist die Katze ein eben solches Qubit, welches die Zustände 0 (tote Katze) und 1 (lebendige Katze) annehmen kann. So wie wir in der Theorie und ohne Berücksichtigung weiterer Überlegungen bezüglich makroskopischer Objekte davon ausgehen, dass sich die Katze in einem Überlagerungszustand befindet, d. h. sowohl tot als auch lebendig ist, so befindet sich auch das Qubit sowohl im Zustad 0 als auch im Zustand 1. Auf diese Weise wurden zwei Zahlen (0 und 1) dargestellt, die nur ein Qubit verwenden. Ein klassisches Bit hingegen würde 2 Bits erfordern, jeweils eines für den Zustand "tot" (0) und ein anderes für den Zustand "lebendig" (1).
Der Quantencomputer manipuliert die Bits so, dass die Wahrscheinlichkeit des korrekten Ergebnisses im Verlauf der Berechnung zunimmt. Für das Speichern der Information in einem von der Umgebung relativ isolierten Quanten-Zustand bietet sich die Verwendung des sog. Spins (Drehimpuls eines Teilchens) an – was in der Quantenmechanik einer Drehung der Spitze entspricht –. Auf diese Weise können Informationen für wenige Sekunden gespeichert werden. Der Spin bietet den Vorteil, dass kleine Fluktuationen (Schwankungen) der Umgebung den Quanten-Zustand und damit die Quanten-Kohärenz des Systems kaum beeinträchtigen.
Was ist die "Quanten-Kohärenz"? Damit ist in erster Linie das Ausmaß der Wechselwirkung zwischen Computer und Umgebung gemeint. Da sich ein Elementarteilchen in mehreren Zuständen befinden kann, fallen, wenn die Quanten-Zustände mit der Umgebung interagieren, Informationen über Zustände wie die Teilchendrehung oder die Position der Atome aus. Dadurch verlieren die Quanten-Zustände ihre Kohärenz und die Fähigkeit der Überlagerung; das ist sehr nachteilig, da Überlagerungsmuster wichtige Informationen über die Konfiguration der Quantenbits erhalten. Die meisten Theorien der Quantenberechnung basieren auf eben dieser Überlagerungsfähigkeit der Quanten-Zustände, deshalb konzentrieren sich die wissenschaftlichen Forschungen auf die Aufrechterhaltung der Kohärenz.
(Zitiert nach: Wrixon, Fred: Codes, Chiffren & andere Geheimsprachen, S. 293ff.)
Den ersten praktisch anwendbaren Algorithmus für den Quantencomputer entwickelte 1994 Peter Shor von AT&T Bell Labs. Dieser Algorithmus vermag eine Zahl schneller in ihre Primfaktoren zu zerlegen als herkömmliche Faktorisierungs-Algorithmen.
Bei diesem Algorithmus werden alle möglichen Werte aus einem Register in einer Superposition aller möglichen Werte berechnet. Zwar kann das Ergebnis nun nicht durch eine Messung ermittelt werden – diese würde nur zufällige Werte zurückliefern –, mit der sog. Diskreten Fourier-Transformation kann jedoch das korrekte Ergebnis ermittelt werden.
Die Berechnungszeit dieses Algorithmus nimmt deutlich langsamer zu als die des besten klassischen Verfahrens. Während sich herkömmliche superschnelle Computer, die vielleicht eine Billion (1012) Divisionen pro Sekunde berechnen können, bräuchten mit dem Verfahren der versuchsweisen Division (der einfachste Faktorisierungs-Algorithmus, d. h. man probiert alle Zahlen von 1 bis Wurzel N) für eine 100-stellige Zahl weitaus länger als die geschätzte Dauer des Universums. Der Quantencomputer hingegen könnte diese Zahl in einer verhältnismäßig kurzen Zeit faktorisieren.
Somit leuchtet ein, dass der Quantencomputer die Sicherheit von RSA und allen Verfahren, deren Sicherheit auf dem Faktorisierungsproblem beruht, bedroht. Warten wir ab, ob er irgendwann einmal gebaut wird. Eine Erfahrung wär's wert ... ;-)
Weitere Anwendungsmöglichkeiten des Quantencomputers sind z. B. Suchalgorithmen. Während ein herkömmlicher Computer zum Durchsuchen einer Liste mit N Einträgen gewöhnlich N/2 Versuche benötigt, braucht ein Quantencomputer nur Wurzel N Schritte. Dies ist der sog. "Grover-Iteration" zu verdanken, bei der im Quantenregister die Wahrscheinlichkeit für das richtige Ergebnis erhöht, die der falschen aber verringert wird. So kann man durch einfaches Auslesen das richtige Ergebnis erhalten.
Sollte ein Quantencomputer mit ausreichend vielen Qubits jemals gebaut werden, so wird er natürlich nicht den normalen PC ersetzen, sondern für spezielle Anwendungen in der Wissenschaft und Forschung eingesetzt werden. Wie immer sind aber auch hier Vorhersagen schwer zu treffen; wer hätte schon vor 50 Jahren an die heutige Allgegenwart der Computer gedacht? ...
(Zitiert nach: Bezold, Matthias, siehe http://www.quantencomputer.de.)
News zum Thema Quantencomputer:
21.12.2001 Durchbruch: Erste Implementation eines Quanten-Algorithmus
Am IBM Almaden Research Center in San Jose wurde der erste Quantenalgorithmus implementiert. Mithilfe der NMR-Technik gelang es den Wissenschaftlern, mit dem Faktorisierungsalgorithmus von Shor mit einem 7-Bit-Quantencomputer die Zahl 15 in ihre Faktoren 3 und 5 zu zerlegen. Dazu verwendeten Sie 1018 Moleküle, mit denen sich jeweils 7 Qubits darstellen lassen.
Dieser Durchbruch kam schneller als von vielen erwartet, zeigt er doch, dass sich ein Quantencomputer wirklich für die Lösung praktischer Probleme einsetzen läßt. Die Kryptographie basiert z.B. darauf, dass sich große Zahlen mit klassischen Rechnern nicht faktorisieren lassen. Es dürfte allerdings noch einige Zeit dauern, bis ein Quantencomputer mit 1024 Bits rechnen kann - falls dies überhaupt einmal möglich sein sollte.
Quelle: www.quantencomputer.de
Möchten Sie mehr über Quantenmechanik erfahren? Buchtipp: Das Quantenuniversum von Tony Hey und Patrick Walters (Spektrum Verlag, ISBN 3-8274-0315-4).
Mehr über Quantencomputer im Internet:
 Zurück |
nach oben |
 |
 Übersicht |
Weiter  |
Letzte Änderung: 28.03.2002
© 2002 by Christian Thöing