notes/school/intro-crypto/uebung/05/05.tex

\documentclass[12pt,a4paper,german]{article}
\usepackage{url}
%\usepackage{graphics}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{pifont}
\usepackage{ngerman}
\usepackage{float}
\usepackage{diagbox}
\usepackage[latin1]{inputenc}
\usepackage{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{delarray}
% \usepackage{minted}
\usepackage{csquotes}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{longtable}
\usepackage{paralist}
\geometry{left=2.0cm,textwidth=17cm,top=3.5cm,textheight=23cm}

\graphicspath{.}

%%%%%%%%%% Fill out the the definitions %%%%%%%%%
\def \name {Valentin Brandl}					%
\def \matrikel {108018274494}				%
% \def \pname {Vorname2 Nachname2}				%
% \def \pmatrikel {Matrikelnummer2}				%
\def \gruppe {Gruppe 193}					%
\def \uebung {5}								%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 % DO NOT MODIFY THIS HEADER
\newcommand{\hwsol}{
\vspace*{-2cm}
\noindent \matrikel \quad \name \hfill Gruppe:\gruppe \\
% \noindent \pmatrikel \quad \pname \\
\begin{center}{\Large \bf L\"osung f\"ur \"Ubung \# \uebung}\end{center}
}

\newcommand{\cmark}{\ding{51}}%
\newcommand{\xmark}{\ding{55}}%
\newcommand{\csquare}{\text{\rlap{$\checkmark$}}\square}%

\begin{document}
%Import header
\hwsol


\section*{Aufgabe 1}

\begin{enumerate}[a)]

    \item Das National Bureau of Standards (NBS) (heute National Institute of Standards and Technology (NIST)) hat die
        Entwicklung des DES ausgeschrieben.

    \item DES wurde 1977 standardisiert.

    \item Die National Security Agency (NSA) hat an der Entwicklung des DES mitgewirkt.

    \item Die Kryptographen, die den Kandidaten eingereicht haben, geh<65>rten IBM an.

    \item Auf einen Feistel Netz mit einer Blockgr<67><72>e von 64 bit und einer Schl<68>ssell<6C>nge von 128 bit

    \item Die Schl<68>ssell<6C>nge von Lucifer ist 128 bit

    \item Die Schl<68>ssell<6C>nge des DES ist 56 bit und das Sicherheitsniveau ist 56 bit.

    \item Es werden 64 bit in einer DES Operation verschl<68>sselt.

    \item Abbildung \ref{feist_alg} und \ref{feist_round}

        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.5]{./build/school/intro-crypto/uebung/05/a1i.png}
            \caption{Allgemeine Struktur eines Feistel Netzes}
            \label{feist_alg}
        \end{figure}
        \begin{figure}[h!]
            \centering
            \includegraphics[width=\textwidth/2]{school/intro-crypto/uebung/05/a1i2.jpg}
            \caption{Struktur einer Feistel Runde}
            \label{feist_round}
        \end{figure}

\end{enumerate}

\section*{Aufgabe 2}

\begin{enumerate}[a)]

    \item
        \begin{tabular}{|c|ccccc|}
            \hline
            $S_4$ & 0 & 1 & 2 & 3 & 4 \\\hline
            0 & 07 & 13 & 14 & 03 & 00 \\\hline
            1 & 13 & 08 & 11 & 05 & 06 \\\hline
        \end{tabular}

        \begin{tabular}{|c|ccccc|}
            \hline
            & 0 & 1 & 2 & 3 & 4 \\\hline
            $(y_1,y_2,y_3,y_4)$ & 0111 & 1101 & 1110 & 0011 & 0000 \\\hline
            $(y_2,y_1,y_4,y_3)$ & 1011 & 1110 & 1101 & 0011 & 0000 \\\hline
            $(y_2,y_1,y_4,y_3) \oplus (0,1,1,0)$ & 1101 & 1000 & 1011 & 0101 & 0110 \\\hline
            Dezimal & 13 & 8 & 11 & 5 & 6 \\\hline
        \end{tabular}

        Das Ergebnis entspricht genau der 1. Zeile in der S-Box $S_4$.

    \item
        \begin{tabular}{|c|ccccc|}
            \hline
            $S_4$ & 0 & 1 & 2 & 3 & 4 \\\hline
            2 & 10 & 06 & 09 & 00 & 12 \\\hline
            3 & 03 & 15 & 00 & 06 & 10 \\\hline
        \end{tabular}

        Tabelle in bin<69>r:

        \begin{tabular}{|c|ccccc|}
            \hline
            $S_4$ & 0 & 1 & 2 & 3 & 4 \\\hline
            2 & 1010 & 0110 & 1001 & 0000 & 1100 \\\hline
            3 & 0011 & 1111 & 0000 & 0110 & 1010 \\\hline
        \end{tabular}

        Gesucht:

        \begin{itemize}
            \item Permutationsfunktion $f : (y_1,y_2,y_3,y_4) \to (y_1',y_2',y_3',y_4')$
            \item xor Parameter $x = (x_1,x_2,x_3,x_4)$
    \end{itemize}

    Der Ausgangswert von Spalte 3 (0000) bleibt von der Permutationsfunktion unver<65>ndert: $f(0000) = 0000 \Rightarrow x
    = 0000 \oplus 0110 = 0110$

        \begin{tabular}{|c|ccccc|}
            \hline
            $S_4$ & 0 & 1 & 2 & 3 & 4 \\\hline
            3 & 0011 & 1111 & 0000 & 0110 & 1010 \\\hline
            Zeile $3 \oplus 0110$ & 0101 & 1001 & 0110 & 0000 & 1100 \\\hline
            2 & 1010 & 0110 & 1001 & 0000 & 1100 \\\hline
        \end{tabular}

        Man kann sehen, dass wieder $y_1$ mit $y_2$ und $y_3$ mit $y_4$ vertauscht werden.

        $\Rightarrow$ Ableitung von Zeile 2 zu 3:

        \begin{align*}
            (y_1,y_2,y_3,y_4) \to (y_2,y_1,y_4,y_3) \oplus (0,1,1,0)
        \end{align*}


