IT-Sicherheit

Kapitel 3

Public Key Kryptographie

Dr. Christian Rathgeb

Sommersemester 2014

1 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

2

• In der symmetrischen Kryptographie verwenden Sender und

Empfänger den selben Schlüssel → die Teilnehmer müssen sich

voll vertrauen und auf einen Schlüssel einigen.

• Bei N miteinander kommunizierenden Teilnehmern muss jeder

Teilnehmer N-1 Schlüssel geheim halten. (insgesamt N*(N-1)/2)

• Bei Hinzukommen eines neuen Teilnehmers müssen alle

Teilnehmer die Liste ihrer Schlüssel aktualisieren.

• Anforderung: hohe Sicherheit für den Schlüsseltransport!

IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Einführung

3

• Public Key Kryptographie wird auch als asymmetrische

Kryptographie bezeichnet.

• Es gibt ein Schlüsselpaar bestehend aus einem privaten (Private

Key = Entschlüsselungskey) und einem dazugehörigen

öffentlichen Schlüssel (Public Key = Verschlüsselungskey)

• Die beiden Schlüssel sind NICHT identisch. Der Private Key kann

nicht (in vernünftiger Zeit) aus dem Public Key berechnet werden.

• Public-Key Algorithmen haben den großen Vorteil, dass kein

sicherer Kanal für die Übertragung eines öffentlichen Schlüssels

benötigt wird!

IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Einführung

4 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Einführung

• Anfang der 1970er erfinden Mathematiker beim britischen

Geheimdienst (angeblich) „Non-Secret Cryptography“.

• 1976 publizieren Whitfield Diffie und Martin Hellman ihren

richtungsweisenden Artikel.

• 1978 veröffentlichen Ron Rivest, Adi Shamir und Leonard

Adleman das RSA-Verfahren.

• 1985 publiziert Taher ElGamal ein Verschlüsselungs- und

Signaturverfahren auf Basis von Diffie-Hellman.

5

• Public Key: Der Verschlüsselungskey kann öffentlich bekannt

gegeben werden und wird daher auch als Public Key bezeichnet.

Jede Person, die Zugang zu diesem Schlüssel hat, kann eine

Nachricht verschlüsseln. Eine Entschlüsselung ist damit aber nicht

mehr möglich.

• Private Key: Der Entschlüsselungskey muss geheim gehalten

werden und wird daher auch als Private Key bezeichnet. Jene

Person, die ihn besitzt, kann eine mit dem zugehörigen Public Key

verschlüsselte Nachricht entschlüsseln.

• Die öffentlichen Schlüssel sind jeweils allen Teilnehmern bekannt

(z.B. über eine zentrale öffentliche Datenbank).

IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Einführung

6

• Bei N Nutzern sind nur noch N Schlüsselpaare nötig. (insgesamt

2*N Schlüssel)

• Kommunikationsmodell:

IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Einführung

7 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Einführung - Laufzeit

• Laufzeiten von Algorithmen werden NICHT in Zeiteinheiten

angegeben!

• Man sucht eine obere Schranke für die Anzahl der einfachen

Operationen (Schritte).

• Eine Funktion f heißt genau dann Laufzeit eines Algorithmus, wenn

für alle Eingabelängen n der Algorithmus höchstens f(n) Schritte

benötigt.

• Dabei wird f(n) nicht exakt über eine Formel bestimmt, sondern für

große Werte von n approximiert.

8 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Einführung - Laufzeit

• O-Notation: Möchte man wissen ob eine Laufzeit in eine Klasse

gehört, so muss man ihr asymptotisches Wachstum beobachten!

• Es gilt f = O(g) („f ist groß O von g“), wenn es zwei Zahlen c und n0

gibt, so dass f(n) ≤ c * g(n) gilt für alle n ≥ n0.

• Mathematische Definition:

g : ℕ → ℝ+

