Kryptographie I - Zusammenfassung

Caesar et al.

Caesar

MASC

Verschlüsseln

z.B. mit Schlüsselwort ERLANGEN

$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

DEPA THEM
RTME ATIK
NTMA WXYZ

Entschlüsseln

Schlüsseltext spaltenweise in $m \times n$ Matrix schreiben und zeilenweise auslesen.

TRANSSPA

Verschlüsseln

Mit Schlüssel ERLANGEN und Text AMFREITAGENTFAELLTDIEVORLESUNG

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{aligned} f ((\begin{array}{c} x \\ y \end{array})) & = (\begin{array}{c} k_{1} & k_{2} \\ k_{4} & k_{5} \end{array}) (\begin{array}{c} x \\ y \end{array}) (\begin{array}{c} k_{3} \\ k_{6} \end{array}) \end{aligned}

STROM

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

Text

Schlüssel

PLAYFAIR

Wir ersetzen I mit J.

Verschlüsseln

mit Schlüsselwort KRYPTOGRAPHIE in 5×5-Matrix

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 → WA, SX, SE, RX

VIGENÈRE

Text

\dots

Schlüssel

\dots

ADFGVX

Kasiski-Test

Zahlentheorie

Primfaktorzerlegung

\begin{aligned} ggT (\pm Π p_{i}^{a_{i}}, \pm Π p_{i}^{b_{i}}) & = Π p_{i}^{min (a_{i}, b_{i})} \\ ggT (\pm Π p_{i}^{a_{i}}, 0) & = Π p_{i}^{a_{i}} \\ ggT (0, 0) & = 0 \end{aligned}

\begin{aligned} kgV (\pm Π p_{i}^{a_{i}}, \pm Π p_{i}^{b_{i}}) & = Π p_{i}^{max (a_{i}, b_{i})} \\ kgV (\pm Π p_{i}^{a_{i}}, 0) & = 0 \\ kgV (0, 0) & = 0 \end{aligned}

Euklidischer Algorithmus

Satz von Bézout: $ggT (a, b) = x \cdot a + y \cdot b$

z.B für $ggT (10, 7)$ :

\begin{aligned} 10 & = 1 \cdot 7 + 3 \\ 7 & = 2 \cdot 3 + 1 \\ 3 & = 3 \cdot 1 + 0 \end{aligned}

$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 $Z / 10 Z$

Die Gleichung $a \cdot x + b \cdot y = c$

genau dann lösbar, wenn $ggT (a, b) ∣ c$

Invertierbarkeit

Sei $n \in N$ und $a \in Z$

$a$ hat genau dann ein Inverses in $Z / n Z$ , wenn $ggT (n, a) = 1$

Eulersche φ-Funktion

$ggT (m, n) = 1 ⟹ φ (m \cdot n) = φ (m) \cdot φ (n)$

Die Gleichung $a \cdot x \equiv b mod m$

Seien $a, b \in Z$ und $m \in N$ , $a \cdot u + m \cdot v = ggT (a, m)$

$a \cdot x \equiv b mod m$ ist genau dann lösbar, wenn $ggT (a, m) ∣ b$
Gilt $ggT (a, m) ∣ b$ , dann gilt
$x_{0} = \frac{b}{ggT (a, m)} \cdot u a \cdot x_{0} \equiv b mod m$
Gilt $a \cdot x_{0} \equiv b mod m$ , dann folgt
${x \in Z ∣ a \cdot x \equiv b mod m} = {x_{0} + i \cdot \frac{m}{ggT (a, m)} ∣ i \in Z}$
Gilt $ggT (a, m) ∣ b$ , dann gibt es genau $ggT (a, m) mod m$ verschiedene Lösungen

Chinesischer Restesatz

\begin{aligned} x & \equiv a_{1} mod m_{1} \\ x & \equiv a_{2} mod m_{2} \\ x & \equiv a_{3} mod m_{3} \end{aligned}

\begin{aligned} 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{aligned}

Die Lösung ist dann eindeutig in $Z / t Z$

\begin{aligned} d_{1} & \equiv t_{1}^{- 1} mod m_{1} \\ d_{2} & \equiv t_{2}^{- 1} mod m_{2} \\ d_{3} & \equiv t_{3}^{- 1} mod m_{3} \end{aligned}

$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} mod t$

Fibonacci

n	0	1	2	3	4	…
$f_{n}$	0	1	1	2	3

Primzahltests

Fermat

kleiner Satz von Fermat

für

p

prim und

a \in Z

a^{p} \equiv a mod p

ggT (a, p) = 1 ⟹ a^{p - 1} \equiv 1 mod p

Satz von Euler

für $n \in N, a \in Z$ und $ggT (a, n) = 1$ , dann gilt
$a^{φ (n)} \equiv 1 mod n$

