\documentclass{uebungsblatt}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Grundlagen Betriebssysteme}
\blatt{13}
\gruppe{22}
\usepackage{listings}
\usepackage{pifont}

\lstset{language=Lisp,breaklines=true,postbreak=\ding{229}}

\begin{document}

\aufgabe

\teilaufgabe

$ n = p \cdot q = 47 \cdot 71 = 3337 $

$ x = (p - 1) \cdot (q - 1) = (47 - 1) \cdot (71 - 1) = 46 \cdot 70 = 3220 $

\teilaufgabe

Der Rechenweg wird durch dieses Scheme-Programm beschrieben:

\lstinputlisting{pseudorsa.scm}

Das Programm nutzt Erweiterungen von PLT Scheme 4 und wurde auf PLT Scheme
4.2.4 getestet. Der Fokus der Implementation lag auf der sauberen, funktionalen
Problemlösung, die Performance ist außer acht gelassen wurden, so sind auch die
rekursiven Funktionen bewusst nicht endrekursiv. Es wurde jedoch geachtet,
keine ``Tricksereien'' zu verwenden, wie etwa die triviale Aufteilung einer der
Nachricht durch das Konvertieren in einen String und das Aufteilen des Strings
in gleich größe Blöcke. Dieser Ansatz ist zwar simpler, vermittelt jedoch den
Eindruck einer unsauberen Lösung.

Um die Nachricht zu verschlüsseln ist folgender Aufruf notwendig:

\begin{lstlisting}
(encrypt message e n)
\end{lstlisting}

Diese Funktion gibt die verschlüsselte Nachricht zurück, im Fall der
Beispielwerte (message = 688"-232"-687"-966"-668"-003 und e = 79) ist dies der
Wert 157"-027"-562"-091"-227"-624"-230"-158.

\teilaufgabe

Es ist lediglich notwendig die Umkehrfunktion zum verschlüsseln aufrufen:

\begin{lstlisting}
(decrypt (encrypt message e n) d n)
\end{lstlisting}

Der Rückgabewert mit den im Blatt angegebenen Werten (d = 1019) beträgt
688"-232"-687"-966"-668"-003, was genau der Eingabenachricht entspricht. Dies
zeigt, dass Roundtrips zumindest mit den getesteten Daten möglich sind.

\end{document}