O(g):={f: ℕ → ℝ+ | ∃ c ∈ ℝ+ ∃ n0 ∈ ℕ ∀ n > n0: f(n) ≤ c*g(n)}.

9 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Einführung - Laufzeit

• Ein Algorithmus mit Eingabelänge n hat genau dann lineare

Laufzeit, wenn die Laufzeit O(n) beträgt.

• Ein Algorithmus mit Eingabelänge n hat genau dann polynomielle

Laufzeit, wenn die Laufzeit O(na) für eine natürliche Zahl a > 1

beträgt.

• Ein Algorithmus mit Eingabelänge n hat genau dann exponentielle

Laufzeit, wenn die Laufzeit O(cn) für ein c > 1 beträgt.

• Nur eine lineare und polynomielle Laufzeit ist effizient!

10 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Einführung - Laufzeit

• Die Komplexitätsklasse 𝒫 beschreibt diejenigen Probleme zu

deren Lösung es einen Algorithmus mit polynomieller Laufzeit

gibt. (Klasse der „praktisch lösbaren“ Probleme)

• Die Komplexitätsklasse 𝒩𝒫 beschreibt diejenigen Probleme, bei

denen die Verifikation einer Lösung eine polynomielle Laufzeit

besitzt. (Bsp: Traveling Salesman Problem) 𝒫 ⊆ 𝒩𝒫

• Ungelösten Frage der theoretischen Informatik: gilt 𝒫 = 𝒩𝒫 ?

(Ist ein sogenanntes $1 Millionen Problem)

Dh: Ist jedes Problem, deren Lösung in polynomieller Laufzeit

verifizierbar ist auch in polynomieller Laufzeit lösbar?

11 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

One-way / Trapdoor Functions

• Eine Abbildung f heißt One-Way Function (Einwegfunktion), falls gilt:

1. y = f(x) ist effizient berechenbar und

2. x = f-1(y) ist nicht effizient berechenbar.

• Eine Abbildung f heißt Trapdoor Function (Falltürfunktion), falls gilt:

1. f ist eine Einwegfunktion und

2. x = f-1(y) ist effizient berechenbar mit Hilfe einer Zusatzinformation

(Trapdoor).

12 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

One-way / Trapdoor Functions

• Kryptographie mit Trapdoor Function:

1. Ein Teilnehmer A wählt eine Falltürfunktion f, bei der nur er die Zusatzinformation kennt.

2. Der Teilnehmer B wendet die Falltürfunktion f auf seine Nachricht x an und sendet das Ergebnis y = f(x) an A.

3. Unter der Annahme, dass nur A die Zusatzinformation kennt, kann A die Funktion f umkehren und die Nachricht x = f-1(y) entschlüsseln.

• Beispiele: Faktorisierung ganzer Zahlen, Diskreter Logarithmus, Elliptische Kurven;

13 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Digitale Signaturen

• Digitale Signatur ermöglichen, dass Zugehörigkeit zu einer Nachricht geprüft werden kann!

• Mit Public Key Kryptographie kann man mittels digitaler Signatur die folgende Schutzziele realisieren:

1. Integrität

2. Nachrichtenauthentizität

3. Verbindlichkeit

• Integrität und Nachrichtenauthentizität können auch mit Message Authentication Codes realisiert werden, aber die Verbindlichkeit gewährleistet ausschließlich die digitale Signatur.

14 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Digitale Signaturen

• Digitale Unterschriften mit Public Key:

1. Alice verschlüsselt die Nachricht mit ihrem Private Key.

2. Alice schickt die Nachricht an Bob.

3. Bob entschlüsselt die Nachricht mit dem Public Key von Alice.

• Bob kann sicher sein, dass die Nachricht von Alice ist!

• Es wird dabei gefordert, dass es praktisch unmöglich ist, ohne den

Private Key eine gültige digitale Signatur erzeugen zu können.

15 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Digitale Signaturen

