Kryptographie II (5 ECTS)

Mega entspannte Atmosphäre. Ruppert ist cool drauf. Alle Antworten sollten auch an die Tafel geschrieben werden (auch Antworten, die keine Formeln waren) Wenn nicht gerade Corona ist schreibt man bei ihm auf Papier Ergebnis: 1.0

1. Mit was wollen Sie denn anfangen?
→ Primzahltests
2. Ok. Wofür braucht man Primzahltests denn?
→ große Primzahlen braucht man für diverse Verschlüsselungsverfahren
3. Wie groß müssen die Primzahlen denn so sein?
→ ssh-keygen so ca. 4096 bit. BSI empfiehlt mehr als 3000 bit (Primzahlen also dann halb so groß)
4. Welche Primzahltests kennen sie denn (es sollten nur welche genannt werden)
→ Fermat-Test, Miller-Rabin-Test, Solovay-Strasen-Test, BPSW (das ist der Beste Test. Bisher wurde noch kein zusammengesetztes n gefunden, welches diesen Test besteht)
5. Erklären sie doch mal den Solovay-Strasen-Test (der kam dieses Semester [im vgl. zu Krypt I im letzten Semester] neu dazu)
6. Und was ist das für ein Symbol (deutet auf Jacobi Symbol)?
→ Jacobi-Symbol
7. Wie ist das definiert?
→ Formel angeschrieben
8. Welche Eigenschaften hat das Jacobi-Symbol?
→ ich habe erstmal dumm geschaut, mit einem kleinen Schubs war dann aber klar was er hören wollte
→ quadratisches Reziprozitätsgesetz, Formeln für a=2 und a=-1, (a/n) = (a mod n/n), (a*b/n) = (a/n)*(b/n)
9. Das Jacobi-Symbol ist die Erweiterung des…
→ Legendre-Symbols
10. Beide Symbole haben ja ähnliche Eigenschaften. Was sagt denn das Legendre-Symbol aus?
→ a ist ein Quadrat mod p (x^2 = a mod p existiert)
11. Wenn das Legendre-Symbol also 1 ist weiß man das so ein x existiert. Können sie das jetzt auch ausrechnen?
→ Tonelli-Verfahren (erklärung des Tonelli-Verfahren wollte er nicht haben)
12. Kennen sie eine Formel zum Berechnen?
→ a^((p+1)/4) ist Quadratwurzel zu a, falls p = 3 mod 4
13. Kommen wir nun zu den Anwendungen. Welche Verfahren kennen sie wo sie die großen Primzahlen vom Anfang benötigen?
→ Goldwasser-Micali-Verfahren ausführlich erklärt
→ Angreifer der den Ciphertext abfängt kann nicht feststellen, ob b_i ein Quadrat mod N ist (dafür müsste er p, q kennen. Jacobi-Symbol (b/n) zu berechnen bringt ihm auch nichts)
14. Kennen sie noch ein Verfahren?
→ Fiat-Shamir Identifikationsprotokoll
→ Allgemein: Man identifiziert sich dadurch dass man Wurzeln mod N berechnen kann (ohne die Wurzeln der anderen Seite zu zeigen)
→ Funktionsweise erklärt
→ Kurz angeschnitten warum ein Angreifer auf lange Sicht keine Chance hat sich für jemand anderen auszugeben, dann war die Zeit schon rum