Kryptografische Verfahren – Einführung und Wiederholung

Was ist Kryptografie?

Ziele der Kryptografie: Informationsschutz/-sicherheit

Vertraulichkeit (Schutz vor Zugriff)
Integrität (Schutz vor Veränderung)
Authentizität (Schutz vor Fälschung)
Verbindlichkeit/Nichtabstreitbarkeit

sehr alte Wissenschaft: bis ca. 3000 v. Chr., enger Zusammenhang zu verschiedenen, eher neueren Wissenschaften wie Zahlentheorie, Algorithmentechnik, Statistik, Informationstheorie, Algebra usw.

auch Zusammenhang zu: Komplexitätstheorie (Geschwindigkeit von Algorithmen), Elektrotechnik (kryptografische Verfahren in Chips „gießen“), Quantenphysik (schnelle Faktorisierung von Zahlen) usw.

Informationstheoretisches Schema der Kryptografie

$(1.1–1.0) \{begin}{align*} \xymatrix @R=5mm@C=5mm{ &{\text {Nachricht}}\ar [d]&& {\text {Nachricht}}\\ &*++[F]{\txt {\textbf {Quellencodierung}\\(Datenkompression)}}\ar [d]&& *++[F]{\text {\textbf {Quellendecodierung}}}\ar [u]\\ {\text {Schlüssel } k_e}\ar [r]& *++[F]{\text {\textbf {Verschlüsselung} } c}="a"\ar [d]&& *++[F]{\text {\textbf {Entschlüsselung} } d}="b"\ar [u]& {\text {Schlüssel } k_s}\ar [l]\\ &*++[F]{\txt {\textbf {Kanalcodierung}\\(fehlerkorrigierende/\\-erkennende Codes)}}\ar [r]& *++[F-:<5mm>]{\text {\textbf {Kanal}}}\ar [r]& *++[F]{\text {\textbf {Kanaldecodierung}}}\ar [u]& } \{end}{align*}$

$k_e$ steht für encryption key und $k_s$ steht für secret key. Der Kanal kann z. B. eine DVD oder eine Telefonleitung sein. Einen Kanal zusammen mit einer Kanalcodierung und -decodierung heißt fehlerfreier Kanal (die übertragenen Daten enthalten keinen Fehler). Ein fehlerfreier Kanal zusammen mit einer Ver- und einer Entschlüsselung heißt sicherer Kanal (die übertragenen Daten wurden nicht abgehört oder verändert).

Wiederholung: Algebra und Modulo-Arithmetik

Restklassenringe

Teiler/Vielfaches: Seien $k, \ell \in \integer $.
Dann ist $k$ ein Teiler von $\ell $ und $\ell $ ein Vielfaches von $k$ ($k \teilt \ell $), falls $\exists _{m \in \integer }\; km = \ell $.

Restklassenring: Sei $n \in \natural $. Dann heißt $\ZnZ := \{0 \bmod n, \dotsc , (n - 1) \bmod n\}$ mit
$a \bmod n := \big \{b \in \integer \;\big |\; n \teilt (a - b)\big \}$ für $a \in \integer $ Restklassenring modulo $n$.
$\ZnZ $ ist ein Ring mit den (wohldefinierten) Operationen
$(a \bmod n) + (b \bmod n) := (a + b) \bmod n$ und $(a \bmod n)(b \bmod n) := (ab) \bmod n$.
Zur Vereinfachung lässt man die Nebenklassen weg: Aus jeder Nebenklasse wählt man stets den Repräsentanten, der in $\{0, \dotsc , n - 1\}$ liegt. Man schreibt also $\ZnZ = \{0, \dotsc , n - 1\}$ und definiert $a \bmod n$ als diesen Repräsentanten (d. h. $a \bmod n := a - \lfloor \frac {a}{n}\rfloor n$).
Man schreibt $a \equiv b \pmod n$ oder $a \equiv _n b$, falls $n \teilt (a - b)$, d. h. falls $a \bmod n = b \bmod n$.

