Kryptologie (Vorlesung 7)

Skript-Anfang	Skript – Seite 24
Skript-Ende	Skript – Seite 29

Sichere Hashfunktionen: Sha-224, Sha-256, Sha-384, Sha-512 (Zahl gibt die Bitgröße des Bildraumes an)
Bitstrings beliebiger länge in Bitstrings fester länge abbilden (H:{0,1}^* → {0,1} ⁿ
Wann erreicht eine Hashfunktion das Sicherheitsniveau von 100 Bit?
- Betrachtung der Eigenschaft #3 Kollisionsresistenz
Folgender Angriff:
- Wähle zufällige Werte m₁ , … , m_k
- Berechne H(m_i)= h_i
- Wahrscheinlichkeit, dass eine Kollision gefunden wird
Offensichtlich: Je kleiner der Bildraum {0,1}ⁿ, desto größer die Wahrscheinlichkeit
Gesucht: Untere Schranke für den Bildraum, d.h. für n (nur eine notwendinge Bedingung für die Sicherheit)

Fragestellung: Wie groß ist die Wahrscheinlichkeit dafur, dass 23 zufällig ausgewählte Personen am selben Tag Geburtstag haben? (Jahrgang spielt keine Rolle)
Wahrscheinlichkeit, dass k Personen alle an unterschiedlichen Tagen Geburtstag haben:
- \( \prod_{i=1}^{n}\frac{365-i+1}{365} \)
- = 365/365 * 364/365 * 363/365 …
Wahrscheinlichkeit dafür, dass mindestens zwei Personen am selben Tag Geburtstag haben:
- \( 1- \prod_{i=1}^{n}\frac{365-i+1}{365} \)
- \( 1-\prod_{i=1}^{n-1}\frac{365-i}{365} \)
- Für n = 10 beträgt die Wahrscheinlichkeit 0.117
- Für n = 23 beträgt die Wahrscheinlichkeit 0.507
- Für n = 36 beträgt die Wahrscheinlichkeit 0.832

Wie groß ist die Wahrscheinlichkeit eine Kollision zu finden?
Ausrechnen wie viele Nachrichten (m₁ , … , m_k) gewählt werden müssen, um mit hoher Wahrscheinlichkeit eine Kollision zu finden
Um Sicherheitsniveau zu erreichen mindestens 2¹⁰⁰ Nachrichten

\( 1-\prod_{i=1}^{n}\frac{2^n-i+1}{2^n} = 1-\prod_{i=1}^{n-1}1-\frac{i}{2^n} \)
Grobe Abschätzung: \( 1-x \approx e^{-x} \)
p ist die Wahrscheinlichkeit eine Kollision bei der Hashfunktion H mit der Wahl von k Nachrichten zu finden
Berechnung mit Hilfe von Gaußsche Summenformel
\( p = 1-e^{\frac{k(k-1))}{2*2^n}} \)

\( p = 1-e^{\frac{k(k-1))}{2*2^n}} \)
\( k \approx 2{\frac{n+1}{2}}*\sqrt{\ln\frac{1}{1-p}} \)
Für die Wahrscheinlichkeit von 50% (p=0.5) zu finden benötigt man also n mit mind. 200
- \( k = 0.83*2^{\frac{k+1}{2}} \)

siehe Definition 1.2
Verfahren, die garantieren, dass übersandte / gespeicherte Daten nicht verändert wurden
Wir unterscheiden:
- symmetrische Verfahren (Schlüssel zur Berechnung und Prüfung der Prüfsumme gleich)
- asymmetrische Verfahren (einen geheimen Schlüssel, zur Berechnung der Prüfsumme, und einen öffentlichen Schlüssel, zur Prüfung der Prüfsumme) →Signaturverfahren