# Gedankenprotokoll Einfuehrung in die Kryptographie WS2023

- Aufbau relativ ähnlich zur Musterklausur SoSe 2022
- auch zeitlich sehr eng

## Aufgabe 1: Perfekte Sicherheit & Vernachlaessigbare Funktionen

### Aufgabe 1.1: Perfekte Sicherheit

KGen($1^N$):
$N = 2^\lambda$
$k <-\$ [0, N - 1]$
return $k$

Enc (k, m):
$N = 2^\lambda$
return $k + m \mod N$

Dec (k, c):
$N = 2^\lambda$
return $k + c \mod N$
wahrscheinlich war hier eher $k - c \mod N$ gemeint (d.h. keine Korrektheit vom Schema Dec(Enc(..))!=m und somit nicht perfekt sicher?)

Wann ist ein Verfahren perfekt sicher? Begruenden Sie, ob dieses Verfahren perfekt sicher ist.

### Aufgabe 1.2: Vernachlässigbare Funktionen

a) $\frac{n^5+1}{n^3} \cdot n^{-\log \log n}$
b) $\frac{n!}{n^5}$
c) Gilt für alle vernachlässigbaren Funktionen $\lim_{n\to\inf} f(n) = 0$

## Aufgabe 2: Pseudozufall
- zwei KGen Funktionen gegeben, und angenomen G ist PRG
- 1. return $k \in (0,1)^{4\lambda}$
- 2. $s \in (0,1)^{\lambda}, \text{return }PRG(s)$
- welche der beiden KGens kann man schneller Brute-Forcen?

- Neues Spiel "weak/schwache PRF" gegeben. Zeigen Sie, dass jede sichere PRF auch eine schwache PRF ist. (Reduktionsbox gegeben, ausserdem dazu alle "Argumente" aufschreiben (effizienz, ununterscheidbar, gewinnwsk))

- Gegeben sichere PRF F. PRF F' die F(k,x+1) ausgibt falls x ungerade, sonst F(k,x). Beweisen Sie, dass die PRF F nicht sicher ist.
- Lösung: Angreifer wählt x_0 zufällig >1 gerade und x_1 = m_0 - 1 (also ungerade). Er fragt beides am Orakel an, falls b=0 sind y_0=y_1, weil F(k, x_1) = F(k, x_0 -1 +1) = F(k, x_0). Angreifer ist effizient & gewinnt immer mit dieser Strategie

- Gegeben sichere PRF F. PRF F' die $0^\lambda$ ausgibt falls $x=0^\lambda$ oder $x=1^\lambda$, sonst F(k,x). Beweisen Sie, dass die PRF F nicht sicher ist.
- Ich habe in Erinnerung, dass die Aufgabe eine Hashfunktion, 2PR anstatt PRF F'. Habe ich mir das falsch gemerkt?

- Argumentieren Sie, dass F' schwach sicher ist

## Aufgabe 3: Blockchiffren und Modes of Operation

- neuer in der Vorlesung nicht behandelter Operationsmodus gegeben (graphisch, nur ENC)(IGE: https://blog.susanka.eu/ige-block-cipher-mode/)
- Luecken in der graphischen Version von Dec dazu ausfuellen
- dazu die Funktionen fuer Enc und Dec aufschreiben
- Mit CBC vergleichen bzgl zwei Egenschaften (hier sollte auch der Unterschied noch aufgezeigt werden)
- Ob bei IGE auch in Dec vorgerechnet werden kann.
- Ob bei IGE auch wie bei CBC bei Verlust eines c_i dann m_i und m_i+1 betroffen werden.
- Warum/ob der IV zufällig gewählt wird anstatt fest?
- Was ist algorithmisch der Unterschied zwischen Enc Ausgabe von CBC und von IGE?
- Erläutern, ob bzw. warum parallele Entschlüsselung möglich ist oder auch nicht bei IGE.

Enc war irgendwie $c_i = m_{i-1} \oplus F_k(m_i \oplus c_{i-1})$ mit $c_0 = IV_c$ zufällig und $m_0 = IV_m$ zufällig (oder andere Namen)

## Aufgabe 4: MACs & symmetrische Verschluesselung

- gegeben MAC_1 als Verfahren konstruiert aus MAC sicherem Verfahren MAC, gibt einfach nur anstatt $(\tau)$ $(m,\tau)$ zurueck, auch Vf entsprechend angepasst, dass nur das hintere verifiziert wird und m in Tag gleich übergebener Nachricht ist
- Beweisen Sie, dass MAC_1 SUF-CMA ist (komplette Reduktion mit allen Argumenten, keine Boxen vorgezeichnet)
- Encrypt-and-MAC-Schema mit MAC_1 als IND-CCA beweisen oder widerlegen
- Enc_1 = (Enc(m), Mac_1(m))
- Lösung ist einfach m aus dem Tag auslesen, da das Tag aus dem Klartext anstatt Ciphertext erstellt wurde und Mac_1 an das $\tau$ auch m im Klartext anhängt. Somit ist das Verfahren weder IND, noch IND-CPA oder IND-CCA

## Aufgabe 5: Hashfunktionen

a) Passwörter können mithilfe von SHA-3 gespeichert werden: $SHA-3(password)$ Dabei können Salts eingesetzt werden: $(salt, SHA-3(salt || password))$. Nennen Sie einen Vorteil von Salts (?)

b) Welche Konstruktion kann verwendet werden, um eine Hashfunktion zu bauen?

c) Geben sie ein Signaturverfahren an, dass eine Hashfunktion nutzt.

## Aufgabe ?: Asymetrische Verschlüsselung
a) Lückentext mit DDH-Annahme

b) auch ein Lueckentext mit IND-CPA von PKE.

c) Zeigen, dass ein Angreifer der DLog brechen kann, auch das CDH-Problem loesen kann

- Was unterscheidet KEM von PKE-Verschluesselungsverfahren?

## Aufgabe 7: Digitale Signaturen

a) Ein Smartphone kommuniziert mit einem Webserver. Zu Beginn der Kommunikation möchte der Webserver seinen Namen "Integritätsschützen" (weiß nicht mehr das Verb). MAC oder Digitale Signaturen? Warum?

b) Hash-then-Sign: Funktionsweise kurz erklären
c) Hash-then-Sign: Vorraussetzungen für EUF-CMA
d) Hash-then-Sign: Was wird darüber hinaus für SUF-CMA für H-then-Sign benötigt