# Krypto für Klausur
**Generelles Vorgehen:**

Annahme
Definition
Beweis
Fazit/Aussage

## Korrektheit zur Private Key Verschlüsselung

$Dec_k(Enc_k(m)) = m$

## Perfekte Sicherheit


## Negl.

## OWF


1) $\exists ppt$ Algorithmus und positive Polynom $p$
2) Annahme: $f'$ kein OWF $Pr[Invert_{A',f'}(n) = 1] \leq \frac{1}{p(n)}$
3) Algorithmus $A$ erstellen und nutzt $A'$, sodass man OWF invertieren kann
4) $A'$ ist PPT $\Rightarrow$ A ist ein PPT
5) $A$ ist PPT, dann kann $A$ keine OWF invertieren, was ein Widerspruch ist $\unicode{x21af}$
6) Wenn man $A$ invertieren kann, dann kann $A'$ erst recht invertieren
7) Deshalb war die Probability von A höher

* Meistens sind OWF mit Konkatenation ($\mathbin\Vert$) **immer** OWF
* Meistens sind OWF mit XOR ($\oplus$) **keine** OWF

| OWF | Yes/No | Why | Proof method|
| ----------------------------------------- | -------- | -------- | --- |
| $f'(x) = f(x) \oplus g(x)$ | ✖ | $f(x) = g(x)$ | Design counter example |
| $f'(x_1 \mathbin\Vert x_2) = f(x_2) \mathbin\Vert 0^n$|✔|$f'$ insecure $\Rightarrow f$ insecure, but this contradicts that $f$ is a OWF|Proof by contradition|
| $f'(x) = f(f(x))$ |✖|Verwende $f'(x_1 \mathbin\Vert x_2) = f(x_2)\oplus 0^n$ und komme auf $g(0^n) \mathbin\Vert 0^n$|Design counter example|
| $f'(x_1,x_2) = f(x_1) \mathbin\Vert f(x_2)$ |✔|$f(x_1)$ und $f(x_2)$ geben zufällige Werte aus und daher kann $A'$ kein|Direct proof|

# PRG


Starke PRP hat zusätzlich Zugriff auf eine umkehrfunktion F-1 abhängig von k

strong PRP
Bspw: 4 Runden Feistel, wenn Rundenfunktion eine PRF ist

| PRG | Yes/No | Why | Proof method |
| ----------------------------------------- | -------- | -------- | --- |
| $G'(s) = G(s) \mathbin\Vert s$ | ✖ | Define the $s$ part as $x_1...x_l(n) = G(x_{l(n)+1}...x_{l(n)+n})$. It is easy to see that $D$ can distinguish $s$, because $\underbrace{G(s)}_{\text{Länge } l(n)} \mathbin\Vert \underbrace{s}_{G(x_{l(n)+1}...x_{l(n)+n})}$ | Design counter example |
| $G'(x_1 \mathbin\Vert x_2) = G(x_1) \mathbin\Vert G(x_2)$ | ✔ | Aus dem Angreifer $A'$ gegen $G'$ bastelt man einen Angreifer $A$ gegen $G$. Wenn $A$ seine Aufgabe $C$ bekommt, wählt er ein zufälliges $x$, und sendet $C$||G(x)$ an $A'$, und übernimmt die Ausgabe | Proof by Reduction |
| $G'(s) = f(G(s))$ | ✔ | Aus $D'$ gegen $G'$ baut man $D$ gegen $G$. Bekommt $D$ die Aufgabe $C$, berechnet er $f(C)$ und sendet es an $D'$ | Proof by Reduction |

| 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. |

| Definition | YES/NO | Why? |
|------------|--------|------|
| $f': \{0, 1\}^n \rightarrow \{0, 1\}^n, f'(x) := f(x) \oplus g(x)$ | NO | If we consider $f = g$, then we have $\forall x, f'(x) = 0$. |
| $f': \{0, 1\}^n \rightarrow \{0, 1\}^n, f'(x) := f(f(x))$ | NO | Let $x = x_1 \| x_2, g: \{0, 1\}^{n/2} \rightarrow \{0, 1\}^{n/2}$ be a OWF, define $f(x) = g(x_2) \| 0^{n/2}$, then $f(f(x)) = g(0^{n/2}) \| 0^n$ is a constant function. |
| $f': \{0, 1\}^{2n} \rightarrow \{0, 1\}^{2n}, f'(x_1, x_2) := f(x_1) \| f(x_2)$ | YES | Otherwise can break the assumption that $f$ is a OWF. |

## Proof by Reduction Idee
$G'$ kein $PRG$ $\Rightarrow$ es gibt $D'$ $\Rightarrow$ es gibt $D$ $\Rightarrow$ $G$ ist KEIN $PRG$

