TUD Logo

TUD Startseite » ... » Lehre » Betriebssysteme und Sicherheit » Kryptographie

Betriebssysteme

Übung: Kryptographie

Kryptographie

Geplante Bearbeitungszeit: eine Woche

1. Aufgabe:

  1. Welches sind die drei Haupt-Schutzziele in der Datensicherheit?
  2. Welche Aufgaben haben kryptographische Systeme?
  3. Nach welchem Grundprinzip arbeiten solche Systeme? Was versteht man unter symmetrischen, asymmetrischen und hybriden kryptographischen Systemen?

2. Aufgabe:

Der RSA-Algorithmus (Algorithmus von Rivest/Shamir/Adleman, 1977) hat folgende Struktur:
  1. Wähle zufällig zwei Primzahlen p ≠ q mit annähernd gleicher Stellenzahl.
  2. Bilde n = pq. In diesem Fall gilt für die Eulersche Funktion φ: φ(n) = (p − 1)⋅(q − 1).
  3. Wähle c mit 2 < c < φ(n), so dass ggT(c, φ(n)) = 1.
  4. Berechne d mit cd ≡ 1\operatornamemodφ(n) und 1 < d < φ(n).
  5. Verteile den Modul n sowie c als öffentlichen Schlüssel und nutze d als privaten Schlüssel.
Eine Nachricht x wird durch xc ≡ y\operatornamemodn verschlüsselt und entschlüsselt durch yd ≡ x\operatornamemodn, wobei 0 ≤ x, y < n.
  1. Auf welcher Annahme basiert die Sicherheit dieses Algorithmus?
  2. Begründen Sie die einzelnen Restriktionen in und . Welche Aussage trifft die Eulersche Funktion? Welche Bedeutung hat Schritt für das Vorgehen?
  3. Demonstrieren Sie den RSA-Algorithmus an folgendem Beispiel:\begin_inset Separator latexpar\end_inset
    Der Modul sei n = 55, der öffentliche Schlüssel sei c = 7. Verschlüsseln Sie damit die Nachricht x = 2. Berechnen Sie den privaten Schlüssel d, entschlüsseln Sie die verschlüsselte Nachricht und zeigen Sie deren Übereinstimmung mit x.
Hinweise:
  • Benutzen Sie zur Berechnung des ggT zweier Zahlen a und b mit (o.B.d.A.) a > b sowie der Summendarstellung nach dem Erweiterten Euklidischen Algorithmus eine Tabelle folgender Form:\begin_inset Separator latexpar\end_inset
    a b
    a 1 0
    b 0 1
    xi si ti yi
    mit
    yi =  − (xi − 1\operatornamedivxi)
    xi + 1 = xi − 1\operatornamemodxi
    si + 1 = siyi + si − 1
    si + 1 = siyi + si − 1
    \operatornamediv bezeichnet die ganzzahlige Division, \operatornamemod den dabei auftretenden Rest.
    In obiger Tabelle beginnt i mit 0, die Formeln gelten ab i = 1 (zuerst ist also y1 in der „b-Zeile“ zu berechnen). Der Algorithmus bricht ab bei xi = 0, und dann gilt: xi − 1 =  ggT(a, b) = si − 1a + ti − 1b.
    Die letzte Gleichung gilt auch in jeder Zeile, was zur Rechenkontrolle genutzt werden sollte.
  • Benutzen Sie zur Entschlüsselung der Nachricht binäre Exponentiation, auch bekannt als „Square and Multiply“. Zur einfachen Notation bietet sich dabei das folgende Schema zur Berechnung von ab an:
    b a
    xi yi
      mit  xi + 1  = xi÷2 x0  = b yi + 1  = y2i y0  = a
    Der Algorithmus bricht ab bei xi = 1. Abschließend werden alle diejenigen yi zum Endergebnis aufmultipliziert, deren zugehöriges xi ungerade ist.

3. Aufgabe:

Um die Faktoren p, q eines RSA-Schlüsselpaars zu generieren werden in der Praxis Zufallszahlen benutzt.
  1. Wie kann man auf einem Computer Zufall (Entropie) erzeugen?
  2. Einige Endgeräte verwenden schlechte Entropiequellen. Was kann passieren, wenn eine große Anzahl solcher Systeme RSA-Schlüssel generiert?
  3. Die öffentlichen Schlüssel von Alice und Bob haben folgende Moduln: na = 73.684.837 und nb = 63.546.229. Überprüfen Sie, ob beide Moduln sich einen Faktor teilen! Faktorisieren Sie na und nb!
Stand: 9.12.2018, 22:48 Uhr
Autor: Jan Bierbaum

Kontakt
Bitte entschuldigen Sie – beim Einbinden der Informationen ist ein Fehler aufgetreten

Regelungen
  • ModuleModule: INF-B-380, INF-LE-EUI
  • 4/2/0 = 6 SWS
Zeit und Ort
  • Vorlesung, wöchentlich
    TimeDi, 9:20 Uhr PlaceHSZ 0004
  • Vorlesung, wöchentlich
    TimeFr, 9:20 Uhr PlaceHSZ 0003
Mailingliste