• Digitale Unterschriften mit Hash & Sign:

• Problem: Public-Key-Verfahren sind sehr langsam. Die digitale Signatur ist ebenso lang wie die Nachricht.

• Lösung: Hashen der Nachricht und Signieren des Hashwertes! Die Fälschungssicherheit, die Verifizierbarkeit und die Verbindlichkeit gelten zunächst für den Hashwert. Durch eine kollisionsresistente Hashfunktion übertragen sich die Eigenschaften auch auf die Nachricht.

16 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Digitale Signaturen

• Digitale Unterschriften mit Hash & Sign:

• Vorgangsweise:

1. Alice erzeugt den One-Way Hash eines Dokumentes.

2. Alice verschlüsselt den Hash mit ihrem Private Key (=Unterschrift).

3. Alice schickt das Dokument mit dem Unterschriftshash an Bob.

4. Bob produziert One-Way Hash des Dokumentes und entschlüsselt den unterschriebenen One-Way Hash. Stimmen die beiden überein, ist die Unterschrift gültig.

17 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Hybride Verfahren

• Asymmetrische Verfahren haben gegenüber den symmetrischen

Verfahren den Vorteil, dass ein gemeinsamer Schlüssel NICHT

über einen vertraulichen Kanal ausgetauscht werden muss.

• Symmetrische Verfahren lassen sich gegenüber asymmetrischen

Verfahren sehr effizient implementieren (ca. Faktor 1000).

• Ziel ist es die Vorteile von asymmetrischen und symmetrischen

Verfahren zu nutzen.

• Lösung: verschlüssele die eigentliche Nachricht symmetrisch,

wobei mittels asymmetrischer Verschlüsselung ein symmetrischer

Schlüssel vertraulich transportiert wird!

18 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Hybride Verfahren

• Vorgangsweise:

1. Bob sendet seinen Public Key an Alice.

2. Alice erzeugt einen zufälligen Session Key K und verschlüsselt

diesen mit dem Public Key von Bob und schickt EB(K) an Bob.

3. Bob entschlüsselt Alices Nachricht mit seinem Private Key und

erhält den Session Key K=DB(EB(K)).

4. Beide ver- und entschlüsseln ihre Kommunikation mit dem

Session Key K.

19 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Standards

• Das IEEE P1363 Projekt entwickelt Standard Spezifikationen für

Public-Key Kryptographie.

• Spezifikationen beinhalten:

1. Schlüsselvereinbarungsprotokolle

2. Schlüsseltransportprotokolle

3. Signaturalgorithmen

• Es werden keine Schlüssellängen empfohlen!

20 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Standards

• ANSI Standards:

• X9.30-1 Digital Signature Algorithm (DSA)

• X9.30-2 Hashing Algorithms for DSA

• X9.31-1 RSA Signature Algorithm

• X9.31-2 Hashing Algorithms for RSA

• X9.42 Key Management using Diffie-Hellman

• X9.62 Elliptic Curve Digital Signature Algorithm (ECDSA)

• X9.63 Elliptic Curve Key Agreement and Transport

21 IT-Sicherheit – Kapitel 3 – Public Key Kryptographie

Standards

• Public Key Crypto Standards: (von RSA Laboren aus um asymmetrische Kryptogrphie zu verbreiten)

• PKCS#1 RSA Cryptography

• PKCS#3 Diffie-Hellman Key Agreement

• PKCS#5 Password Based Cryptography

• PKCS#6 Extended Certificate Syntax

• PKCS#7 Cryptographic Message Syntax

• PKCS#8 Private Key Information Syntax

• PKCS#9 Selected Attribute Types

• PKCS#10 Certification Request Syntax

• PKCS#11 Cryptographic Token Interface

• PKCS#12 Personal Information Exchange Syntax

• PKCS#13 Elliptic Curve Cryptography

• PKCS#15 Cryptographic Token Information Format