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
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 | 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×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 | 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
Euklidischer Algorithmus
- Satz von Bézout
- \[
\mathrm{ggT}(a,b) = x\cdot a + y\cdot b
\]
z.B für \(\mathrm{ggT}(10,7)\):
\(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 φ-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
Die Lösung ist dann eindeutig in \(\mathbb{Z}/t\mathbb{Z}\)
\[
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
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 \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 \]
Insbesondere
\[
a^x \equiv a^{x \bmod \varphi(n)} \pmod{n}
\]
- Fermat-Pseudoprimzahl zur Basis \(a\)
\(n\) zusammengesetzt, aber \(\mathrm{ggT}(a,n) = 1\) und \(a^{n-1} \equiv 1 \bmod n\)
Miller-Rabin
- Miller-Rabin-Primzahltest zur Basis \(a\)
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\)
- 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\)?
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\)
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\)
\[
c = m^e \bmod N
\]
Entschlüsseln von \(m\)
\[
m = c^d \bmod N
\]
Signieren von \(m\)
Alice signiert mit ihrem privaten Schlüssel \((N,d)\)
Bob verifiziert mit Alices öffentlichen Schlüssel \((N,e)\)
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)
\]
Bei Kenntnis des öffentlichen und privaten Schlüssels
Gegeben sei öffentlicher Schlüssel \((N,e)\) und privater Schlüssel \((N,d)\).
- \[
k := \left\lfloor \frac{e\cdot d}{N} \right\rfloor
\]
- \(k:= k+1\) solange bis \(k \mid e\cdot d - 1\)
- \(s = N +1 - \frac{e\cdot d - 1}{k}\) und \(\Delta = \left\lfloor \sqrt{s^2 - 4\cdot N} \right \rfloor\)
- 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\)
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)\)
Entschlüsseln von \((c_1,c_2)\)
$$
\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*}
$$
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\)
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)\).
Die Signatur ist gültig, wenn \(0 \leq b \leq p - 1\) und \(t = t'\)