Kryptologie (Vorlesung 7)

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

Hashfunktionen

• 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)

Geburtstagsparadoxon

• 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

Anwendung auf Hashfunktion

• 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

Wie groß ist die Wahrscheinlichkeit eine Kollision zu finden?

• \( 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}} \)

Wie viele Nachrichten benötige ich dafür?

• \( 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}} \)

Datenauthentisierung

• 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