Kryptographische Grundlagen - Fakultät für Mathematik

Transcrição

Symmetrische Verschlüsselung
Asymmetrische Verschlüsselung
Kryptographische Grundlagen
Bernhard Lamel
Universität Wien, Fakultät für Mathematik
10. Mai 2007
Praxis
Outline
1
2
3
Praxis
Praxis
Verschlüsseln und Entschlüsseln
A und B sind im Besitz eines Schlüssels K und eines
Algorithmus S(K , M), der eine Nachricht M in
verschlüsseln kann:
C = S(K , M) (die “Chiffre”) kann mit Hilfe von K wieder in
M übersetzt werden, M = S −1 (K , C)
Aus C soll weder auf K noch auf M geschlossen werden
können
Alle Schlüssel ausprobieren immer möglich (“Brute-Force”
Attacken); Anzahl der möglichen Schlüssel deswegen
wichtig!
Algorithmen sind öffentlich–Schlüssel sind geheim
Praxis
Ein Beispiel–oder warum Algorithmen wichtig sind
A und B einigen sich auf einen 8-Bit Schlüssel, sagen wir,
01010101 = 85, und verschlüsseln ihre Nachricht (eine
Folge von ganzen Zahlen zwischen 0 und 256) mit Hilfe
eines logischen “XOR” (dh 1 wenn die Bits ungleichen
Wert haben, 0 sonst)
Aus {2, 13, 14} = {102 , 11012 , 100010102 } wird so
{87, 88, 91}
Um zu entschlüsseln, nimmt man dann einfach ein XOR
des Schlüssels mit der Chiffre
Problem: Aus Kenntnis des Klartexts M kann auf den Schlüssel
geschlossen werden! (Mögliche Angriffe sollten so teuer sein
wie Brute-Force) Wichtige Verschlüsselungsalgorithmen:
(Triple) DES, Rijndael, Blowfish,. . .
Praxis
Wie komme ich an den Schlüssel?
Das Schlüsselverteilungsproblem war schon immer wichtig
(Codebücher, usw)!
Schlüssel sollten geheim bleiben
Persönliche Weitergabe meist schwierig
Vertrauen in dritte Person problematisch
Praxis
Der Diffie-Hellman Schlüsselaustausch
A und B einigen sich auf ein Paar (g, p), wo p eine Primzahl ist
und g eine primitive Wurzel.
Hilfe, was heisst das?!?!
Eine Primzahl ist eine Zahl, die nur durch sich selber (und 1)
teilbar ist. Mit den Restklassen modulo p, die durch die Zahlen
0, . . . , p − 1 repräsentiert werden können, rechnet man wie mit
normalen Zahlen, nur um sie zu vergleichen, reduziert man sie
auf ihren Rest, wenn man durch p dividiert. Dass g eine
primitive Wurzel ist, heisst daß g p−1 = 1 ist, aber g j 6= 1 für
j < p − 1. (g erzeugt die multiplikative Gruppe der Restklassen
mod p)
Praxis
Restklassen modulo 5
Example
Die Restklassen modulo 5 sind 0, 1, 2, 3, 4. Für die
Exponentiation haben wir:
g
1
2
3
4
g2
1
4
4
1
g3
1
3
2
4
g4
1
1
1
1
Also sind 2 und 3 primitive Wurzeln modulo 5, 1 und 4 nicht.
Praxis
Also, A und B haben sich auf (g, p) geeinigt–(g, p) ist öffentlich!
A wählt nun eine geheime Zahl M ≤ p − 1, und bildet g M . B
wählt eine geheime Zahl N ≤ p − 1 und bildet g N . Diese
Zahlen werden nun verschickt. Nun bildet B (g N )M = K , und A
bildet (g M )N = K . A und B befinden sich nun im Besitz von K .
Example
Wir wählen (g, p) = (2, 5). A wählt M = 2 und sendet B 4. B
wählt N = 3 und sendet A 3. Nun bildet A 32 = 4 und B 43 = 4.
Praxis
Wie schwierig ist es, N zu finden, wenn man g N kennt?
Es gibt keinen effizienten Algorithmus, um N
auszurechnen–dh man kann im Grunde einfach für jedes j
g j bilden und mit g N vergleichen.
Die Anzahl der Zahlen mit, sagen wir, 300 Stellen ist 10300 ;
wir wählen p in dieser Grössenordnung. Die Grösse von g
ist eigentlich unerheblich. Angenommen, wir können jede
Sekunde 1000000 = 106 Zahlen überprüfen, dann
brauchen wir ungefähr 1050 Sekunden um N zu finden.
Das Universum existiert seit ungefähr 4, 3 ∗ 1017
Sekunden.
Zusammengenommen: Es dauert wirklich, wirklich lange.
Praxis
Praktische Probleme
Der öffentliche Schlüsselaustauch ist inherent gegen
"Man-in-the-Middle"-Attacken anfällig
Es ist also notwendig, daß wir uns sicher sind, daß
tatsächlich der gewünschte Kommunikationspartner am
anderen Ende ist!
Praxis
Asymmetrische Verschlüsselung-Public Key
Cryptography
A und B befinden sich jeder im Besitz eines privaten
Schlüssels KA (bzw KB ), sowie eines öffentlichen
Schlüssels PA (bzw PB ). Wir identifizieren im folgenden die
Schlüssel mit den durch sie durchgeführten
Verschlüsselungen (i.e. PA (M) ist die Chiffre der Nachricht
M unter dem Schlüssel PA )
Der Verschlüsselungsalgorithmus erfüllt:
K (P(M)) = P(K (M)) = M.
Durch die Kenntnis von P, M, und P(M) kann man nicht auf
K schliessen
Durch die Kenntnis von M und K (M) kann man auch nicht
auf K schliessen
Praxis
Mit Hilfe eines solchen Systems lassen sich die Probleme von
vorher ziemlich rasch aus der Welt schaffen.
Private Nachrichten: A sendet B eine Nachricht, indem sie
PB (M) übermittelt. Damit kann nur jemand etwas
anfangen, der KB kennt (also, hoffentlich nur B!)
Authentifizierung des Kommunikationspartners: A
unterschreibt ihre Nachricht, indem sie KA (M) übermittelt.
Diese kann mit Hilfe von PA (bekannt) entschlüsselt
werden–und kann ja nur von A stammen!
Kombination: A schickt einfach PB (KA (M)). Nur B kann
entschlüsseln, und auch sichergehen, daß die Nachricht
von A stammt.
Schlüsselverteilung: Nachdem es möglich ist, mit seinem
privaten Schlüssel die Authentizität eines öffentlichen
Schlüssels zu bestätigen, können (mit Hilfe geeigneter
Infrastruktur, PKI, “Web of Trust”) vertrauenswürdige
öffentliche Schlüssel übergeben werden.
Praxis
Der RSA-Algorithmus
Der Schlüssel besteht aus einer Zahl n = pq, die Produkt
von zwei Primzahlen ist, sowie Zahlen d (teilerfremd zu
(p − 1)(q − 1)) und einer Zahl e, die de = 1 modulo
(p − 1)(q − 1) erfüllt
(e, n) ist der öffentliche, (d, n) der private Schlüssel
Verschlüsselt wird M durch C = M e (modulo n);
entschlüsselt wird C durch M = C d (modulo n).
Das Finden des Schlüssels ist so schwierig wie das
Faktorisieren von n in Primfaktoren (und das ist schwer!)
Das Paper von Rivest-Shamir-Adleman kann auf
http://theory.lcs.mit.edu/~cis/cis-publications.html
gefunden werden
Praxis
Wie sicher kann das sein?
Um Zahlen zu faktorisieren, muss man–im Grunde–einfach
für alle Primzahlen (bis zu einer bestimmten Grösse)
ausprobieren, ob sie die gegebene Zahl teilen.
Der Primzahlsatz besagt, daß die Anzahl π(N) der
Primzahlen kleiner gleich N asymptotisch N/ ln N ist:
π(N) ≈
N
.
ln N
Die Verteilung der Primzahlen ist extrem irregulär und
unvorhersagbar (zB Primzahlpaare, Satz von Green-Tao)
Praxis
Beispiel: OpenSSL und vsftpd
Natürlich brauchen wir OpenSSL–also installieren–ich tippe
apt-get install openssl.
Schlüssel erstellen
openssl req -x509 -nodes -days 365 \
-newkey rsa:1024 \
-keyout /etc/ssl/certs/vsftpd.pem \
-out /etc/ssl/certs/vsftpd.pem
openssl erstellt ein X509 Zertifikat und stellt dazu ein paar
Fragen.
Nun passen wir noch die Konfiguration von vsftpd an
und–übermitteln unsere Passwörter nicht mehr im Klartext!
Praxis
Beispiel: SSH
SSH verwendet folgenden Ansatz:
Bei der ersten Kontaktaufnahme übermittelt der Server
seinen Public Key an den Client, welcher ihn mit einer
Datenbasis abgleicht und ihn uU abspeichert
Ist der Key unbekannt, so ist das Verhalten konfigurierbar
Selber erstellt man Keys für ssh mit ssh-keygen. Schlüssel
werden auf Client-Seite mit ssh-agent und ssh-add
verwaltet.
Praxis

Kryptographische Grundlagen - Fakultät für Mathematik

Transcrição

Documentos relacionados

Better Privacy

Pressemitteilung

Pearl Vibe

LCS-PL200-KIT

Datenschutz

INHALTSVERZEICHNIS Vorbereitung: Gebrauchshinweis

DES und AES

Sicherheit

Verschlüsselung von Bestandsdaten aus Rechenzentrumssicht

Sicherer Surfen im Internet – aktuelle Tipps und Trends