## Ablauf wenn es PRG ist


$F2:\{0,1\}^n \{0,1\}^{m+n},\ F2(s) :=G(s)||f(s)$

1) $\exists ppt$ Algorithmus und positive Polynom $p$
2) Annahme: $G$ ist keine PRG $|Pr[D(G'(s) = 1] - Pr[D(G'(r) = 1]| \gt \frac{1}{p(n)}$
3) Baue einen Challenger

## Ablauf wenn es **KEIN** PRG ist

# PRP


## Stark PRP


Blockchiffre werden durch PRP erstellt

## Blockchiffre

vorteil:
* einfacher zu implementieren
* schutz vor backdoor
* Symmetrie

Feistel-chiffre - DES

Substitutions-permutations netzwerk - AES

# PRF


Immer wenn es ein Random Wert gibt, ist es CPA sicher.

$F2:\{0,1\}^n \{0,1\}^{m+n},\ F2(s) :=f_1(s)||f_2(s)$
$f_1,f_2$ sind PRF's
1) $\exists ppt$ Algorithmus und positive Polynom $p$
2) Annahme: $PRF$ ist keine $|PR[PRF_{A,\pi}=1] - |PR[PRF_{A',\pi}=1/2]| \gt negl.$

# Hash


# IND-CPA game
CPA Stateless ist immer unsicher.

Definition

# IND-CCA game


## Gruppen

## Diffie-Hellman-Schlüsselaustausch

Ablauf:

1. A generiert $(G,q,g)$, wobei $q$ prim ist.
2. A wählt zufälliges $x \in Z_q$ und berechnet $h_A=g^x$
3. A sendet $(G,q,g,h_A)$ an B
4. B wählt zufälliges $y \in Z_q$ und berechnet $h_B=g^y$
5. B sendet $h_B$ an A
6. Schlüsselberechnung: $k_A=h_B^x$, $k_B=h_A^y$

Korrektheit: $k_A=h_B^x=(g^y)^x=g^{xy}=(g^x)^y=h_A^y=k_B$

## Signature

## DES

## Feistel Netzwerk

## MAC

Die Definition von MAC ist =

$\pi = k \leftarrow Gen(1^n)$
$t \leftarrow Mac(k,m)$
$b \leftarrow Vrfy(k,m,t)$

$∀n, k \leftarrow Gen(1^n),\ ∀m\ \in\ {0, 1}^n,\ it\ holds\ that$
$Vrfyk(m,\ Mack(m))\ =\ 1$


## MAC - forge

Definition:
$∀ ppt A: ∃\ negl() s.d.: [𝑃𝑟 Mac − forge_{𝐴,Π} (𝑛) = 1] ≤ negl(𝑛)$

$m0 \neq m1$

digraph hierarchy {
  nodesep=0.4 // Increases the separation between nodes
  node [color=Darkgreen,fontname=Courier,shape=box] // All nodes will this shape and colour
  edge [color=Black, style=dashed] // All the lines look like this
  t->{m0  m1}
}

## Korrektheit der MAC

Es exitstieren unterschiedliche Arten von MACs:
1. Informationstheoretisch sichere MACs.
Diese Konstruktionen sind allerdings nicht effizient für
Authenfizierung von vielen Nachrichten
2. Komplexitätstheoretisch sichere MACs:
a. Für Nachrichten fixer Länge.
b. Für Nachrichten mit beliebiger Länge (theoretische
Konstruktion)
c. Für Nachrichten mit beliebiger Länge (praktische
Konstruktionen): z.B. CBC-MAC und HMAC

## Hash-and-Mac



1) $\exists ppt$ Algorithmus und positive Polynom $p$
2)

## SMAC - forge


Defintion:
$∀ ppt A: ∃\ negl() s.d.: 𝑃𝑟[ SMac − forge_{𝐴,Π} (𝑛) = 1] ≤ negl(𝑛)$

$t0 \neq t1$

digraph hierarchy {
  nodesep=0.4 // Increases the separation between nodes

  node [color=Darkgreen,fontname=Courier,shape=box] // All nodes will this shape and colour
  edge [color=Black, style=dashed] // All the lines look like this

  m->{t0  t1}
}

# Public-Private Cryptography

## Elgamal


Falls die DDH Annahme gilt, ist das El Gamal Verschlüsselungsverfahren 𝚷 CPA
sicher.

$Definition:$
___
$Gen(1^n)$

zyklische Gruppe G

wähle eine Primzahl q und einen Generator g (Aus einer zyklischen Gruppe G)
$x \leftarrow G$ and $h = g^x$
$pk = (G,q,g,h)$
$sk = (G,q,g,x)$

____
$Enc_{pk}(m)$

$m \in G$ $y\leftarrow Z_q$
$c = (g^y,h^ym)$

