TUD Logo

TUD Home » ... » Teaching » Operating Systems and Security » Cryptography

Operating Systems

Exercise: Cryptography

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!
Last modified: 3rd Dec 2018, 5.54 PM
Author: Jan Bierbaum

Contact
Sorry — there was an error in gathering the desired information

Regulations
  • ModuleModules: INF-B-380, INF-LE-EUI
  • 4/2/0 = 6 SWS
Time and Place
  • Lecture, weekly
    TimeTue, 9.20 AM PlaceHSZ 0004
  • Lecture, weekly
    TimeFri, 9.20 AM PlaceHSZ 0003
Mailing List