17
1 TOP SECRET

TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

  • Upload
    vanmien

  • View
    218

  • Download
    0

Embed Size (px)

Citation preview

Page 1: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

1

TOP SECRET

Page 2: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

2

Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA

Quartalsarbeit von Lina Humbeck

im Fach Mathematik

April 2007

Page 3: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

3

Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA

1. Einleitung

2. Abkürzungen

3. Begriffe

4. RSA

4.1. Primzahlen und Primfaktorzerlegung

4.2. Euler Funktion

4.3. Euklidischer Algorithmus

4.4. Verschlüsselung und Entschlüsselung

4.5. Angriffe

5. Quantenkryptologie und Elliptic Curve Cryptography (ECC)

6. Anhang

7. Literaturverzeichnis

Page 4: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

4

1. Einleitung Seit Menschen auf der Erde existieren, gibt es Informationen, die nicht für jeden bestimmt sind. Als Erstes wurde versucht die Existenz dieser Information überhaupt zu verbergen. Dann kam man auf die Idee, die Existenz der Information nicht mehr geheim zu halten, sondern nur noch deren Inhalt. Schon Caesar bediente sich zu diesem Zweck einer Verschlüsselung. Bei dieser sogenannten Caesar-Verschlüsselung wurde das Alphabet um drei Buchstaben nach rechts verschoben. Da es sich hierbei nur um ein einziges Alphabet handelt, wird diese Art von Verschlüsselung auch monoalphabetische Verschlüsselung genannt. Diese Verschlüsselung war allerdings leicht zu durchschauen. Deshalb wurde eine neue erfunden, die sogenannte Vigenère-Verschlüsselung, die auf der Benutzung mehrerer Alphabete beruht. Sie wird auch als polyalphabetische Verschlüsselung bezeichnet. Durch Häufigkeitsanalyse (siehe dazu auch 6. Anhang) konnten auch diese Verschlüsselungen leicht dechiffriert werden. Im zweiten Weltkrieg war die Nachfrage nach Kryptographie sowie nach Kryptoanalyse groß. Durch die Entwicklung der Telegrafen kam es zu einem sprunghaften Anstieg des Informationsaustausches. Die Deutschen bedienten sich einer Verschlüsselungsmaschine, der Enigma, die allerdings von den Entschlüsselungsmaschinen in England, den sogenannten „Bomben“, nach einiger Zeit geknackt wurde. Die Verschlüsselung mit der Enigma hatte eine große Schwachstelle, und zwar die des Schlüsselvergabe-Problems. Die Walzen der Enigma mussten in bestimmte Positionen gebracht werden, um mit ihr entschlüsseln und verschlüsseln zu können. Das Problem war, dass diese Informationen von Tag zu Tag allen Kommunikationspartnern auf sicherem Weg mitgeteilt werden mussten. Es gab Codebücher, die für eine Woche galten, wäre eines davon nicht absolut sicher zu einem Kommunikationspartner gelangt, so wäre die ganze Verschlüsselung umsonst gewesen. Das Problem der Schlüsselvergabe galt lange als unlösbar, bis Deffie und Hellmann 1975 das erste Public Key Kryptographie Verfahren entwickelten. Ihre Idee war es mit einem öffentlichen Schlüssel, der allen zugänglich ist, zu verschlüsseln und mit einem privaten oder geheimen Schlüssel, den nur der Empfänger der Nachricht kennt, zu entschlüsseln (Deffie-Hellman-Merkle-Schlüsselaustausch). Sie hatten allerdings noch keine Idee, wie dies mathematisch umsetzbar ist. Denn dieses Public Key Verfahren fordert eine Einwegfunktion, deren Existenz erst von Rivest, Shamir und Adleman bewiesen und die anschließend in ein vollständiges Kryptosystem umgesetzt wurde. Diese Arbeit wird sich mit diesem System, genannt RSA, näher befassen. Es werden das Vorgehen bei einer RSA-Verschlüsselung und Entschlüsselung, die Sicherheit von RSA und neue Wege der Verschlüsselung untersucht.

Page 5: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

5

2. Abkürzungen PFZ Primfaktorzerlegung ASCII American Standard Code for

Information Interchange (a,b) oder ggT(a,b)

Größter gemeinsamer Teiler von a und b

m│n m teilt n, m ist Teiler von n

PZ Primzahl A ≡ b (mod n)

A ist kongruent b modulo n

RSA Asymmetrisches Verschlüsselungsverfahren

PGP Pretty Good Privacy, Programm, das mit RSA arbeitet von P. Zimmermann

3. Begriffe

• a ist kongruent b modulo n: a lässt bei ganzzahliger Division durch n den gleichen Rest wie b, man sagt a und b besitzen die gleiche Restklasse

