ad-20240418.tex

% ad-20240418.pdf - Lecture Slides on Algorithms and Data Structures in C/C++
% Copyright (C) 2018, 2019, 2020, 2021, 2022, 2023, 2024  Peter Gerwinski
%
% This document is free software: you can redistribute it and/or
% modify it either under the terms of the Creative Commons
% Attribution-ShareAlike 3.0 License, or under the terms of the
% GNU General Public License as published by the Free Software
% Foundation, either version 3 of the License, or (at your option)
% any later version.
%
% This document is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details.
%
% You should have received a copy of the GNU General Public License
% along with this document.  If not, see <http://www.gnu.org/licenses/>.
%
% You should have received a copy of the Creative Commons
% Attribution-ShareAlike 3.0 Unported License along with this
% document.  If not, see <http://creativecommons.org/licenses/>.

% README: Mathematische Grundlagen der Kryptographie

\documentclass[10pt,t]{beamer}

\usepackage{pgslides}
\usepackage{tikz}
%\usepackage{rotating}

\newcommand{\underconstruction}{%
  \begin{picture}(0,0)
    \color{black}
    \put(6,-2.2){\makebox(0,0)[b]{\includegraphics[width=1.5cm]{Zeichen_123.pdf}}}
    \put(6,-2.5){\makebox(0,0)[t]{\shortstack{Änderungen\\vorbehalten}}}
  \end{picture}}

\title{Algorithmen und Datenstrukturen in C/C++}
\author{Prof.\ Dr.\ rer.\ nat.\ Peter Gerwinski}
\date{18.\ April 2024}

\begin{document}

\maketitleframe

\nosectionnonumber{\inserttitle}