Insbesondere
$a^{x} \equiv a^{x mod φ (n)} (\mod n)$

Fermat-Pseudoprimzahl zur Basis $a$

$n$ zusammengesetzt, aber $ggT (a, n) = 1$ und $a^{n - 1} \equiv 1 mod n$

Miller-Rabin

Miller-Rabin-Primzahltest zur Basis $a$: Sei $n \in N$ ungerade und $n > a$ .
Wir zerlegen $n - 1 = 2^{ℓ} q$ , $q \equiv 1 mod 2$ und $b = a^{q} mod n$ .
Wenn
$b = 1 oder b^{2^{i}} \equiv n - 1 mod n, 0 \leq i \leq ℓ - 1$
besteht $n$ den Miller-Rabin-Test zur Basis $a$
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 N$ , $n$ zusammengesetzt. $n$ ist eine Carmichael-Zahl, wenn für alle $b \in Z$ , $b, n$ koprim:
$b^{n - 1} \equiv 1 mod n$

Korselt-Kriterium
$n \in N$ , $n$ zusammengesetzt, ist genau dann eine Carmichael-Zahl, wenn für alle Primteiler $p$ von $n$ gilt $p - 1 ∣ n - 1$ und $n$ ist quadratfrei, d.h. für alle Primteiler $p$ gilt $p^{2} ∤ n$ .

Ordnung

${ord}_{n} (a) = min {k \in B ∣ a^{k} \equiv 1 mod n}$

Sei $n \in N, a \in Z, ggT (a, n) = 1$

$a^{k} \equiv 1 mod n \Leftrightarrow {ord}_{n} (a) ∣ k$
${k \in B ∣ a^{k} \equiv 1 mod n} = {ℓ \cdot {ord}_{n} (a) ∣ ℓ \in N}$
${ord}_{n} (a) ∣ φ (n)$
$a^{k} \equiv a^{l} mod n \Leftrightarrow k \equiv l mod {ord}_{n} (a)$

Primitive Wurzel

Ist ${ord}_{p} (g) = p - 1$ , dann ist $g$ Primitivwurzel modulo $p$

Ist $g$ Primitivwurzel modulo $p$ ?

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}}} ≢ 1 mod p$
für alle $i$

Diskrete Logarithmen

$g^{x} \equiv a mod n$

Ist bestimmt in ${ord}_{n} (g)$
Ist genau dann lösbar wenn ${ord}_{n} (a) ∣ {ord}_{n} (g)$

RSA

Methode

Schlüsselerzeugung

Wähle Primzahlen $p, q$ und berechne $N = p \cdot q$ .
Dann ist $φ (N) = (p - 1) \cdot (q - 1)$
Wähle $e > 1$ mit $ggT (e, φ (N)) = 1$
Berechne $d = e^{- 1} mod φ (N)$

Öffentlicher Schlüssel	$(N, e)$
Privater Schlüssel	$(N, d)$

Verschlüsseln von $m$

$c = m^{e} mod N$

Entschlüsseln von $m$

$m = c^{d} mod N$

Signieren von $m$

Alice signiert mit ihrem privaten Schlüssel $(N, d)$

\begin{aligned} h & = hash (m) \\ s & = h^{d} mod N \end{aligned}

Bob verifiziert mit Alices öffentlichen Schlüssel $(N, e)$

\begin{aligned} h & = hash (m) \\ h^{'} & = s^{e} mod N \end{aligned}

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$

$⌈ \sqrt{2263} ⌉ = 48$

$u$ $u^{2} - N$ $\sqrt{u^{2} - N}$

48 41 6.4

49 138 11.75

$⋮$ $⋮$ $⋮$

52 441 21

$2263 = 52^{2} - 21^{2} = (52 - 21) \cdot (52 + 21) = 31 \cdot 73$

$u$	$u^{2} - N$	$\sqrt{u^{2} - N}$
48	41	6.4
49	138	11.75
$⋮$	$⋮$	$⋮$
52	441	21

Bei Kenntnis des öffentlichen und privaten Schlüssels

Gegeben sei öffentlicher Schlüssel $(N, e)$ und privater Schlüssel $(N, d)$ .

$k := ⌊ \frac{e \cdot d}{N} ⌋$
$k := k + 1$ solange bis $k ∣ e \cdot d - 1$
$s = N + 1 - \frac{e \cdot d - 1}{k}$ und $Δ = ⌊ \sqrt{s^{2} - 4 \cdot N} ⌋$
Wenn $s^{2} - 4 \cdot N \neq Δ^{2}$ , gehe zu 2, sonst $N = \frac{s - Δ}{2} \cdot \frac{s + Δ}{2}$

Bei Kenntnis eines Exponenten für $Z / N Z$

Mit Kettenbrüchen

Kettenbruchentwicklung

z.B für $α = \frac{449}{211}$

\begin{aligned} 449 & = 2 \cdot 211 + 27 \\ 211 & = 7 \cdot 27 + 22 \\ 27 & = 1 \cdot 22 + 25 \\ 22 & = 4 \cdot 5 + 2 \\ 5 & = 2 \cdot 2 + 1 \\ 2 & = 2 \cdot 1 + 0 \end{aligned}

Somit hat $α$ die Kettenbruchentwicklung $[2, 7, 1, 4, 2, 2]$

Näherungsbrüche

Sei $[a_{0}, a_{1}, a_{2}, \dots]$ die Kettenbruchentwicklung von $a \in R$ so ist $[a_{0}, a_{1}, \dots, a_{n}]$ der n-te Näherungsbruch von $a$ .

\begin{aligned} [2] & = 2 \\ [2, 3] & = 2 + \frac{1}{3} \\ [2, 3, 5] & = 2 + \frac{1}{3 + \frac{1}{5}} \end{aligned}

Im Fall $d ⪅ 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}} mod p$
Bob wählt geheim $e_{B}$ und sendet $f_{B} = g^{e_{B}} mod p$
$k_{A} B \equiv g^{e_{A} \cdot e_{B}} \equiv f_{A}^{e_{B}} \equiv f_{B}^{e_{A}} mod p$