• Algorithmus: endliche, allgemeingültige, eindeutige und ausführbare Rechenvorschrift, die zum Lösen einer Gruppe von Problemen in endlicher Zeit dient

• Alice, Bob und Eve: Alice und Bob sind Kommunikationspartner, die geheime Informationen austauschen, welche Eve abzufangen versucht, um sie auch evtl. zu ändern

• Asymmetrische Verschlüsselung oder Public-Key-Kryptographie: zum Verschlüsseln wird vom Sender der öffentliche Schlüssel (public Key) und vom Empfänger zum Entschlüsseln der geheime (private Key) benutzt. Diese beiden Schlüssel sind verschieden von einander

• Chiffrieren oder verschlüsseln: ein Plaintext wird mit Hilfe eines Verschlüsselungsverfahrens in einen Cryptotext umgewandelt

• Cryptotext: ist der verschlüsselte Plaintext und wird auch Geheimtext genannt • Dechiffrieren oder entschlüsseln: einen Cryptotext wieder in den Plaintext

umwandeln • Effizient: ist ein Verfahren, wenn der Rechenaufwand und damit auch der zeitliche

und finanzielle Aufwand dem Ziel angemessen (vertretbar) ist • Einwegfunktion: eine Funktion f(x), bei der y = f(x) effizient berechnet werden kann

und zu einem gegebenen y nicht effizient das Urbild x gefunden werden kann • Größter gemeinsamer Teiler: ggT(a,b) = g ist die größte Zahl g mit g|a und g|b • Kryptoanalyse: ist eine Wissenschaft, die sich damit befasst aus dem Cryptotext den

Plaintext wiederherzustellen, ohne den Schlüssel zu kennen oder zu besitzen • Kryptographie: Wissenschaft, die sich mit dem Chiffrieren von Plaintexten zu

Cryptotexten, dem Dechiffrieren mit Schlüssel und der Entwicklung neuer Chiffrieralgorithmen befasst

• Kryptologie: ist die Wissenschaft, die sich sowohl mit der Kryptographie, als auch mit der Kryptoanalyse befasst

• Plaintext: auch Klartext genannt, ist das originale, unverschlüsselte Schriftstück • Teilbarkeit: eine Zahl m teilt eine andere Zahl n, wenn n = m*u, mit m,n,u ε n • Symmetrische Verschlüsselung: so wie verschlüsselt wird, so wird auch entschlüsselt,

es existiert also nur ein Schlüssel

Page 6: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

6

• Trapdoor Einwegfunktionen: sind Einwegfunktionen, bei denen die Umkehrfunktion bei der Kenntnis einer Zusatzinformation effizient auszuführen ist

• Verschlüsselungsalgorithmus: ein allgemeiner Verschlüsselungsprozess, bei dem man durch verschiedene Schlüssel dessen Spezialfälle erhält

• Qubit: Quantenbit, Zustände von Quanten mit 1 oder 0 bezeichnet

4. RSA Die beiden Computerwissenschaftler Ronal Rivest und Adi Shamir und der Mathematiker Leonard Adleman entdeckten 1977 die erste Public Key Verschlüsselungstechnik, die sie dann nach den Anfangsbuchstaben ihrer Nachnamen benannten. Grundsätzlich beruht die asymmetrische Verschlüsselungstechnik auf einer Trapdoor-Einwegfunktion. Diese Funktion besteht aus dem Multiplizieren zweier Primzahlen. Die Umkehrfunktion, also die PFZ, ist mit einem großen Rechenaufwand verbunden. Auf diesem Rechenaufwand beruht die Sicherheit von RSA. Es ist noch unklar, ob die PFZ, zum „Knacken“ von RSA überhaupt benötigt wird und wie komplex die PFZ wirklich ist. In den folgenden Kapiteln sollen der Algorithmus, auf dem RSA beruht, und die Angriffe beschrieben werden. Als Erstes wird die Grundlage von RSA untersucht, also die eindeutige Primfaktorzerlegung. 4.1. Primzahlen und Primfaktorzerlegung Berechnung von n, dem public Key: Um RSA nutzen zu können, müssen als Erstes zwei große Primzahlen p und q gefunden und anschließend multipliziert werden. „Groß“ bedeutet für den normalen Anwender rund 100 Dezimalstellen pro PZ, bei Banktransaktionen werden allerdings Primzahlen mit 150 und mehr Dezimalstellen verwendet. Das Produkt ist der public Key n. Um große Primzahlen zu finden, wird per „random“ (also Zufall) eine Zahl x ermittelt. Ist x gerade, dann wird x := x+1 gerechnet. Anschließend wird ein Primzahltest (siehe 6. Anhang), wie der Miller-Selfridge-Rabin-Test durchgeführt. Wie diese Primzahltests im Einzelnen aussehen, soll nicht Thema dieser Arbeit sein. Allerdings sei gesagt, dass die meisten Tests dieser Art auf dem kleinen Fermat beruhen, der auf Seite 8 näher erläutert ist. Ist x nicht prim, so wird x := x+2 gerechnet, solange, bis x Prim ist. Primzahlen und deren Eigenschaften spielen in RSA eine wichtige Rolle, daher soll der folgende Abschnitt sich mit Primzahlen näher beschäftigen. Definition der Primzahlen: Eine Zahl p, deren Teiler nur ±1 und ±p sind. Für p > 1, p, a, b ε N und p│ab, so ist p│a oder p│b. Der Beweis dieser Aussage soll an dieser Stelle nicht erfolgen. SATZ1 von Euklid: Es gibt unendlich viele Primzahlen.