___
$Dec_{sk}(c)$

$c = (c_1,c_2) \in G\ x\ G$
$m = c_1^{-x}c_2$

___
Schritte:

$Enc((G,g,q,h),m) = (g^y,h^ym)$

$Dec((G,g,p,x),(c_1,c_2)) = c_1^{-x}c_2$

$= (g^y)^{-x}h^y\ m$
$=m\ (g^x)^y\ (g^y)^{-x}$
$=m\ g^{xy}\ g^{-yx}$
$m$

___
Annahme:
$∀ 𝑷𝑷𝑻 𝑨 ∃ negl(), s.d.:$
$|𝑷𝒓[𝑨((𝑮, 𝒒,𝒈),𝒈^𝒙,𝒈^𝒚,𝒈^{𝒙𝒚}) = 𝟏] − 𝑷𝒓[𝑨((𝑮, 𝒒, 𝒈),𝒈^𝒙,𝒈^𝒚,𝒈^𝒛) = 𝟏]|≤ 𝐧𝐞𝐠𝐥(𝒏)$


## Probleme bei Textbook RSA

1. Das Verfahren ist deterministisch
2. Enc und Dec sind deterministische Algorithmen in Textbook RSA -> Textbook RSA ist nicht CPA-Sicher
3. Kein deterministisches PKE ist CPA-sicher.
4. Wie kann ein Angreifer das CPA-Spiel gewinnen?
5. Er wählt zwei Nachrichten $m_0,m_1$
6. Er berechnet $c_0 = Enc_{pk}(m_0)$ mit Hilfe des öffentlichen Schlüssels
7. Er vergleicht den Challenge Chiffretext $c\ mit\ c_0$
3. Das Verfahren ist homomorph (Schutz: Padding)
4. $Enc_{N,e}(m_0\ ⋅\ m_1)$
$=(m_0\ ⋅\ m_1)^e$
$= Enc_{N,e}(m_0)\ Enc_{N,e}(m_1)$
Problem: Für Chiffretexte $𝒄_i\ = 𝒎^e_i\ mod\ N$ kann ein Angreifer prüfen, ob $𝒄_2 = 𝒄_0 ⋅ 𝒄_1.$ Falls dies gilt, folgt auch $𝒎_2 = 𝒎_0 ⋅ 𝒎_1$

5. Das Jacobi Symbol verrät Informationen über Klartexte
Jakobis Methode ermöglicht es manchmal zu erraten, ob der geheime Schlüssel zum Entschlüsseln eine gerade oder ungerade Zahl ist. Das macht die RSA-Verschlüsselung etwas unsicherer, da der Schlüssel eigentlich komplett geheim bleiben sollte.

## RSA Berechnen


Generator g, zufällige große Primzahl p.

Public key = {e, p}
Secret key = {d, p}

Nachricht verschlüsseln
$c\ =\ m^e\ mod\ p$

Nachricht entschlüsseln
$m\ =\ c^d\ mod\ p$

Definition:

$RSA - LSB_A(n)$

Wahrscheinlichkeit:
$Pr[RSA - LSB_A(n) = 1] \le \frac{1}{2} + negl(n)$


## Fälschung von RSA signierten Nachrichten


Beweis für rsa textbook signaturen
Zeigt, dass man mit Homomorphismen und 2 nachrichten eine gültige Signatur forgen kann

### Beliebiger Länge


## Fiat-Shamir-Transformation
- Identifikationsschema $\rightarrow$ Signaturschema

Signatur: "Simuliere" Ablauf eines ID-Schemas
1. Prover berechnet $(I, st)=P_1(sk)$, sendet $I$ an Verifier
2. V wählt $r=H(I, m)$, sendet $r$ an Prover
3. Prover berechnet $s=P_2(sk, st, r)$
4. Signatur: $\sigma =(r,s)$

Verifikation:
Valide, wenn $r=H(V(pk, r, s), m)$

Sicher, wenn ID-Schema sicher und Hash-Funktion als Random Oracle modelliert.

## Schnorr Algorithmus
- basiert auf Fiat-Shamir-Transformation und Gruppen
- Generierung: Wähle $(G,q,g)$ mit $q$ prim, wähle $x\leftarrow_R Z_q$, berechne $y=g^x$
- $sk=(G,q,g,x)$, $pk=(G,q,g,y)$
- Signatur wie bei Fiat-Shamir
- $P_1(sk)=g^k$, mit $k\leftarrow_R Z_q$
- $P_2(sk)=rx+k \mod q$
- Verifikation wie bei Fiat-Shamir
- $V(pk,r,s)=\frac{g^s}{y^r}$

# Hashfunktionen



Beweis wieder Reduktionsbeweis für Hashfunktione