\begin{frame}

  \shownosectionnonumber

  \begin{itemize}
    \item[\textbf{1}] \textbf{Einführung}
      \underconstruction
      \hfill\makebox(0,0)[br]{\raisebox{2.25ex}{\url{https://gitlab.cvh-server.de/pgerwinski/ad}}}
%    \item[\textbf{\color{red}i}] {\color{red}Online-Werkzeuge für Home Office, Lehre\\
%                                             und Kommunikation mit Unterdrückten}
    \item[\textbf{2}] \textbf{Arrays und Zeiger für Fortgeschrittene}
    \item[\textbf{3}] \textbf{Langzahl-Arithmetik}
    \item[\textbf{4}] \textbf{Kryptographie}
    \item[\textbf{5}] \textbf{C++}
    \item[\textbf{6}] \textbf{Datenorganisation}
    \vspace{-\smallskipamount}
    \item[\textbf{\dots}]
  \end{itemize}

\end{frame}

\setcounter{section}{2}
\section{Langzahl-Arithmetik}

\begin{frame}

  \showsection

  Problem: Rechnen mit ganzen Zahlen, die größer sind als das,\\
  was der Rechner normalerweise verarbeiten kann

  \bigskip

  {\large\textbf{Aufgabe: Addition langer Zahlen}\par}
  \smallskip
  \begin{itemize}
    \item[(a)]
      Überlegen Sie sich eine Datenstruktur, um eine lange Zahl zu speichern.
    \item[(b)]
      Schreiben Sie eine Funktion, die zwei lange Zahlen addiert.
  \end{itemize}

  \bigskip

  {\large\textbf{Lösungsansätze}\par}
  \smallskip
  \begin{itemize}
    \item
      ziffernweise (z.\,B.\ Zahlen als Strings abspeichern)
    \item
      zu einer Zehnerpotenz-Basis (z.\,B.\ 1\,000\,000\,000)
    \item
      zu einer Zweierpotenz-Basis (z.\,B.\ $2^{32}$)\\
    \item
      speziell: Registerbreite \textarrow\ Hardware-Unterstützung (in Assembler)
  \end{itemize}

\end{frame}

\begin{frame}

  \showsection

  Problem: Rechnen mit ganzen Zahlen, die größer sind als das,\\
  was der Rechner normalerweise verarbeiten kann

  \medskip

  \begin{itemize}
    \item
      Grundrechenarten (einschließlich "`modulo"'):\\
      "`schriftlich"' rechnen
    \item
      \href{https://de.wikipedia.org/wiki/Binäre_Exponentiation}%
           {binäre Exponentiation}:\\
      Basis fortlaufend quadrieren, ggf.\ damit multiplizieren\\
      Beispiel: $x^9 = ((x^2)^2)^2 \cdot x$
    \item
      Suche nach $d$ mit $d\cdot e~\text{mod}~N = 1$:\\
      \href{https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus}%
           {erweiterter euklidischer Algorithmus}
    \smallskip
    \arrowitem
      RSA
  \end{itemize}

  \bigskip

  {\large\textbf{Aufgabe: RSA effizient implementieren}\par}
  \smallskip
  \begin{itemize}
    \item
      Verwenden Sie den Datentyp \lstinline{uint64_t}
      (oder Langzahl-Arithmetik)
    \item
      Für Details siehe: \file{ad-20240411.txt}
  \end{itemize}

\end{frame}

\section{Kryptographie}
\subsectionnonumber{\boldmath 4.$(x^2 - 1)$\quad Der Herr der Ringe: Manchmal ist $1 + 1 = 0$.}
\subsubsectionnonumber{\boldmath 4.$(x^2 - 1).x$\quad Motivation}

\begin{frame}

  \showsection
%  \pause
  \showsubsectionnonumber
%  \pause
  \showsubsubsectionnonumber

  Man kann auch mit sehr merkwürdigen Objekten\\
  wie mit "`ganz normalen"' Zahlen rechnen.

%  \pause
  \bigskip
  
  Anwendungen:
  \begin{itemize}
    \item Funktionsweise von Computern (\textarrow\ Rechnertechnik)
    \item Fehlererkennung
    \item Fehlerkorrektur
    \item Verschlüsselung
    \item Digitale Signaturen
  \end{itemize}

\end{frame}

\subsubsectionnonumber{\boldmath 4.$(x^2 - 1).(x + 1)$\quad Gruppen}

\begin{frame}

  \showsection
  \showsubsectionnonumber
  \showsubsubsectionnonumber

  \textbf{Definition:}
  Sei $G$ eine Menge, $*$ eine Verknüpfung auf $G$.
  Wenn
  \begin{itemize}
    \item
      $\forall a, b, c \in G$: $(a * b) * c = a * (b * c)$ \quad (Assoziativgesetz),
    \item
      $\exists e \in G$: $\forall a \in G$: $a * e = e * a = a$ \quad (neutrales Element),
    \item
      $\forall a \in G$: $\exists a^{-1} \in G$: $a * a^{-1} = a^{-1} * a = e$ \quad (inverses Element),
  \end{itemize}
  dann heißt $(G,*)$ eine \newterm{Gruppe}.

%  \pause
  \bigskip

  \textbf{Definition:}
  Sei $(G,*)$ eine Gruppe.
  Wenn zusätzlich
  \begin{itemize}
    \item
      $\forall a, b \in G$: $a * b = b * a$ \quad (Kommutativgesetz),
  \end{itemize}
  dann heißt $(G,*)$ eine \newterm{kommutative Gruppe}.

\end{frame}

\subsubsectionnonumber{\boldmath 4.$(x^2 - 1).(x + 2)$\quad Ringe}

\begin{frame}

%  \showsection
  \showsubsectionnonumber
  \showsubsubsectionnonumber

  \textbf{Definition:}
  Sei $R$ eine Menge; seien $+$ und $\cdot$ Verknüpfungen auf $R$.
  Wenn
  \begin{itemize}
    \item
      $(R,+)$ eine kommutative Gruppe ist,
    \item
      $\forall a, b, c \in R$: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ \quad (Assoziativgesetz),
    \item
      $\forall a, b, c \in R$: $(a + b)\cdot c = a\cdot c + b\cdot c$
      und $a\cdot(b + c) = a\cdot b + a\cdot c$ \quad (Distributivgesetze),
  \end{itemize}
  dann heißt $(R,+,\cdot)$ ein \newterm{Ring}.

%  \pause
  \bigskip

  \textbf{Definition:}
  Sei $(R,+,\cdot)$ ein Ring.
  Wenn zusätzlich
  \begin{itemize}
    \item
      $\forall a, b \in R$: $a \cdot b = b \cdot a$ \quad (Kommutativgesetz),
  \end{itemize}
  dann heißt $(R,+,\cdot)$ ein \newterm{kommutativer Ring}.

%  \pause
  \bigskip

  \textbf{Definition:}
  Sei $(R,+,\cdot)$ ein (kommutativer) Ring.
  Wenn zusätzlich
  \begin{itemize}
    \item
      ein $e \in R$ existiert, so daß für alle $a \in R$ gilt: $a \cdot e = e \cdot a = a$\\
      (neutrales Element),
  \end{itemize}
  dann heißt $(R,+,\cdot)$ ein \newterm{(kommutativer) Ring mit 1}.

  \vspace*{-1cm}

\end{frame}

\subsubsectionnonumber{\boldmath 4.$(x^2 - 1).(x + 3)$\quad Körper}

\begin{frame}

%  \showsection
  \showsubsectionnonumber
  \showsubsubsectionnonumber

  \textbf{Definition:}
  Sei $K$ eine Menge; seien $+$ und $\cdot$ Verknüpfungen auf $K$.
  Wenn
  \begin{itemize}
    \item
      $(K,+,\cdot)$ ein Ring mit 1 ist und
    \item
      $(K \backslash \{0\},\cdot)$ eine kommutative Gruppe ist,
  \end{itemize}
  dann heißt $(K,+,\cdot)$ ein \newterm{Körper}.

\end{frame}

\subsubsectionnonumber{\boldmath 4.$(x^2 - 1).(x + 4)$\quad Anwendungen}

\begin{frame}

%  \showsection
  \showsubsectionnonumber
  \showsubsubsectionnonumber

  Man kann auch mit sehr merkwürdigen Objekten\\
  wie mit "`ganz normalen"' Zahlen rechnen.

  \bigskip
  
  \begin{itemize}
    \item
      innermathematisch: Man kann beweisen,\\
      daß es ab $x^5$ keine "`$p$-$q$-Formel"' mehr gibt\\
      und daß bestimmte Operationen mit Zirkel und Lineal unmöglich sind.
    \item
      asymmetrische Verschlüsselung, Signaturen:\\
      RSA, ElGamal\color{gray}, elliptische Kurven
    \item
      symmetrische Verschlüsselung: AES
    \item
      Fehlererkennung: Parität, CRC\\
      Anwendungen: Datenübertragung, RAID
    \item
      Fehlerkorrektur: Reed-Solomon\\
      Anwendungen: Raumsonden, optische Datenträger, ECC-RAM
  \end{itemize}

\end{frame}

\end{document}