chinesischer Restsatz: Seien $m, n \in \natural $ teilerfremd.
Dann ist $\integer /mn\integer \rightarrow \integer /m\integer \times \integer /n\integer $, $x \bmod mn \mapsto (x \bmod m, x \bmod n)$ ein Ringisomorphismus.
Insbesondere ist die Abbildung wohldefiniert und für $x, y \in \integer /mn\integer $ gilt $x \equiv _{mn} y$ genau dann, wenn $x \equiv _m y$ und $x \equiv _n y$.
Außerdem hat für vorgegebene $y_1, y_2 \in \integer $ das Kongruenzsystem $x \equiv _m y_1$ und $x \equiv _n y_2$ genau eine Lösung $x \in \integer /mn\integer $. Diese Lösung ist gegeben durch $x = y_1 a n + y_2 b m$, wobei $a \in \integer /m\integer $ mit $an \equiv _m 1$ und $b \in \integer /n\integer $ mit $bm \equiv _n 1$.
Diese Aussagen können auf $k$ Restklassenringe verallgemeinert werden.

Größter gemeinsamer Teiler

größter gemeinsamer Teiler: Seien $a, b \in \integer $ mit $(a, b) \not = (0, 0)$.
Dann heißt $k \in \natural $ mit $k \teilt a$, $k \teilt b$ und $\forall _{\ell \in \natural ,\; \ell \teilt a,\; \ell \teilt b}\; \ell \teilt k$ größter gemeinsamer Teiler $\ggT (a, b)$ von $a$ und $b$. Für $a = b = 0$ definiert man $\ggT (0, 0) := 0$.

teilerfremd: $a, b \in \integer $ heißen teilerfremd, falls $\ggT (a, b) = 1$.

Lemma von Bézout: Seien $a, b \in \integer $. Dann gibt es $s, t \in \integer $ mit $\ggT (a, b) = sa + tb$.

erweiterter euklidischer Algorithmus: Mit dem erweiterten euklidischen Algorithmus kann man $\ggT (a, b)$ in Zeit $\O (\log \min \{a, b\})$ für $a, b \in \integer \setminus \{0\}$ berechnen.
Anfangs sei $u = t := 1$ und $v = s := 0$.

Ist $b = 0$, so ist $\ggT (a, b) = |a|$ (analog bei $a = 0$).
Berechne $q, r$ mit $a = qb + r$ und $0 \le r < b$ durch Division mit Rest.
Setze $a^\ast := b$, $b^\ast := r$, $u^\ast := s$ und $v^\ast := t$.
Berechne $s^\ast := u - qs$ und $t^\ast := v - qt$.
Wiederhole mit $a^\ast , b^\ast , u^\ast , v^\ast , s^\ast , t^\ast $, bis $a = 0$ oder $b = 0$.

In jedem Schritt gilt $a = ua_0 + vb_0$ und $b = sa_0 + tb_0$ (mit den Eingabewerten $a_0, b_0$). Daher gilt $\ggT (a_0, b_0) = sa_0 + tb_0$ mit $s, t$ den Werten aus dem vorletzten Schritt (bevor $r = 0$ ist).

Prime Restklassengruppen

Primzahl: $p \in \natural $ heißt Primzahl oder prim, falls es genau zwei verschiedene natürliche Zahlen gibt, die Teiler von $p$ sind (nämlich $1$ und $p$ selbst). $\PP \subset \natural $ ist die Menge der Primzahlen.

zusammengesetzte Zahl: Eine nicht-prime Zahl $n \in \natural $ mit $n > 1$ heißt zusammengesetzt.

prime Restklassengruppe: Sei $n \in \natural $ mit $n > 1$.
Dann heißt $(\ZnZ )^\ast := \{a \in \ZnZ \;|\; \exists _{b \in \ZnZ }\; ab \equiv _n 1\}$ prime Restklassengruppe modulo $n$ (sie ist eine Gruppe bzgl. der Multiplikation in $\ZnZ $).
Für $a \in \ZnZ $ gilt $a \in (\ZnZ )^{\ast } \iff \ggT (a, n) = 1$.
Für $p \in \natural $ prim ist $(\ZpZ )^\ast = \{1, \dotsc , p-1\}$ ein Körper.

