Die Autoren des englischen Artikels sind Graeme L. Cohen (University of Technology, Sydney), Seven Galbraith (University of Auckland) und Edoardo Persichetti (University of Auckland).
Vom Englischen ins Deutsche übersetzt von Anna-Katharina Roos (Universität Würzburg)
Wie können wir auf eine sichere Art und Weise unsere Kreditkarten-Informationen über das Internet oder per Handy versenden, wenn andere unsere Mitteilungen abfangen können? Wie können wir Software Updates vertrauen, obwohl wir wissen, dass Computerviren nichts Ungewöhnliches mehr sind? Kryptographie (die Untersuchung der Techniken zur sicheren Kommunikation in der Gegenwart von feindlichen Attacken) gibt Antworten auf diese Fragen und die Mathematik liefert ihre Grundlage.
Kurzer geschichtlicher Hintergrund
Sichere Kommunikation ist seit Jahrentausenden wichtig gewesen: Es gibt Belege, dass Julius Cäsar eine einfache Kryptographie ein Methode verwendet hat, um sich mit seinen Generälen zu verständigen. Dieses Verfahren ist bekannt als „Cäsar Chiffre“ und besteht aus einer Verschiebung der Buchstaben einer Nachricht um eine bestimmte Positionsanzahl um ein neues Schriftstück, das Geheimtext genannt wird, zu erhalten. Die ursprüngliche Nachricht kann beim Empfänger wieder hergestellt werden durch Invertieren dieser Operation, das heißt, durch das Zurückverschieben der Buchstaben des erhaltenen Geheimtextes um dieselbe Anzahl an Positionen.
Die entscheidende Idee dabei ist, dass sowohl der Sender als auch der Empfänger eine geheime Größe kennen (in diesem Fall, die Anzahl der zu verschiebenden Positionen), von der angenommen wird, dass sie für die Leute, die die Nachricht versuchen zu abzufangen, unbekannt ist. Die geheime Größe ist der sogenannte Schlüssel. Im Fall des Cäsar Chiffre ist der Schlüssel eine Zahl zwischen und . Der Verschlüsselungsalgorithmus hat als input eine Nachricht und einen Schlüssel , zum Beispiel (HELLO)=KHOOR. Der Entschlüsselungsalgorithmus hat als input einen Geheimtext und denselben Schlüssel, zum Beispiel (KHOOR)=HELLO.
Kryptosysteme, bei denen derselbe Schlüssel für die Ver- und Entschlüsselung verwendet wird, werden symmetrische Verfahren bzw. private-key Verfahren genannt.
Die Cäsar Chiffre selbst ist viel zu einfach um in der heutigen Welt sicher zu sein, aber es gibt moderne symmetrische Verschlüsselungsverfahren, die gegenwärtig in vielen Situationen verwendet werden; ein Beispiel ist der sehr bekannte AES, einer der Standards der US Regierung, um Daten zu übertragen. Diese Verfahren sind effizient und sicher, aber sie bringen ein Problem mit sich: Sowohl Sender als auch Empfänger müssen bereits ein Geheimnis teilen. Wie können wir sicher über das Internet kommunizieren mit Menschen, die wir noch nie getroffen haben?
Ein beeindruckendes Konzept, das public-key Kryptographie genannt wird und 1976 in der Veröffentlichung „ New directions in cryptography“ von Whitfield Diffie und Martin Hellman angestoßen wurde, löst dieses Problem. In dessen Ansatz gibt es anstatt der Nutzung desselben Schlüssels für die Ver- und Entschlüsselung einen öffentlichen Schlüssel, der allen möglichen Nutzern zur Verfügung steht, und einen privaten Schlüssel, der geheim bleibt für den einzelnen Nutzer. Mit anderen Worten kann jeder eine Nachricht versenden, aber nur eine Person kann sie empfangen: Jeder kann einen Brief durch den Briefschlitz werfen, aber nur die Person, die den Briefkastenschlüssel hat, kann den Brief herausholen. Um sicher mit Alice zu kommunizieren, muss man ihren öffentlichen Schlüssel heraussuchen und ihn anwenden, um einen Geheimtext zu generieren. Nur Alice kann den Geheimtext entschlüsseln, da nur sie den privaten Schlüssel kennt.
Public-key Kryptosysteme müssen auf rechnerischen Problemen basieren, die schwer zu lösen sind. Die Mathematik stellt solche Probleme zur Verfügung. Zum Beispiel ist das RSA-Kryptosystem, das gestützt ist auf die Schwierigkeit die Primfaktoren einer sehr großen ganzen Zahl zu finden.
Etwas Zahlentheorie
Bevor das sehr bekannte RSA Verschlüsselungsverfahren beschrieben wird, müssen wir einige Ergebnisse der Zahlentheorie erarbeiten. Dies erfordert eine gewisse Vertrautheit mit dem binomischen Lehrsatz und modularer Arithmetik.
In der modularen Arithmetik versammelt man ganze Zahlen in Klassen bezüglich ihres Restes nach dem Teilen durch eine bestimmte Zahl , welches modulo genannt wird. So ist zum Beispiel, falls , in der Klasse von , und , und sind alle in derselben Klasse. Man schreibt und . Man sieht leicht, dass es, wenn man mit modulo 7 arbeitet, nur 7 mögliche Klassen gibt, die durch repräsentiert werden. Es ist möglich, Addition und Multiplikation modulo 7 durchzuführen, indem man einfach das Ergebnis reduziert, nachdem man die Operation auf herkömmliche Art ausgeführt hat, so ist und . Man bemerkt, dass für dann ein Vielfaches von ist.
Seien und Primzahlen, und sei eine ganze Zahl, die kein Vielfaches von oder ist. Wir werden nun zeigen, dass die Formel gilt. Diese Formel ist ein Spezialfall des Satzes von Euler-Fermat.
Der Beweis fängt mit der Formel des Binomialkoeffizienten an:
mit als ganzer Zahl . Mit
folgt, dass ein Teiler von sein muss, da die rechte Seite teilt aber nicht .
Dann ist für beliebige ganze Zahlen und , mit dem binomischen Lehrsatz,
Nimmt man eine weitere ganze Zahl hinzu, ergibt sich
Auf diese Art erhält man für beliebige ganze Zahlen , , …, ,
Setzt man nun , erhält man
Diese Gleichung drückt aus, dass ein Vielfaches von ist. Da nicht teilt und eine Primzahl ist, folgt dass
Nun erhöht man den Exponenten auf beiden Seiten der Kongruenz um dem Faktor :
Wiederholt man diesen Schritt mit an Stelle von , erhält man
Dementsprechend gibt es ganze Zahlen und , so dass
somit . Dann teilt (da und verschiedene Primzahlen sind), und damit für ganze Zahlen . Nun weiß man , oder
Dies vervollständigt den Beweis.
Das RSA-Kryptosystem
Das Akronym RSA steht für Rivest, Shamir und Adleman, die dieses Verfahren zuerst 1977 aufgestellt haben. Es funktioniert folgendermaßen.
Wählen Sie zunächst zwei verschiedene Primzahlen und . Berechnen Sie und . Wählen Sie eine ganze Zahl zwischen und beliebig, aber so, dass und teilerfremd sind. Der öffentliche Schlüssel ist das Tupel . Der private Schlüssel , den der Sender geheim halten wird, wird berechnet so dass , das ist die Zahl, so dass (Diese erhält man leicht, wenn man den euklidischen Algorithmus verwendet). Nehmen Sie zum Beispiel , , und .
Nachrichten sind im RSA -Verfahren ganze Zahlen , so dass . Es könnte anfangs nicht klar sein, wie man die Textnachrichten mit einem Verfahren, das ganze Zahlen verwendet, verschlüsselt. Jedoch sind Kryptographie Systeme auf Computern implementiert und dort sind alle Dokumente reine Binärdaten, die durch die Verwendung von ganzen Zahlen kodiert werden können.
Es gibt folgenden Verschlüsselungsprozess. Stellen Sie sich vor Bob möchte eine Nachricht an Alice senden. Er sucht Alices öffentlichen Schlüssel heraus, berechnet , und sendet an Alice. Um den Geheimtext zu entschlüsseln, benutzt Alice den privaten Schlüssel , indem sie berechnet.
Es ist wichtig zu betonen, dass, obwohl , und groß sind, es möglich ist zum Beispiel mit Hilfe einer Technik, die modulare Exponentiation genannt wird, effizient zu berechnen.
Die Entschlüsselung funktioniert, da für ganze Zahlen , und wie zuvor gezeigt wurde
(In der Praxis kann der Fall, wenn ein Vielfaches von oder ist, vernachlässigt werden) und daher
Ein Angreifer, der den privaten Schlüssel nicht kennt, müsste faktorisieren um und zu bestimmen. Das geht über die Grenzen der aktuellen Rechenleistung hinaus, falls diese Primzahlen ausreichend groß sind, sprich mehr als Stellen (die derzeitigen Weltrekorde für das Faktorisieren von sind mit und je Stellen).
Dies definiert momentan das Sicherheitslevel des Verfahrens. Der hauptsächliche Gedanke der public-key Kryptographie ist in der Tat, dass ein Kryptosystem so lange sicher ist, wie der Rechenaufwand, der benötigt wird um es zu knacken, über die Ressourcen der Angreifer hinausgeht. Dies wird a priori festgelegt (gewöhnlich oder bit Operationen) und hängt vom Kontext und dem Ziel der Kommunikation ab. Natürlich genügen eine geheime CIA Nachricht und eine Email zweier Internetnutzer sehr unterschiedliche Sicherheitsstandards!
Signaturen
Jetzt können wir uns dem Problem der Software Updates zuwenden. Mit anderen Worten dem Problem der Authentifizierung. Wie zuvor gibt es einen öffentlichen und einen privaten Schlüssel. Alice, die ihren privaten Schlüssel nutzt, erstellt eine digitale Signatur, die mit einem Dokument versendet wird, um dessen Echtheit nachzuweisen(die Signatur hängt an dem Dokument und kann nicht in ein anderes Dokument eingefügt werden). Der Empfänger verifiziert dann die digitale Signatur, indem er den öffentlichen Schlüssel verwendet.
Nehmen Sie zum Beispiel an, dass ihr Computer Ihnen sagt, dass er ein Update für Adobe gefunden hat. Woher weiß der Computer, dass die Software von Adobe kommt und dass es kein Virus ist, das als Update getarnt ist? Die Lösung liefert die Tatsache, dass das Update eine digitale Signatur hat, mit Bezug auf den öffentlichen Adobe Schlüssel. Dieser öffentliche Schlüssel ist bereits in der Adobe Software auf dem Computer installiert, so dass der Computer die Signatur überprüfen kann, bevor er das Update installiert; eine erfolgreiche Überprüfung belegt, dass das Update wirklich von Adobe und von keinem anderen ist.
Wir zeigen nun, wie man mit Hilfe von RSA digitale Signaturen erstellt. Die privaten und öffentlichen Schlüssel sind dieselben wie zur Verschlüsselung. Wenn Alice ein Dokument (zum Beispiel ein Software Update) authentisieren möchte, kodiert sie es als ganze Zahl , berechnet und bringt die Signatur an ihrem Dokument an. Um die Signatur zu verifizieren sucht Bob Alices öffentlichen Schlüssel heraus und gleicht die Signatur ab, indem er ausrechnet und nachprüft, dass . Logischerweise braucht ein Angreifer der darauf abzielt eine gültige Signatur herzustellen (zum Beispiel ein Hacker der einen Virus anfertigt), genau wie für das RSA Kryptosystem den Exponent und dafür den Faktor .
Aktuelle Forschung
Wir haben das RSA-Kryptosystem ebenso wie das Verfahren der digitalen Signatur skizziert. Jedoch gibt es viele weitere Verfahren, die auf mathematischen Objekten wie Galoiskörpern, elliptischen Kurven, nicht-linearen mehrdimensionalen Gleichungen, fehlerkorrigierenden Codes und mehr basieren. Public-key Kryptographie ist ein sehr aktives Forschungsfeld und es gibt noch immer offene Fragen, die erforscht werden.
Ein Post-Quanten Szenario
Sind all unsere Probleme gelöst mit RSA? Leider lautet die Antwort nein. Die Sicherheit, die RSA uns bietet, genauso wie die vieler andere Verfahren, die auf der Zahlentheorie basieren, ist ernsthaft bedroht durch die potentielle Entwicklung von Quantencomputern. Shors Algorithmus, der in einer Veröffentlichung von 1994 mit dem bedeutungsschweren Titel „ Polynomial time algorithms for discrete logarithms and factoring on a quantum computer“ herausgebracht wurde, ist fähig, das RSA Kryptosystem zu durchbrechen solange ein ausreichend großer Quantencomputer gebaut werden kann. Sehr kleine Quantencomputer sind bereits Realität, und es sind höchstwahrscheinlich in der nahen Zukunft Verbesserungen zu erwarten.
Deshalb ist es wichtig alternative Verfahren zur Verfügung zu stellen, deren Sicherheit nicht davon abhängt, ob das obige Szenario Realität wird. Die Kryptographie Gemeinschaft ist sehr aktiv in dieser Richtung und die aktuelle Forschung ist darauf fokussiert, neue Kryptosysteme aus verschiedenen mathematischen Gebieten zu entwickeln, basierend auf Rechenproblemen, die hoffentlich nicht dieselbe Angreifbarkeit im Hinblick auf Quantencomputer aufweisen.
Literatur
[1] Simon Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography (2000), Anchor.