Public Key Kryptographie

Transcrição

Einführung
Einwegfunktionen
Diffie Hellman Schlüsseltausch
Massey Omura Kryptosystem
Georg Stütz
4. Dezember 2007
Georg Stütz
Einführung
Einwegfunktionen
Outline
1
Einführung
2
Einwegfunktionen
3
4
Georg Stütz
Einführung
Einwegfunktionen
Einführung
1976 – Whitefield Diffie und Martin Hellman
2 Schlüsselprinzip – Asymmetrische Verschlüsselungsverfahren
public Key
private Key
Anwendung
E-Mail – PGP openPGP
https
digitale Signatur
Georg Stütz
Einführung
Einwegfunktionen
Anwendungsbeispiel
A und B wollen sicher kommunizieren (symmetrisch)
tausch eines Schlüssels k mit Public-Key Verfahren
A sendet eB (k) an B
B kann mit dB die Nachricht eB (k) entschlüsseln:
dB (eB (k)) = k
Georg Stütz
Einführung
Einwegfunktionen
Unterschiede zwischen symmetrischen und asymmetrischen
Verfahren
Anzahl der Schüssel
Verschlüsselungszeit
Schlüssellänge
Schlüsseltausch
Geheimhaltung der Schlüssel
Georg Stütz
Einführung
Einwegfunktionen
Unterschiede zwischen symmetrischen und asymmetrischen
Verfahren
Verschlüsselungsgeschwindigkeit
Schlüsselanzahl bei
n Teilnehmern
Symmetrisch
Public-Key
hoch
niedrig
n
2
=
n∗(n−1)
2
n
Schlüssellänge
kurz (64, 128, 256
Bit)
relativ lang (1024,
2048 Bit)
Schlüsselgenerierung
einfach
aufwändig
Georg Stütz
Einführung
Einwegfunktionen
Einwegfunktionen
schwierig berechenbar −→ nicht in polynomialer Zeit
berechenbar
Definition
Eine Funktion f : D −→ B bei der sich f (x) ∀x ∈ D einfach
berechnen lässt, während es für fast alle y ∈ Im(f ) schwierig ist ein
Urbild von y (d.h. f (x) = y ) zu bestimmen, wird als
Einwegfunktion bezeichnet.
Definition
Eine Einwegfunktion f : D −→ B bei der sich mit Kenntnis einer
Zusatzinformation (trap-door) auch f −1 (y ) einfach berechnen
lässt, wird als trap-door Funktion bezeichnet.
Georg Stütz
Einführung
Einwegfunktionen
Square and multiply Methode
Siehe RSA Präsentation
Georg Stütz
Einführung
Einwegfunktionen
Beispiel für eine Einwegfunktion
fg ,N : x 7→ g x mod N ist eine Einwegfunktion
f ist ∀x ∈ N in polynomialer Zeit berechenbar
Umkehrfunktion f −1 = logg (y ) nach derzeitigem
Wissensstand nicht in Polynomialzeit berechenbar
Georg Stütz
Einführung
Einwegfunktionen
Beispiel für eine trap-door Funktion
fk,N : x 7→ x k mod N ist eine trap-door Funktion falls,
1
2
N = pq mit p und q prim
ggT(k, ϕ(N)) = 1
Berechnung von k −1 mod ϕ(N) mit dem erweiterten
Euklidischen Algorithmus
−1 l
−1
≡ x 1+lϕ(N) ≡ x x ϕ(N) ≡ x · 1l ≡ x
(x k )k ≡ x kk
mod N
Georg Stütz
Einführung
Einwegfunktionen
1976 – Whitefield Diffie – Martin Hellman
Verwedung zur Erzeugung eines geheimen Schlüssels
basiert auf dem diskreten Logarithmus Problem
Georg Stütz
Einführung
Einwegfunktionen
Das Verfahren
Teilnehmer A und B wollen sicher kommunizieren
wählen große Primzahl p und ein g ∈ {1, 2, . . . , p − 1} sodass
g ein Generator von F∗p ist
A wählt ein zufälliges a ∈ {1, 2, . . . , p − 1}
berechnet g a ∈ F∗p und überträgt g a an B
B wählt ein zufälliges b ∈ {1, 2, . . . , p − 1}
berechnet g b ∈ F∗p und überträgt g b an A
g ab ∈ F∗p gemeinsamer geheimer Schlüssel
A und B können diesen berechnen, da
(g b )a = g ba = g ab = (g a )b ∈ F∗p
Georg Stütz
Einführung
Einwegfunktionen
Bestimmung eines Generators von F∗p
durch sukzessives Ausprobieren der Elemente von F∗p
durch zufälliges Auswählen eines Elements a ∈ F∗p
ϕ(p − 1) Generatoren in F∗p
für p − 1 = 2q für q prim −→ Wahrscheinlichkeit
ϕ(p−1)
q−1
1
p−1 = 2q ≈ 2
1
allgemeinen Fall −→ Wahrscheinlichkeit ≥ 6 ln ln(p−1)
überprüfen ob ein a ∈ F∗p Generator ist
nur bei gegebener Faktorisierung von p − 1 effizient möglich
Georg Stütz
Einführung
Einwegfunktionen
Man in the middle Attack
Angriffsform auf Rechnernetze.
Der Angreifer befindet sich dabei physikalisch oder logisch
zwischen den Teilnehmern.
Der Angreifer erhält die Kontrolle über den Datenverkehr
Er täuscht den Kommunikationspartnern ihr jeweiliges
Gegenüber vor.
Georg Stütz
Einführung
Einwegfunktionen
ermöglicht Teilnehmern den Austausch geheimer Nachrichten
ohne gemeinsamen geheimen Schlüssel
basiert auf dem diskreten Logarithmus Problem
Georg Stütz
Einführung
Einwegfunktionen
Das Verfahren
Teilnehmer A und B wollen Nachricht N sicher austauschen
wählen große Primzahl p
A wählt sich ein eA mit ggT(eA , ϕ(p)) = 1
brechnet eA−1 mit erweiterten euklidischen Algorithmus
B wählt sich ein eB mit ggT(eB , ϕ(p)) = 1
brechnet eB−1 mit erweiterten euklidischen Algorithmus
A berechnet N eA und sendet dies an B
B berechnet sich aus N eA die Information (N eA )eB = N eA eB
und sendet dies an A
A berechnet sich nun mittels eA−1 die Information
−1
−1
(N eA eB )eA = N (eA eA )eB = N eB und sendet dies an B
−1
B kann nun mit eB−1 die Nachricht N eB eB = N entschlüsseln
Georg Stütz
Einführung
Einwegfunktionen
Sicherheit
dritte können durch mithöhren nicht auf den Originaltext
schließen
Man In The Middle Attacke
Authentifizierung
Georg Stütz
Einführung
Einwegfunktionen
Vielen Dank für Ihre Aufmerksamkeit!
Georg Stütz

Public Key Kryptographie

Transcrição

Documentos relacionados

Mitschrift 21.04.2015

MASSEY FERGUSON MF 5700 SL: ALLROUNDER DER

Literaturempfehlun gen bis zum Ende der Schulzeit 1

Professor Dr. Joachim von zur Gathen - Gepris

SubVirt

Paper

MF 400 - Die BayWa

Scheduling

DSA-Rätsel 1 - orakeldel.net

Sicherheitsanalyse des WEP Protokolls im IEEE 802.11

Entwurf einer Sicherheitsinfrastruktur in VANETs