multiplikative Inverse: Für $a \in (\ZnZ )^\ast $ lässt sich das eindeutige $b \in (\ZnZ )^\ast $ mit $ab \equiv _n 1$ mit dem erweiterten euklidischen Algorithmus berechnen. Wegen $\ggT (a, n) = 1$ gilt mit dem Lemma von Bézout $\exists _{s, t \in \integer }\; 1 = sn + ta$. Modulo $n$ gilt daher $1 = sn + ta \equiv _n ta$, d. h. $b := t \bmod n$.

Eulersche $\varphi $-Funktion: Die Abb. $\varphi \colon \natural \rightarrow \natural $, $\varphi (n) := \left |\{a \in \{1, \dotsc , n\} \;|\; \ggT (a, n) = 1\}\right |$ heißt Eulersche $\varphi $-Funktion. Es gilt $\varphi (n) = |(\ZnZ )^\ast |$.
Für $p \in \natural $ prim gilt $\varphi (p) = p - 1$. Für $p, q \in \natural $ teilerfremd gilt $\varphi (p \cdot q) = \varphi (p) \cdot \varphi (q)$.
Insbesondere gilt $\varphi (pq) = (p-1)(q-1)$ für verschiedene Primzahlen $p, q$.

Satz von Euler: Seien $a \in \integer $ und $n \in \natural $ mit $\ggT (a, n) = 1$.
Dann gilt $a^{\varphi (n)} \equiv _n 1$.

kleiner Satz von Fermat: Seien $a \in \integer $ und $p$ eine Primzahl mit $\ggT (a, p) = 1$.
Dann gilt $a^{p-1} \equiv _p 1$.

Gruppen

Gruppe: Eine Gruppe $(G, \ast )$ ist eine Menge $G$ mit einer Abbildung $\ast \colon G \times G \rightarrow G$, sodass $\ast $ assoziativ ist, ein neutrales Element $e$ existiert und inverse Elemente $g^{-1}$ existieren.

Untergruppe: Eine Teilmenge $H \subset G$ einer Gruppe $G$ heißt Untergruppe von $G$ ($H < G$), falls $e \in H$ sowie $\forall _{x, y \in H}\; x \ast y \in H,\; x^{-1} \in H$. $(H, \ast )$ ist selbst eine Gruppe.

zyklisch: Eine Gruppe $G$ heißt zyklisch, falls $\exists _{g \in G}\; G = \{g^n \;|\; n \in \integer \}$.
In diesem Fall heißt jedes Element $g \in G$ mit dieser Eigenschaft Erzeuger von $G$.
$\{g^n \;|\; n \in \integer \}$ ist eine Untergruppe von $G$, die von $g$ erzeugte zyklische Untergruppe $\erzeugnis {g}$ von $G$.
Ist $G$ zyklisch und endlich, so ist $G$ isomorph zu $(\ZnZ , +)$ mit $n := |G|$.
Ist $G$ zyklisch und unendlich, so ist $G$ isomorph zu $(\integer , +)$.
$(\ZnZ , +)$ ist zyklisch, die Erzeuger sind genau die Restklassen, die teilerfremd zu $n$ sind.
$((\ZnZ )^\ast , \cdot )$ ist zyklisch genau dann, wenn $\exists _{p > 2 \text { prim}} \exists _{k \in \natural }\; n \in \{2, 4, p^k, 2p^k\}$ (insbesondere ist $(\ZpZ )^\ast $ zyklisch für $p \in \natural $ prim).

Primitivwurzel:
Ist $((\ZnZ )^\ast , \cdot )$ zyklisch, dann heißen Erzeuger von $(\ZnZ )^\ast $ Primitivwurzeln modulo $n$.

Ordnung

Gruppenordnung: Sei $G$ eine Gruppe. Dann heißt $\ord (G) := |G|$ Gruppenordnung von $G$.

