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

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

\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 φ-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

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)\)

\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\)

    \(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\)

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\)

\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 ρ-Methode

Author: Florian Guthmann

Created: 2023-03-10 Fri 12:19

Validate