36
Mathematische Grundlagen der Kryptographie

Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

  • Upload
    others

  • View
    6

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Mathematische Grundlagen

der Kryptographie

Page 2: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Organisatorisches

Die Veranstaltung sollte uber “Aktuelle Trends der Informatik”abgerechnet werden.

Sie besteht aus Vorlesung und Praktikum.

Im Praktikum sollen Algorithmen in python implementiert werden.

Hierzu: Tocas

Die Prufungsleistung besteht aus:

Im Zweier-Team:

I Implementieren von kleineren Algorithmen

I Ein großeres Projekt: Implementieren und Beschreibung undDokumentation

I Prasentation (Zu Beginn oder zum Ende der Semesterferien)

Page 3: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Einige Worte zur Kryptographie

Page 4: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Warnhinweis

Die Vorlesung wird deutlich anders werden,als die folgenden Ausfuhrungen.

Page 5: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Was bedeutet “Kryptographie”?

Bis ca. 1970:

Kryptographie = Geheimschrift

(Wortschopfung aus der Neuzeit)

Seit ca. 1918:

Kryptologie = Kryptographie + Kryptoanalyse

(nicht einheitlich)

Page 6: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Was bedeutet “Kryptographie”?

Heute: Der Begriff hat eine wesentlich weitere Bedeutung.

Ein Definitionsversuch:

Kryptographie ist die Benutzung und das Studium vonTechniken fur alle sicherheitsrelevanten Aspekte des Ver-arbeitens, Ubertragens und Benutzens von Informationenin Anwesenheit eines Gegners.

(vergleiche englischsprachige Wikipedia)

Page 7: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Was bedeutet “Kryptographie”?

Ziele heute.

I Vertraulichkeit

I Authentisierung

I Verbindlichkeit

I Integritat

Page 8: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Klassische Ideen

Zwei Personen wollen verschlusselt Nachrichten austauschen.

1. Ansatz

Veranderung auf Buchstabenebene

I Substitution (ersetze einen Buchstaben durch einen anderen)

I Transposition (verandere die Reihenfolge)

2. Ansatz

Benutzung eines Codebuch

Angriffe mittels statistischer Analyse.

In beiden Fallen:

Es gibt ein Verfahren und einen Schlussel.

Page 9: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Das Keckhoffs’sche Prinzip

Auguste Kerckhoffs: La cryptographie militaire von 1883:

Das Prinzip kurz und knapp:

Das Geheimnis darf nur im Schlussel liegen, und diesermuss noch wahrend der Kommunikation veranderbar sein.

Page 10: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Kleiner historischer Uberblick

Drei Perioden:

I Bis 1918: Papier-und-Bleistift-Periode

I 1918 – ca. 1970: Periode der elektrisch-mechanischenChffriermaschinen

I ab ca. 1970: Das elektronische Zeitalter(→ Moderne Kryptographie)

Page 11: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Der Weg zur modernen Kryptographie

Bis 1918: Klassische Ideen mit “Papier und Bleistift”

Das Zimmermann-Telegramm (19.1.1917)

Page 12: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Der Weg zur modernen Kryptographie

Ab 1918: Elektrisch-mechanische Chiffriermaschinen

eine Enigma und eine Lorenz-Schlusselmaschine

Page 13: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Der Weg zur modernen Kryptographie

Im II. Weltkrieg:

I neue Methoden zur Entziffernung (Gruppentheorie)

I Computer fur die Kryptoanalyse

Colossus

Page 14: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Der Weg zur modernen Kryptographie

Ab 1960: Datenverarbeitung kommt auf.

1973 – 1977: Wettbewerb zum “Digital Encryption Standard(DES)” von NIST

1976: Whitfield Diffie und Martin Hellman, New directions incryptography

Page 15: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Der Weg zur Modernen Kryptographie

Umbruche und Paradigmenwechsel um 1980

I Technischer Umbruch: hin zu Computern

I Neue, weitere Zielsetzungen

I Neue Arten von Verfahren (insb. Kryptographie mitoffentlichen Schlusseln)

I Neue Methoden: Komplexitatstheorie und Zahlentheorie

I Offene Forschung statt geheimer militarischer Forschung

I Verwissenschaftlichung der Kryptographie

Page 16: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Das Diffie-Hellman Protokoll

Page 17: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische
Page 18: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

ModulorechnenEs sei p eine Primzahl.

Wir haben die Menge der Restklassen

Z/pZ .

Beispiel.Z/11Z = {[0]11, [1]11, . . . , [10]11}

[11]11 = [0]11 , [24]11 = [13]11 = [2]11 = [−9]11

[5]11 + [6]11 = [11]11 = [0]11

[3]11 · [4]11 = [12]11 = [1]11