Ordnung: Seien $G$ eine Gruppe und $g \in G$.
Dann heißt $\ord (g) = \ord _G(g) := \min \{k \in \natural \;|\; g^k = e\}$ Ordnung von $g$ in $G$. Für $G := (\integer /n\integer )^\ast $ und $a \in (\integer /n\integer )^\ast $ heißt $\ord _n(a) := \min \{k \in \natural \;|\; a^k \equiv _n 1\}$ Ordnung von $a$ modulo $n$.
Es gilt $\ord (g) = \ord (\erzeugnis {g})$. $g$ ist ein Erzeuger von $G$ genau dann, wenn $\ord (g) = \ord (G)$.
Für $\ell \in \natural $ gilt $g^\ell = e$ genau dann, wenn $\ord (g) \teilt \ell $.

Satz von Lagrange: Seien $G$ eine endliche Gruppe und $H < G$. Dann gilt $|H| \teilt |G|$.

Index: Seien $G$ eine endliche Gruppe und $H < G$.
Dann heißt $[G : H] := \frac {|G|}{|H|} \in \natural $ Index von $H$ in $G$.

Ringe und Körper

Ring: Ein Ring $(R, +, \cdot )$ ist eine Menge zusammen mit Abbildungen $+, \cdot \colon K \times K \rightarrow K$, sodass $(K, +)$ eine abelsche Gruppe mit neutralem Element $0$ ist, $\cdot $ assoziativ ist und das Distributivitätsgesetz gilt.

Körper: Ein Körper $(K, +, \cdot )$ ist eine Menge zusammen mit Abbildungen $+, \cdot \colon K \times K \rightarrow K$, sodass $(K, +)$ eine abelsche Gruppe mit neutralem Element $0$ ist, $(K \setminus \{0\}, \cdot )$ eine abelsche Gruppe mit neutralem Element $1$ ist und das Distributivitätsgesetz gilt.
Ein Körper ist ein kommutativer Ring mit Eins mit allen $a \in K \setminus \{0\}$ multiplikativ invertierbar.
Ein Körper ist nullteilerfrei, d. h. aus $ab = 0$ für $a, b \in K$ folgt $a = 0$ oder $b = 0$.
Jedes Polynom vom Grad $n \ge 1$ in $K[x]$ hat höchstens $n$ Nullstellen.

endlicher Körper: Für jeden endlichen Körper $\FF $ mit $q := |\FF |$ gilt $q = p^n$ für eine Primzahl $p \in \natural $ und $n \in \natural $. Bis auf Isomorphie gibt es genau einen Körper mit $q$ Elementen, der mit $\FF _q$ bezeichnet wird. Für $q = p$ prim gilt $\FF _p \cong \ZpZ $. Für jeden endlichen Körper $\FF _q$ ist $\FF _q^\ast $ zyklisch.

Konstruktion von endlichen Körpern: Seien $p$ prim, $\FF _p := \ZpZ $ und $f(X) \in \FF _p[X]$ irreduzibel (nicht darstellbar als Produkt zweier nicht-konstanter Polynome) mit $n := \deg f \ge 1$.
Dann ist $\KK := \FF _p[X]/\erzeugnis {f(X)}$ ein Körper mit $|\KK | = p^n$, d. h. $\KK \cong \FF _q$ mit $q = p^n$. Man kann $f$ auch als Polynom in $\KK [Y]$ betrachten: $\overline {X} := X + \erzeugnis {f(X)}$ ist eine Nullstelle von $f(Y) \in \KK [Y]$, insbesondere ist $f(Y) \in \KK [Y]$ reduzibel für $\deg f \ge 2$.

Charakteristik: Sei $\FF $ ein Körper. Dann heißt die kleinste Zahl $p \in \natural $ mit $p \cdot 1_\FF = 0_\FF $ ($p$-fache Summe von $1_\FF $) Charakteristik von $\FF $. Gilt $\forall _{p \in \natural }\; p \cdot 1_\FF \not = 0_\FF $, dann hat $\FF $ die Charakteristik $0$. Die Charakteristik ist entweder $0$ oder eine Primzahl $p$. Der endliche Körper $\FF _q$ mit $q = p^n$ hat die Charakteristik $p$. (Körper mit Charakteristik $0$ sind unendlich, die Umkehrung gilt i. A. nicht.)