Quelltext der Seite Kryptologie - Mathematische Vertiefung (PH Freiburg SS 2017)

<small>''Auf diesen Seiten entsteht gemeinsam mit Studierenden der PH Freiburg eine Sammlung zu Inhalten der Kryptologie, die mathematisch vertieft werden und für den Einsatz im Unterricht der Sekundarstufe I aufbereitet werden. In der Lehrveranstaltung soll der mathematische Horizont, auch über die mit dem Schulcurriculum verbundene Mathematik hinaus erweitert werden. (Dozentin: Dr. Melanie Platz)''<br />
Hilfe für die Bearbeitung des Wikis: [https://de.wikipedia.org/wiki/Hilfe:%C3%9Cbersicht Wikipedia-Hilfe] und für das Einfügen mathematischer Formeln: [https://de.wikipedia.org/wiki/Hilfe:TeX Tex-Hilfe] </small><br />

<br />
Die '''[https://de.wikipedia.org/wiki/Kryptologie Kryptologie]''' lässt sich in die '''[https://de.wikipedia.org/wiki/Kryptographie Kryptographie]''' und die '''[https://de.wikipedia.org/wiki/Kryptoanalyse Kryptoanalyse]''' gliedern.<br />
Die Kryptographie bezeichnet die Wissenschaft der Entwicklung von Kryptosystemen und die Kryptoanalyse die Kunst diese zu brechen.<ref>Beutelspacher, A. "Kryptologie. Eine Einführung in die Wissenschaft vom Verschlüsseln, Verbergen und Verheimlichen [Cryptology. Introduction to the science of encrypting, hiding and concealing]." Springer-Verlag. (2015).</ref><br />
<br />
[[File:Mindmap mit Inhalten der Kryptologie.svg|Mindmap mit Inhalten der Kryptologie|700px]]
<br />
'''Definition: ''' ''Text/ Nachricht''
<math> A </math> ist ein Alphabet.<br />
<math> A^n = A \times A \times ... \times A = \{ (z_1, ..., z_n) \mid \forall k \in \{1,..., n\}: z_k \in A \} </math> ist das <math>n</math>-fache [https://de.wikipedia.org/wiki/Kartesisches_Produkt kartesische Produkt] des Alphabets <math>A</math><br />
<math> A^n </math> sind die Nachrichtentexte der Länge <math> n </math>.<br />
<math> A^+ = \bigcup \limits^\infty_{n=1} A^n </math><br />
<math> A^+ </math> sind alle Nachrichten aus Buchstaben des Alphabets <math> A </math>.<br />
<br />


'''Definition: ''' ''Bijektiver Schlüssel''<br />
<math> A, B </math> sind Alphabete.
<math> f:A\rightarrow B </math> ist eine bijektive Abbildung.<br />
Dann nennt man <math> f </math> einen bijektiven Schlüssel für Nachrichten aus <math> A^+ </math>.<br />


= Bijektivität =
<small>'''Arbeitsauftrag 1 a)''': Was war nochmal „bijektiv“? Erläutern Sie den Begriff mathematisch mit Beispielen und stellen Sie dar, wie Sie den Begriff Schüler*innen der Sekundarstufe I erklären würden.</small><br />
[[File:Bijektivität Mengen.jpg|thumb|Beispiel für eine bijektive Funktion]]
'''Definition: ''' ''Bijektivität''<br />Jedem Element x aus der Wertemenge A wird genau ein Element y aus der Zielmenge B zugeordnet.

Ist eine Abbildung '''surjektiv''' ''(jedem Element x aus der Wertemenge A wird mindestens ein Element y aus der Zielmenge B zugeordnet)'' '''und''' '''injektiv''' ''(jedem Element x aus der Wertemenge wird höchstens ein Element y aus der Zielmenge zugeordnet''), dann ist sie bijektiv.
Bijektive Abbildungen sind immer umkehrbar.<br />
<br />[[File:Bijektivität.png|thumb|Beispiel für eine bijektive Funktion]]<br />

'''Erklärung für Schüler: ''' ''Beispiel aus dem Alltag''<br />
* "In einem Glas befinden sich 25 Bonbons. Die Klasse besteht aus 25 Schülerinnen und Schülern. Jeder Schüler bekommt genau ein Bonbon."<br />''Diese Abbildung ist '''bijektiv''', da ja jeder Schüler '''genau ein''' Bonbon bekommt. Niemand bekommt mehrere Bonbons und auch niemand wird ausgelassen.''<br />
* "Zum Frühstück liebt Familie Maier Brezeln. Jedes Familienmitglied isst immer mindestens eine Brezel. Der Vater isst immer zwei Brezeln und Pit und Anna manchmal auch, wenn sie besonders großen Hunger haben."<br />''Diese Situation ist '''nicht bijektiv''', da nicht jeder genau eine Brezel isst.
* "Jeder Mensch muss einmal sterben"<br />''Diese Situation ist '''bijektiv''', weil wirklich jeder Mensch einmal sterben wird und man stirbt nur einmal.<br />
<br />


'''Definition: ''' ''Abbildung''<br />

Es seien zwei Mengen <math>A,B </math> gegeben. Unter einer Abbildung <math>f </math> von <math>A </math> nach <math>B </math> verstehen wir eine Vorschrift, die jedem Element <math>x \in A </math> genau ein Element <math>y = f (x) \in B </math> zuordnet: <br />
<math>\forall x \in A \exists ! y \in B: y = f (x) </math><br />



'''Definition: ''' ''Injektivität, Surjektivität, Bijektivität''<br />

Es seien A und B Mengen und <math>f:A \rightarrow B</math> eine Abbildung zwischen A und B.<br />
f heißt:<br />
* injektiv<math>:\Leftrightarrow \forall a_1,a_2 \in A: f(a_1)=f(a_2) \rightarrow a_1=a_2</math>.
* surjektiv<math>:\Leftrightarrow \forall b \in B \exists a \in A: f(a)=b</math>.
* bijektiv<math>:\Leftrightarrow f</math> ist injektiv und <math>f</math> ist surjektiv.

= Symmetrische Verschlüsselung =

'''Definition: ''' ''Symmetrische Verschlüsselung''<br />
Sender und Empfänger haben den gleichen Schlüssel.

== Substitutionsalgorithmen ==
Bei einem Substitutionsalgorithmus oder Verschiebechiffre behält jeder Buchstabe seine Position, wird aber durch einen anderen ersetzt.<br />

=== Monoaplhabetische Substitution ===
Als [https://de.wikipedia.org/wiki/Monoalphabetische_Substitution monoalphabetische Substitution] bezeichnet man ein Verschlüsselungsverfahren, bei dem nur ein einziges (festes) Schlüsselalphabet zur Verschlüsselung, also zur Umwandlung des Klartextes in den Geheimtext, verwendet wird. Es gibt genau 26! monoalphabetische Chiffrierungen über dem natürlichen Alphabet <math>\{a, ..., z\}</math>.<br />
Die Caesar-Verschlüsselung ist ein Sonderfall der einfachen monoalphabetischen Substitution.<br />

=== Caesar-Verschlüsselung ===
<small>'''Arbeitsauftrag 1 b):''' Wie Funktioniert die „Caesar-Verschlüsselung“? Erläutern Sie die Funktionsweise, die mathematischen Hintergründe und erstellen Sie mit Hilfe von [https://www.libreoffice.org/discover/calc/ LibreOffice Calc] (oder Microsoft Excel) ein Programm, mit dem das Ver- und Entschlüsseln mittels Caesar-Verschlüsselung möglich ist.</small>
<br />[[File:GraphCapture.png|thumb|Excel Graph der Funktion von Klartext auf Chiffrierter Text]]<br />

Die "Caesar-Verschlüsselung" ist eine Verschlüsselungstechnik, bei dem jeder Buchstabe um die gleiche Zahl verschoben und so einem anderen Buchstaben zugeordnet wird. 
Bei einer Verschiebung v um 3 wird z.B. A zu D chiffriert, B zu E, C zu F, usw. Dabei handelt es sich um eine zyklische Verschiebung, das bedeutet: Bei einer Verschiebung um 3 wird X zu A, Y zu B und Z zu C.
Dabei wird der gesamte Klartext um die gleiche Zahl verschoben. Die Caesar-Verschlüsselung bietet eine begrenzte Anzahl an Verschlüsselungsmöglichkeiten.


'''Mathematischer Hintergrund:''' 
Gegeben ist ein Klartextalphabet <math>A = \{z_1, z_2, ..., z_{|A|}\} </math> und ein Geheimtextalphabet <math>B</math> und es gilt <math>A=B</math>. Die Mächtigkeit <math>|A|</math> ist die Anzahl aller Elemente des Alphabets <math>A</math>. Man nummeriert jedes Element des Alphabets mit den natürlichen Zahlen von <math>0</math> bis <math>|A|-1</math> mit Hilfe folgender Abbildung:<br />
<math>f: A \to \{0, ..., |A|-1\}</math><br />
:: <math>z_1 \mapsto 0</math><br />
:: <math>z_2 \mapsto 1</math><br />
::: <math>\vdots </math><br />
:: <math>z_{|A|} \mapsto |A|-1</math><br />
Bei der Caesar-Verschlüsselung handelt es sich um eine bijektive Abbildung <br />
<math>V: A \rightarrow B </math><br />
:: <math> a \mapsto V(f(a))= (f(a)+k)~mod ~ |A| </math>,<br />
wobei <math> k\in \mathbb{N}, 0\leq k \leq |A|</math> der Schlüssel ist.<br />
Entschlüsselt wird mit der Umkehrabbildung von <math>V, V^{-1} = : E </math>. <br />
<math>E: B \rightarrow A </math><br />
:: <math> b \mapsto E(f(b))=(f(b)-k)~ mod ~ |A| </math>,<br />
wobei k derselbe Schlüssel ist, der zum Verschlüsseln verwendet wurde.<br />

== Transpositionschiffre ==
Bei einer Transpositionschiffre bleiben die Buchstaben was sie sind, aber nicht wo sie sind. Es handelt sich um eine Permutation der Stellen des Klartextes.<br />

=== Skytala-Verschlüsselung ===
<small>'''Arbeitsauftrag 1 c):''' Wie Funktioniert die „Skytala-Verschlüsselung“? Erläutern Sie die Funktionsweise,
die mathematischen Hintergründe und erstellen Sie mit Hilfe von [https://www.libreoffice.org/discover/calc/ LibreOffice Calc] (oder
Microsoft Excel) ein Programm, mit dem das Ver- und Entschlüsseln mittels Skytala-
Verschlüsselung möglich ist.</small>

Bei der Entschlüsselung einer Skytala-Verschlüsselung wird ein horizontal beschrifteter Textstreifen um einen Stab gewickelt. Dadurch wird der codiert aufgeschriebene Text wieder lesbar.
Bei der Verschlüsselung wird die Skytala-Verschlüsselung variiert mit dem Durchmessers des verwendeten Stabes. Die Abstände im resultierenden Textband, zwischen zwei Zeichen aus dem zu verschlüssenden Text, sind direkt abhängig vom verwendeten Stab. Diese Abstände bleiben im kompletten Textband gleich.
Zeilenweise lässt sich dann auf dem Stab der ursprüngliche Text wieder lesen.<br />

'''Mathematischer Hintergrund:''' Gegeben ist ein Klartext mit der Textlänge <math>t</math>. Die Positionen der Buchstaben sind bei Transpositionschiffren wichtig, die Positionen im Klartext stammen aus der Menge <math>P := \{1,..., t\}</math> und sind folgendermaßen nummeriert: <math>(1, 2, ... t)</math>. Sei nun <math>u</math> der Umfang des Stabs, der durch die Anzahl der Zeilen des Geheimtextes bestimmt wird und <math>l</math> die Länge der Nachricht, wenn sie um den Stab gewickelt ist, die durch die Anzahl der Spalten des Geheimtextes bestimmt wird. Es gilt <math>t=l\cdot u</math> Dann wird durch folgende Abbildung verschlüsselt:<br />
<math>V: P \to P </math><br />
::<math>p\mapsto
\begin{cases}
(p-1)l+1,\ \ falls\ 0<p\leq u,\\
(p-u-1)l+2,\ falls\ u<p\leq 2u,\\
\vdots\\
(p-(l-1)u-1)l+l,\ falls\ (l-1)u<p\leq lu.
\end{cases}
</math><br />
Entschlüsselt wird wiederum mit der Umkehrabbildung <math>V^{-1}</math>.<br />

=== Gartenzaun-Chiffre ===

<small>'''Arbeitsauftrag 1 d):''' Wie Funktioniert die „Gartenzaun-Verschlüsselung“? Erläutern Sie die Funktionsweise,
die mathematischen Hintergründe und erstellen Sie mit Hilfe von [https://www.libreoffice.org/discover/calc/ LibreOffice Calc] (oder
Microsoft Excel) ein Programm, mit dem das Ver- und Entschlüsseln mittels Gartenzaun-Verschlüsselung möglich ist.</small>

Auch bei der Gartenzaunchiffre ist das Ziel, einen Klartext in eine Geheimbotschaft umzuwandeln, die mit einem Schlüssel wieder dechiffriert werden kann.

'''Verschlüsselung'''
[[File:Abbildung Gartenzaunchiffre.png|thumb|Abbildung Gartenzaunchiffre]]
Bei der Verschlüsselung wird mithilfe dieser Methode der Klartext in einem Zickzack-Muster aufgeschrieben (siehe Abb.). Dabei sind folgende Kriterien entscheidend:
* Die Höhe des Gartenzauns, diese entspricht der Anzahl der Zeilen des Zickzack-Musters
* Der Beginn des Gartenzauns->Es ist möglich, dass der Gartenzaun nicht auf der obersten Stufe beginnt
* Die Richtung des Gartenzaunes->Der Gartenzaun kann von rechts nach links bzw. auch von links nach rechts aufgestellt werden.
* Zusätzlich können die Stufen beim weiteren Verschlüsseln vertauscht werden.
Zuerst bestimmt der Verschlüssler die Höhe des Gartenzauns und schreibt den Klartext in dem Zickzack-Muster auf. Dabei überlegt er sich, in welcher Zeile er beginnt und in welcher Richtung er das Zickzack-Muster notiert. Um die Methode noch sicherer zu machen, vertauscht er die Zeilen, wenn er die Buchstaben aus dem Zickzack-Muster zeilenweise abschreibt. Er beginnt dann nicht mit der ersten, sondern z. B. mit der dritten Zeile und schreibt die Buchstaben hintereinander gesondert auf, dann folgt die erste Zeile usw.
Damit der Entschlüssler weiß, welche dieser Kriterien der Verschlüssler benutzt hat, braucht dieser einen separaten Schlüssel, den ihm der Verschlüssler zusätzlich mitteilen muss.
[[File:Schlüssel2.png|center|Schlüsselerzeugung:]]
'''Entschlüsselung'''

Für die Entschlüsselung ist es wichtig, dass die Person, die die Nachricht entschlüsseln möchte bzw. für die die Geheimbotschaft bestimmt ist, über den vom Verschlüssler individuell gesetzten Schlüssel Bescheid weiß.
Die Vorgehensweise kann bei der Entschlüsselung unterschiedlich verlaufen. Wird davon ausgegangen, dass der oben in der Abbildung veranschaulichte Schlüssel gewählt wurde, bietet es sich beispielsweise an folgendermaßen beim Entschlüsseln vorzugehen:

1.	Es werden die einzelnen Zeilen je nach Zeilenhöhe des Gartenzauns untereinander nummeriert.

2.	Unter jeden Buchstaben des Worts in der dritten Spalte werden Ziffern je nach alphabetischer Reihenfolge der Buchstaben unter die einzelnen Buchstaben des Worts (hier: APFEL) geschrieben.

3.	Mithilfe der zweiten sowie der letzten Spalte ist es nun möglich, den Beginn des ersten Buchstabens der Botschaft zu ermitteln.

4.	Je nach Verlauf des Zickzack-Musters, welches sich aus der ersten Spalte ablesen lässt, kann nun die Nachricht unter Beachtung der vertauschten Stufen im Zickzack-Muster über die Stufen verteilt von links nach rechts aufgeschrieben werden.<br />


'''Mathematischer Hintergrund:''' Gegeben ist ein Klartext mit der Textlänge <math>t</math>. Die Positionen der Buchstaben sind bei Transpositionschiffren wichtig, die Positionen im Klartext stammen aus der Menge <math>P := \{1,..., t\}</math> und sind folgendermaßen nummeriert (wir legen fest, dass unser Gartenzaun mit variabler Höhe <math>h</math> und Anzahl der Spitzen <math>m</math> und Täler <math>m-1</math> mit <math>h,m \in \N</math> stets folgende Form hat):
[[File:Gartenzaunchiffre.jpg|center|Form des Gartenzauns]]<br />
Dann wird durch folgende Abbildung verschlüsselt:<br />
<math>V: P \to P </math><br />
::<math>p\mapsto
\begin{cases}
2(p-1)h-(2(p-1)-1),\ \ falls\ 0<p\leq m,\\
\vdots\\
(2(p-1)-1)h-(2(p-1)-2),\ falls\ m+(h-2)(m-1)<p\leq m(h-2)(m-1)+(m-1).
\end{cases}
</math><br />
Entschlüsselt wird wiederum mit der Umkehrabbildung <math>V^{-1}</math>.<br />

== Kryptoanalyse ==

=== Systematische Schlüsselsuche ===
Jeder Verschlüsselungsalgorithmus kann durch eine systematische Anwendung möglicher Schlüssel auf den Geheimtext gebrochen werden. Bei einer Anzahl von <math> k </math> möglichen Schlüsseln, benötigt man höchstens <math> k </math> Versuche, durchschnittlich allerdings nur <math> \frac{k}{2} </math> Versuche. Je größer die Anzahl der möglichen Schlüssel, umso schwerer ist ein Verschlüsselungsalgorithmus zu knacken.<br />


=== Statistische Analyse ===
Die Statistische Analyse kann bei Substitutionsalgorithmen angewendet werden.
Durch die Bestimmung der relativen Häufigkeiten der Buchstaben eines Geheimtextes (z.B. mit Hilfe eines [https://jumk.de/wortanalyse/ Applets zum Buchstabenzählen]), können diese mit der [https://de.wikipedia.org/wiki/Buchstabenh%C3%A4ufigkeit Häufigkeit der Buchstaben der deutschen Sprache] abgeglichen werden und entsprechend ersetzt werden.<br />

== Unterrichtsplanung ==

<small>'''Arbeitsauftrag 1 e):''' Wie würden Sie Caesar-Verschlüsselung, Skytala-Verschlüsselung und Gartenzaun-
Chiffre im Schulunterricht umsetzen? Erstellen Sie einen Unterrichtsentwurf für die Sekundarstufe I.</small><br />

Der Unterricht teilt sich ein in 3 Einheiten:<br /> Einleitung (5 min),<br />Hauptteil (25 min)<br />und Schluss (15 min).

In der '''Einleitung''' wird die Problemstellung (Verschlüsselung der Nachricht von Caesar) thematisiert und zusammen mit der Klasse werden die Verschlüsselungstechniken durch das Sammeln von Ideen erarbeitet.<br /> Im '''Hauptteil''' bearbeiten die Schüler und Schülerinnen einen Text, den sie selbst entschlüsseln müssen. Dieser beinhaltet 3 Verschlüsselungstechniken: Ceasar-, Skytala-Verschlüsselung und Gartenzaun-Chiffre. Dabei variieren die Bedingungen während der Bearbeitung. Die Caeser-Verschlüsselung kann durch eine Drehplatte mit zwei Buchstabenreihen veranschaulicht werden. Bei der Skytala-Verschlüsselung können die Radien der Rohre verändert werden, um die Komplexität des Entschlüsselns hervorzuheben. Die Gartenzaun-Chiffre lässt sich durch die Höhe des "Zauns" verändern.<br /> Im '''Schluss''' geht es um die Anwendung der Entschlüsselungsmethode, indem die Schüler und Schülerinnen einen Textentwurf an den Sitznachbar anfertigen. Anschließend folgt eine Diskussion über den Zweck und Nutzen einer Verschlüsselung.

== Polyalphabetische Verschlüsselung ==

=== Verschlüsseln mit Zufallsexperimenten ===

<br />
'''Beispiel: ''' <br />
Gegeben sei das Klartextalphabet <math> A := \{A, N, S\} </math> und der Klartext <math>\omega=(A,N,A,N,A,S)\in A^+</math>.<br />
Das Häufigkeitsprofil dieses Textes sieht folgendermaßen aus:<br />

{| class = wikitabelle
|-
! Buchstabe !! Häufigkeit
|-
| A || <math> \frac{3}{6} = \frac{1}{2} </math>
|-
| N || <math> \frac{2}{6} = \frac{1}{3}</math>
|-
| S || <math> \frac{1}{6} </math>
|}<br />

'''Ziel:''' Jeder Buchstabe im Geheimtext soll mit der gleichen Häufigkeit vorkommen, sodass eine Kryptoanalyse über das Sprachprofil nicht möglich ist.<br />

Sei nun das Geheimtextalphabet <math> B:= \{1,2,3, ... , 12\} </math> und der Schlüssel zur Verschlüsselung des Klartextes sei folgendermaßen definiert:
{| class = wikitabelle
|-
! Klartextbuchstabe !! Menge der zugeordneten Geheimtextbuchstaben !! Anzahl der zugeordneten Geheimalphabetbuchstaben !! Anteil
|-
| A || <math> \{1, 3, 8, 9, 11, 12\} =\Omega_A  </math> || <math> 6  =|\Omega_A|  </math>  || <math>\frac{|\Omega_A|}{|B|}=\frac{6}{12} =  \frac{1}{2}</math>
|-
| N || <math> \{2, 5, 7, 10\} =\Omega_N   </math> ||  <math> 4  =|\Omega_N|  </math> ||  <math> \frac{|\Omega_N|}{|B|}=\frac{4}{12} =  \frac{1}{3}</math>
|-
| S || <math> \{4, 6\}=\Omega_S </math> || <math> 2  =|\Omega_S|  </math> || <math> \frac{|\Omega_S|}{|B|}=\frac{2}{12} =  \frac{1}{6}</math>
|}<br />

Um den Klartext zu verschlüsseln, werden Zufallsexperimente verwendet, um jeweils einen der jeweils zugeordneten Geheimtextbuchtaben zufällig auszuwählen.<br />
Zur Verschlüsselung des Buchtabens "A" benötigen wir ein Zufallsexperiment, bei dem jedes Ereignis mit der Wahrscheinlichkeit <math> \frac{1}{6} </math> eintritt, sodass jeder der 6 Geheimtextbuchstaben mit der gleichen Wahrscheinlichkeit ausgewählt werden könnte. Als Zufallsgenerator könnte ein Würfel gewählt werden und zeigt der Würfel beispielsweise die Augenzahl 1, wird beispielsweise der Geheimtextbuchstabe "1" zugeordnet, bei einer 2 wird der Geheimtextbuchstabe "3" zugeordnet usw.<br />
Zur Verschlüsselung des Buchtabens "N" benötigen wir ein Zufallsexperiment, bei dem jedes Ereignis mit der Wahrscheinlichkeit <math> \frac{1}{4} </math> eintritt, sodass jeder der 4 Geheimtextbuchstaben mit der gleichen Wahrscheinlichkeit ausgewählt werden könnte. Als Zufallsgenerator könnte blind aus einer Urne mit 4 Kugeln gezogen werden, die mir den Ziffern "2", "5", "7" und "10" beschriftet sind.<br />
Zur Verschlüsselung des Buchtabens "S" benötigen wir ein Zufallsexperiment, bei dem jedes Ereignis mit der Wahrscheinlichkeit <math> \frac{1}{2} </math> eintritt, sodass jeder der 2 Geheimtextbuchstaben mit der gleichen Wahrscheinlichkeit ausgewählt werden könnte. Als Zufallsgenerator könnte eine faire Münze gewählt werden, bei Kopf könnte der Geheimtextbuchstabe "4", bei Zahl der Geheimtextbuchstabe "6" gewählt werden.<br />
Wird auf diese Weise verschlüsselt, kommt jeder Buchstabe aus B im Geheimtext mit einer Häufigkeit von etwa <math> \frac{1}{12} </math> vor.
<br />
<br />


'''Definition: ''' ''σ-Algebra''<br />
Sei <math> \Omega </math> eine nichtleere Menge und sei <math> \mathcal P(\Omega) </math> die Potenzmenge dieser Menge.

Ein Mengensystem <math> \mathcal S \subset \mathcal P(\Omega) </math>, also eine Menge von Teilmengen von <math> \Omega </math>, heißt σ-Algebra (auf oder über <math> \Omega </math>), wenn es die folgenden drei Bedingungen erfüllt:

* (1) <math> \mathcal S </math> enthält die Grundmenge. Es gilt also <math> \Omega \in \mathcal S </math>
* (2) <math> \mathcal S </math> ist stabil bezüglich der Komplementbildung. Ist also <math> S \in \mathcal S </math>, so ist auch <math>S^{\mathsf c} = \Omega\setminus S</math> in <math> \mathcal S </math> enthalten.
* (3) <math> \mathcal S </math> ist stabil bezüglich abzählbarenVereinigungen. Sind also Mengen
::<math> S_1, S_2, S_3, \dots </math> in <math> \mathcal S </math> enthalten, so ist auch <math> \bigcup_{i=1}^\infty S_i </math> in <math> \mathcal S </math> enthalten.<br />
<br />

'''Ziel:''' Man möchte nicht nur einzelnen Buchstaben <math> \omega \in \Omega </math> eine Wahrscheinlichkeit zuordnen, sondern auch Teilmengen des Alphabets.<br />
<br />
'''Beispiele:''' Bei folgenden Mengen handelt es sich um σ-Algebren:
* <math> \{\emptyset, \Omega\} </math>
* <math> \{\emptyset, A, A^C, \Omega\} </math>
* <math> \{\emptyset, \R, [0,1], (-\infty, 0)\cup (1,\infty)\} </math>
<br />


'''Definition: ''' ''Wahrscheinlichkeitsraum <math> (\Omega, \mathcal S, P) </math>''<br />
Sei <math>\Omega</math> (ein Alphabet) eine nichtleere Menge und <math> \mathcal S </math> eine σ-Algebra über <math>\Omega</math>.<br />
Ferner gibt es eine Abbildung <math>P</math> mit 

* (1) <math>P \colon \mathcal S \to [0,1]</math>
:::<math>E \mapsto P(E)</math>.
::<math>P</math> ordnet jeder Menge <math>E \in \mathcal S </math> einen Wahrscheinlichkeitswert zu.
* (2) <math>P(\Omega) = 1</math>. Die Wahrscheinlichkeit, dass ein Buchstabe aus dem Alphabet <math> \Omega </math> stammt, ist 1.
* (3) <math> \forall E_n \in \mathcal S, n \in \N: E_n </math> paarweise disjunkt <math> \Rightarrow P(\bigcup_{n\in\N} E_n)=\sum\limits_{n\in\N}P(E_n) </math><br />
<br />


'''Beispiel:''' Münzwurf (einfaches Werfen mit einer fairen Münze).<br />
<math>\Omega = \{K,Z\}, \mathcal{S} =\{ \emptyset, \{K\}, \{Z\}, \{K,Z\}\}</math><br />
Es gilt:
* (1) <math>P \colon \mathcal S \to [0,1]</math>
::::<math>\emptyset \mapsto 0</math><br />
:::<math>\{K\} \mapsto \frac{1}{2}</math><br />
:::<math>\{Z\} \mapsto \frac{1}{2}</math><br />
::<math>\{K, Z\} \mapsto 1 </math><br />
* (2) <math>P(\{K, Z\}) = 1 </math>
* (3) Es gilt: <math>\{K\}</math> und <math>\{Z\}</math> p.w.d. <math> \Rightarrow P(\{K\}\cup \{Z\})=P(\{K,Z\}) = 1 = \frac{1}{2} + \frac{1}{2} = P(\{K\}) + P(\{Z\}) </math>
<br />

'''Definition: ''' ''Trägermenge, Wahrscheinlichkeitsverteilung''<br />
Sei <math> (\Omega, \mathcal S, P) </math> ein diskreter Wahrscheinlichkeitsraum, dann definiert man den Träger <math> Tr(P) </math> wie folgt: <math> Tr(P):=\{\omega\in\Omega\mid P(\{\omega\})>0\} </math>.<br />
<br />


'''Beispiel:''' Münzwurf (einfaches Werfen mit einer fairen Münze).<br />
Sei <math>\Omega = \{K,Z,R\}</math> mit <math> P(R) = 0 </math>, R: Rand der Münze.
Dann ist <math> Tr(P) =\{K,Z\} </math>.<br />


'''Satz: ''' ''Träger und Geheimtexte''<br />
Sei <math>A</math> das Klartextalphabet und <math>B</math> das Geheimtextalphabet. 
Ferner sei ein stochastischer Schlüssel<br />
<math>f \colon A \to_{P} B</math>
:<math> x \mapsto_{P} (\Omega_x, \mathcal S_x, P_x)</math><br />
gegeben, dann sind alle Geheimtexte aus der Menge <math>\Omega^+</math> mit <math>\Omega=\bigcup_{x\in A}Tr(P_x)</math>.

'''Beweis: ''' ''Träger und Geheimtexte''<br />
Dem Satz entnehmen wir, <math>A</math> ist das Klartextalphabet und <math>B</math> das Geheimtextalphabet.<br />
Es gilt:<br />
* (1) <math>\forall x \in A : y \in B \land f(x)=y \land P_x(\{y\}) > 0 </math> für die Abbildung <math>P_x</math> <br/>
* (2) Für den Klartext gilt:<br />
:<math> \omega = (\omega_1, \omega_2, ..., \omega_n) \in A^+ </math>
* (3) Für den Chiffretext gilt:<br />
:<math> (f(\omega_1), f(\omega_2), ..., f(\omega_n)) \in B^+ </math> mit <math> y_1 = f(\omega_1), y_2 = f(\omega_2), ..., y_n=f(\omega_n) </math>
* (4) Für die Trägermenge gilt:<br />
:<math> y_1 \in Tr(P_{\omega_1}) \land y_2 \in Tr(P_{\omega_2}) ,..., \land y_\omega \in Tr(P_{\omega_n}) </math>
* (5) Daraus Folgt:<br />
::<math>\Rightarrow \forall k \in \{1,2,3,...,n\} : y_k \in Tr(P_{\omega_k})</math> <br/>
::<math>\Rightarrow \forall k \in \{1,2,3,...,n\} : y_k \in \bigcup\limits_{i=1}^{n}Tr(P_{\omega_i})</math> <br/>
::<math>\Rightarrow \forall k \in \{1,2,3,...,n\} : y_k \in \Omega </math> <br/>
::<math>\Rightarrow y = (y_1, y_2, y_3,..., y_n) \in \Omega^{+} </math> <br/>
::::::::::::::::::''q.e.d.''

'''Satz: ''' ''Eindeutigkeit der Entschlüsselung mit stochastischen Schlüsseln''<br />
Sei <math>A</math> das Klartextalphabet und <math>B</math> das Geheimtextalphabet und <br />
<math>f \colon A \to_{P} B</math>
:<math> x \mapsto_{P} (\Omega_x, \mathcal S_x, P_x).</math><br />
* (1) Die Dechiffrierung ist genau dann eindeutig, wenn die Trägermenge <math> Tr(P_x) </math> für alle <math> x\in A </math> paarweise disjunkt sind.
* (2) Gilt die Bedingung (1), existiert eine Abbildung
::<math>f^{-1} \colon \Omega \to A</math>
:::<math> x \mapsto f^{-1}(x)</math><br />
:: mit <math>\Omega:=\bigcup\limits_{x\in A}Tr(P_x)</math> für die Entschlüsselung von Geheimtexten <math>y=(y_1,...,y_n)\in B^+</math>, die mit <math>f</math> verschlüsselt werden.<br />

'''Bew:''' ''Eindeutigkeit der Entschlüsselung mit stochastischen Schlüsseln''<br />
(1) Die erste Aussage ist eine genau dann Aussauge. Zunächst beweisen wir die Rückrichtung und danach die Hinrichtung.<br />

"<math> \Leftarrow </math>" Seien für alle <math> x\in A </math> die Trägermengen <math> Tr(P_x) </math> paarweise disjunkt. <br />
:Aus dem Satz für Träger und Geheimtexte folgt <br />
::<math> \forall y=(y_1,...,y_n) \in B^+ : y \in \Omega^+ </math> mit <math> \Omega^+= \bigcup\limits_{x\in A}Tr(P_x) </math> <br />
::<math> \Rightarrow \forall y_k, k\in\{1,...,n\}~\exists!~Tr(P_{x_k}):y_k\in Tr(P_{x_k}) </math> <br />
::<math> \Rightarrow \forall y_k\in\{1,...,n\}: y_k\in\Omega_{x_k} </math> <br />
::<math> \Rightarrow </math> Das Klartextzeichen zu <math> y_k </math> ist <math> x_k </math> <br />
:Durch den stochastischen Schlüssel entsteht für jedes Klartextzeichen <math> x_k </math> der Wahrscheinlichkeitsraum <math> (\Omega_{x_k},S_{x_k},P_{x_k}) </math>. <br />

"<math> \Rightarrow </math>" Sei die Entschlüsselung eindeutig. <br /> 
:Wir nehmen nun an, dass die Trägermengen <math> Tr(P_x) </math> nicht paarweise disjunkt sind und zeigen, dass dies zum Widerspruch führt. <br />
::<math> \Rightarrow\exists y\in B,~\exists x_1,x_2\in A~:~y\in Tr(P_{x_1})\cap Tr(P_{x_2})\neq\emptyset </math> <br />
::<math> \Rightarrow y\in Tr(P_{x_1}) \land y\in Tr(P_{x_2})</math> <br />
:Damit ist das <math> y </math> durch Verschlüsselung mit <math> (\Omega_{x_1},S_{x_1},P_{x_1}) </math> und <math> (\Omega_{x_2},S_{x_2},P_{x_2}) </math> entstanden. <br />
:Es ist also nicht möglich dem <math> y </math> eindeutig ein <math> x\in B </math> zuzuordnen.<br />
<br />
(2) Für die zweite Aussage zeigen wir nun, dass so eine Abbildung <math> f^{-1} </math> (die jedem verschlüsselten <math> y\in B </math> wieder ein eindeutiges Klartextzeichen <br /> 
<math> x\in A </math> zuordnet) existiert, falls Bedingung (1) erfüllt ist. <br />

:Seien für alle <math> x\in A </math> die Trägermengen <math> Tr(P_x) </math> paarweise disjunkt und <math> \Omega := \bigcup\limits{x\in A}Tr(P_x) </math>. <br /> 
:<math> \Rightarrow \forall y\in\Omega ~\exists! ~x\in A~:~y\in Tr(P_x) </math> <br />
:Definiere also<br />
:<math> f^{-1}:\Omega\rightarrow A,~y\rightarrow x,~</math>falls<math>~y\in Tr(P_x)</math> <br />
:::::::::::::::::::::<math> \Box </math> <br />

== Verschlüsselung beliebiger digitaler Daten ==

[Verwendung von [https://www.gnu.org/software/octave/ GNU Octave].]<br />


'''Definition:''' ''p-adisches Stellenwertsystem''<br />

Sei <math>z\in\N_0</math> gegeben. <br />
<math> z </math> besitzt in dem <math>p</math>-adischen Stellenwertsystem die Darstellung <math>(z_n, z_{n-1}, ... , z_1, z_0)_p</math>, wenn gilt: <math> z_n, z_{n-1}, ... , z_1, z_0 \in \{0,1, ..., p-1\}</math>.<br />
<math>z = \sum\limits_{k=0}^\infty z_k\cdot p^k</math> mit <math> z_k\in\{0,1, ..., p-1\}</math>.<br />


'''Beispiel:''' ''Umrechnung von <math> 43210_5 </math> in das Dezimalsystem''<br />

Jede Stelle hat den Wert der entsprechenden Fünferpotenz. Die der ersten Ziffer von rechts entsprechende Potenz ist <math> 5^0 = 1 </math>.<br />
'''Vorgehen''': Multipliziere jede Ziffer mit der entsprechenden Potenz und summiere. Gehe am besten von rechts nach links vor:<br />
:<math> 0 \cdot 5^0 + 1 \cdot 5^1 + 2 \cdot 5^2 + 3 \cdot 5^3 + 4 \cdot 5^4 </math><br />
<math>= 0 \cdot 1 + 1 \cdot 5 + 2 \cdot 25 + 3 \cdot 125 + 4 \cdot 625</math><br />
<math>= 0 + 5 +50 + 375 + 2500</math><br />
<math>= 2930</math><br />
Ergebnis: <math>43210_5 = 2930_{10}</math><br />


'''Beispiel:''' ''Umrechnung von <math> 375_{10} </math> in das Binärsystem''<br />

'''Vorgehen''': (1) Teile die Zahl mit Rest durch die Basis 2. (2) Der Divistionsrest ist die Ziffer im Binärsystem (von rechts nach links). (3) Falls der (ganzzahlige) Quotient 0 ist, ist das Verfahren beendet, ansonsten nimm den (ganzzahligen) Quotienten als neue Zahl und wiederhole ab (1).<br />
<math> 375 : 2 = 187\ Rest\ 1 </math><br />
<math> 187 : 2 = 93\ \ Rest\ 1 </math><br />
<math> \ 93 : 2 = 46\ \ Rest\ 1</math><br />
<math> \ 46 : 2 = 23\ \ Rest\ 0</math><br />
<math> \ 23 : 2 = 11\ \ Rest\ 1</math><br />
<math> \ 11 : 2 = 5\ \ \ Rest\ 1</math><br />
<math> \ \ 5 : 2 = 2\ \ \ Rest\ 1</math><br />
<math> \ \ 2 : 2 = 1\ \ \ Rest\ 0</math><br />
<math> \ \ 1 : 2 = 0\ \ \ Rest\ 1</math><br />
Ergebnis: <math>375_{10} = 101110111_2</math><br />


'''Nebenbei:'''<br />
- ''There are only 10 types of people in the world: those who understand binary, and those who don't.'' - <br />
- ''Why do mathematicians confuse Halloween and Christmas? - Because 31 Oct = 25 Dec.'' - <br />



'''Definition:''' ''Kodierung reeller Zahlen im p-adischen Stellenwertsystem''<br />

Sei <math>z\in\R^+</math> gegeben. <br />
<math>(z_n, z_{n-1}, ... , z_1, z_0, z_{-1}, z_{-2}, ...)_p</math> stellt die Zahl <math> z </math> wie folgt dar: <br />
<math>z = \sum\limits_{k=-\infty}^n z_k\cdot p^k</math> mit <math> z_k\in\{0,1, ..., p-1\}</math>.<br />


=== Verschlüsseln von digitalen Bytefolgen ===

==== Bilder ====

Graustufen werden durch Werte zwischen 0 und 255 kodiert. Farben können analog durch 24 bit dargestellt werden.<br />


[[File:Bildverschlüsselung.jpg|center|Beispiel zur Verschlüsselung digitaler Daten: Bildverschlüsselung]]

==== Texte ====

Die Zuordnung von Buchstaben und Sonderzeichen (Alphabet <math> B </math>) nach <math> \tilde{A} </math> erfolgt über eine bijektive Abbildung (Schlüssel):<br />
<math> f: B \rightarrow \tilde{A} </math><br />
::<math>  z \mapsto f(z)  </math><br />
Bei diesem bijektiven Schlüssel geht es nicht um Geheimhaltung, sondern um Standardisierung.<br />
Beispiel: [https://de.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange ASCII]-Code.<br />

==== Audio ====

'''Definition:''' ''Digitalisierung eines Audiosignals''<br />

Sei <math> f:[a,b] \rightarrow [c,d] </math> ein analoges Audiosignal und <math> (x_1, ... , x_n)</math> eine äquidistante Unterteilung von <math> [a,b]</math> mit <math>x_1=a </math> und <math> x_n=b </math>. <br />
<math> (f(x_1), ..., f(x_n))\in [c,d]^n</math><br />
Ferner sei <math> (y_1, ... , y_n)</math> eine äquidistante Unterteilung von <math> [c,d]</math> mit <math> f(x_1), ..., f(x_n)\in \{y_1, ..., y_n\}</math>.<br />


==== Videos ====

Video entsteht aus einer Folge von Einzelbildern und einem Audiosignal.


==== Integrität von Daten ====

'''Ziel:''' Nachricht von Sender A an B zu übermitteln und B möchte sicher sein, dass die Daten nicht verändert wurden.<br />
<br />

'''Überprüfung über die Quersumme - Übermittlung mit digitaler Unterschrift'''<br />
<br />

'''Definition:''' ''Gewichtete Quersumme''<br />

Sei <math> a= (a_1, ..., a_n) \in \N_0^n</math> ein Tupel aus natürlichen Zahlen. <math> r= (r_1, ..., r_n) \in \R^n</math>.<br />
<math> \sum\limits_{k=1}^{n} a_k\cdot r_k = a \cdot r^T = (a_1, ..., a_n) \cdot \left(\begin{smallmatrix} r_1\\\vdots\\r_n \end{smallmatrix}\right)</math> nennt man gewichtete Quersumme mit <math> r \in \R^n</math>.<br />
<br />

'''Ziel:''' Durch die gewichtete Quersumme kann man die Restklasse bei der Division durch n bestimmen. Die Restklasse ist eine digitale Unterschrift der p-adischen Zahlenfolge.<br />
<br />

'''Definition:''' ''Gewichtete Quersumme für Restklassen''<br />

Sei <math> (z_n, ..., z_0) \in (0, ... , p-1)^{n+1}</math> sei eine Ziffernfolge im p-adischen System. <math> r_n:= p^n \mod m </math> mit <math> r_n\in \{0,...,m-1\} </math>.<br />
<math> \tilde{r} = \sum\limits_{k=0}^{n} r_k\cdot z_k \mod m</math> mit <math> \tilde{r}\in \{0,...,n-1\} </math>.<br />
<math> \sum\limits_{k=0}^{n} r_k\cdot z_k</math> ist die gewichtete Quersumme bei Division durch <math>m</math>. <br />
<math> \tilde{r}</math> ist die digitale Unterschrift für <math>(z_n, ..., z_0)</math> mit Schlüssel <math>m\in \N, m > 1</math>.<br />
Die Gewichte der Quersumme sind periodisch.<br />


'''Satz:''' ''Perioden in Quersummenregeln''<br />

Sei <math> r:= (r_k)_{k\in\N}\in \{0,...,m-1\}^{\N_0}</math>.<br />
<math> r_k \equiv p^k \mod m </math> (Rest, den die Bündelungseinheit <math> p^k </math> bei Division durch <math> m </math> lässt.)<br />
Dann gibt es ab einer bestimmten Indexschranke eine Periode in der Folge der <math> r_k </math>.<br />


'''Beweis:''' ''Perioden in Quersummenregeln''<br />
Seien <math> r_0, r_1, ..., r_{m-1}</math> die ersten m Reste aus <math> (r_k)_{k\in\N_0}</math>.<br />
''Bei der Division durch m muss mindestens bei m+1 ein Rest doppelt auftreten, da die Anzahl der Reste endlich ist. Reste <math> ({0,1,...,m-1})</math>.''<br />
Ohne Einschränkung gelte: <math> r_m = r_i </math>. mit <math> \displaystyle{i}\in \{0,...,m-1\} </math>.<br /> ''(Wir gehen einfach davon aus, dass dieser Rest doppelt vorkommt.)''<br/>

<math> r_0, r_1,..., r_i, r_{i+1},..., r_{m-1}, r_m, r_{m+1},... </math>.<br />
<math> r_{i+1} \equiv p^{i+1} \equiv p^i \cdot p^i \equiv r_i \cdot p^1 \equiv r_m \cdot p^1 \equiv p^m \cdot p^1 \equiv p^{m+1} \equiv r_{m+1} \mod m </math>. <br />

Man erhält mit <math> r_{i+1}=r_{m+1} </math> auch <math> r_{i+2}= r_{m+2} </math>.<br />

<math> r_{i+2} \equiv p^{i+2} \equiv p^{i+1} \cdot p^1 \equiv r_{i+1} \cdot p^1 \equiv r_{m+1} \cdot p^1 \equiv p^{m+1} \cdot p^1 \equiv p^{m+2} \equiv r_{m+2} \mod m </math>. <br />

Man erhält sukzessiv:<br />
<math> r_0, r_1, ..., r_i, r_{i+1}, ..., r_{m-1}, r_m, r_{m+1}, ..., r_{2m-1}, r_{2m}, ...</math>. <br />
<math> r_{i+k} \equiv r_{m+k} </math> für alle <math> {k\in\N_0}</math>.<br />

Damit haben wir eine Periode der Länge <math> l\leq m-i </math>.<br />
q.e.d.

= Asymmetrische Verschlüsselung =

'''Definition:''' ''Public-Key-Kryptosystem oder Asymmetrisches Kryptosystem''<br />

In einem Public-Key-Kryptosystem hat jeder Teilnehmer <math> T </math> ein Paar von Schlüsseln:
* einen öffentlichen Schlüssel <math> E:=E_T </math> zur Verschlüsselung und 
* einen privaten Schlüssel <math> D:=D_T </math> zum Entschlüsseln,
die sich durch folgende entscheidende Public-Key-Eigenschaft auszeichnen:<br>
Aus der Kenntnis des öffentlichen Schlüssels <math> E_T </math> ist der private Schlüssel <math> D_T </math> nicht zu erschließen.<br>
<br>


'''Definition:''' ''Public-Key-Verschlüsselungssystem''<br />

Ein asymmetrisches Kryptosystem heißt Public-Key-Verschlüsselungssystem (asymmetrisches Verschlüsselungssystem), falls für jede Nachricht <math> m </math> gilt:<br>
Wenn <math> c=E(m) </math> ist, dann gilt <math> D(c) = m </math>, d.h. <math> D(E(m)) = c </math>.<br>
Die mit <math> E </math> verschlüsselte Nachricht wird mittels <math> D </math> wieder korrekt entschlüsselt.<br>

== Der RSA-Algorithmus ==

=== Das Verfahren ===

''Beispiel:''

'''(1) Schlüsselerzeugung'''

 (a)   p = 11 ; q = 13

 (b)   N = p · q = 11 · 13 = 143

 (c)   <math> \varphi</math>(N) = (p-1) · (q-1) = 10 · 12 = 120

 (d)   e = 23

'''Euklidischer Algorithmus:'''

 120 = 5 · 23 + 5
  23 = 5 · 5 + 3
   5 = 1 · 3 + 2
   3 = 1 · 2 + 1
   2 = 2 · 1 + 0    → Abbruchbedingung
    ggT (120;23)

  e · d = 1 mod <math> \varphi</math>(N)

<u>''Ziel:''</u>''  1 = d · 23 + y · 120''

 (e)     1 = 3 - 1 · 2 = (23- 4 · 5) - (5 - 1 · 3)
           = 23 - 4 · 5 + 1 · 3 = 23 - 5 · (120 - 5 · 23) + (23 - 4 · 5)
           = 23 - 5 · 120 + 25 · 23 + 23 - 4 · (120 - 5 · 23)
           = 47 · 23 - 9 · 120

 (f)    (e; N) = (23,143); (d,N) = (47,143)


'''(2) Verschlüsseln der Klartextnachricht K = 7'''

         c <math>\equiv </math>   K<small><sup>e</sup></small> mod N  <math>\equiv </math>  7<small><sup>23</sup></small> mod 143
                         <math>\equiv </math>  7<small><sup>21</sup></small> · 7<small><sup>2</sup></small> mod 143
                         <math>\equiv </math>  (7<small><sup>7</sup></small>)<small><sup>3</sup></small> · 7<small><sup>2</sup></small> mode 143
                         <math>\equiv </math>  6<small><sup>3</sup></small> · 7<small><sup>2</sup></small> mod 143
                         <math>\equiv </math>  73 · 49 mod 143
                         <math>\equiv </math>  2 mod 143

'''(3) Entschlüsseln der Geheimbotschaft c = 2'''

            K <math>\equiv </math>  c<small><sup>d</sup></small> mod N <math>\equiv </math>  2<small><sup>47</sup></small> mod 143
                          <math>\equiv </math>  2<small><sup>(6 · 7)</sup></small> · 2<small><sup>5</sup></small> mod 143
                          <math>\equiv </math>  7 mod 143

=== Die Mathematik hinter dem RSA-Algorithmus ===

'''Definition:''' ''Eulersche <math> \varphi</math>-Funktion''<br />

<math>\varphi(n) := |G_n|</math> mit <math>G_n := \{k\in \N \mid ggT(n,k)=1, k \leq n\}</math>.<br>
<math>\varphi(n)</math> gibt die Menge aller Zahlen <math>k\in\N</math> mit <math> k \leq n </math> an, die teilerfremd zu <math> n </math> sind.<br />


'''Satz:''' ''<math> \varphi</math>-Funktion und Primzahlen''<br />
b
Sei <math>p\in\N</math> eine Primzahl (<math>p\in\mathbb P</math>), dann gilt: <math>\varphi(p) = p-1 </math>. <br>

'''Beweis:''' ''<math> \varphi</math>-Funktion und Primzahlen''<br />
z.Z. <math> \varphi{(p)}</math>=|<math>G_{p}|=p-1</math><br />
In <math>G_{p}</math> können <math> {1,...,p-1,p} </math>, also <math> p </math> mögliche Zahlen liegen.<br />
<math>G_{p}</math>:={<math>k\in\N</math><math>|ggT(p,k)=1</math>, <math> k \leq p </math>}<br />
Es gilt: <math>p\notin G_{p}</math>, da <math> ggT(p,p)=p </math> (für <math>p>1 </math>) gilt.<br />
<math>1\in G_{p}</math>, da für alle <math>p\in\N</math> gilt: <math>ggT(p,1)=1</math> <br />
Für alle <math>k\in \{2,...,p-1\} </math> gilt ebenfalls <math>ggT(p,k)=1</math>, denn sonst wäre <math> p </math> keine Primzahl und hätte den Teiler <math> k </math> mit <math>k|p  \land  1<k<p. </math> <br />
Also gilt:<math> \varphi{(p)}=p-1.</math>

<br />
'''Satz:''' ''Multiplikativitätssatz der <math> \varphi</math>-Funktion''<br />

Seien <math>p,q\in\mathbb P</math> gegeben, dann gilt <math>\varphi(p \cdot q) = \varphi(p) \cdot \varphi(q) </math>.

'''Beweis:''' z.Z.: Seien <math>p,q\in\mathbb P</math> Primzahlen: <math>\varphi(p \cdot q) = \varphi(p) \cdot \varphi(q) </math>.

In <math>G_{pq}</math> können nur die Elemente <math>{1,...,pq-1,pq}</math> also <math>pq</math> Elemente enthalten sein <math>(\vert G_{pq} \vert \leq pq)</math>.

Nun schließen wir aus dieser Menge Elemente aus, die nicht in <math>G_{pq}</math> enthalten sein können:

Es gilt <math>pq\notin G_{pq}</math>, da <math>ggT(pq,pq)=pg\neq 1</math>.

Es bleiben als mögliche Zahlen <math>G_{pq} \subseteq {1,...,pq-1} := M_{pq}; \vert M_{pq} \vert =pq-1</math>

Wir betrachten alle Zahlen, die nicht Teilerfremd zu pq sind.

<math>1 \cdot p,2 \cdot p,...,(q-1)p</math> also <math>q-1</math> nicht Teilerfremde Zahlen aus <math>M_{pq}</math>

<math>1 \cdot q,2 \cdot q,...,(p-1)q </math> also <math>p-1</math> nicht Teilerfremde Zahlen aus <math>M_{pq}</math>

Dabei kommt keine Zahl doppelt vor.

Damit folgt für die Anzahl der Elemente in <math>\vert G_{pq} \vert = \vert M_{pq} \vert - (q-1)-(p-1)</math>.

Durch Umformung ergibt sich nun:
<math>\vert G_{pq} \vert = \vert M_{pq} \vert - (q-1)-(p-1)

=pq-1-q+1-p+1

=pq-q-p+1

=q(p-1)-p+1

=q(p-1)-1(p-1)

=(p-1)(q-1)</math>


'''Definition:''' ''Gruppe''<br />

Eine Gruppe ist ein Paar <math>(G,*)</math> bestehend aus einer Menge <math>G</math> und einer (inneren) Verknüpfung <math>*</math> auf <math>G</math>.<br />
Das heißt, durch <math>*</math> wird die Abbildung <math>*\colon G \times G \to G, (a,b) \mapsto a*b</math> beschrieben.<br />
Erfüllt die Verknüpfung die folgenden Axiome, dann wird <math>(G,*)</math> Gruppe genannt:<ref>Siegfried Bosch: ''Algebra''. 6. Auflage. Springer-Verlag, 2006, ISBN 3-540-40388-4, S. 11.</ref>

* '''(AG)''' Für alle Gruppenelemente <math>a</math>, <math>b</math> und <math>c</math> gilt: <math>(a*b)*c = a*(b*c).</math>
* '''(NE)''' Es gibt ein neutrales Element <math>e\in G</math>, mit dem für alle Gruppenelemente <math>a\in G</math> gilt: <math>a*e = e*a = a</math>.
* '''(IE)''' Zu jedem Gruppenelement <math>a\in G</math> existiert ein inverses Element <math>a^{-1}\in G</math> mit <math>a*a^{-1} = a^{-1}*a = e</math>.


'''Definition:''' ''Abelsche Gruppe''<br />

Eine Gruppe <math>(G,*)</math> heißt ''abelsch'' oder ''kommutativ'', wenn zusätzlich das folgende Axiom erfüllt ist:

* '''(KG)''' Für alle Gruppenelemente <math>a</math> und <math>b</math> gilt <math>a*b = b*a</math>.<br>


'''Definition:''' ''Potenzen in Gruppen''<br />

Sei <math>(G,*)</math> eine Gruppe. Dann definiert man: <br>
<math>a^n:= \underbrace{a*a*...*a}_{n-fach} = ((...((a*a)*a)*...*a)</math> für <math>n\in\N</math>.<br>
<math>a^{-n}:= \underbrace{a^{-1}*a^{-1}*...*a^{-1}}_{n-fach} = ((...((a^{-1}*a^{-1})*a^{-1})*...*a^{-1})</math> für <math>n\in\N</math>.<br>
<math>a^0:= e</math><br>


'''Definition:''' ''Untergruppe''<br />
Sei <math>(G,*)</math> eine Gruppe.<br>
<math>\emptyset \neq U \subseteq G</math> heißt Untergruppe <math>(U,*)</math> von <math>(G,*)</math> <math>:\Leftrightarrow \forall a,b\in U: a*b^{-1}\in U</math>.<br>

oder

Sei <math>(G,*)</math> eine Gruppe und <math>U </math> eine nicht leere Teilmenge von <math>G</math>.<br>
<math>(U,*)</math> heißt Untergruppe von <math>(G,*)</math> <math>:\Leftrightarrow </math>
* '''(IV)''' Durch <math>*</math> wird die Abbildung <math>*\colon U \times U \to U, (a,b) \mapsto a*b</math> beschrieben.
* '''(AG)''' Für alle Gruppenelemente <math>a</math>, <math>b</math> und <math>c</math> gilt: <math>(a*b)*c = a*(b*c).</math>
* '''(NE)''' Es gibt ein neutrales Element <math>e\in U</math>, mit dem für alle Gruppenelemente <math>a\in U</math> gilt: <math>a*e = e*a = a</math>.
* '''(IE)''' Zu jedem Gruppenelement <math>a\in U</math> existiert ein inverses Element <math>a^{-1}\in U</math> mit <math>a*a^{-1} = a^{-1}*a = e</math>.<br>


'''Satz:''' ''Neutrales Element der Untergruppe''<br />
Wenn <math>(U,*)</math> Untergruppe der Gruppe <math>(G,*)</math> ist, dann besitzt <math>(U,*)</math> das gleiche neutrale Element <math>e</math> wie <math>(G,*)</math>.<br>


'''Definition:''' ''Faktorgruppe''<br />
Sei <math>(G,*)</math> eine Gruppe und <math>(U,*)</math> eine Untergruppe von <math>(G,*)</math>, dann nennt man <math>G/U</math> Faktorgruppe (mit <math>(G,*)</math> kommutativ). Die Faktorgruppe enthält folgende Elemente: <br>
<math>G/U:= \{a*U\mid a\in G\}</math>.<br>
<math> a*U </math> nennt man Nebenklasse von <math>U</math>.<br>


'''Satz''' ''von Euler bzw. kleiner Satz von Fermat''<br />
Seien <math> m,n\in\N </math> gegeben mit <math> ggT(m,n)=1 </math>.<br>
Dann gilt: <math> m^{\varphi(n)}\equiv 1 \mod n </math><br>


'''Satz''' ''Gruppe bezüglich <math> \varphi (n)</math> ''<br />
Sei <math> n\in\N, n \geq 1 </math> gegeben.<br>
<math> (R_n,\cdot) </math> sei das multiplikative Verknüpfungsgebilde der Restklassen<br>
<math> R_n = \{\bar{0}_n,\bar{1}_n,..., \overline{n-1}_n\}</math>, dann gilt:<br>
<math> R_n^* = \{\bar{z}_n \mid z \in T_n = \{ z\in \N \mid (z \leq n)\wedge ggT(z,n) =1\}\}</math><br>
ist eine abelsche Gruppe mit <math> \varphi(n)</math> Elementen.<br>
Die abelsche Gruppe <math> (R_n,\cdot) </math> nennt man reduziertes Restsystem.<br>
<br>

''' Beweis:''' <br />
z.z.: <math>(R_n^*, \cdot)</math> ist eine abelsche Gruppe.<br />
* '''(IV)''' z.z.: Durch <math>\cdot</math> wird die Abbildung <math>\cdot\colon R_n^* \times R_n^* \to R_n^*, (a,b) \mapsto a \cdot b</math> beschrieben mit <math> a:= \bar{a}_n </math> und <math>b:= \bar{b}_n</math>.
: Es muss also gezeigt werden: <math>a \cdot b = \bar{a}_n \cdot \bar{b}_n = (\overline{a\cdot b})_n \in R_n^*</math>.
: ''Vorüberlegungen:''<br />
:* Ohne Einschränkung können wir später für <math> a \cdot b</math> einen Repräsentanten aus <math> \{0,...,n-1\}</math> wählen.<br />
:* Zu zeigen ist: <math> ggT(a,n)=1 \wedge ggT(b,n)=1 \Rightarrow ggT(a\cdot b,n)=1</math>, bzw. dass für <math> a \cdot b = k \cdot n +r </math> gilt: <math> ggT(r,n)=1 </math>, denn dann gilt <math> \bar{r}_n\in R_n^*</math>.<br>
:* <math> M_T(a) = \{t\in\N\mid t|a\} </math> (Teilermenge von <math> a </math>). <math> M_T(b) \cap M_T(n) = \{1\} = M_T(a) \cap M_T(n)</math>.
:* <math> a\cdot b</math> kann auch keine gemeinsamen Teiler mit <math> n </math> besitzen, da <math> M_T(a), M_T(b) \subseteq M_T(a\cdot b)</math><br>
* '''(AG)''' z.z.: Für alle Gruppenelemente <math>a,b,c \in R_n^*</math> gilt: <math>(a\cdot b)\cdot c = a\cdot(b\cdot c).</math>
: Das Assoziativgesetz ist in <math>(R_n^*, \cdot)</math> erfüllt, weil es in der Gruppe <math>(R_n, \cdot)</math> gilt.
* '''(KG)''' z.z.: Für alle Gruppenelemente <math>a,b \in R_n^*</math> gilt: <math>a\cdot b = b\cdot a.</math>
: Das Kommutativgestetz ist in <math>(R_n^*, \cdot)</math> erfüllt, weil es in der abelschen Gruppe <math>(R_n, \cdot)</math> gilt.
* '''(NE)''' z.z.: Es gibt ein neutrales Element <math>e \in R_n^*</math>, mit dem für alle Gruppenelemente <math>a\in R_n^*</math> gilt: <math>a\cdot e = e\cdot a = a</math>.
: Sei <math>e = \bar{1}_n </math>. Es gilt: <math>a\cdot e = \bar{a}_n \cdot \bar{1}_n = \bar{1}_n\cdot \bar{a}_n = \bar{a}_n = a</math> und <math> \bar{1}_n \in R_n^* </math>, da <math> ggT(1,n)=1 </math>.
* '''(IE)''' z.z.: Zu jedem Gruppenelement <math>a\in R_n^*</math> existiert ein inverses Element <math>a^{-1}\in R_n^*</math> mit <math>a\cdot a^{-1} = a^{-1}\cdot a = e</math>.
: Da <math> ggT(a,n)=1 </math> für <math>\bar{a}_n \in R_n^*</math>, kann man ein modulares Inverses <math>a^{-1}</math> bestimmen mit <math> ggT(a^{-1},n)=1 </math>, also <math>a^{-1}\in R^*_n</math>, und <math>a\cdot a^{-1} = \bar{a}_n \cdot \overline{a^{-1}}_n= \overline{a^{-1}}_n\cdot \bar{a}_n = a^{-1}\cdot a = e = \bar{1}_n</math>.<br>
Insgesamt ist <math>(R_n^*, \cdot)</math> ist eine abelsche (multiplikative) Gruppe.<br>


'''Bemerkung:''' <math> R_{n}^{*}</math> hängt mit <math> T_n</math> wie folgt zusammen: <math> T_n</math> ist ein Repräsentantensystem für <math> R_{n}^{*}</math>.<br />


'''Definition:''' ''Repräsentantensystem''<br />
Sei <math> z, n > 1 </math> mit <math> n\in\N</math> gegeben. <br>
Wir betrachten die Restklassen <math> R_n \mod n</math>.<br>
Sei <math> T^* \subseteq R_n </math> und <math> T \subseteq \Z </math>.<br>
<math> T </math> heißt Repräsentantensystem von <math> T^* : \Leftrightarrow (\{\bar{z}_n\mid z \in T\} = T^*) \wedge (\forall z,y\in T: z \neq y \rightarrow \bar{z}_n \neq \bar{y}_n)</math>.<br>
Damit gilt insgesamt <math> \varphi(n) = |R^*_n|, R^*</math> Gruppe.<br>


'''Satz:''' ''Nachrichtenmenge''<br />
Mit dem RSA-Algorithmus können Mengen <math> \{0,1, ..., k\} </math> mit <math> k = \min \{p,q\}-1</math> und <math> n= p\cdot q</math> verschlüsselt werden. <br>

'''Beweis:''' ''Nachrichtenmenge''<br />
Nach der Methode der Schlüsselgenerierung wird <math> n=p\cdot q </math> mit <math> p,q\in P </math> als Produkt von zwei Primzahlen <math> p </math> und <math> q </math> erzeugt, wobei <math> p\ne q </math>.<br />
<math> T(n) = T(p,q) = \{1,p,q,p\cdot q\} </math> ist die Teilmenge von <math> n </math>. <br />
<math> ggT(p,K)=1 </math><br>

'''1.Fall:''' <math> p<q </math> Alle Zahlen <math> \{1,...,p-1\} </math> sind Teilerfremd zu <math> p,q </math> und <math> n </math>.<br />
'''2.Fall:''' <math> p>q </math> Alle Zahlen <math> \{1,...,q-1\} </math> sind Teilbar zu <math> p,q </math> und <math> n </math>.<br />
'''3.Fall:''' <math> p=q </math> Muss nicht geprüft werden, da <math> p\ne q </math> gilt. Trifft trotzdem zu.<br />
Wenn <math> p=q </math>, dann gilt: <math> T(n)=T(p\cdot q)=T(p^{2})=\{1,p,p^{2}\} </math>. Alle Zahlen <math> \{1,...,p-1\} </math> sind Teilerfremd zu <math> p,q </math> und <math> n </math>.<br />
<math> K= min\{p,q\}-1 </math>, um <math> p </math> und <math> q </math> auszuschließen.<br />
Dann gilt: <math> ggT(p,n)=p\ne 1 </math> und <math> ggT(q,n)=q\ne 1 </math>.<br>


'''Definition:''' ''Ordnung eines Elements''<br />
Sei <math> U = <a> </math> und <math> a \in G </math> mit <math> (G,*) </math> Gruppe.<br>
<math> Ord(a) = |U| =k </math> mit <math> k:= \min\{\tilde{k} \in \N \mid a^{\tilde{k}}=e\}. </math><br>


'''Satz:''' ''Lagrange''<br />
Sei <math> (G,*) </math> eine abelsche Gruppe und <math> U </math> eine Untergruppe von <math> G</math>, dann gilt: <br>
<math> |U| \mid |G| </math><br>


'''Beweis:'''<br />

''Idee'': Disjunkte Zerlegung von <math> G </math> in gleichmächtige Mengen.<br>

* '''Zerlegung von <math> G </math> in Teilmengen durch die Zerlegung in Nebenklassen'''
: Wir betrachten die Nebenklassen <math> a*U </math> mit  <math> a \in G </math> und  <math> U </math> Untergruppe von  <math> G </math>.
: z.z.: <math>\bigcup\limits_{a\in G} a * U = G </math>
: Beweis: 
:* "<math>\subseteq</math>": 
:: <math> a*U = \{\underbrace{a*u}_{\in G} \mid u \in U\} \subseteq G </math>
:: Da jede Nebenklasse eine Teilmenge von <math> G </math> ist, ist auch die Vereinigung der Nebenklassen  <math>\bigcup\limits_{a\in G} a*U </math> eine Teilmenge von <math> G </math>.
:* "<math>\supseteq</math>":
:: Sei <math> e\in G </math> das neutrale Element von <math> G </math>.
:: <math> \Rightarrow e \in U </math>, da <math> U </math>  die Untergruppe von <math> G </math> ist.
:: <math> \tilde{a} = \tilde{a} * e \in \tilde{a} * U </math>.
:: Damit ist jedes beliebige <math> \tilde{a} \in G </math> ein Element von <math> \tilde{a} * U \subseteq \bigcup\limits_{a\in G} a * U = G</math>.
: Damit wissen wir, dass wir <math> G </math> in die Nebenklassen <math> a*U</math> zerlegen können.<br>
* '''Zerlegung von <math> G </math> in paarweise disjunkte Nebenklassen'''
: Seien <math> T_a = a*U </math> und <math> T_b = b*U </math> mit <math> a,b \in G </math> beliebig gewählte Nebenklassen. 
: z.z: <math>T_a \neq T_b \Rightarrow T_a\cap T_b = \emptyset </math>
: Beweis: 
: Sei <math> s \in T_a \cap T_b =(a*U)\cap (b*U) \Rightarrow s\in T_a \wedge s \in T_b \Rightarrow (\exists u_1\in U: s= a*u_1)\wedge (\exists u_2\in U: s= b*u_2)</math>.
: Wir zeigen nun, dass <math> a*U = b*U </math>.
:* "<math>\subseteq</math>": 
:: Sei <math> u\in U</math> beliebig gewählt mit <math> a*u \in a*U </math>.
:: Mit <math> a*u_1 = s = b*u_2 </math> gilt <math> a = (b*u_2)*u_1^{-1} = b* (u_2 * u_1^{-1})</math>.
:: Da <math> (U,*) </math> eine Untergruppe von <math> (G,*) </math> ist, gilt mit <math> u_1 \in U </math> auch <math> u_1^{-1} \in U </math>.
:: Ferner gilt auch <math> u_2 * u_1^{-1} \in U </math>, weil <math> * </math> einen innere Verknüpfung in <math> (U,*) </math>.
:: <math> a*u = (b* (u_2 * u_1^{-1}))* u \stackrel{AG\ in\ (G,*)}{=} b * \underbrace{(\underbrace{(u_2 * u_1^{-1})}_{\in U}*\underbrace{u}_{\in U})}_{\in U} \in b*U </math>.
:* "<math>\supseteq</math>":
:: Sei <math> u\in U</math> beliebig gewählt mit <math> b*u \in b*U </math>.
:: Mit <math> a*u_1 = s = b*u_2 </math> gilt <math> a = (a*u_1)*u_2^{-1} = a* (u_1 * u_2^{-1})</math>.
:: Analog gilt auch <math> u_1 * u_2^{-1} \in U </math> wegen der Untergruppeneigenschaft von <math> (U,*) </math>.
:: <math> b*u = (a* (u_1 * u_2^{-1}))* u \stackrel{AG\ in\ (G,*)}{=} a * \underbrace{(\underbrace{(u_1 * u_2^{-1})}_{\in U}*\underbrace{u}_{\in U})}_{\in U} \in a*U </math>.
: Insgesamt gilt also <math> a*U = b*U </math>, da wir beide Teilmengenbeziehungen <math> a*U \subseteq b*U </math> und  <math> a*U \supseteq b*U </math> gezeigt haben.
: Insbesondere heißt das für die Nebenklassen <math> a*U </math>, dass zwei Nebenklassen entweder gleich oder disjunkt sind.
* '''Zerlegung von <math> G </math> in paarweise disjunkte gleichmächtige Nebenklassen'''
: Wir definieren eine bijektive Abbildung zwischen <math> U </math> und einer beliebigen Nebenklasse <math> a*U </math>:
: <math> \varphi: U \rightarrow a*U; u \mapsto a*u, a \in G </math> beliebig gewählt.
: z.z.: <math> \varphi\ surjektiv\wedge\ \varphi\ injektiv </math> 
:* <math> \varphi\ surjektiv </math>: 
:: z.z: <math> \forall y\in a*U \exists x\in U: \varphi(x)=y </math>
:: Sei <math> y\in a*U </math> beliebig gewählt.
:: <math>\Rightarrow \exists u_y \in U: y = a * u_y </math>  
:: <math>\Rightarrow \exists (x := u_y) \ wedge (\varphi(x) = \varphi(u_y) = a * u_y =y) </math>
:* <math> \varphi\ injektiv </math>: 
:: z.z: <math> \forall x_1, x_2\in U: \varphi(x_1)=\varphi(x_2) \Rightarrow x_1 = x_2 </math>
:: Seien <math> x_1, x_2\in U </math> so gewählt, dass <math> varphi(x_1)=\varphi(x_2) </math> gilt.
:: <math> \Rightarrow varphi(x_1) = a * x_1 = a * x_2 = varphi(x_2) </math>
:: <math> \Rightarrow a * x_1 = a * x_2 </math> mit <math> a\in G </math> und <math> a^{-1}\in G </math>, da <math> (G,*) </math> Gruppe.
:: <math> \Rightarrow a^{-1}*(a * x_1) = a^{-1}*(a * x_2) </math>
:: <math> \stackrel{AG}{\Rightarrow} (a^{-1}*a) * x_1 = (a^{-1}*a) * x_2 </math>
:: <math> \stackrel{IE}{\Rightarrow} e * x_1 = e * x_2 </math>
:: <math> \stackrel{NE}{\Rightarrow} x_1 = x_2 </math>
:: Also ist <math> \varphi </math> auch injektiv.
* '''Untersuchung der Teilbarkeitseigenschaften'''
: Wir suchen nun ein Repräsentantensystem <math> V </math> für die Faktorgruppe <math> G/U = \{a*U\mid a\in G\} </math>.
: Für <math> V </math> <math> (a,b \in V) \wedge (a \ neq b ) \Rightarrow a * U \neq b*U</math>
: <math> G/U = \{a*U\mid a\in V\} </math>
: Wir benötigen das Repräsentantensystem, damit wir Nebenklassen nicht mehrfach zählen.
:* Sei <math> |G| = \infty \wedge |U| \geq 1 \wedge |U| < \infty</math>.
:: <math> \Rightarrow |G| = |\bigcup\limits_{a\in V} a*U| = \sum\limits_{a\in V} |a*U|= \sum\limits_{a\in V} |U| = |V|\cdot |U|</math>.
:: Mit  <math> |G| = \infty </math> gilt auch <math> |V| = \infty </math> und somit <math> |G| = |V|\cdot|U| = \infty </math>.
:: Mit  <math> |G| = \infty </math> und <math> |U| = \infty </math> gilt insbesondere <math> |V|\geq 1 </math>, da es mindestens eine Nebenklasse <math> e*U </math> gibt, <math> e </math> neutrales Element in <math> G </math>.
:: Damit gilt auch <math> |G| = |U|\cdot |V| = \infty </math>.
:* Für endliche Gruppen gilt:
:: <math> k = |G| \geq |U| > 1, |G|  \geq |V|  \geq 1 </math>.
:: <math> |G| = |\bigcup\limits_{a\in V} a*U|= \sum\limits_{a\in V} |a*U| = \sum\limits_{a\in V} |U| = |V|\cdot |U|</math>
:: <math> \Rightarrow |U| | |G| </math>.<br>


'''Satz:''' ''RSA-Algorithmus''<br />
Sei <math> m </math> eine Klartextnachricht, die mit dem RSA-Algorithmus verschlüsselt wird.  Sei <math>(e,n)</math> sei der öffentliche Schlüssel und  <math>(d,n)</math> der private Schlüssel. 
Dann gilt:
<math>  m^{e\cdot d} \mod n \equiv m \mod n </math><br>.

''' Beweis:'''<br />
z.z.: <math>  m^{e\cdot d} \mod n \equiv m \mod n </math>.<br>
:<math>  m^{e\cdot d} \mod n </math><br>
<math>  \equiv m^{1+k\cdot \varphi(n)} \mod n </math><br>
<math>  \equiv m^1 \cdot m^{k\cdot \varphi(n)} \mod n </math><br>
<math>  \equiv m^1 \cdot (m^{\varphi(n)})^k \mod n </math><br>
<math>  \equiv m \cdot ((m^{Ord(m)})^{\frac{\varphi(n)}{Ord(m)}})^k \mod n </math><br>
<math>  \equiv m \cdot (1^{\frac{\varphi(n)}{Ord(m)}})^k \mod n </math><br>
<math>  \equiv m \cdot 1^k \mod n </math><br>
<math>  \equiv m \mod n </math><br>

= Grundlegende Definitionen =

'''Definition:''' ''Relation''<br />

Eine Relation <math>R</math> zwischen zwei Mengen <math>A</math> und <math>B</math> ist eine Teilmenge des kartesischen Produkts <math>A \times B = \{(a,b) \mid a \in A, b \in B\}\colon</math>
:<math>R \sube A \times B.</math><br />


'''Definition:''' ''Äquivalenzrelation''<br />

Eine Äquivalenzrelation auf einer Menge <math>M</math> ist eine Teilmenge <math>R \subseteq  M \times M</math>, welche folgende Bedingungen erfüllt:
* Reflexivität: Für alle <math>a\in M</math> ist <math>(a,a)\in R</math>.
* Symmetrie: Für alle <math>a,b\in M</math>, für die <math>(a,b)\in R</math> gilt, ist auch <math>(b,a) \in R</math>.
* Transitivität: Für alle <math>a,b,c \in M</math> mit <math>(a,b) \in R</math> und <math>(b,c) \in R</math> gilt, dass auch <math>(a,c) \in R</math>.<br />


'''Definition:''' ''Äquivalenzklasse''<br />

Ist <math>R</math> eine Äquivalenzrelation auf einer Menge <math>M</math>, so nennt man für ein <math>a\in M</math> die Teilmenge<br />
<math>[a]_R = \{x\in M\mid (x, a) \in R\} \subseteq M</math><br />
die Äquivalenzklasse von <math>a</math> unter der Äquivalenzrelation <math>R</math>.<br />


'''Definition:''' ''Teilbarkeit''<br />

<math>a|b \Leftrightarrow \exists k\in\Z: b = k \cdot a.</math><br />


'''Definition:''' ''Kongruenzrelation''<br />

Für <math>a,b\in\Z</math> und <math>m\in\N</math> wird definiert:<br />
<math>a\equiv b \mod m :\Leftrightarrow m|(a-b).</math><br />


'''Satz:''' ''Kongruenzrelation''<br />

Es gilt:
<math>a\equiv b \mod m \Leftrightarrow \exists q\in\Z:a=b+q\cdot m.</math><br />


'''Definition:''' ''Restklasse''<br />

Es sei <math>m</math> eine von 0 verschiedene ganze Zahl und <math>a</math> eine beliebige ganze Zahl. Die Restklasse von <math>a</math> modulo <math>m</math>
ist die Äquivalenzklasse von <math>a</math> bezüglich der Kongruenz modulo <math>m</math>, also die Menge der ganzen Zahlen, die bei Division durch <math>m</math> den gleichen Division mit Rest wie <math>a</math> ergeben. Sie besteht somit aus allen ganzen Zahlen <math>b</math>, die sich aus <math>a</math> durch die Addition ganzzahliger Vielfacher von <math>m</math> ergeben:
<math>[a]_{\equiv}= \{ b\mid b=a+km\ \, \mathrm{f\ddot ur\ ein}\ \, k\in\mathbb Z\} = \{ b \mid b \equiv a \; ({\rm mod} \; m) \}</math>.<br />
<br />

''Allgemeine Formel für Modulo-Rechnungen
''[[File:Formel_für_Modulo-Rechnen.png|center|Abbildung Formel_für_Modulo-Rechnen.png]]

= Quellen zu Kryptologie im Schulunterricht =
* [https://cses.informatik.hu-berlin.de/selected_reports/Unterrichtskonzept_Kryptologie_Ghomi.pdf Schriftliche Ausarbeitung einer Unterrichtsreihe zum Thema Kryptologie (von Mina Ghomi)]
* [http://www.mathematik.tu-dortmund.de/ieem/bzmu2011/_BzMU11_2_Einzelbeitraege/BzMU11_BORYS_T_Vernetzung.pdf Codes und Verschlüsselungen integrativ im Mathematikunterricht: Vorschlag für ein Curriculum (von Thomas Borys)]
* [https://www.mathematik.tu-dortmund.de/ieem/cms/media/BzMU/BzMU2009/Beitraege/BORYS_Thomas_2009_Codierungen.pdf Codierungen im Spiegel der fundamentalen Ideen der Mathematik (von Thomas Borys)]
* [https://www.mathematik.tu-dortmund.de/ieem/cms/media/BzMU/BzMU2010/BzMU10_BORYS_Thomas_Vernetzung.pdf Welche Vernetzungsmöglichkeiten bietet die Kryptologie? (von Thomas Borys)]
* [https://www.zauberhogwarts.de/ Zauberhogwarts]

= Lernen durch Autorentätigkeit =
Diese Seite entsteht nach dem Prinzip Lernen durch Autorentätigkeit in Wikiversity (siehe [https://en.wikiversity.org/wiki/Risk_Management#Learning_Task Learner being an Author]).

= Literatur =