Z/pZ ist ein Korper mit Null-Element [0]p und Einselement [1]p.Bezeichnung: Fp. Die multiplikative Gruppe ist

F∗p = Fp\{[0]p} = Fp\{0} .

Page 19: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Die Ordnung

Fur a ∈ F∗p betrachten wir

〈a〉 := {a0 = 1 , a1 = a , a2 , . . . , ai , . . .} .

Die Anzahl #〈a〉 = {ai | i ∈ N0} heißt die Ordnung von a, ord(a).

Es ist 〈a〉 = {a0 = 1 , a1 = a , a2 , . . . , aord(a)−1},

aord(a) = a0 = 1 .

Beispiel. Es ist

[4]211 = [5]11 , [4]311 = [9]11 , [4]411 = [3]11 , [4]511 = [1]11 = 1

und somit ord([4]11) = 5.

Page 20: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Das Diffie-Hellman Protokoll

Alice und Bob einigen sich (in der Offentlichkeit) auf eine großePrimzahl p und ein Element a ∈ F∗

p.

Alice BobWahlt x < ord(a). Wahlt y < ord(a).

X :=ax //

Y :=ayoo

Y x = axy = X y

Page 21: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Das Diffie-Hellman Protokoll

Alice und Bob einigen sich (in der Offentlichkeit) auf eine großePrimzahl p und ein Element a ∈ F∗

p .

Alice BobWahlt x < ord(a). Wahlt y < ord(a).

X :=ax //

Y :=ayoo

Y x = axy = X y

Page 22: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Zur Sicherheit

Zur Sicherheit des Protokolls:

I Fur die Sicherheit des Protokolls ist das Diffie-HellmanProblems relevant:Gegeben p; a,X = ax ,Y = ay , berechne axy .

I Hierfur ist insbesondere die Schwierigkeit des klassischendiskreten Logarithmusproblems relevant:Gegeben p; a,X = ax , berechne x .

I Wir haben eine Reduktion vom DHP auf das DLP(DHP ≤ DLP)

Page 23: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Das Diffie-Hellman Protokoll

Alice und Bob einigen sich (in der Offentlichkeit) auf eine großePrimzahl p und ein Element a ∈ F∗

p.

Alice BobWahlt x < ord(a). Wahlt y < ord(a).

X :=ax //

Y :=ayoo

Y x = axy = X y

Page 24: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Zur Sicherheit IIZur Sicherheit des Protokolls:

I Besser: Das Protokoll ist fur Parameter p, a genau dann sichergegenuber Lauschern, wenn das entsprechende Diffie-HellmanProblem nicht gelost werden kann:Gegeben X = ax ,Y = ay , berechne axy .

I Aber: Wer sagt, dass man “sicher” nicht auch andersdefinieren kann? Vielleicht gibt es andere sinnvollleDefinitionen.

I Dazu: Das Protkoll wird zur gemeinsamen Schlusselerzeugungeingesetzt. Man will: Das Ergebnis soll (de facto)ununterscheidbar von einem echt zufalligen Element in{0, 1, . . . , ord(a)− 1} sein.

I Dies fuhrt zu einem anderen algorithmischen Problem, demDiffie-Hellmann-Entscheidungsproblem:Gegeben X = ax ,Y = ay , unterscheide axy von einem uniformzufalligen Element in {0, 1, . . . , ord(a)− 1}.

Page 25: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Zur Sicherheit III

Zur Sicherheit des Protokolls:

I Diffie-Hellman-Entscheidungsproblem (DDHP) (zuParametern p und a):Gegeben X = ax ,Y = ay , unterscheide axy von einem uniformzufalligen Element in {0, 1, . . . , ord(a)− 1}.

I Rechnerisches Diffie-Hellman-Problem (DHP) (zu p und a):Gegeben X = ax ,Y = ay , berechne axy .

I Klassisches diskretes Logarithmusproblem (DLP) (zu p und a):Gegeben X = ax , berechne x .

I Wir haben Reduktionen

DDHP ≤ DHP ≤ DLP

Page 26: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Zur Sicherheit IV

I Das Protokoll ist vollkommen unsicher gegenuber aktivenAngreifern.

I Authentisierung fehlt!

I Fur ein Protokoll mit Authentisierung will man zweigen: Jedereffiziente Angriff aus einer großen Angriffsklasse fuhrt zueinem effizienten Algorithmus fur dasDH-Entscheidungsproblem (oder besser: fur das recherischeDH-Problem oder sogar fur das DLP) (reduktivesSicherheitsresultat).

Page 27: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Zur Sicherheit kryptographischer Verfahren

Page 28: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Zur Sicherheit kryptographischer Verfahren

Eine Aussage der Form “Das Verfahren ist sicher” ist nur sinnvollbezuglich eines klar definierten Angriffsszenarios.

Fragen, die man immer im Kopf haben sollte:

I Sicher gegenuber welcher Art von Angreifern?Oder: In welchem Kontext wird der Angriff betrachtet?

Mogliche Arten von Angriffen bei Verschlusselungssystemensind z.B.:Lauscher, chosen palintext attack (gewahlter-Klartext-Antriff),chosen ciphertext attack (gewahlter-Chiffriertext-Angriff)

Klare, umfassende Definitionen sind wichtig!

Page 29: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Zur Sicherheit kryptographischer Verfahren

I Angreifer mit welchen Ressourcen werden betrachtet?Unterscheidung zwischenI asyptotischen, qualitativen Betrachtungen zu Verfahren

(Komplexitatstheorie)und

I konkreten Betrachtungen fur konkrete Parameter

(z.B.: Angreifer kann eine Zahl n = pq mit p, q je 500 bitnicht faktorisieren.)

Page 30: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Zur Sicherheit kryptographischer Verfahren

I Welche Annahmen werden getroffen?

Was man gerne hatte:

Wenn ein bestimmtes “schones” Problem schwer ist, istdas Verfahren sicher in dem vorgegebenen Angriffsszena-rio.

Z.B.:Wenn das DLP nicht qualitativ effizient gelost werdenkann, ist das Verfahren qualitativ sicher bezuglich diesesAngriffsszenarios.

Deutlich schwerer zu begrunden sind solche Aussagen:

Wenn das DLP fur ein p mit x bit schwer ist, ist dasVerfahren sicher bezuglich dieser und jener Angriffe.

Page 31: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Zur Sicherheit kryptographischer Verfahren

Alle Sicherheitsresultate (“Sicherheitsbeweise”) zur Kryptographiemit offentlichen Schlusseln sind wenn-dann-Aussagen.

Selbst wenn scheinbar ein “Sicherheitsbeweis” vorliegt, kann einVerfahren angreifbar sein

wegen:

I Angriffen außerhalb des Szenarios(insb. solche mit “Abstrahlung”)

I Fehlern im “Beweis”

I Programmierfehlern

I Falscher Verwendung rein asyptotischer Resultate

I Das “unterliegende Problem” ist schwacher als angenommen.(Insbesondere konnte es ein merkwurdiges ad hoc Problemsein.)

Page 32: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Diese Vorlesung

Was wir machen und was nicht

Page 33: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Diese Vorlesung

Es geht im Folgenden weitgehend um grundlegendezahlentheoretische Methoden und Probleme fur kryptographischeVerfahren mit offentlichen Schlusseln:

I Zahlentheoretische Grundlagen, einfache AlgorithmenI Schwere, sicherheitsrelevante algorithmische Probleme:

I das diskrete LogarithmenproblemI das Faktorisierungsproblem

I Algorithmen zum Losen dieser Probleme

Dies ist ein Aspekt der Konstruktion in der Praxis sicherer Systeme.

Page 34: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Was wir durchnehmen werden

1. Grundlagen

2. Euklidische Ringe

3. Primzahltests

4. Endliche Korper

5. Faktorisierung

6. Berechnung diskreter Logarithmen

7. Elliptische Kurven

Page 35: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Literatur

C.D. Kryptologie – Methoden, Anwendungen undHerausforderungen

C.D. Skript zur Vorlesung Linearen Algebra fur Mathematiker,insb. Kapitel 1 und Abschnitt 4.1

Neal Koblitz. A course in number theory and cryptography

Johannes Buchmann. Einfuhrung in die Kryptographie

Eric Bach, Jeffrey Shallit. Algorithmic number theory

Steven Galbraith. Handbook of public key cryptography

Page 36: Mathematische Grundlagen der Kryptographiediem/math-krypto/mathe-fuer-krypto... · I Zahlentheoretische Grundlagen, einfache Algorithmen I Schwere, sicherheitsrelevante algorithmische

Mogliche Projekte

1. Dicht besetzte Matrizen, Polynomfaktorisierung (wirdbenotigt in P8)

2. Dunn besetzte Matrizen, der Berlekamp-Massey- und derWiedemann-Algorithmus (sollte benutzt werden in P6,P7,P8,P10)

3. Dunn besetzte Matrizen und der Lanczos-Algorithmus (solltebenutzt werden in P6,P7,P8, P10)

4. Generische Methoden fur das Faktorisieren und das DLP

5. Elliptische Kurven und Faktorisierung mit Elliptischen Kurven

6. Faktorisieren mit Faktorbasis und Sieb

7. Faktorisieren mit Faktorbasis und Kettenbruchzerlegung

8. Diskrete Logarithmen in kleiner Charakteristik

9. Elliptische Kurven und Reduktion vom ECDLP zum DLP

10. Hyperelliptische Kurven und das diskrete LogarithmusProblem hierfur