\end{enumerate}

\section*{Aufgabe 3}




\begin{enumerate}[a)]

    \item
        \begin{tabular}{|c|ccccccccc|}
            \hline
            & $x_1$ & $x_2$ & ... & $x_{56}$ & $x_{57}$ & $x_{58}$ & ... & $x_{63}$ & $x_{64}$ \\\hline
            Eingabe $x$ & 1 & 1 & ... & 1 & 0 & 1 & ... & 1 & 1 \\\hline
            $IP(x)$     & 1 & 1 & ... & 1 & 1 & 1 & ... & 0 & 1 \\\hline
        \end{tabular}

        \begin{align*}
            L_0 &= 11111111111111111111111111111111 \\
            R_0 &= 11111111111111111111111111111101 = L_1
        \end{align*}

        Das zu beobachtende Bit steht an Position $31$.

        \begin{align*}
            E(R_0) &= 111111111111111111111111111111111111111111111011
        \end{align*}

        Auswirkungen:

        $S_1\ \square$
        $S_2\ \square$
        $S_3\ \square$
        $S_4\ \square$
        $S_5\ \square$
        $S_6\ \square$
        $S_7\ \square$
        $S_8\ \csquare$

        Eingangsbits: $E(R_0) \oplus 111111111111111111111111111111111111111111111111$

        S-Box $S_1$: $000000$

        S-Box $S_2$: $000000$

        S-Box $S_3$: $000000$

        S-Box $S_4$: $000000$

        S-Box $S_5$: $000000$

        S-Box $S_6$: $000000$

        S-Box $S_7$: $000000$

        S-Box $S_8$: $000100$

    \item
        Ausgabe der S-Boxen:

        S-Box $S_1$: $14 = 1110$

        S-Box $S_2$: $15 = 1111$

        S-Box $S_3$: $10 = 1010$

        S-Box $S_4$: $07 = 0111$

        S-Box $S_5$: $02 = 0010$

        S-Box $S_6$: $12 = 1100$

        S-Box $S_7$: $04 = 0100$

        S-Box $S_8$: $08 = 1000$

        Ausgabe nach allen S-Boxen:

        \begin{align*}
            s &= 11101111101001110010110001001000 \\
            P(s) &= 10000010010110011101011100111011 \\
            P(s) \oplus L_0 &= 01111101101001100010100011000100 = R_1 \\
            \\
            L_1 = R_0 &= 11111111111111111111111111111101 \\
            R_1 &= 01111101101001100010100011000100
        \end{align*}

    \item
        \begin{tabular}{|c|ccccccccc|}
            \hline
            & $x_1$ & $x_2$ & ... & $x_{56}$ & $x_{57}$ & $x_{58}$ & ... & $x_{63}$ & $x_{64}$ \\\hline
            Eingabe $x$ & 1 & 1 & ... & 1 & 1 & 1 & ... & 1 & 1 \\\hline
            $IP(x)$     & 1 & 1 & ... & 1 & 1 & 1 & ... & 1 & 1 \\\hline
        \end{tabular}

        \begin{align*}
            L_0 &= 11111111111111111111111111111111 \\
            R_0 &= 11111111111111111111111111111111 = L_1 \\
            E(R_0) &= 111111111111111111111111111111111111111111111111 \\
            E(R_0) &\oplus 111111111111111111111111111111111111111111111111 \\
                   &= 000000000000000000000000000000000000000000000000
        \end{align*}

        Einzige <20>nderung in S-Box $S_8$:

        \begin{align*}
            S_8(000000) &= 13 = 1101 \\
            s &= 11101111101001110010110001001101 \\
            P(s) &= 10000010011110011101011110111011 \\
            \\
            L_1 = R_0 &= 11111111111111111111111111111111 \\
            R_1 &= 01111101100001100010100001000100 \\
        \end{align*}

        Anzahl ge<67>nderter Bits: In $L_1$: 1, in $R_1$: 2. Insgesamt 3 ge<67>nderte Bits

