#+title: Kryptographie I - Zusammenfassung
#+author: Florian Guthmann
#+email: florian.guthmann@fau.de
#+options: num:nil \n:t html-style:nil html5-fancy:t
#+html_doctype: xhtml5
#+html_head:
#+html_head:
#+html_mathjax: path:/~oc45ujef/mathjax/es5/tex-mml-chtml.js
* Caesar et al.
** Caesar
** MASC
*** Verschlüsseln
z.B. mit Schlüsselwort =ERLANGEN=
#+attr_html: :border 2 :rules all :frame border
| $x$ | A | B | C | D | E | F | G | H | $\dots$ |
|--------+---+---+---+---+---+---+-----+---+---------|
| $f(x)$ | E | R | L | A | N | G | *H* | I | $\dots$ |
*** Entschlüsseln
Mit Tabelle.
** TRANSMAT
*** Verschlüsseln
Schlüssel aus zwei natürlichen Zahlen $n,m$
Zeilenweise in $m\times n$ Matrix schreiben
z.B. $(m,n) = (3,4)$, Text =DEPARTMENT MATHEMATIK=
#+begin_example
DEPA THEM
RTME ATIK
NTMA WXYZ
#+end_example
*** Entschlüsseln
Schlüsseltext spaltenweise in $m\times n$ Matrix schreiben und zeilenweise auslesen.
** TRANSSPA
*** Verschlüsseln
Mit Schlüssel =ERLANGEN= und Text =AMFREITAGENTFAELLTDIEVORLESUNG=
#+attr_html: :border 2 :rules all :frame border
| E | R | L | A | N | G | E | N |
| 2 | 8 | 5 | 1 | 6 | 4 | 3 | 7 |
|---+---+---+---+---+---+---+---|
| A | M | F | R | E | I | T | A |
| G | E | N | T | F | A | E | L |
| L | T | D | I | E | V | O | R |
| L | E | S | U | N | G | | |
Wobei in der zweiten Zeile jeweils der Index des Zeichens im Schlüsselwort unter stabiler Sortierung ist.
Den Chiffretext durch spaltenweises Auslesen mit Reihenfolge aus Zeile 2.
=RTIUAGLLTEOIAVGFNDSEFENALRMETE=
*** Entschlüsseln
** ALBC-2
\begin{align*}
f\left(\begin{pmatrix}
x\\
y
\end{pmatrix}\right) &=
\begin{pmatrix}
k_1 & k_2\\
k_4 & k_5
\end{pmatrix}
\begin{pmatrix}
x\\
y
\end{pmatrix}
\begin{pmatrix}
k_3\\
k_6
\end{pmatrix}\\
\end{align*}
** STROM
#+attr_html: :border 2 :rules all :frame border
| Text | $m_1$ | $m_2$ | $\dots$ |
| Schlüssel | $k_1$ | $k_2$ | $\dots$ |
| Chiffretext | $f(m_1,k_1)$ | $f(m_2,k_2)$ | $\dots$ |
** AUTOKEY
#+attr_html: :border 2 :rules all :frame border
| Text | W | I | N | T | E | R | S | E | M | E | S | T | E | R |
| Schlüssel | F | R | E | I | T | A | G | W | I | N | T | E | R | S |
** PLAYFAIR
Wir ersetzen =I= mit =J=.
*** Verschlüsseln
mit Schlüsselwort =KRYPTOGRAPHIE= in 5\times5-Matrix
#+attr_html: :border 2 :rules all :frame border
| K | R | Y | P | T |
| O | G | A | H | I |
| E | *B* | C | D | F |
| L | M | N | Q | S |
| U | V | W | X | Z |
Teile Text in Blöcke der Länge 2, evtl mit eingesetztem =X=
=WASSER= \to =WA=, =SX=, =SE=, =RX=
** VIGENÈRE
#+attr_html: :border 2 :rules all :frame border
| Text | A | U | C | H | I | M | O | K | T | O | B | E | R | $\dots$ |
| Schlüssel | F | R | E | I | T | A | G | F | R | E | I | T | A | $\dots$ |
** ADFGVX
** Kasiski-Test
* Zahlentheorie
** Primfaktorzerlegung
\begin{align*}
\mathrm{ggT}(\pm \Pi p_i^{a_i}, \pm \Pi p_i^{b_i}) &= \Pi p_i^{\min(a_i,b_i)}\\
\mathrm{ggT}(\pm \Pi p_i^{a_i}, 0) &= \Pi p_i^{a_i}\\
\mathrm{ggT}(0, 0) &= 0\\
\end{align*}
\begin{align*}
\mathrm{kgV}(\pm \Pi p_i^{a_i}, \pm \Pi p_i^{b_i}) &= \Pi p_i^{\max(a_i,b_i)}\\
\mathrm{kgV}(\pm \Pi p_i^{a_i}, 0) &= 0\\
\mathrm{kgV}(0, 0) &= 0\\
\end{align*}
** Euklidischer Algorithmus
- Satz von Bézout ::
\[
\mathrm{ggT}(a,b) = x\cdot a + y\cdot b
\]
z.B für $\mathrm{ggT}(10,7)$:
\begin{align*}
10 &= 1 \cdot 7 + 3\\
7 &= 2 \cdot 3 + 1\\
3 &= 3 \cdot 1 + 0\\
\end{align*}
$1 = 7 - 2 \cdot 3 = 7 - 2 \cdot (10 - 1 \cdot 7) = -2 \cdot 10 + 3 \cdot 7$
Also ist 3 multiplikativ invers 7 in $\mathbb{Z}/10\mathbb{Z}$
*** Die Gleichung $a\cdot x + b\cdot y = c$
- genau dann lösbar, wenn $\mathrm{ggT}(a,b) \mid c$
*** Invertierbarkeit
Sei $n \in \mathbb{N}$ und $a \in \mathbb{Z}$
- $a$ hat genau dann ein Inverses in $\mathbb{Z}/n\mathbb{Z}$, wenn $\mathrm{ggT}(n,a) = 1$
*** Eulersche \phi-Funktion
- $\mathrm{ggT}(m,n) = 1 \implies \varphi(m\cdot n) = \varphi(m) \cdot \varphi(n)$
*** Die Gleichung $a\cdot x \equiv b \bmod m$
Seien $a,b \in \mathbb{Z}$ und $m \in \mathbb{N}$, $a\cdot u + m \cdot v = \mathrm{ggT}(a,m)$
- $a\cdot x \equiv b \bmod m$ ist genau dann lösbar, wenn $\mathrm{ggT}(a,m) \mid b$
- Gilt $\mathrm{ggT}(a,m) \mid b$, dann gilt
\[
x_0 = \frac{b}{\mathrm{ggT}(a,m)}\cdot u\\
a\cdot x_0 \equiv b \bmod m
\]
- Gilt $a\cdot x_0 \equiv b \bmod m$, dann folgt
\[
\{x \in \mathbb{Z} \mid a\cdot x \equiv b \bmod m\} = \{x_0 + i \cdot \frac{m}{\mathrm{ggT}(a,m)} \mid i \in \mathbb{Z} \}
\]
- Gilt $\mathrm{ggT}(a,m) \mid b$, dann gibt es genau $\mathrm{ggT}(a,m) \bmod m$ verschiedene Lösungen
** Chinesischer Restesatz
\begin{align*}
x &\equiv a_1 \bmod m_1\\
x &\equiv a_2 \bmod m_2\\
x &\equiv a_3 \bmod m_3
\end{align*}
\begin{align*}
t &= m_1 \cdot m_2 \cdot m_3\\
t_1 &= \frac{t}{m_1} = m_2 \cdot m_3\\
t_2 &= \frac{t}{m_2}\\
t_3 &= \frac{t}{m_3}\\
\end{align*}
Die Lösung ist dann eindeutig in $\mathbb{Z}/t\mathbb{Z}$
\begin{align*}
d_1 &\equiv t_1^{-1} \bmod m_1\\
d_2 &\equiv t_2^{-1} \bmod m_2\\
d_3 &\equiv t_3^{-1} \bmod m_3\\
\end{align*}
\[
x \equiv d_1 \cdot t_1 \cdot a_1 + d_2 \cdot t_2 \cdot a_2 + d_3 \cdot t_3 \cdot a_3 \bmod t
\]
** Fibonacci
#+attr_html: :border 2 :rules all :frame border
| n | 0 | 1 | 2 | 3 | 4 | \dots |
| $f_n$ | *0* | 1 | 1 | 2 | 3 | |
** Primzahltests
*** Fermat
- kleiner Satz von Fermat :: für $p$ prim und $a \in \mathbb{Z}$
\[
a^p \equiv a \bmod p\\
\]
\[
\mathrm{ggT}(a,p) = 1 \implies a^{p-1} \equiv 1 \bmod p
\]
- Satz von Euler :: für $n \in \mathbb{N}, a \in \mathbb{Z}$ und $\mathrm{ggT}(a,n) = 1$, dann gilt
\[
a^{\varphi(n)} \equiv 1 \bmod n
\]
#+begin_verse
Insbesondere
\[
a^x \equiv a^{x \bmod \varphi(n)} \pmod{n}
\]
#+end_verse
- *Fermat-Pseudoprimzahl* zur Basis $a$ ::
#+begin_verse
$n$ zusammengesetzt, aber $\mathrm{ggT}(a,n) = 1$ und $a^{n-1} \equiv 1 \bmod n$
#+end_verse
*** Miller-Rabin
- *Miller-Rabin-Primzahltest* zur Basis $a$ ::
#+begin_verse
Sei $n \in \mathbb{N}$ ungerade und $n > a$.
Wir zerlegen $n - 1 = 2^{\ell}q$, $q \equiv 1 \bmod 2$ und $b = a^q \bmod n$.
Wenn
\[
b = 1 \text{ oder } b^{2^i} \equiv n - 1 \bmod n, 0 \leq i \leq \ell - 1
\]
besteht $n$ den Miller-Rabin-Test zur Basis $a$
#+end_verse
- Miller-Rabin-Pseudoprimzahl zur Basis $a$ :: $n$ zusammengesetzt, aber besteht Miller-Rabin-Test zur Basis $a$
**** Carmichael-Zahlen
"Fermat-Pseudoprimzahl für alle $a$ "
Sei $n \in \mathbb{N}$, $n$ zusammengesetzt. $n$ ist eine Carmichael-Zahl, wenn für alle $b \in \mathbb{Z}$, $b,n$ koprim:
\[
b^{n-1} \equiv 1 \bmod n
\]
- Korselt-Kriterium :: $n \in \mathbb{N}$, $n$ zusammengesetzt, ist genau dann eine Carmichael-Zahl, wenn für alle Primteiler $p$ von $n$ gilt $p - 1 \mid n - 1$ und $n$ ist quadratfrei, d.h. für alle Primteiler $p$ gilt $p^2 \nmid n$.
** Ordnung
\[
\mathrm{ord}_n(a) = \min \{k \in \mathbb{B} \mid a^k \equiv 1 \bmod n\}
\]
Sei $n \in \mathbb{N}, a \in \mathbb{Z}, \mathrm{ggT}(a,n) = 1$
- $a^k \equiv 1 \bmod n \Leftrightarrow \mathrm{ord}_n(a) \mid k$
- $\{k \in \mathbb{B} \mid a^k \equiv 1 \bmod n\} = \{\ell \cdot \mathrm{ord}_n(a) \mid \ell \in \mathbb{N}\}$
- $\mathrm{ord}_n(a) \mid \varphi(n)$
- $a^k \equiv a^l \bmod n \Leftrightarrow k \equiv l \bmod \mathrm{ord}_n(a)$
** Primitive Wurzel
Ist $\mathrm{ord}_p(g) = p - 1$, dann ist $g$ Primitivwurzel modulo $p$
*** Ist $g$ Primitivwurzel modulo $p$?
#+begin_verse
Sei $p-1 = q_1^{e_1} \cdot q_2^{e_2} \cdot \dots \cdot q_n^{e_n}$.
$g$ ist *Primitivwurzel* modulo $p$ genau dann wenn
\[
g^{\frac{p - 1}{q_i}} \not\equiv 1 \bmod p
\]
für alle $i$
#+end_verse
** Diskrete Logarithmen
\[
g^x \equiv a \bmod n
\]
- Ist bestimmt in $\mathrm{ord}_n(g)$
- Ist genau dann lösbar wenn $\mathrm{ord}_n(a) \mid \mathrm{ord}_n(g)$
* RSA
** Methode
*** Schlüsselerzeugung
Wähle Primzahlen $p,q$ und berechne $N = p \cdot q$.
Dann ist $\varphi(N) = (p - 1) \cdot (q - 1)$
Wähle $e > 1$ mit $\mathrm{ggT}(e, \varphi(N)) = 1$
Berechne $d = e^{-1} \bmod \varphi(N)$
| Öffentlicher Schlüssel | $(N,e)$ |
| Privater Schlüssel | $(N,d)$ |
*** *Verschlüsseln* von $m$
#+begin_verse
\[
c = m^e \bmod N
\]
#+end_verse
*** *Entschlüsseln* von $m$
#+begin_verse
\[
m = c^d \bmod N
\]
#+end_verse
*** Signieren von $m$
Alice signiert mit ihrem privaten Schlüssel $(N,d)$
\begin{align*}
h &= \mathrm{hash}(m)\\
s &= h^d \bmod N
\end{align*}
Bob verifiziert mit Alices öffentlichen Schlüssel $(N,e)$
\begin{align*}
h &= \mathrm{hash}(m)\\
h' &= s^e \bmod N
\end{align*}
Die Signatur ist gültig, wenn $h = h'$
** Faktorisierungsmethoden und Angriffe
*** Fermat
Sei $N$ eine ungerade natürliche Zahl. Wir suchen
\[
N = u^2 - w^2
\]
da dann
\[
N = (u -w)\cdot (u + w)
\]
**** Beispiel $N= 2263$
$\lceil\sqrt{2263}\rceil = 48$
#+attr_html: :border 2 :rules all :frame border
| $u$ | $u^2 - N$ | $\sqrt{u^2 - N}$ |
|----------+----------+-----------------|
| 48 | 41 | 6.4 |
| 49 | 138 | 11.75 |
| $\vdots$ | $\vdots$ | $\vdots$ |
| 52 | 441 | 21 |
\[
2263 = 52^2 - 21^2 = (52 - 21) \cdot (52 + 21) = 31 \cdot 73
\]
*** Bei Kenntnis des öffentlichen und privaten Schlüssels
Gegeben sei öffentlicher Schlüssel $(N,e)$ und privater Schlüssel $(N,d)$.
1. \[
k := \left\lfloor \frac{e\cdot d}{N} \right\rfloor
\]
2. $k:= k+1$ solange bis $k \mid e\cdot d - 1$
3. $s = N +1 - \frac{e\cdot d - 1}{k}$ und $\Delta = \left\lfloor \sqrt{s^2 - 4\cdot N} \right \rfloor$
4. Wenn $s^2 - 4\cdot N \neq \Delta^2$, gehe zu 2, sonst $N = \frac{s-\Delta}{2} \cdot \frac{s+\Delta}{2}$
*** Bei Kenntnis eines Exponenten für $\mathbb{Z}/N\mathbb{Z}$
*** Mit Kettenbrüchen
- Kettenbruchentwicklung ::
z.B für $\alpha = \frac{449}{211}$
\begin{align*}
449 &= {\color{pink} 2} \cdot 211 + 27\\
211 &= {\color{pink} 7} \cdot 27 + 22\\
27 &= {\color{pink} 1} \cdot 22 + 25\\
22 &= {\color{pink} 4} \cdot 5 + 2\\
5 &= {\color{pink} 2} \cdot 2 + 1\\
2 &= {\color{pink} 2} \cdot 1 + 0\\
\end{align*}
Somit hat $\alpha$ die Kettenbruchentwicklung $[2,7,1,4,2,2]$
- Näherungsbrüche ::
Sei $[a_0, a_1,a_2,\dots]$ die Kettenbruchentwicklung von $a \in \mathbb{R}$ so ist $[a_0,a_1,\dots,a_n]$ der *n-te Näherungsbruch* von $a$.
\begin{align*}
[2] &= 2\\
[2,3] &= 2 + \frac{1}{3}\\
[2,3,5] &= 2 + \dfrac{1}{3 + \dfrac{1}{5}}
\end{align*}
Im Fall $d \lessapprox N^{\frac{1}{4}}$ kann $N$ mit Kettenbruchentwicklungen faktorisiert werden.
\[
\frac{e}{(p-1)(q-1)} - \frac{k}{d} = \frac{1}{d(p-1)(q-1)}
\]
* Weitere Methoden
** Diffie-Hellman
Alice und Bob einigen sich auf Primzahl $p$ und $g$, $2 \leq g \leq p - 2$.
Alice wählt geheim $e_A$ und sendet $f_A = g^{e_A} \bmod p$
Bob wählt geheim $e_B$ und sendet $f_B = g^{e_B} \bmod p$
\[
k_AB \equiv g^{e_A \cdot e_B} \equiv f_A^{e_B} \equiv f_B^{e_A} \bmod p
\]
** ElGamal
*** Schlüsselerzeugung
Wähle Primzahl $p$ und Primitivwurzel $g$ modulo $p$, $3 \leq g \leq p - 1$ und $g \nmid p - 1$.
Wähle $e, 0 \leq e \leq p - 2$ und berechne
\[
f = g^e \bmod p
\]
| Öffentlicher Schlüssel | $(p,g,f)$ |
| Privater Schlüssel | $e$ |
*** *Verschlüsseln* von $m$
#+begin_verse
Wähle $z, 0 \leq z \leq p - 2$ zufällig.
$$
\begin{align*}
c_1 &= g^z \bmod p\\
c_2 &= m \cdot f^z \bmod p
\end{align*}
$$
Cyphertext ist $(c_1,c_2)$
#+end_verse
*** *Entschlüsseln* von $(c_1,c_2)$
#+begin_verse
$$
\begin{align*}
m &= c_1^{p - 1 - e} \cdot c_2 \bmod p &\\
m &= \frac{c_2}{c_1^e} \equiv c_2 \cdot (c_1^e)^{-1} &\text{(alternativ)}\\
\end{align*}
$$
#+end_verse
*** Signieren von $m$
Alice signiert mit öffentlichen Schlüssel $(p,g,f)$ und privaten Schlüssel $e$
Wähle zufällig $z, 0 \leq z \leq p - 2$ mit $\mathrm{ggT}(z,p-1) = 1$
\begin{align*}
h &= \mathrm{hash}(m)\\
b &= g^z \bmod p\\
c &= z^{-1} \cdot (h - b \cdot e) \bmod (p - 1)
\end{align*}
Wobei $0 \leq b \leq p - 1$ und $0 \leq c \leq p - 2$
Die Signatur ist $(b,c)$
Bob verifiziert Alices Signatur $(b,c)$ mit Alices öffentlichen Schlüssel $(p,g,f)$.
\begin{align*}
h &= \mathrm{hash}(m)\\
t &= f^b \cdot b^c \bmod p\\
t' &= g^h \bmod p
\end{align*}
Die Signatur ist gültig, wenn $0 \leq b \leq p - 1$ und $t = t'$
** Pollardsche \rho-Methode