close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Kryptographie I (FSS 09) Übung 1 Anforderungen an Kryptosysteme

EinbettenHerunterladen
¨
Kryptographie I - Ubung
1
1/10
¨
Kryptographie I - Ubung
1
2/10
Anforderungen an Kryptosysteme
Datenbankmanagementsysteme sollen
verl¨assliche Datenhaltung m¨
oglichst effizient erm¨
oglichen
Kryptographie I (FSS 09)
¨
Ubung
1
Analog sollen Kryptosysteme
sichere Kommunikation m¨
oglichst effizient gew¨ahrleisten
Wie spezifiziert man Effizienz?
Laufzeit- und Speicherplatzverbrauch pro Nutzdateneinheit
Programmgr¨
oße
03. M¨arz 2009
...
→ F¨
ur uns im Rahmen von Kryptographie I weniger wichtig
Uns interessiert vor allem: Wie spezifiziert man Sicherheit?
¨
Kryptographie I - Ubung
1
3/10
Was heißt hier sicher?
¨
Kryptographie I - Ubung
1
4/10
Sicherheitsanalyse u¨ber Angreifer
Sicherheit ist immer bezogen auf Sicherheitsziele, z.B.
Um zu analysieren, inwieweit ein gegebenes Kryptosystem ein
bestimmtes Sicherheitsziel erreicht,
Vertraulichkeit
Nur legale Nutzer des Systems k¨onnen Nachrichten lesen.
1
Authentizit¨at und Integrit¨at von Daten
¨
Ubermittelte
Nachrichten stammen tats¨achlich vom
¨
angegebenen Absender und sind w¨ahrend der Ubermittlung
nicht ver¨andert worden.
die Informationen, die ihm zur Verf¨
ugung stehen
seine Berechnungskraft
sein Ziel
2
Authentizit¨at von Kommunikationspartnern
Die Gespr¨achspartner sind wirklich, wer sie vorgeben zu sein.
untersuche, ob und ggf. mit welchem Aufwand ein solcher
Angreifer sein Ziel erreichen kann.
→ Je m¨achtiger die Angreifer, denen das System widerstehen
kann, desto besser.
Problem: Wie will man u
ufen und messen, ob ein System
¨berpr¨
ein bestimmtes Sicherheitsziel erreicht?
¨
Kryptographie I - Ubung
1
definiere einen Angreifer auf das System durch
5/10
Verschl¨usselungssysteme (Chiffren)
¨
Kryptographie I - Ubung
1
6/10
Einfache symmetrische Beispielchiffren
Chiffren sollen das Sicherheitsziel Vertraulichkeit gew¨ahrleisten.
Caesar-Chiffre:
Definition
Eine symmetrische Chiffre besteht aus
E : ΣN × K → ΣN
(x, k) → (x1 ⊗ k, x2 ⊗ k, . . . , xN ⊗ k)
einer Menge P von m¨
oglichen Klartexten
einer Menge C von m¨
oglichen Chiffretexten
mit xi ⊕ k := xi + k mod |Σ|, K = {0, . . . , |Σ| − 1},
Σ {0, . . . , |Σ|}
einer Menge K von m¨
oglichen Schl¨
usseln
einer Verschl¨
usselungsfunktion E : P × K → C
Beispiel: Σ = {A, . . . , Z }
einer Entschl¨
usselungsfunktion D : C × K → P mit
D(E (x, k), k) = x f¨
ur alle x ∈ P und alle k ∈ K
Substitutionschiffre:
E : ΣN × K → ΣN
weitere Eigenschaften:
Ek (x) := E (x, k) ist f¨
ur fixiertes k injektiv (sonst kann man
nicht eindeutig entschl¨
usseln).
Aus Effizienzgr¨
unden gilt oft |C| = |P| bzw. C = P.
Dann sind Ek und Dk bijektiv.
¨
Kryptographie I - Ubung
1
(x, π) → (π(x1 ), π(x2 ), . . . , π(xN ))
mit K = {π : Σ → Σ|π bijektiv}
7/10
Shannon-Modell f¨ur symmetrische Chiffren
Nachrichtenquelle
x
E
y
k
D
k
{0, . . . , 25}, K = {0, . . . , 25}
¨
Kryptographie I - Ubung
1
7/10
Shannon-Modell f¨ur symmetrische Chiffren
x
Nachrichten-
x
E
quelle
Schl¨
ussel-
quelle
quelle
M¨
ogliches Ziel des Angreifers: Finde den Schl¨
ussel k.
unbeschr¨ankt
→ informationstheoretische Sicherheit
beschr¨ankt
→ komplexit¨atstheoretische Sicherheit
D
k
Schl¨
ussel-
M¨
ogliche Berechnungskr¨afte:
y
x
k
M¨
ogliche Informationstypen:
ciphertext only (Angreifer kennt s Chiffretexte)
known plaintext
(Angreifer kennt s Klartext-Chiffretext Paare)
chosen plaintext
(Angreifer kann sich s Klartexte verschl¨
usseln lassen)
chosen ciphertext
(Angreifer kann sich s Chiffretexte entschl¨
usseln lassen)
Immer bekannt: Spezifikation der Chiffre (Kerckhoffs Prinzip)
¨
Kryptographie I - Ubung
1
8/10
Angreifer im Ciphertext-only Szenario (CTO)
¨
Kryptographie I - Ubung
1
9/10
Eigenschaften der Substitutionschiffre
Charlie
E : ΣN × K → ΣN
x ∈ Σn
y ∈ Σn
E
Alice
k
D
(x, π) → (π(x1 ), π(x2 ), . . . , π(xN ))
x
mit K = {π : Σ → Σ|π bijektiv}
Bob
k
Beobachtung: Wenn die relative H¨aufigkeit von σ in x durch q(σ)
gegeben ist, dann ist die relative H¨aufigkeit von π(σ) in y ebenfalls
q(σ).
→ H¨aufigkeiten u
¨bertragen sich direkt auf den Chiffretext.
Schl¨
usselquelle
Charlie kennt verschl¨
usselte Nachricht y und sucht geheimen Schl¨
ussel k.
Beste Angreiferstrategie: Bayes-Entscheidung, d.h. bestimme x ∗ ∈ P mit
Angriffsstrategie f¨
ur Σ = {a,. . .,z} und S = {deutsche Texte}:
Vermute, dass h¨aufigster Buchstabe in y der Verschl¨
usselung
von e entspricht.
Vermute, dass zweith¨aufigster Buchstabe in y der
Verschl¨
usselung von n entspricht.
usw.
Pr[x = x ∗ |Y = y ] = max Pr[X = x|Y = y ] .
x∈P
Wir wissen aus der Vorlesung:
Pr[X = x |Y = y ] =
Pr[X = x ] · |{k ∈ K : E (x , k) = y }|
.
Pr[X = x] · |{k ∈ K : E (x, k) = y }|
x∈P
¨
Kryptographie I - Ubung
1
10/10
Analyse und Gegenmaßnahmen
Um abzusch¨atzen, mit welcher Wahrscheinlichkeit diese
Vermutungen zutreffen, seien
q(σ) := relative H¨aufigkeit von σ ∈ Σ in fixiertem Klartext x
p(σ) := Auftrittswahrscheinlichkeit von σ .
Dann gilt die H¨
offdingsche Ungleichung
Pr[|q(σ) − p(σ)| > δ] < 1 − 2e −2δ
2N
.
Anwendung auf die Substitutionschiffre: Aufgabe 1.2
Wie kann man den Angriff auf die Substitutionschiffre erschweren?
Verschl¨
ussle Buchstabenbl¨
ocke statt einzelner Buchstaben
Idealfall: Kein Chiffretextblock tritt doppelt auf
¨
→ Blockl¨ange hinreichend groß w¨ahlen (vgl. n¨achstes Ubungsblatt)
Document
Kategorie
Internet
Seitenansichten
9
Dateigröße
112 KB
Tags
1/--Seiten
melden