# Gedächtnisprotokoll Einführung in die Kryptographie 08.03.2021 von Prof. Faust

## Aufgabe 1
- 2 x mal gegeben Keyspace , Ciphertext Messsage space.

- Beim ersten war der keyspace ein Bit kleiner(n - 1) und beim zweiten ein Bit größer als Message Space (n + 1)

a)
$n \ge 1$
$k \in K, m \in M$
$K = \{ 0,1\}^n$
$M = \{0,1 \}^{n-1}$

Das Shannon Theorem besagt $|M| \leq |K|$ für die obere Aufgabe gilt
$|M|-1 = |K|$. Da der Nachrichtenraum kleiner als der Schlüsselraum ist, gilt immer noch die Perfekte Sicherheit nach Shannon.

b)
$n \ge 1$
$k \in K, m \in M$
$K = \{ 0,1\}^n$
$M = \{0,1 \}^{n+1}$

Das Shannon Theorem besagt $|M| \leq |K|$, sodass für die obere Aufgabe gilt
$|M|+1 = |K|$. Das Verletzt das Theorem von Shannon. Es ist nicht Perfekt Sicher.

## Aufgabe 2
- 5 x Funktionen - man musste entscheiden ob sie Neglible sind - und immer begründen - Analog zu der OWF/PRG Aufgaben aus der Probeklausur. (Funktion - JA/NEIN - Begründung)

| Definition | YES/NO | Why? |
|------------|--------|------|
| $G_1: \{0, 1\}^n \rightarrow \{0, 1\}^m, G_1(k) := G(k) \oplus 1^m$ | YES | Let $\|x\| = n$, $x$ is a pseudorandom string $\Rightarrow (x \oplus 1^n)$ is a pseudorandom string. |
| $G_2: \{0, 1\}^n \rightarrow \{0, 1\}^m, G_2(k) := G(k \oplus 1^n)$ | YES | $x \leftarrow \{0, 1\}^n$, i.e. $x$ is a random string $\Rightarrow (x \oplus 1^n)$ is a random string. |
| $G_3: \{0, 1\}^n \rightarrow \{0, 1\}^{m+1}, G_3(k) := G(k) \| 0$ | NO | random string has 0 in last position with $Pr = \frac{1}{2}$, $G_3(k)$ has 0 at last position with $Pr = 1$. |
| $G_4: \{0, 1\}^n \rightarrow \{0, 1\}^{2n}, G_4(k) := F_k(0^n) \| k$ | NO | can use $k$ to check structure of $G_4(k)$. |
| $G_5: \{0, 1\}^n \rightarrow \{0, 1\}^{2n}, G_5(k) := F_k(0^n) \| F_k(1^n)$ | YES | otherwise can break the PRF assumption. |

| Function | Definition |
|----------|------------|
| $$ G'(k) $$ | $$ G'(k) := G(k \oplus 1^n) $$ |
| $$ G'(s) $$ | $$ G'(s) := f(G(s)) $$ |
| $$ f'(x) $$ | $$ f'(x) := f(G(x)) $$ |
| $$ G'(x_1 \parallel x_2) $$ | $$ G'(x_1 \parallel x_2) := G(x_1) \parallel G(x_2) $$ |

- 5 x Funktionen - man muss entscheiden ob es PRFs sind. Analog zur OWF/PRG Aufgabe aus der Probeklausur. (Funktion - JA/NEIN - Begründung)

- 3 x Funktionen - eine Reihe von Funktionen und man muss entscheiden ob es sichere PRGs sind. Analog zu der PRG Aufgabe aus der Probeklausur (Funktion - JA/NEIN - Begründung)

## Aufgabe 3
Symmetrische Verschlüsselung
- CCA Spiel - Textbox ausfüllen
- CCA sicheres Verfahren überprüfen ob es wirklich CCA Sicher ist

## Aufgabe 4
- MAC Definition - Lückentext ausfüllen
- MAC Spiel - Textbox ausfüllen - MacForge
- 2 alternative CBC Macs - entscheiden ob diese sicher sind und begründen - Weihnachtsaufgabe 2a) sehr ähnlich - Macs wurden auch graphisch dargestellt.

## Aufgabe 5
- Asymmetrische Verschlüsselung mit alternativen El-Gamal
- Reduktion zum Ausfüllen zu: Wenn ppt A CPA des Verfahrens bricht, kann auch ppt DDH brechen (Im Prinzip das DDH Spiel)

## Aufgabe 6
- Alternatives Schnorr Verfahren auf Sicherheit prüfen
- beschreibe einen Angriff auf Textbook-RSA-Sig (6pkte)