140 lines
9.6 KiB
TeX
140 lines
9.6 KiB
TeX
\chapter{Stromverschlüsselungsverfahren}
|
|
Bei einem Stromverschlüsselungsverfahren wird eine Nachricht zeichenweise verschlüsselt.
|
|
Die Menge der verschlüsselten Zeichen $\mathscr{M}$ ist als endliche Folge von Elementen einer Zeichenmenge $\mathscr{Z}$ definiert.
|
|
$$\mathscr{M} = \mathscr{Z}^{>0} := \bigcup_{l\in \mathbb{N}}\mathscr{Z}^l=\{(m_1,m_2,...,m_l)\mid m_i\in\mathscr{Z},l\in\mathbb{N}\}$$
|
|
Die Verschlüsselungsfunktion $E_k$ lässt sich zeichenweise beschreiben:
|
|
$$E^{(i)}:\mathscr{K}\times\mathscr{Z}^i\rightarrow\mathscr{Z}\space\text{für alle }i\in\mathbb{N}$$
|
|
mit:
|
|
$$E_k((m_1,m_2,...,m_l))=(E^{(1)}(k,(m_1)),E^{(2)}(k,(m_1,m_2)),...,E^{(l)}(k,(m_1,m_2,...,m_l)))$$
|
|
Bei manchen Verfahren können bei der Berechnung des $i$-ten Geheimtextzeichens $c_i=E^{(i)}(k,(m_1,m_2,...,m_i))$ auch die vorherigen Zeichen miteinfließen.
|
|
|
|
\includegraphics{Stromverschlüsselung.png}
|
|
|
|
\section{Synchrone Stromverschlüsselungsverfahren}\label{synchrone Stromverschlüsselung}
|
|
Bei synchronen Stromverschlüsselungsverfahren hängen die Zeichen einer Geheimtextnachricht nicht von den vorherigen ab.
|
|
So ist es möglich die einzelnen Zeichen des Klartextes gleichzeitig (synchron) zu verschlüsseln.
|
|
Ein Beispiel hierfür sind monoalphabetische Verschlüsselungsverfahren (siehe \ref{monoalphabet}).
|
|
$$E^{(i)}:\mathscr{K}\times\mathscr{Z}\rightarrow\mathscr{Z}$$
|
|
wobei gelten muss:
|
|
$$E_k((m_1,m_2,...,m_l))=(E^{(1)}(k,m_1),E^{(2)}(k,m_2),...,E^{(l)}(k,m_l))$$
|
|
|
|
\includegraphics{synchrone Stromverschlüsselung.png}
|
|
|
|
\section{Zustandsabhängige Stromverschlüsselungsverfahren}
|
|
Bei einer zustandsabhängigen Stromverschlüsselung werden die Zeichen mithilfe eines Zustands verschlüsselt, der sich abhängig vom vorherigen Zeichen ändert.
|
|
Hierzu werden benötigt:
|
|
$$\begin{aligned}
|
|
\mathscr{S}&:\text{Menge der Zustände}\\
|
|
s_0&:\mathscr{K}\rightarrow\mathscr{S}\\
|
|
s&:\mathscr{S}\times\mathscr{Z}\rightarrow\mathscr{S}\\
|
|
E&:\mathscr{S}\times\mathscr{Z}\rightarrow\mathscr{Z} \space \text{(bijektiv)}
|
|
\end{aligned}$$
|
|
Mithilfe von $s_0$ und einem Schlüssel $k$ wird ein Startzustand $\sigma_1 := s_0(k)$ festgelegt.
|
|
Die folgenden Zustände $\sigma_i$ werden mithilfe der Abbildung $s$ errechnet:
|
|
$$\sigma_i := s(\sigma_{i-1},m_{i-1})$$
|
|
Die einzelnen Zeichen lassen sich dann mithilfe von $E$ in Abhängigkeit von dem jeweiligen Zustand bestimmen:
|
|
$$c_l := E(\sigma_l,m_l)$$
|
|
|
|
\includegraphics{zustandsabhängige Stromverschlüsselung.png}\label{zustandsabhängige Stromverschlüsselung}
|
|
|
|
\subsection{Additive zustandsabhängige Stromverschlüsselungsverfahren}
|
|
Additive zustandsabhängige Stromverschlüsselungsverfahren sind zustandsabhängige Stromverschlüsselungsverfahren, mit einer Funktion $S:\mathscr{S}\rightarrow\mathscr{Z}$.
|
|
Die Verschlüsselungsfunktion ist hierbei durch $E(\sigma,m) = S(\sigma) + m$ definiert, wobei hierbei eine modulare Addition (siehe \ref{modulare_addition}) über $\mathscr{Z}$ stattfindet.
|
|
$s_0$,$s$ und $S$ bilden den Schlüsselstromgenerator, der den folgenden Schlüsselstrom erzeugt:
|
|
$$z_i := S(\sigma_i) = S(s(\sigma_{i-1},m_{i-1}))$$
|
|
|
|
\includegraphics{additive zustandsabhängige Stromverschlüsselung.png}
|
|
|
|
\subsubsection{Synchrone additive Stromverschlüsselungsverfahren}\label{synchron additive Stromverschlüsselung}
|
|
eine additive Stromverschlüsselung lässt sich synchron durchführen, falls die Übergangsfunktion $s$ nicht von den Zeichen des Klartextes abhängt.
|
|
$$\sigma_{i+1}=s(\sigma_i) \text{ mit } s:\mathscr{S}\rightarrow\mathscr{S}$$
|
|
Hierdurch definiert sich der Schlüsselstrom:
|
|
$$z_i=S(s^{i-1}(s_0(k))) \hspace{5mm} (i\in \mathbb{N})$$
|
|
|
|
\includegraphics{synchrone additive Stromverschlüsselung.png}
|
|
|
|
\section{Schlüsselstrom vs. One-Time-Pad}
|
|
Ein One-Time-Pad (siehe \ref{otp}) ist eine spezielle Form einer additiven Stromverschlüsselung, wobei die Schlüsselstormzeichen $S{\sigma_i}$ direkt aus dem Schlüssel $k$ entnommen werden.
|
|
Aufgrund dieser Tatsache kann eine Schlüsselstrom als Ersatz für ein One-Time-Pad betrachtet werden.
|
|
Hierbei ist allerdings darauf zu achten, dass folgendende Bedingungen erfüllt sind:
|
|
\begin{itemize}
|
|
\item Schlüsselstromzeichen dürfen keinen Aufschluss über die nachfolgenden Zeichen geben
|
|
\begin{itemize}
|
|
\item Schlüsselstromzeichen müssen statistisch gleichverteilt und unkorreliert sein
|
|
\item ein Schlüssel $k\in \mathscr{K}$ dient gut zur Initialisierung eines Pseudozufallsgenerators
|
|
\end{itemize}
|
|
\item die Bestimmung des Schlüssels $k$ darf nicht effizienter als mit einer Brute-Force-Suche (siehe \ref{brute-force}) im Schlüsselraum $\mathscr K$ möglich sein.
|
|
\end{itemize}
|
|
|
|
\section{Nonces zur Initialisierung eines Schlüsselstromgenerators}
|
|
Wie bei einem One-Time-Pad (siehe \ref{otp}) sollte ein Schlüsselstrom nur einmalig verwendet werden.
|
|
Da der Austausch von Schlüsseln bei synchronen Verschlüsselungsverfahren allerdings sehr aufwendig ist, wird versucht den Schlüssel weiter zu verwenden.
|
|
Hierfür gibt es mehrere Möglichkeiten:
|
|
\begin{itemize}
|
|
\item Der Schlüsselstrom wird nicht neu initialisiert und durchgehend weiterverwendet (Schlüsselstrom muss zwischen Sender und Empfänger synchron bleiben).
|
|
\item Der verwendete Schlüssel wird durch einen Nonce-Wert $\eta_m$ verändert.
|
|
\begin{itemize}
|
|
\item $\eta_m$ muss mit übertragen werden und zwischen Sender und Empfänger synchron gehalten werden
|
|
\item Der Schlüssleraum $\mathscr k$ wird kleiner, da er sich in einen Raum $\mathscr K_{eff}$, in dem $k$ liegt und einen Bereich $\mathscr N$ für den Nonce-Wert aufteilt
|
|
\end{itemize}
|
|
\item Die Funktion $s_0$ (siehe \ref{zustandsabhängige Stromverschlüsselung}) wird so erweitert, dass sowohl Werte aus $\mathscr K$, als auch aus $\mathscr N$ einfließen:
|
|
$$s_0:\mathscr K \times \mathscr N \rightarrow \mathscr S$$
|
|
\includegraphics{Schlüsselstromgenerator mit Nonce.png}
|
|
\end{itemize}
|
|
|
|
\section{ChaCha20}
|
|
Der ChaCha20-Schlüsselstromgenerator nutzt für die Initialisierung des Zustands $s_0$ einen Schlüsselwert $k\in\mathscr K$ und einen Nonce-Wert $\eta\in\mathscr N$.
|
|
Für die Beschreibung des Algorithmus werden die folgenden Mengen benötigt:
|
|
$$\begin{aligned}
|
|
(\text{byte-basiert})\hspace{10mm} \mathscr Z &= \mathbb{Z}_{2^8}\\
|
|
(\text{int-basiert})\hspace{10mm} \mathscr K &= (\mathbb{Z}_{2^{32}})^8\\
|
|
(\text{int-basiert})\hspace{10mm} \mathscr S &= (\mathbb{Z}_{2^{32}})^{16}\times(\mathbb{Z}_{2^{32}})^{16}\times\mathbb{Z}_{2^{38}+1}\\
|
|
(\text{int-basiert})\hspace{10mm} \mathscr N &= (\mathbb{Z}_{2^{32}})^3\\
|
|
\end{aligned}$$
|
|
Elemente im Zustandsraum $\mathscr S$ bestehen aus 3-Tupeln:
|
|
$$(s^0,s,c)= (\mathbb{Z}_{2^{32}})^{16}\times(\mathbb{Z}_{2^{32}})^{16}\times\mathbb{Z}_{2^{38}+1}$$
|
|
In $s^0$ werden der Schlüssel $k$ und der Nonce-Wert $\eta$ mit fest definierten Konstanten nach der Initialisierung abgespeichert.
|
|
Bei der Initialisierung und nach Ausgabe von jeweils 64 Bytes wird der Wert von $s^0$ nach $s$ kopiert und in einen Block von 64 Schlüsselstrombytes überführt.
|
|
$c$ speichert die Anzahl der bereits verwendeten Schlüsselstrombytes (nach Spezifikation max. $2^{38}$ Bytes)\\
|
|
\textbf{Initalisierung:}
|
|
$$s_0:\mathscr K \times \mathscr N \rightarrow \mathscr S$$
|
|
daraus ergibt sich:
|
|
$$\begin{aligned}
|
|
s_0((k,\eta)) =& s_0(((k_1,...,k_8),(n_1,n_2,n_3)))\\
|
|
:=& s(((c_1,c_2,c_3,c_4,k_1,...,k_8,0,n_1,n_2,n_3),(0,...,0),0))\\
|
|
=& s((s^0,0,0))
|
|
\end{aligned}$$
|
|
wobei $c_i$ die folgende Konstanten sind:
|
|
$$\begin{aligned}
|
|
c_1 =&0x61707865\\
|
|
c_2 =&0x3320646e\\
|
|
c_3 =&0x79622d32\\
|
|
c_4 =&0x6b206574\\
|
|
\end{aligned}$$
|
|
und
|
|
$$s^0 := (c_1,c_2,c_3,c_4,k_1,...,k_8,0,n_1,n_2,n_3)$$
|
|
\textbf{Update-Funktion:} $s: \mathscr S \rightarrow\mathscr S$\\
|
|
Solange $c<2^{38}$ gilt:
|
|
$$s((s^i,s,c)):=\begin{cases}
|
|
(s^i,s,c+1) &\text{falls }c \mod 64 \ne 0\\
|
|
(s^{i+1},s^i\oplus {f_{ib}}^{10}(s^i),c+1) &\text{falls }c\mod 64 = 0
|
|
\end{cases}$$
|
|
$f_{ib}$ wird 10 mal wiederholt und bildet die folgende Abbildung:
|
|
$$f_{ib}:(\mathbb{Z}_{2^{32}})^{16}\rightarrow(\mathbb{Z}_{2^{32}})^{16}$$
|
|
Die Funktion ist in RFC 8439 definiert.\\
|
|
\textbf{Extraktion der Schlüsselstromzeichen:} $S;\mathscr S \rightarrow \mathscr S$\\
|
|
Mit der Funktion $S$ werden die Bytewerte, aus denen die Zahlen $s_0,s_1,...,s_{15}$ der zweiten Komponente eines Elements aus $\mathscr S$ zusammengesetzt sind, extrahiert:\\
|
|
Für
|
|
$$(s^0,s,c) = (s^0,(s_0,s_1,...,s_{15}),c)\in\mathscr S$$
|
|
werden Hierzu
|
|
$$\begin{aligned}
|
|
i&=\lfloor c/4 \rfloor \mod 16\\
|
|
j&=c \mod 4
|
|
\end{aligned}$$
|
|
berechnet und
|
|
$$S((s^0,(s_0,s_1,...,s_{15}),c)) := \lfloor \frac{s_i}{2^{8j}} \rfloor \mod 2^8$$
|
|
gesetzt.
|
|
|
|
\section{Cipher-Instanzen: Verschlüsselungsalgorithmen in Java-Laufzeitumgebungen}
|
|
siehe Skript2 1.5 (Seite 19).
|