ElGamal

Schlüsselerzeugung

Wähle Primzahl $p$ und Primitivwurzel $g$ modulo $p$ , $3 \leq g \leq p - 1$ und $g ∤ p - 1$ .
Wähle $e, 0 \leq e \leq p - 2$ und berechne
$f = g^{e} mod p$

Öffentlicher Schlüssel	$(p, g, f)$
Privater Schlüssel	$e$

Verschlüsseln von $m$

Wähle $z, 0 \leq z \leq p - 2$ zufällig.
$\begin{aligned} c_{1} & = g^{z} mod p \\ c_{2} & = m \cdot f^{z} mod p \end{aligned}$
Cyphertext ist $(c_{1}, c_{2})$

Entschlüsseln von $(c_{1}, c_{2})$

$\begin{aligned} m & = c_{1}^{p - 1 - e} \cdot c_{2} mod p \\ m & = \frac{c_{2}}{c_{1}^{e}} \equiv c_{2} \cdot (c_{1}^{e})^{- 1} & (alternativ) \end{aligned}$

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 $ggT (z, p - 1) = 1$

\begin{aligned} h & = hash (m) \\ b & = g^{z} mod p \\ c & = z^{- 1} \cdot (h - b \cdot e) mod (p - 1) \end{aligned}

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{aligned} h & = hash (m) \\ t & = f^{b} \cdot b^{c} mod p \\ t^{'} & = g^{h} mod p \end{aligned}

Die Signatur ist gültig, wenn $0 \leq b \leq p - 1$ und $t = t^{'}$

Caesar et al.

Caesar

MASC

Verschlüsseln

Entschlüsseln

TRANSMAT

Verschlüsseln

Entschlüsseln

TRANSSPA

Verschlüsseln

Entschlüsseln

ALBC-2

STROM

AUTOKEY

PLAYFAIR

Verschlüsseln

VIGENÈRE

ADFGVX

Kasiski-Test

Zahlentheorie

Primfaktorzerlegung

Euklidischer Algorithmus

Die Gleichung a⋅x+b⋅y=c

Invertierbarkeit

Eulersche φ-Funktion

Die Gleichung a⋅x≡bmodm

Chinesischer Restesatz

Fibonacci

Primzahltests

Fermat

Miller-Rabin

Ordnung

Primitive Wurzel

Ist g Primitivwurzel modulo p?

Diskrete Logarithmen

RSA

Methode

Schlüsselerzeugung

Verschlüsseln von m

Entschlüsseln von m

Signieren von m

Faktorisierungsmethoden und Angriffe

Fermat

Bei Kenntnis des öffentlichen und privaten Schlüssels

Bei Kenntnis eines Exponenten für Z/NZ

Mit Kettenbrüchen

Weitere Methoden

Diffie-Hellman

ElGamal

Schlüsselerzeugung

Verschlüsseln von m

Entschlüsseln von (c1,c2)

Signieren von m

Pollardsche ρ-Methode

Die Gleichung $a \cdot x + b \cdot y = c$

Die Gleichung $a \cdot x \equiv b mod m$

Ist $g$ Primitivwurzel modulo $p$ ?

Verschlüsseln von $m$

Entschlüsseln von $m$

Signieren von $m$

Bei Kenntnis eines Exponenten für $Z / N Z$

Verschlüsseln von $m$

Entschlüsseln von $(c_{1}, c_{2})$

Signieren von $m$