Page 7: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

7

BEWEIS 1 von SATZ 1: Es wird ein indirekter Beweis durchgeführt. Dazu wird angenommen, dass es nur endlich viele Primzahlen p1,p2,...pr gibt. Nach Satz 2 auf Seite 5 ließe sich jede natürliche Zahl n als Produkt

n = p1k1*p2

k2*...*prkr (#)

darstellen. Jetzt werden die Kehrwerte dieser Primzahlen summiert und es ergibt sich: Σ1/(p1

k1*p2k2*...*pr

kr ). Diese Reihe lässt sich als Produkt mehrerer geometrischer Reihen darstellen, so dass der Wert w der Reihe durch w = 1/[(1-1/p1)*1/(1-1/p2)*...*1/(1-1/pr)] bestimmt ist. Dieses ist möglich, da 1/p1, 1/p2, ..., 1/pr<1 und damit die geometrische Reihe konvergiert und einen Wert besitzt. Allerdings ist die Reihe Σ1/n divergent und geht gegen unendlich. Das bedeutet, dass man mit der Darstellung (#) nicht alle natürlichen Zahlen erfasst haben kann, was zu einem Widerspruch mit der Annahme führt.

� Es muss unendlich viele Primzahlen geben. BEWEIS 2 von SATZ 1: Auch hier für wird ein indirekter Beweis durchgeführt. Es wird also angenommen, dass es endlich viele PZ p1, p2, p3, ..., pk gibt. Dann existiert auch ein n = p1*p2*p3* ...*pk+1. Dieses n ist nicht durch ein pi teilbar, denn sonst wäre auch 1 = n- p1*p2*p3* ...*pk durch dieses pi teilbar. Somit besitzt n keinen bekannten Primteiler und ist damit nach Satz 2 entweder selbst eine neue PZ oder besitzt einen noch unbekannten Primteiler, was einen Widerspruch zur Annahme erzeugt. BEWEIS der Existenz der Primfaktorzerlegung: Der kleinste Teiler von n ε N (nicht Prim), der größer als 1 ist, ist eine Primzahl (p1), so dass n = p1*n1 mit n>n1 gilt. Falls n1 keine Primzahl ist, besitzt auch sie als kleinsten Teiler eine Primzahl p2 mit n1 = p2*n2 mit n1 > n2 und p1 ≤ p2 , ansonsten ist die PFZ schon gegeben. Irgendwann ist ni = 1. Damit ergeben sich zwei Folgen n�1 und p wird immer größer. Wenn ni = 1 ist die Folge beendet und anstelle von jedem ni wird ein pj eingesetzt, so dass: n = p1*p2*…*pk. Damit lässt sich n also nur in Primfaktoren zerlegen. Satz von der eindeutigen Primfaktorzerlegung oder Fundamentalsatz der elementaren Zahlentheorie: SATZ 2 (Hauptsatz der Arithmetik): Jedes n ≥ 2, n ε N lässt sich als Produkt von Primzahlen schreiben, Abgesehen von der

Reihenfolge der Faktoren ist diese Darstellung eindeutig.

BEWEIS von SATZ 2: Es wird ein indirekter Beweis durchgeführt, dessen Annahme es ist, dass es Zahlen ε N gibt, die keine eindeutige PFZ besitzen. Nach dem Axiom der natürlichen Zahlen gibt es auch eine kleinste solche Zahl m, mit

m = p1*p2*…*pr = q1*q2*…*qs . Dann gilt Folgendes :

1. pi ≠ qj für alle i,j. Da ansonsten m durch pi bzw. qj gekürzt werden könnte und sich somit eine kleinere Zahl mit verschiedenen PFZen im Gegensatz zur Wahl von m ergeben würde.

2. p1│ q1*q2*…*qs

Page 8: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

8

Da q1*q2*…*qs nur aus PZen besteht, muss p1 eine diese PZen teilen. Dies ist allerdings nur möglich wenn p1 = qj, was im Widerspruch zu Aussage 1 steht. 4.2. Euler Funktion In diesem Abschnitt wird die Euler Funktion von n (φ(n)) ermittelt, mit deren Hilfe dann der private Key bestimmen werden kann (siehe Kapitel 4.3. Euklidischer Algorithmus). Diese Euler Funktion gibt die Anzahl der zu n teilerfremden Zahlen an.

φ(n) = φ(p)*φ(q) = λ(p)*λ(q) Die Euler Funktion φ(p) ist, wenn p Prim ist, gleich der Carmichael-Funktion λ(p),. Diese ist bei Primzahlen (p-1). So ist φ(n) = (p-1)*(q-1). SATZ 3 (von Euler) : Ist die Primfaktorzerlegung von n gegeben, mit n = p1

a1...pk

ak, dann ist φ(n) = n(1-1/p1)...(1-

1/pk)

Summenformel:

Für di│n ist die Summe über alle φ(di)von 1 bis n gleich n.

Herleitung von SATZ 3: Ist die Primfaktorzerlegung von n gegeben, mit n = p1

a1...pkak, dann ist die Anzahl der zu n

teilerfremden Zahlen die Differenz zwischen n und der Anzahl der Zahlen, die mit n einen gemeinsamen Teiler haben. Da n zusammengesetzt ist, sind die Zahlen, die mit n einen gemeinsamen Teiler haben, Primzahlen oder deren Vielfache. Die Anzahl der Zahlen, die auf Grund des Primteilers p1 einen gemeinsamen Teiler mit n haben, lässt sich bestimmen mit n/ p1. Gibt es nun mehrere Primteiler, dann müssten die Zahlen, die durch p1 und den bzw. die anderen Primteiler teilbar sind, mehrfach in die Rechnung einbezogen werden. Deshalb wird zur Differenz noch der Quotient aus n und dem Produkt der Primteiler dazuaddiert. Pro mögliche Primteilerkombination kommt ein neuer Quotient dazu. So ergibt sich für eine Zahl n, die durch p1 und p2 teilbar ist, φ(n) = n-n/p1-n/p2+n/p1p2. Nun kann n-n/p1 ausgeklammert werden, und es resultiert φ(n) = (n-n/p1) (1-1/p2). Wird jetzt noch n ausgeklammert ergibt sich φ(n) = n*(1-1/p1) (1-1/p2). 4.3. Euklidischer Algorithmus Berechnung von d, dem private Key: Per "random" wird dann wieder eine Zahl d ermittelt, mit d>1 und ggT(d, φ(n)) = 1. Diese Zahl wird dann der private Key. Um zu prüfen, ob ggT(d, φ(n)) = 1, wird der Euklidischen Algorithmus angewendet.

ggT (a,b)=y a = q1b+r1 |r|<|b|

b = q2r1+r2 r1 = q3r2+r3

.

.

. rn-1 = qn+1rn+rn+1

rn = qn+2rn+1

rn+1|a,b und rn+1|r1, folglich rn+1 = y. Hat man d gefunden ist y = 1.

Page 9: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

9

Beispiel.: gesucht: ggT (3485,92)

3485 = 37*92+81

92 = 1*81+11

81 = 7*11+4

11 = 2*4+3

4 = 1*3+1

3 = 3*1+0

ggT (3485,92) = 1

Berechnung von e, dem zweiten public Key: Danach wird eine Zahl e, 1<e< φ (n)gesucht, die der Anforderung ed ≡ 1 (mod φ(n)) genügt. e ist der zweite public Key.

X*φ(n)+e*d = 1 1 = rn-1- qn+1rn

1 = rn-1-( qn+1*(rn-2-qn*rn-1) . . .

Beispiel.: d = 3485 und φ(n )= 92

X*92+e*3485 = 1 1 = 4-3

1 = 4-(11-2*4) 1 = 3*4-11

1 = 3(81-7*11)-11 1 = 3*81-22*11

1 = 3*81-22(92-81) 1 = 25*81-22*92

1 = 25(3485-37*92)-22*92 1 = 25*3485-947*92

25*3485=947*92+1 ≡ 1 (mod 92) e = 25

4.4. Verschlüsselung und Entschlüsselung Nachdem alle notwendigen Schlüssel für das RSA-Verfahren berechnet wurden, möchte Alice nun Bob eine Nachricht schicken. Diese soll mit RSA chiffriert sein, damit Eve keine Informationen erhält. Als Erstes teilt Alice die Nachricht in Blöcke von einer sinnvollen Länge, die stets kleiner als n (public Key) sein muss. Oft wird auch eine feste Blocklänge definiert. Ist ein Block dann kleiner als die festgesetzte Länge, wird von vorne mit Nullen aufgefüllt. Dann nimmt sich Alice einen Standardcode, mit dem Text in Zahlen umgewandelt werden kann zur Hilfe (z.B. ASCII). Nun sucht Alice die public Keys e und n von Bob in einem Register heraus und wendet auf jeden der Blöcke Plaintext w der Nachricht Folgendes an, um den Cryptotext c zu erhalten: v(m) = c ≡ we (mod n). Der Cryptotext kann nun gesendet werden. Bob entschlüsselt den Cryptotext, mit Hilfe des private Key d. Da aus p oder q, sowie aus φ(n) d berechnet werden kann, müssen diese auch geheim gehalten werden. Wurde d einmal berechnet, können zur Erhöhung der Sicherheit p, q und φ(n) vernichtet werden. Bob rechnet nun d(m) = w ≡ cd (mod n) und schon hat Bob den Plaintext, den Alice gesendet hat. Da Eve nicht den private Key d kennt, kann sie den abgefangenen Cryptotext nicht dechiffrieren und so bleibt ihr die Information der Nachricht verborgen.

Page 10: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

10

Um zu beweisen, dass nach einer Chiffrierung und einer anschließenden Dechiffrierung des gleichen Textes wieder der zuerst verschlüsselte Plaintext entsteht, wird das Verfahren im Folgenden überprüft. Dazu werden drei weitere Sätze zu Hilfe gezogen. SATZ 4 (Euler-Fermat): Es gilt a

φ(n) ≡ 1 (mod n) für alle a und n mit ggT(a,n) = 1.

BEWEIS von SATZ 4: Nach Detlef Gronau, 2007 (http://www.uni-graz.at/~gronau/Zv.pdf). SATZ 5 (kleiner Fermat): p sei eine Primzahl und n kein Vielfaches von p, so gilt:

np-1 ≡ 1

(mod p).

BEWEIS von SATZ 5: Da φ(p) = p-1, handelt es sich bei Satz 5 um einen Spezialfall (historisch gesehen, ist der Satz von Euler-Fermat die Verallgemeinerung des kleinen Fermat) des Satzes 4. Von Nutzen kann auch noch der folgende Satz sein: SATZ 6 (Chinesischer Rest(klassen)satz): Seien p, q teilerfremde natürliche Zahlen und a, b ε Z beliebig, so existiert ein x ε Z, welches

x ≡ a (mod p) und x ≡ b (mod q) löst.

Die Überprüfung der Korrektheit des Verfahrens: Damit das Verfahren korrekt ist, muss folgendes gelten:

1. d(v(m)) = m 2. v(d(m)) = m

zu 1.: d(v(m)) ≡ (v(m))

d ≡ (me)d ≡ med (mod n) zu 2.: v(d(m)) ≡ (d(m))

e ≡ (md)e ≡ med (mod n) Da ed ≡1 (mod φ(n)), ist ed = k *φ(n)+1 mit k ε Z, somit ist med ≡ m k φ(n)+1 (mod n). Nach Satz 5 gilt: mp-1 ≡ 1 (mod p), wenn p kein Teiler von m ist. φ(n) = (p-1)(q-1), somit (p-1)│φ(n) und m k φ(n)+1 ≡ m (mod p). Der letzte Ausdruck gilt auch für den Fall, dass p Teiler von m ist, somit ist die Gültigkeit für alle m garantiert. Ähnlich kann jetzt mit q vorgegangen werden, so dass sich zum Schluss m k φ(n)+1 ≡ m (mod q) ergibt. Aus m k φ(n)+1 ≡ m (mod p) und m k φ(n)+1 ≡ m (mod q) folgt, dass

med ≡ m k φ(n)+1 ≡ m (mod n) Da die Nachricht in Blöcke, die stets kleiner als n sind, eingeteilt wurde, ist

med ≡ m k φ(n)+1 ≡ m (mod n) = m. Damit wären die beiden Aussagen 1. und 2. erfüllt und das Verfahren ist korrekt. An dieser Stelle soll darauf hin gewiesen werden, dass auch mit dem private Key chiffriert und anschließend mit dem public Key dechiffriert werden könnte, so wie es bei der Signatur von Nachrichten praktiziert wird. Ein aktiver Angriff kann so entdeckt und die Authentizität des Senders überprüft werden. Näheres zu Angriffen ist im nächsten Kapitel zu finden.

Page 11: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

11

4.5. Angriffe Die genauere Betrachtung von Angriffen, auch Kryptoanalyse genannt, ist zum besseren Verständnis des Kryptosystems (insbesondere dessen Vorteile und Nachteile) notwendig. Zudem kann durch die Kenntnis der möglichen Angriffe die Sicherheit des Kryptosystems festgestellt werden. Zur Sicherheit: Da ein Verschlüsselungssystem nie 100% sicher sein kann, ist die erste Frage, die gestellt werden muss: Welchen Aufwand würde jemand aufbringen, um die Informationen zu erhalten? Es muss gelten, dass wenn der „Angreifer“ durch das Raten des Schlüssels einen Gewinn von nur ein paar Millionen Euro erwartet, es für ihn immer noch ökonomischer ist, sein Geld für Lotto auszugeben (vgl. A. Beutelspacher, Kryptology S. 78). Es gibt zwei große Gruppen von Angriffen, die sich dann wiederum in einzelne Untergruppen gliedern. Es gibt die passiven und die aktiven Angriffe. Vom Kryptoanalytiker wird angenommen, dass der Angreifer zwar die Methode der Verschlüsselung kennt, aber nicht im Besitz des Schlüssels ist. Bei passiven Angriffen ist das Ziel des Kryptoanalytikers, Kenntnis über den Inhalt der gesendeten Informationen zu erlangen. Wogegen bei aktiven Angriffen der Kryptoanalytiker den Inhalt der gesendeten Information oder die Information selber, nicht nur zu kennen, sondern auch zu verändern versucht (z.B. durch das Hinzufügen oder Löschen von Informationen). Es wird angenommen, dass die Dechiffrierung von einem mit RSA chiffrierten Cryptotext genauso schwer ist wie die Faktorisierung von n. Im Folgenden sollen verschiedene Methoden aufgezeigt werden, die ein Kryptoanalytiker versuchen könnte, um den private Key d zu erhalten. Wobei noch nicht geklärt ist, ob eine Funktion existiert, die ohne den private Key aus dem Cryptotext wieder den Plaintext dechiffriert. Als Erstes wird die Faktorisierung von n untersucht. Faktorisierung von n: Die effiziente PFZ ist ein sehr lang bekanntes zahlentheoretisches Problem. Es existieren zwar Algorithmen, mit denen eine Zahl in ihre Primfaktoren zerlegt werden kann, doch sind diese nicht effizient genug. Doch die Technik wird immer besser, so dass Bob und Alice gezwungen werden immer größere PZ zu verwenden, was einen Verlust von Schnelligkeit mit sich bringt. In der Tabelle 1 sind erfolgreiche Faktorisierungen großer Zahlen aufgelistet. Aus der Tabelle kann man auch entnehmen, dass die Entwicklung immer bessere Verfahren hervorbringt und dass ein Schlüssel mindestens 150 Dezimalstellen haben sollte.

Jahr Zahl Stellen Bits 1990 C116 116 1993 RSA-120 120 1994 RSA-129 129 1996 RSA-130 130 1999 RSA-140 140 1999 RSA-155 155 512 2002 C158 158 2003 RSA-160 160 530 2003 RSA-576 174 576 2005 C176 176 2005 RSA-200 200 663 2005 RSA-640 193

Tabelle 1: Erfolgreiche Faktorisierungen

Page 12: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

12

Berechnung von φ(n): Außerdem könnte ein Kryptoanalytiker versuchen φ(n) zu berechnen, ohne dabei n zu faktorisieren. Mit φ(n) kann dann der private Key d über den euklidischen Algorithmus bestimmt werden. Neben der Berechnung von d kann n mit Hilfe von φ(n) leicht faktorisiert werden. Somit kann die Berechnung von φ(n) nicht wesentlich leichter sein, als n zu faktorisieren. Berechnung von d: Würde ein Kryptoanalytiker versuchen d zu berechnen, so ist dies genauso schwer, wie n zu faktorisieren, da er mit d n leicht faktorisieren könnte. Implementierung und Brute-Force-Angriff: Viele Kryptoanalytiker „greifen“ allerdings nicht direkt den Algorithmus von RSA an, sondern dessen Implementierung. Ein weiterer Angriff, der aber nur zu einer sehr kleinen Wahrscheinlichkeit Erfolg hat, ist der Brute-Force-Angriff. Hierbei wird einfach durchprobiert, ob der Schlüssel nicht zufällig gefunden wird. Bei RSA muss der Anwender große PZ finden, dazu gibt es ein paar Hilfsverfahren. Diese könnte auch der Angreifer ausprobieren und ausrechnen, ob die Zahl Teiler von n ist. Aufbewahrung des Schlüssels: Auf keinen Fall darf der Schlüssel aufgeschrieben und offen zugänglich sein. Es können Plaintextspuren auf dem Computer gefunden werden. Dateien die gelöscht werden, werden nicht richtig gelöscht, nur gegebenenfalls überschrieben. So können alte Plaintexte und alte temporäre Dateien wiederhergestellt werden. Hier gibt es PGP (ab bestimmten Versionen), das allerdings nur hilft, wenn das Betriebssystem die Dateien beim Überschreiben nicht an einen anderen Ort auf der Festplatte legt. Es gibt auch Auslagerungsdateien, die ebenfalls angegriffen werden. Auch überschriebene Dateien können einem „guten“ Angriff nicht standhalten. So können mit einem Rasterelektronenmikroskop immer noch geringe Magnetspuren gefunden, ausgewertet und letztendlich daraus der Plaintext rekonstruiert werden. Verschlüsselung wird angewendet, um vertraulich mit Personen kommunizieren zu können, das heißt z.B. verschlüsselte E-Mails über das Internet zu verschicken. Doch besteht über das Internet auch die Gefahr eines Virus oder trojanischen Pferdes, welches z.B. den private Key an einen Angreifer sendet. Außerdem kann die elektromagnetische Strahlung, die ein Computer aussendet, abgefangen und damit kann jede Aktion des Rechners bzw. des Benutzers beobachtet werden. Dagegen hilft eine Abschirmung, z.B. mit Kupferdrahtnetzen.

5. Alternativen zu RSA RSA ist eine gute Methode die Datensicherheit und Privatsphäre zu gewährleisten. Allerdings wird nach der Kryptoanalyse klar, dass RSA zwar sicher, aber dennoch nicht undechiffrierbar ist. Auch die immer größer werdende Schlüssellänge macht auf Grund der sich ständig verbessernden Technik (besonders der Computer) und neuer Erkenntnisse in der Mathematik das Verfahren komplexer und teurer. Im folgenden Kapitel soll ein Überblick über zwei neue Verschlüsselungstechniken, die Quantenkryptologie und die Elliptic Curve Kryptographie, gegeben werden.

Page 13: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

13

5.1. Quantenkryptologie Bei der Quantenkryptologie wird mit den Lichtquanten (Photonen) gearbeitet, welche Energieportionen von elektromagnetischen Wellen sind. Es ist zumeist das Ziel, mit dieser Technik nur den Schlüssel sicher zu übertragen. Wird nach dem erfolgreichen Schlüsselaustausch, dann das one time Pad (näheres siehe 6. Anhang) genutzt, so ist die Nachricht sicher. Soll die Quantenkryptographie, die 1984 von C. Bennett und G. Brassard entwickelt wurde, benutzt werden, werden Photonen mit einer bestimmten Polarisation vom Sender zum Empfänger gesendet. Die Verschlüsselung erfolgt dabei mit Hilfe der Polarisation der Photonen. Der Empfänger muss seinen Polarisationsfilter (z.B. doppelbrechender Kristall) im Voraus auf eine der möglichen Polarisationen einstellen. Diese Polarisation hat, wird sie gemessen, einen von zwei möglichen Werten, die auch als 0 oder 1 bezeichnet werden können und damit Qubits sind. Nach der Übertragung der Photonen teilt der Empfänger dem Sender mit, welche Einstellungen der Polarisationsfilter hatte. Der Sender gibt daraufhin an, welche der Einstellungen die richtigen waren. Diese ergeben dann den Schlüssel. Versucht jemand den Photonenstrahl anzuzapfen, um die Informationen aus der gemessenen Polarisation zu erhalten, fällt das dem Sender und Empfänger sofort auf, da bei falsch eingestelltem Filter eine Störung des Systems erfolgt. Die Grundlage hierfür ist die Heisenbergsche Unschärferelation. Ein Problem ergibt sich allerdings bei dem Versuch, Photonen über eventuell lange Distanzen zu senden. Da ein Quantum in mehreren Zuständen gleichzeitig vorliegen kann, gibt es eine Steigerung der Zustände bei der sogenannten Verschränkung mehrerer Photonen. Die Vielfalt der Zustände kann genutzt werden, um eine hohe Anzahl von Rechnungen durchzuführen. Damit wären auch z.B. die eindeutige Primfaktorzerlegung oder die Berechnung des diskreten Logarithmus, welcher bei ECC (siehe unten) eine Rolle spielt, in einer effizienten Zeit möglich. Ein entsprechender Algorithmus wurde schon von Peter W. Shor 1996 (http://www.arxiv.org/PS_cache/quant-ph/pdf/9508/9508027v2.pdf) vorgelegt. Bis jetzt fehlt allerdings die Realisierung eines effizienten Quantencomputers. 5.2. ECC- Elliptic Curve Cryptography Der Vollständigkeit halber wird an dieser Stelle auch noch kurz auf die Elliptic Curve Cryptography (ECC) eingegangen. Diese kryptographische Technik wurde 1985 von Victor Miller und Neil Koblitz entdeckt. Hier wird, wie bei ElGamel, das diskrete Logarithmus Problem angewandt, allerdings auf der Basis von elliptischen Kurven. Dies scheint schwieriger zu sein, als das Problem der Primfaktorzerlegung von ganzen Zahlen. Die Fortschritte dieses Problem zu lösen, gehen nur langsam voran, so dass kleinere Schlüssel als bei RSA verwendet werden können, die die gleiche Sicherheit gewährleisten. Dazu siehe auch Diagramm 1. Dies bedeutet wiederum einen geringereren Rechenaufwand und somit ist ECC auch auf Festplatten mit geringem Speicherplatz möglich. So sind z.B. digitale Signaturen auf dem elektronischen Pass mit ECC verschlüsselt.

Page 14: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

14

Sicherheit [Jahr]: Gibt das Jahr an, in dem das Verfahren mit der entsprechenden Schlüssellänge voraussichtlich gebrochen wird. RSA: Verschlüsselung mit RSA ECC: Verschlüsselung mit ECC, bei der Annahme, dass sich keine erfolgreiche Kryptoanalyse entwickelt ECC+: Verschlüsselung mit ECC, bei der Annahme, dass sich eine erfolgreiche Kryptoanalyse entwickelt

Diagramm 1: Abhängigkeit der Sicherheit von der Schlüssellänge

Page 15: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

15

6. Anhang One time Pad: Beim one time Pad wird ein Schlüssel als zufällige Folge von Zahlen (0 und 1) erstellt. Der Schlüssel wird nur ein einziges Mal benutzt und ist genauso lang, wie die eigentliche Nachricht, die zuvor auch in Dualzahlen verwandelt wurde. Nun werden beide Zahlen addiert, wobei 0+0 = 0, 0+1 = 1+0 = 1 und 1+1 = 0. Es entsteht ein Cryptotext, der ohne die Kenntnis des Schlüssels nicht dechiffriert werden kann. Dies gilt allerdings mit der Ausnahme, dass der Angreifer den Schlüssel zufällig errät, also mit dem Brute-Force-Angriff Erfolg hat. Häufigkeitsanalyse: Bei diesem kryptoanalytischen Verfahren werden alle Buchstaben gezählt und nach ihrer Häufigkeit geordnet. Jede Sprache verwendet verschiedene Buchstaben unterschiedlich häufig. So ist mit 17,4% in der deutschen Sprache das Schriftzeichen „e“ der häufigste Buchstabe. Der häufigste Buchstabe eines deutschen Cryptotextes ist bei hinreichendem Datenmaterial also wahrscheinlich äquivalent zu dem Plaintextbuchstaben e. Weitere Häufigkeiten der Buchstaben des deutschen und des englischen Alphabets in den folgenden Tabellen 2 und 3.

Tabelle 2: Häufigkeiten der Buchstaben in der deutschen Sprache

Page 16: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

16

Tabelle 3: Häufigkeitsverteilung der Buchstaben in der englischen Sprache

7. Literaturverzeichnis H. Beker, F. Piper, Cipher Systems: The Protection of Communication (Northwood Books, 1982) A. Beutelspacher, Kryptologie (Vieweg 1993) A. Beutelspacher, J. Schwenk, K. D. Wolfenstetter, Moderne Verfahren der Kryptographie (Vieweg 1998), 2. Auflage J. Buchmann, A. May, U. Vollmer, Perspectives for cryptographic long-term security, Communications of the ACM, Vol. 49 No. 9, September 2006 A. Cho, Simple noise may stymie spies without quantum weirdness, Science, Vol. 309, 30. September 2005 C. Creutzig, A. Buhl, P. Zimmermann: PGP Pretty Good Privacy: Der Briefumschlag für Ihre elektronische Post (Herausgeber: FoeBuD e.V., 1999) H. Delfs, H. Knebl, Introduction to Cryptography: Principles and Applications (Springer, 2002) D. Gollmann, Algorithmen-Entwurf in der Kryptographie: Aspekte komplexer Systeme Band 1, (BI-Wissenschaftsverlag,1994) M. Hillery, Code-breakers confounded, Nature, Vol. 421, 16. Januar 2003 R. A. Mollin, Discrete mathematics and its applications: RSA and public-key cryptography (Chapman&Hall/CRC, 2003) R. L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public key cryptosystems, Communications of the ACM, Vol. 21 No. 2, Februar 1978 A. Salomaa, Public-Key Cryptography (Springer, 1996), 2.Auflage

%

Page 17: TOP SECRET - Elisabeth Gymnasium Halle Lina Humbeck... · 3 Asymmetrische Verschlüsselungsverfahren am Beispiel von RSA 1. Einleitung 2. Abkürzungen 3. Begriffe 4. RSA 4.1. Primzahlen

17

Verwendete Internetadressen: http://www.arxiv.org/PS_cache/quant-ph/pdf/9508/9508027v2.pdf, P. W. Shor, 27.01.2007 http://www.crypto-world.com/FactorRecords.html, S. Contini, 09.04.2007 http://www-md.e-technik.uni-rostock.de/veroeff/iuk2001_schmalisch.pdf, M. Schmalisch, D. Timmermann, 27.01.2007 http://www.uni-graz.at/~gronau/Zv.pdf, D. Gronau, 30.03.2007 http://www.rsa.com/rsalabs/node.asp?id=2093, RSA Security Inc., 09.04.2007