Public-key Kryptographie

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 $K$ eine Zahl zwischen $0$ und $26$ . Der Verschlüsselungsalgorithmus ${\textsf{Enc}}$ hat als input eine Nachricht $M$ und einen Schlüssel $K$ , zum Beispiel ${\textsf{Enc}}_3$ (HELLO)=KHOOR. Der Entschlüsselungsalgorithmus ${\textsf{Dec}}$ hat als input einen Geheimtext $C$ und denselben Schlüssel, zum Beispiel ${\textsf{Dec}}_3$ (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 $p$ , welches modulo genannt wird. So ist zum Beispiel, falls $p=7$ , $g$ in der Klasse von $2$ , und $5$ , $12$ und $19$ sind alle in derselben Klasse. Man schreibt $9\equiv 2 \pmod 7$ und $12\equiv19\equiv 5 \pmod 7$ . Man sieht leicht, dass es, wenn man mit modulo 7 arbeitet, nur 7 mögliche Klassen gibt, die durch $\{0,1,2,3,4,5,6\}$ 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 $3+8=11\equiv 4 \pmod 7$ und $3\cdot 5=15\equiv 1 \pmod 7$ . Man bemerkt, dass für $a \equiv b \pmod{p}$ dann $(a-b)$ ein Vielfaches von $p$ ist.

Seien $p$ und $q$ Primzahlen, $p \ne q$ und sei $t > 0$ eine ganze Zahl, die kein Vielfaches von $p$ oder $q$ ist. Wir werden nun zeigen, dass die Formel $t^{(p-1)(q-1)}\equiv1 \pmod{pq}$ gilt. Diese Formel ist ein Spezialfall des Satzes von Euler-Fermat.

Der Beweis fängt mit der Formel des Binomialkoeffizienten an:

$\binom pi=\frac{p!}{i!(p-i)!},$

mit $i$ als ganzer Zahl $0 < i < p$ . Mit

$i! \ \binom pi= p(p-1)(p-2)\cdots(p-i+1),$

folgt, dass $p$ ein Teiler von $\binom p i$ sein muss, da $p$ die rechte Seite teilt aber nicht $i!$ .

Dann ist für beliebige ganze Zahlen $A$ und $B$ , mit dem binomischen Lehrsatz,

$(A+B)^p=A^p+\binom p1 A^{p-1}B+\binom p2 A^{p-2}B^2+\cdots+B^p\equiv A^p+B^p \pmod p .$

Nimmt man eine weitere ganze Zahl $C$ hinzu, ergibt sich

$(A+B+C)^p=((A+B)+C)^p\equiv(A+B)^p+C^p\equiv A^p+B^p+C^p \pmod p.$

Auf diese Art erhält man für beliebige ganze Zahlen $A_1$ , $A_2$ , …, $A_t$ ,

$(A_1+A_2+\cdots+A_t)^p\equiv A_1^p+A_2^p+\cdots+A_t^p \pmod p.$

Setzt man nun $A_1=A_2=\cdots=A_t=1$ , erhält man

$t^p\equiv t \pmod p.$

Diese Gleichung drückt aus, dass $(t^p - t) = t( t^{p-1} - 1)$ ein Vielfaches von $p$ ist. Da $p$ nicht $t$ teilt und $p$ eine Primzahl ist, folgt dass

$t^{p-1}\equiv 1 \pmod p.$

Nun erhöht man den Exponenten auf beiden Seiten der Kongruenz um dem Faktor $q-1$ :

$t^{(p-1)(q-1)}\equiv 1 \pmod p.$

Wiederholt man diesen Schritt mit $q$ an Stelle von $p$ , erhält man

$t^{(p-1)(q-1)}\equiv 1 \pmod q.$

Dementsprechend gibt es ganze Zahlen $h$ und $k$ , so dass

$t^{(p-1)(q-1)}=1+ph, \quad t^{(p-1)(q-1)}=1+qk,$

somit $ph=qk$ . Dann teilt $p \mid k$ (da $p$ und $q$ verschiedene Primzahlen sind), und damit $k=pl$ für ganze Zahlen $l$ . Nun weiß man $t^{(p-1)(q-1)}=1+pql$ , oder

$t^{(p-1)(q-1)}\equiv1 \pmod {pq}.$

Dies vervollständigt den Beweis. $\Box$

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 $p$ und $q$ . Berechnen Sie $N=pq$ und $\phi=(p-1)(q-1)$ . Wählen Sie eine ganze Zahl $e$ zwischen $3$ und $N-2$ beliebig, aber so, dass $e$ und $\phi$ teilerfremd sind. Der öffentliche Schlüssel ist das Tupel $(N,e)$ . Der private Schlüssel $d$ , den der Sender geheim halten wird, wird berechnet so dass $d\equiv e^{-1}\pmod\phi$ , das ist die Zahl, so dass $de\equiv1\pmod\phi$ (Diese erhält man leicht, wenn man den euklidischen Algorithmus verwendet). Nehmen Sie zum Beispiel $N = 437 = 19 \cdot 23$ , $\phi = 396$ , $e = 5$ und $d = 317$ .

Nachrichten sind im RSA -Verfahren ganze Zahlen $x$ , so dass $0 < x < N$ . 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 $x$ an Alice senden. Er sucht Alices öffentlichen Schlüssel $(N,e)$ heraus, berechnet $y\equiv x^e \pmod{N}$ , und sendet $y$ an Alice. Um den Geheimtext $y$ zu entschlüsseln, benutzt Alice den privaten Schlüssel $d$ , indem sie $x\equiv y^d \pmod{N}$ berechnet.

Es ist wichtig zu betonen, dass, obwohl $e$ , $d$ und $N$ groß sind, es möglich ist zum Beispiel $y^d \pmod N$ mit Hilfe einer Technik, die modulare Exponentiation genannt wird, effizient zu berechnen.

Die Entschlüsselung funktioniert, da $de=1+k\phi$ für ganze Zahlen $k$ , und wie zuvor gezeigt wurde

$x^\phi=x^{(p-1)(q-1)}\equiv1 \pmod N$

(In der Praxis kann der Fall, wenn $x$ ein Vielfaches von $p$ oder $q$ ist, vernachlässigt werden) und daher

$y^d\equiv (x^e)^d= x^{1 + \phi k} = x(x^\phi)^k\equiv x\cdot1^k=x \pmod N.$

Ein Angreifer, der den privaten Schlüssel $d$ nicht kennt, müsste $N$ faktorisieren um $p$ und $q$ zu bestimmen. Das geht über die Grenzen der aktuellen Rechenleistung hinaus, falls diese Primzahlen ausreichend groß sind, sprich mehr als $200$ Stellen (die derzeitigen Weltrekorde für das Faktorisieren von $N=pq$ sind mit $p$ und $q$ je $100$ 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 $2^{128}$ oder $2^{256}$ 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 $0 < x < N$ , berechnet $\sigma\equiv x^d \pmod{N}$ und bringt die Signatur $\sigma$ an ihrem Dokument an. Um die Signatur zu verifizieren sucht Bob Alices öffentlichen Schlüssel heraus und gleicht die Signatur ab, indem er $x'\equiv \sigma^e \pmod{N}$ ausrechnet und nachprüft, dass $x=x'$ . 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 $d$ und dafür den Faktor $N$ .

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.

Andere Sprachen: Englisch, Französisch, Spanisch, Arabisch, Khmer

Public-key Kryptographie

Schreibe einen Kommentar Antworten abbrechen

Receive notice of every new vignette.

List of Vignettes

Sites of the Month

Books of the Month

Search

Meta

Public-key Kryptographie

Share this:

Schreibe einen Kommentar Antworten abbrechen

Receive notice of every new vignette.

List of Vignettes

Sites of the Month

Books of the Month

Search

Meta