\end{enumerate}

\section*{Aufgabe 4}

Aufbau einer Runde DES:

Input: 64 Bit Daten unterteilt in $L_{n-1}, R_{n-1}$ und der Schl<68>ssel $k_n$

Output: $L_n$ und $R_n$, der Input f<>r die n<>chst Feistel Runde

Eine Runde im Feistel Netz sei beschrieben durch

\begin{align*}
    F &: (L_{n-1}, R_{n-1}, k_n) \to (L_n, R_n) \\
\end{align*}

mit

\begin{align*}
    L_n &= R_{n-1} \\
    R_n &= f(k_n, R_{n-1}) \oplus L_{n-1} \\
    f(k, x) &= P(S(E(x) \oplus k))
\end{align*}

mit den S-Boxen beschrieben in $S$, der E-Box $E$ und der abschlie<69>enden P-Box $P$

Einschub: $a \oplus b = \overline{a} \oplus \overline{b}$ \\

\begin{tabular}{|c|c|c|c|c|c|}
    \hline
    $a$ & $b$ & $\overline{a}$ & $\overline{b}$ & $a \oplus b$ & $\overline{a} \oplus \overline{b}$ \\\hline
    0 & 0 & 1 & 1 & 0 & 0 \\
    0 & 1 & 1 & 0 & 1 & 1 \\
    1 & 0 & 0 & 1 & 1 & 1 \\
    1 & 1 & 0 & 0 & 0 & 0 \\\hline
\end{tabular}

Da $E$ nichts berechnet sondern nur deterministisch manche Bits kopiert, gilt $E(\overline{x}) = \overline{E(x)}$

$\Rightarrow$ Der Input f<>r die S-Boxen ist also

\begin{align*}
    s &= E(\overline{x}) \oplus \overline{k} = \\
      &= \overline{E(x)} \oplus \overline{k} = \\
      &= E(x) \oplus k
\end{align*}

Da der Input der S-Boxen f<>r $f(k, x)$ und $f(\overline{k}, \overline{x})$ gleich ist, ist auch der Output gleich

\begin{align*}
    \Rightarrow f(k, x) &= f(\overline{k}, \overline{x})
\end{align*}

Einschub: $a \oplus \overline{b} = \overline{a \oplus b}$ \\

\begin{tabular}{|c|c|c|c|c|}
    \hline
    $a$ & $b$ & $\overline{b}$ & $a \oplus b$ & $a \oplus \overline{b}$ \\\hline
    0 & 0 & 1 & 0 & 1 \\\hline
    0 & 1 & 0 & 1 & 0 \\\hline
    1 & 0 & 1 & 1 & 0 \\\hline
    1 & 1 & 0 & 0 & 1 \\\hline
\end{tabular} \\

Da der Output von $f$ gleich bleibt f<>r komplement<6E>ren Input:

\begin{align*}
    R_n &= f(k_n, R_{n-1}) \oplus L_{n-1} \\
    \\
    \overline{R_n} &= f(\overline{k_n}, \overline{R_{n-1}}) \oplus \overline{L_{n-1}} \\
                   &= f(k_n, R_{n-1}) \oplus \overline{L_{n-1}} \\
\end{align*}

Da $L_n$ ohne Ver<65>nderung aus $R_{n-1}$ <20>bernommen wird, gilt weiter:

\begin{align*}
    \overline{L_n} &= \overline{R_{n-1}}
\end{align*}

F<EFBFBD>r jede einzelne Runde im Feistel Netz gilt also

\begin{align*}
    F(\overline{L_{n-1}}, \overline{R_{n-1}}, \overline{k_n}) &= \overline{F(L_{n-1}, R_{n-1}, k_n)}
\end{align*}

Da auch die Ein- und Ausgangspermutation $IP$ und $IP^{-1}$ nur Bits auf eine deterministische Weise vertauschen, gilt:

\begin{align*}
    \overline{i(x)} = i(\overline{x}) \forall i \in \{IP, IP^{-1}\}
\end{align*}

Ein- und Ausgangspermutation geben f<>r komplement<6E>ren Input also komplement<6E>ren Output, genauso wie jede Runde im
Feistel Netz und damit der gesamte DES Algorithmus

$\Rightarrow$ Wenn $y = DES_k(x)$, dann $\overline{y} = DES_{\overline{k}}(\overline{x})$

% \section*{Code}

% \inputminted{rust}{./school/intro-crypto/uebung/05/p/src/main.rs}

\end{document}