Kryptologie - Mathematische Vertiefung (PH Freiburg SS 2017)

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)
Hilfe für die Bearbeitung des Wikis: Wikipedia-Hilfe und für das Einfügen mathematischer Formeln: Tex-Hilfe

Die Kryptologie lässt sich in die Kryptographie und die Kryptoanalyse gliedern.
Die Kryptographie bezeichnet die Wissenschaft der Entwicklung von Kryptosystemen und die Kryptoanalyse die Kunst diese zu brechen.


Definition: Text/ Nachricht $A$ ist ein Alphabet.
$A^{n}=A\times A\times ...\times A=\{(z_{1},...,z_{n})\mid \forall k\in \{1,...,n\}:z_{k}\in A\}$ ist das $n$-fache kartesische Produkt des Alphabets $A$
$A^{n}$ sind die Nachrichtentexte der Länge $n$.
$A^{+}=\bigcup \limits _{n=1}^{\infty }A^{n}$
$A^{+}$ sind alle Nachrichten aus Buchstaben des Alphabets $A$.

Definition: Bijektiver Schlüssel
$A,B$ sind Alphabete. $f:A\rightarrow B$ ist eine bijektive Abbildung.
Dann nennt man $f$ einen bijektiven Schlüssel für Nachrichten aus $A^{+}$.

Bijektivität

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.

Beispiel für eine bijektive Funktion

Definition: Bijektivität
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.

Beispiel für eine bijektive Funktion

Erklärung für Schüler: Beispiel aus dem Alltag

• "In einem Glas befinden sich 25 Bonbons. Die Klasse besteht aus 25 Schülerinnen und Schülern. Jeder Schüler bekommt genau ein Bonbon."
  Diese Abbildung ist bijektiv, da ja jeder Schüler genau ein Bonbon bekommt. Niemand bekommt mehrere Bonbons und auch niemand wird ausgelassen.
  
• "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."
  Diese Situation ist nicht bijektiv, da nicht jeder genau eine Brezel isst.
• "Jeder Mensch muss einmal sterben"
  Diese Situation ist bijektiv, weil wirklich jeder Mensch einmal sterben wird und man stirbt nur einmal.
  

Definition: Abbildung

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

Definition: Injektivität, Surjektivität, Bijektivität

Es seien A und B Mengen und $f:A\rightarrow B$ eine Abbildung zwischen A und B.
f heißt:

• injektiv$:\Leftrightarrow \forall a_{1},a_{2}\in A:f(a_{1})=f(a_{2})\rightarrow a_{1}=a_{2}$.
• surjektiv$:\Leftrightarrow \forall b\in B\exists a\in A:f(a)=b$.
• bijektiv$:\Leftrightarrow f$ ist injektiv und $f$ ist surjektiv.

Symmetrische Verschlüsselung

Definition: Symmetrische Verschlüsselung
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.

Monoaplhabetische Substitution

Als 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 $\{a,...,z\}$.
Die Caesar-Verschlüsselung ist ein Sonderfall der einfachen monoalphabetischen Substitution.

Caesar-Verschlüsselung

Arbeitsauftrag 1 b): Wie Funktioniert die „Caesar-Verschlüsselung“? Erläutern Sie die Funktionsweise, die mathematischen Hintergründe und erstellen Sie mit Hilfe von LibreOffice Calc (oder Microsoft Excel) ein Programm, mit dem das Ver- und Entschlüsseln mittels Caesar-Verschlüsselung möglich ist.

Excel Graph der Funktion von Klartext auf Chiffrierter Text

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 $A=\{z_{1},z_{2},...,z_{|A|}\}$ und ein Geheimtextalphabet $B$ und es gilt $A=B$. Die Mächtigkeit $|A|$ ist die Anzahl aller Elemente des Alphabets $A$. Man nummeriert jedes Element des Alphabets mit den natürlichen Zahlen von $0$ bis $|A|-1$ mit Hilfe folgender Abbildung:
$f:A\to \{0,...,|A|-1\}$

$z_{1}\mapsto 0$

$z_{2}\mapsto 1$

$\vdots$

$z_{|A|}\mapsto |A|-1$

Bei der Caesar-Verschlüsselung handelt es sich um eine bijektive Abbildung
$V:A\rightarrow B$

$a\mapsto V(f(a))=(f(a)+k)~mod~|A|$,

wobei $k\in \mathbb {N} ,0\leq k\leq |A|$ der Schlüssel ist.
Entschlüsselt wird mit der Umkehrabbildung von $V,V^{-1}=:E$.
$E:B\rightarrow A$

$b\mapsto E(f(b))=(f(b)-k)~mod~|A|$,

wobei k derselbe Schlüssel ist, der zum Verschlüsseln verwendet wurde.

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.

Skytala-Verschlüsselung

Arbeitsauftrag 1 c): Wie Funktioniert die „Skytala-Verschlüsselung“? Erläutern Sie die Funktionsweise, die mathematischen Hintergründe und erstellen Sie mit Hilfe von LibreOffice Calc (oder Microsoft Excel) ein Programm, mit dem das Ver- und Entschlüsseln mittels Skytala- Verschlüsselung möglich ist.

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.

Mathematischer Hintergrund: Gegeben ist ein Klartext mit der Textlänge $t$. Die Positionen der Buchstaben sind bei Transpositionschiffren wichtig, die Positionen im Klartext stammen aus der Menge $P:=\{1,...,t\}$ und sind folgendermaßen nummeriert: $(1,2,...t)$. Sei nun $u$ der Umfang des Stabs, der durch die Anzahl der Zeilen des Geheimtextes bestimmt wird und $l$ die Länge der Nachricht, wenn sie um den Stab gewickelt ist, die durch die Anzahl der Spalten des Geheimtextes bestimmt wird. Es gilt $t=l\cdot u$ Dann wird durch folgende Abbildung verschlüsselt:
$V:P\to P$

$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}}$

Entschlüsselt wird wiederum mit der Umkehrabbildung $V^{-1}$.

Gartenzaun-Chiffre

Arbeitsauftrag 1 d): Wie Funktioniert die „Gartenzaun-Verschlüsselung“? Erläutern Sie die Funktionsweise, die mathematischen Hintergründe und erstellen Sie mit Hilfe von LibreOffice Calc (oder Microsoft Excel) ein Programm, mit dem das Ver- und Entschlüsseln mittels Gartenzaun-Verschlüsselung möglich ist.

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

Verschlüsselung

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.

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.

Mathematischer Hintergrund: Gegeben ist ein Klartext mit der Textlänge $t$. Die Positionen der Buchstaben sind bei Transpositionschiffren wichtig, die Positionen im Klartext stammen aus der Menge $P:=\{1,...,t\}$ und sind folgendermaßen nummeriert (wir legen fest, dass unser Gartenzaun mit variabler Höhe $h$ und Anzahl der Spitzen $m$ und Täler $m-1$ mit $h,m\in \mathbb {N}$ stets folgende Form hat):

Form des Gartenzauns

Dann wird durch folgende Abbildung verschlüsselt:
$V:P\to P$

$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}}$

Entschlüsselt wird wiederum mit der Umkehrabbildung $V^{-1}$.

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 $k$ möglichen Schlüsseln, benötigt man höchstens $k$ Versuche, durchschnittlich allerdings nur ${\frac {k}{2}}$ Versuche. Je größer die Anzahl der möglichen Schlüssel, umso schwerer ist ein Verschlüsselungsalgorithmus zu knacken.

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 Applets zum Buchstabenzählen), können diese mit der Häufigkeit der Buchstaben der deutschen Sprache abgeglichen werden und entsprechend ersetzt werden.

Unterrichtsplanung

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.

Der Unterricht teilt sich ein in 3 Einheiten:
Einleitung (5 min),
Hauptteil (25 min)
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.
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.
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

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

Buchstabe	Häufigkeit
A	${\frac {3}{6}}={\frac {1}{2}}$
N	${\frac {2}{6}}={\frac {1}{3}}$
S	${\frac {1}{6}}$

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

Sei nun das Geheimtextalphabet $B:=\{1,2,3,...,12\}$ und der Schlüssel zur Verschlüsselung des Klartextes sei folgendermaßen definiert:

Klartextbuchstabe	Menge der zugeordneten Geheimtextbuchstaben	Anzahl der zugeordneten Geheimalphabetbuchstaben	Anteil
A	$\{1,3,8,9,11,12\}=\Omega _{A}$	$6=|\Omega _{A}|$	${\frac {|\Omega _{A}|}{|B|}}={\frac {6}{12}}={\frac {1}{2}}$
N	$\{2,5,7,10\}=\Omega _{N}$	$4=|\Omega _{N}|$	${\frac {|\Omega _{N}|}{|B|}}={\frac {4}{12}}={\frac {1}{3}}$
S	$\{4,6\}=\Omega _{S}$	$2=|\Omega _{S}|$	${\frac {|\Omega _{S}|}{|B|}}={\frac {2}{12}}={\frac {1}{6}}$

Um den Klartext zu verschlüsseln, werden Zufallsexperimente verwendet, um jeweils einen der jeweils zugeordneten Geheimtextbuchtaben zufällig auszuwählen.
Zur Verschlüsselung des Buchtabens "A" benötigen wir ein Zufallsexperiment, bei dem jedes Ereignis mit der Wahrscheinlichkeit ${\frac {1}{6}}$ 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.
Zur Verschlüsselung des Buchtabens "N" benötigen wir ein Zufallsexperiment, bei dem jedes Ereignis mit der Wahrscheinlichkeit ${\frac {1}{4}}$ 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.
Zur Verschlüsselung des Buchtabens "S" benötigen wir ein Zufallsexperiment, bei dem jedes Ereignis mit der Wahrscheinlichkeit ${\frac {1}{2}}$ 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.
Wird auf diese Weise verschlüsselt, kommt jeder Buchstabe aus B im Geheimtext mit einer Häufigkeit von etwa ${\frac {1}{12}}$ vor.

Definition: σ-Algebra
Sei $\Omega$ eine nichtleere Menge und sei ${\mathcal {P}}(\Omega )$ die Potenzmenge dieser Menge.

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

• (1) ${\mathcal {S}}$ enthält die Grundmenge. Es gilt also $\Omega \in {\mathcal {S}}$
• (2) ${\mathcal {S}}$ ist stabil bezüglich der Komplementbildung. Ist also $S\in {\mathcal {S}}$, so ist auch $S^{\mathsf {c}}=\Omega \setminus S$ in ${\mathcal {S}}$ enthalten.
• (3) ${\mathcal {S}}$ ist stabil bezüglich abzählbarenVereinigungen. Sind also Mengen

$S_{1},S_{2},S_{3},\dots$ in ${\mathcal {S}}$ enthalten, so ist auch $\bigcup _{i=1}^{\infty }S_{i}$ in ${\mathcal {S}}$ enthalten.

Ziel: Man möchte nicht nur einzelnen Buchstaben $\omega \in \Omega$ eine Wahrscheinlichkeit zuordnen, sondern auch Teilmengen des Alphabets.

Beispiele: Bei folgenden Mengen handelt es sich um σ-Algebren:

• $\{\emptyset ,\Omega \}$
• $\{\emptyset ,A,A^{C},\Omega \}$
• $\{\emptyset ,\mathbb {R} ,[0,1],(-\infty ,0)\cup (1,\infty )\}$

Definition: Wahrscheinlichkeitsraum $(\Omega ,{\mathcal {S}},P)$
Sei $\Omega$ (ein Alphabet) eine nichtleere Menge und ${\mathcal {S}}$ eine σ-Algebra über $\Omega$.
Ferner gibt es eine Abbildung $P$ mit

• (1) $P\colon {\mathcal {S}}\to [0,1]$

$E\mapsto P(E)$.

$P$ ordnet jeder Menge $E\in {\mathcal {S}}$ einen Wahrscheinlichkeitswert zu.

• (2) $P(\Omega )=1$. Die Wahrscheinlichkeit, dass ein Buchstabe aus dem Alphabet $\Omega$ stammt, ist 1.
• (3) $\forall E_{n}\in {\mathcal {S}},n\in \mathbb {N} :E_{n}$ paarweise disjunkt $\Rightarrow P(\bigcup _{n\in \mathbb {N} }E_{n})=\sum \limits _{n\in \mathbb {N} }P(E_{n})$
  

Beispiel: Münzwurf (einfaches Werfen mit einer fairen Münze).
$\Omega =\{K,Z\},{\mathcal {S}}=\{\emptyset ,\{K\},\{Z\},\{K,Z\}\}$
Es gilt:

• (1) $P\colon {\mathcal {S}}\to [0,1]$

$\emptyset \mapsto 0$

$\{K\}\mapsto {\frac {1}{2}}$

$\{Z\}\mapsto {\frac {1}{2}}$

$\{K,Z\}\mapsto 1$

• (2) $P(\{K,Z\})=1$
• (3) Es gilt: $\{K\}$ und $\{Z\}$ p.w.d. $\Rightarrow P(\{K\}\cup \{Z\})=P(\{K,Z\})=1={\frac {1}{2}}+{\frac {1}{2}}=P(\{K\})+P(\{Z\})$

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

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

Satz: Träger und Geheimtexte
Sei $A$ das Klartextalphabet und $B$ das Geheimtextalphabet. Ferner sei ein stochastischer Schlüssel
$f\colon A\to _{P}B$

$x\mapsto _{P}(\Omega _{x},{\mathcal {S}}_{x},P_{x})$

gegeben, dann sind alle Geheimtexte aus der Menge $\Omega ^{+}$ mit $\Omega =\bigcup _{x\in A}Tr(P_{x})$.

Beweis: Träger und Geheimtexte
Dem Satz entnehmen wir, $A$ ist das Klartextalphabet und $B$ das Geheimtextalphabet.
Es gilt:

• (1) $\forall x\in A:y\in B\land f(x)=y\land P_{x}(\{y\})>0$ für die Abbildung $P_{x}$
  
• (2) Für den Klartext gilt:
  

$\omega =(\omega _{1},\omega _{2},...,\omega _{n})\in A^{+}$

• (3) Für den Chiffretext gilt:
  

$(f(\omega _{1}),f(\omega _{2}),...,f(\omega _{n}))\in B^{+}$ mit $y_{1}=f(\omega _{1}),y_{2}=f(\omega _{2}),...,y_{n}=f(\omega _{n})$

• (4) Für die Trägermenge gilt:
  

$y_{1}\in Tr(P_{\omega _{1}})\land y_{2}\in Tr(P_{\omega _{2}}),...,\land y_{\omega }\in Tr(P_{\omega _{n}})$

• (5) Daraus Folgt:
  

$\Rightarrow \forall k\in \{1,2,3,...,n\}:y_{k}\in Tr(P_{\omega _{k}})$

$\Rightarrow \forall k\in \{1,2,3,...,n\}:y_{k}\in \bigcup \limits _{i=1}^{n}Tr(P_{\omega _{i}})$

$\Rightarrow \forall k\in \{1,2,3,...,n\}:y_{k}\in \Omega$

$\Rightarrow y=(y_{1},y_{2},y_{3},...,y_{n})\in \Omega ^{+}$

q.e.d.

Satz: Eindeutigkeit der Entschlüsselung mit stochastischen Schlüsseln
Sei $A$ das Klartextalphabet und $B$ das Geheimtextalphabet und
$f\colon A\to _{P}B$

$x\mapsto _{P}(\Omega _{x},{\mathcal {S}}_{x},P_{x}).$

• (1) Die Dechiffrierung ist genau dann eindeutig, wenn die Trägermenge $Tr(P_{x})$ für alle $x\in A$ paarweise disjunkt sind.
• (2) Gilt die Bedingung (1), existiert eine Abbildung

$f^{-1}\colon \Omega \to A$

$x\mapsto f^{-1}(x)$

mit $\Omega :=\bigcup \limits _{x\in A}Tr(P_{x})$ für die Entschlüsselung von Geheimtexten $y=(y_{1},...,y_{n})\in B^{+}$, die mit $f$ verschlüsselt werden.

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

"$\Leftarrow$" Seien für alle $x\in A$ die Trägermengen $Tr(P_{x})$ paarweise disjunkt.

Aus dem Satz für Träger und Geheimtexte folgt

$\forall y=(y_{1},...,y_{n})\in B^{+}:y\in \Omega ^{+}$ mit $\Omega ^{+}=\bigcup \limits _{x\in A}Tr(P_{x})$

$\Rightarrow \forall y_{k},k\in \{1,...,n\}~\exists !~Tr(P_{x_{k}}):y_{k}\in Tr(P_{x_{k}})$

$\Rightarrow \forall y_{k}\in \{1,...,n\}:y_{k}\in \Omega _{x_{k}}$

$\Rightarrow$ Das Klartextzeichen zu $y_{k}$ ist $x_{k}$

Durch den stochastischen Schlüssel entsteht für jedes Klartextzeichen $x_{k}$ der Wahrscheinlichkeitsraum $(\Omega _{x_{k}},S_{x_{k}},P_{x_{k}})$.

"$\Rightarrow$" Sei die Entschlüsselung eindeutig.

Wir nehmen nun an, dass die Trägermengen $Tr(P_{x})$ nicht paarweise disjunkt sind und zeigen, dass dies zum Widerspruch führt.

$\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$

$\Rightarrow y\in Tr(P_{x_{1}})\land y\in Tr(P_{x_{2}})$

Damit ist das $y$ durch Verschlüsselung mit $(\Omega _{x_{1}},S_{x_{1}},P_{x_{1}})$ und $(\Omega _{x_{2}},S_{x_{2}},P_{x_{2}})$ entstanden.

Es ist also nicht möglich dem $y$ eindeutig ein $x\in B$ zuzuordnen.

(2) Für die zweite Aussage zeigen wir nun, dass so eine Abbildung $f^{-1}$ (die jedem verschlüsselten $y\in B$ wieder ein eindeutiges Klartextzeichen
$x\in A$ zuordnet) existiert, falls Bedingung (1) erfüllt ist.

Seien für alle $x\in A$ die Trägermengen $Tr(P_{x})$ paarweise disjunkt und $\Omega :=\bigcup \limits {x\in A}Tr(P_{x})$.

$\Rightarrow \forall y\in \Omega ~\exists !~x\in A~:~y\in Tr(P_{x})$

Definiere also

$f^{-1}:\Omega \rightarrow A,~y\rightarrow x,~$falls$~y\in Tr(P_{x})$

$\Box$

Verschlüsselung beliebiger digitaler Daten

[Verwendung von GNU Octave.]

Definition: p-adisches Stellenwertsystem

Sei $z\in \mathbb {N} _{0}$ gegeben.
$z$ besitzt in dem $p$-adischen Stellenwertsystem die Darstellung $(z_{n},z_{n-1},...,z_{1},z_{0})_{p}$, wenn gilt: $z_{n},z_{n-1},...,z_{1},z_{0}\in \{0,1,...,p-1\}$.
$z=\sum \limits _{k=0}^{\infty }z_{k}\cdot p^{k}$ mit $z_{k}\in \{0,1,...,p-1\}$.

Beispiel: Umrechnung von $43210_{5}$ in das Dezimalsystem

Jede Stelle hat den Wert der entsprechenden Fünferpotenz. Die der ersten Ziffer von rechts entsprechende Potenz ist $5^{0}=1$.
Vorgehen: Multipliziere jede Ziffer mit der entsprechenden Potenz und summiere. Gehe am besten von rechts nach links vor:

$0\cdot 5^{0}+1\cdot 5^{1}+2\cdot 5^{2}+3\cdot 5^{3}+4\cdot 5^{4}$

$=0\cdot 1+1\cdot 5+2\cdot 25+3\cdot 125+4\cdot 625$
$=0+5+50+375+2500$
$=2930$
Ergebnis: $43210_{5}=2930_{10}$

Beispiel: Umrechnung von $375_{10}$ in das Binärsystem

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).
$375:2=187\ Rest\ 1$
$187:2=93\ \ Rest\ 1$
$\ 93:2=46\ \ Rest\ 1$
$\ 46:2=23\ \ Rest\ 0$
$\ 23:2=11\ \ Rest\ 1$
$\ 11:2=5\ \ \ Rest\ 1$
$\ \ 5:2=2\ \ \ Rest\ 1$
$\ \ 2:2=1\ \ \ Rest\ 0$
$\ \ 1:2=0\ \ \ Rest\ 1$
Ergebnis: $375_{10}=101110111_{2}$

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

Definition: Kodierung reeller Zahlen im p-adischen Stellenwertsystem

Sei $z\in \mathbb {R} ^{+}$ gegeben.
$(z_{n},z_{n-1},...,z_{1},z_{0},z_{-1},z_{-2},...)_{p}$ stellt die Zahl $z$ wie folgt dar:
$z=\sum \limits _{k=-\infty }^{n}z_{k}\cdot p^{k}$ mit $z_{k}\in \{0,1,...,p-1\}$.

Verschlüsseln von digitalen Bytefolgen

Bilder

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

Beispiel zur Verschlüsselung digitaler Daten: Bildverschlüsselung

Texte

Die Zuordnung von Buchstaben und Sonderzeichen (Alphabet $B$) nach ${\tilde {A}}$ erfolgt über eine bijektive Abbildung (Schlüssel):
$f:B\rightarrow {\tilde {A}}$

$z\mapsto f(z)$

Bei diesem bijektiven Schlüssel geht es nicht um Geheimhaltung, sondern um Standardisierung.
Beispiel: ASCII-Code.

Audio

Definition: Digitalisierung eines Audiosignals

Sei $f:[a,b]\rightarrow [c,d]$ ein analoges Audiosignal und $(x_{1},...,x_{n})$ eine äquidistante Unterteilung von $[a,b]$ mit $x_{1}=a$ und $x_{n}=b$.
$(f(x_{1}),...,f(x_{n}))\in [c,d]^{n}$
Ferner sei $(y_{1},...,y_{n})$ eine äquidistante Unterteilung von $[c,d]$ mit $f(x_{1}),...,f(x_{n})\in \{y_{1},...,y_{n}\}$.

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.

Überprüfung über die Quersumme - Übermittlung mit digitaler Unterschrift

Definition: Gewichtete Quersumme

Sei $a=(a_{1},...,a_{n})\in \mathbb {N} _{0}^{n}$ ein Tupel aus natürlichen Zahlen. $r=(r_{1},...,r_{n})\in \mathbb {R} ^{n}$.
$\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)$ nennt man gewichtete Quersumme mit $r\in \mathbb {R} ^{n}$.

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.

Definition: Gewichtete Quersumme für Restklassen

Sei $(z_{n},...,z_{0})\in (0,...,p-1)^{n+1}$ sei eine Ziffernfolge im p-adischen System. $r_{n}:=p^{n}\mod m$ mit $r_{n}\in \{0,...,m-1\}$.
${\tilde {r}}=\sum \limits _{k=0}^{n}r_{k}\cdot z_{k}\mod m$ mit ${\tilde {r}}\in \{0,...,n-1\}$.
$\sum \limits _{k=0}^{n}r_{k}\cdot z_{k}$ ist die gewichtete Quersumme bei Division durch $m$.
${\tilde {r}}$ ist die digitale Unterschrift für $(z_{n},...,z_{0})$ mit Schlüssel $m\in \mathbb {N} ,m>1$.
Die Gewichte der Quersumme sind periodisch.

Satz: Perioden in Quersummenregeln

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

Beweis: Perioden in Quersummenregeln
Seien $r_{0},r_{1},...,r_{m-1}$ die ersten m Reste aus $(r_{k})_{k\in \mathbb {N} _{0}}$.
Bei der Division durch m muss mindestens bei m+1 ein Rest doppelt auftreten, da die Anzahl der Reste endlich ist. Reste $({0,1,...,m-1})$.
Ohne Einschränkung gelte: $r_{m}=r_{i}$. mit $\displaystyle {i}\in \{0,...,m-1\}$.
(Wir gehen einfach davon aus, dass dieser Rest doppelt vorkommt.)

$r_{0},r_{1},...,r_{i},r_{i+1},...,r_{m-1},r_{m},r_{m+1},...$.
$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$.

Man erhält mit $r_{i+1}=r_{m+1}$ auch $r_{i+2}=r_{m+2}$.

$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$.

Man erhält sukzessiv:
$r_{0},r_{1},...,r_{i},r_{i+1},...,r_{m-1},r_{m},r_{m+1},...,r_{2m-1},r_{2m},...$.
$r_{i+k}\equiv r_{m+k}$ für alle ${k\in \mathbb {N} _{0}}$.

Damit haben wir eine Periode der Länge $l\leq m-i$.
q.e.d.

Asymmetrische Verschlüsselung

Definition: Public-Key-Kryptosystem oder Asymmetrisches Kryptosystem

In einem Public-Key-Kryptosystem hat jeder Teilnehmer $T$ ein Paar von Schlüsseln:

• einen öffentlichen Schlüssel $E:=E_{T}$ zur Verschlüsselung und
• einen privaten Schlüssel $D:=D_{T}$ zum Entschlüsseln,

die sich durch folgende entscheidende Public-Key-Eigenschaft auszeichnen:
Aus der Kenntnis des öffentlichen Schlüssels $E_{T}$ ist der private Schlüssel $D_{T}$ nicht zu erschließen.

Definition: Public-Key-Verschlüsselungssystem

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

Der RSA-Algorithmus

Das Verfahren

Beispiel:

(1) Schlüsselerzeugung

(a)   p = 11 ; q = 13

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

(c)   $\varphi$(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 $\varphi$(N)

Ziel: 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 $\equiv$   Ke mod N  $\equiv$  723 mod 143
                        $\equiv$  721 · 72 mod 143
                        $\equiv$  (77)3 · 72 mode 143
                        $\equiv$  63 · 72 mod 143
                        $\equiv$  73 · 49 mod 143
                        $\equiv$  2 mod 143

(3) Entschlüsseln der Geheimbotschaft c = 2

           K $\equiv$  cd mod N $\equiv$  247 mod 143
                         $\equiv$  2(6 · 7) · 25 mod 143
                         $\equiv$  7 mod 143

Die Mathematik hinter dem RSA-Algorithmus

Definition: Eulersche $\varphi$-Funktion

$\varphi (n):=|G_{n}|$ mit $G_{n}:=\{k\in \mathbb {N} \mid ggT(n,k)=1,k\leq n\}$.
$\varphi (n)$ gibt die Menge aller Zahlen $k\in \mathbb {N}$ mit $k\leq n$ an, die teilerfremd zu $n$ sind.

Satz: $\varphi$-Funktion und Primzahlen
b Sei $p\in \mathbb {N}$ eine Primzahl ($p\in \mathbb {P}$), dann gilt: $\varphi (p)=p-1$.

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

Satz: Multiplikativitätssatz der $\varphi$-Funktion

Seien $p,q\in \mathbb {P}$ gegeben, dann gilt $\varphi (p\cdot q)=\varphi (p)\cdot \varphi (q)$.

Beweis: z.Z.: Seien $p,q\in \mathbb {P}$ Primzahlen: $\varphi (p\cdot q)=\varphi (p)\cdot \varphi (q)$.

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

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

Es gilt $pq\notin G_{pq}$, da $ggT(pq,pq)=pg\neq 1$.

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

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

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

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

Dabei kommt keine Zahl doppelt vor.

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

Durch Umformung ergibt sich nun: $\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)$

Definition: Gruppe

Eine Gruppe ist ein Paar $(G,*)$ bestehend aus einer Menge $G$ und einer (inneren) Verknüpfung $*$ auf $G$.
Das heißt, durch $*$ wird die Abbildung $*\colon G\times G\to G,(a,b)\mapsto a*b$ beschrieben.
Erfüllt die Verknüpfung die folgenden Axiome, dann wird $(G,*)$ Gruppe genannt:

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

Definition: Abelsche Gruppe

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

• (KG) Für alle Gruppenelemente $a$ und $b$ gilt $a*b=b*a$.
  

Definition: Potenzen in Gruppen

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

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

oder

Sei $(G,*)$ eine Gruppe und $U$ eine nicht leere Teilmenge von $G$.
$(U,*)$ heißt Untergruppe von $(G,*)$ $:\Leftrightarrow$

• (IV) Durch $*$ wird die Abbildung $*\colon U\times U\to U,(a,b)\mapsto a*b$ beschrieben.
• (AG) Für alle Gruppenelemente $a$, $b$ und $c$ gilt: $(a*b)*c=a*(b*c).$
• (NE) Es gibt ein neutrales Element $e\in U$, mit dem für alle Gruppenelemente $a\in U$ gilt: $a*e=e*a=a$.
• (IE) Zu jedem Gruppenelement $a\in U$ existiert ein inverses Element $a^{-1}\in U$ mit $a*a^{-1}=a^{-1}*a=e$.
  

Satz: Neutrales Element der Untergruppe
Wenn $(U,*)$ Untergruppe der Gruppe $(G,*)$ ist, dann besitzt $(U,*)$ das gleiche neutrale Element $e$ wie $(G,*)$.

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

Satz von Euler bzw. kleiner Satz von Fermat
Seien $m,n\in \mathbb {N}$ gegeben mit $ggT(m,n)=1$.
Dann gilt: $m^{\varphi (n)}\equiv 1\mod n$

Satz Gruppe bezüglich $\varphi (n)$
Sei $n\in \mathbb {N} ,n\geq 1$ gegeben.
$(R_{n},\cdot )$ sei das multiplikative Verknüpfungsgebilde der Restklassen
$R_{n}=\{{\bar {0}}_{n},{\bar {1}}_{n},...,{\overline {n-1}}_{n}\}$, dann gilt:
$R_{n}^{*}=\{{\bar {z}}_{n}\mid z\in T_{n}=\{z\in \mathbb {N} \mid (z\leq n)\wedge ggT(z,n)=1\}\}$
ist eine abelsche Gruppe mit $\varphi (n)$ Elementen.
Die abelsche Gruppe $(R_{n},\cdot )$ nennt man reduziertes Restsystem.

Beweis:
z.z.: $(R_{n}^{*},\cdot )$ ist eine abelsche Gruppe.

• (IV) z.z.: Durch $\cdot$ wird die Abbildung $\cdot \colon R_{n}^{*}\times R_{n}^{*}\to R_{n}^{*},(a,b)\mapsto a\cdot b$ beschrieben mit $a:={\bar {a}}_{n}$ und $b:={\bar {b}}_{n}$.

Es muss also gezeigt werden: $a\cdot b={\bar {a}}_{n}\cdot {\bar {b}}_{n}=({\overline {a\cdot b}})_{n}\in R_{n}^{*}$.

Vorüberlegungen:

• Ohne Einschränkung können wir später für $a\cdot b$ einen Repräsentanten aus $\{0,...,n-1\}$ wählen.
  
• Zu zeigen ist: $ggT(a,n)=1\wedge ggT(b,n)=1\Rightarrow ggT(a\cdot b,n)=1$, bzw. dass für $a\cdot b=k\cdot n+r$ gilt: $ggT(r,n)=1$, denn dann gilt ${\bar {r}}_{n}\in R_{n}^{*}$.
  
• $M_{T}(a)=\{t\in \mathbb {N} \mid t|a\}$ (Teilermenge von $a$). $M_{T}(b)\cap M_{T}(n)=\{1\}=M_{T}(a)\cap M_{T}(n)$.
• $a\cdot b$ kann auch keine gemeinsamen Teiler mit $n$ besitzen, da $M_{T}(a),M_{T}(b)\subseteq M_{T}(a\cdot b)$
  

• (AG) z.z.: Für alle Gruppenelemente $a,b,c\in R_{n}^{*}$ gilt: $(a\cdot b)\cdot c=a\cdot (b\cdot c).$

Das Assoziativgesetz ist in $(R_{n}^{*},\cdot )$ erfüllt, weil es in der Gruppe $(R_{n},\cdot )$ gilt.

• (KG) z.z.: Für alle Gruppenelemente $a,b\in R_{n}^{*}$ gilt: $a\cdot b=b\cdot a.$

Das Kommutativgestetz ist in $(R_{n}^{*},\cdot )$ erfüllt, weil es in der abelschen Gruppe $(R_{n},\cdot )$ gilt.

• (NE) z.z.: Es gibt ein neutrales Element $e\in R_{n}^{*}$, mit dem für alle Gruppenelemente $a\in R_{n}^{*}$ gilt: $a\cdot e=e\cdot a=a$.

Sei $e={\bar {1}}_{n}$. Es gilt: $a\cdot e={\bar {a}}_{n}\cdot {\bar {1}}_{n}={\bar {1}}_{n}\cdot {\bar {a}}_{n}={\bar {a}}_{n}=a$ und ${\bar {1}}_{n}\in R_{n}^{*}$, da $ggT(1,n)=1$.

• (IE) z.z.: Zu jedem Gruppenelement $a\in R_{n}^{*}$ existiert ein inverses Element $a^{-1}\in R_{n}^{*}$ mit $a\cdot a^{-1}=a^{-1}\cdot a=e$.

Da $ggT(a,n)=1$ für ${\bar {a}}_{n}\in R_{n}^{*}$, kann man ein modulares Inverses $a^{-1}$ bestimmen mit $ggT(a^{-1},n)=1$, also $a^{-1}\in R_{n}^{*}$, und $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}$.

Insgesamt ist $(R_{n}^{*},\cdot )$ ist eine abelsche (multiplikative) Gruppe.

Bemerkung: $R_{n}^{*}$ hängt mit $T_{n}$ wie folgt zusammen: $T_{n}$ ist ein Repräsentantensystem für $R_{n}^{*}$.

Definition: Repräsentantensystem
Sei $z,n>1$ mit $n\in \mathbb {N}$ gegeben.
Wir betrachten die Restklassen $R_{n}\mod n$.
Sei $T^{*}\subseteq R_{n}$ und $T\subseteq \mathbb {Z}$.
$T$ heißt Repräsentantensystem von $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})$.
Damit gilt insgesamt $\varphi (n)=|R_{n}^{*}|,R^{*}$ Gruppe.

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

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

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

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

Satz: Lagrange
Sei $(G,*)$ eine abelsche Gruppe und $U$ eine Untergruppe von $G$, dann gilt:
$|U|\mid |G|$

Beweis:

Idee: Disjunkte Zerlegung von $G$ in gleichmächtige Mengen.

• Zerlegung von $G$ in Teilmengen durch die Zerlegung in Nebenklassen

Wir betrachten die Nebenklassen $a*U$ mit $a\in G$ und $U$ Untergruppe von $G$.

z.z.: $\bigcup \limits _{a\in G}a*U=G$

Beweis:

• "$\subseteq$":

$a*U=\{\underbrace {a*u} _{\in G}\mid u\in U\}\subseteq G$

Da jede Nebenklasse eine Teilmenge von $G$ ist, ist auch die Vereinigung der Nebenklassen $\bigcup \limits _{a\in G}a*U$ eine Teilmenge von $G$.

• "$\supseteq$":

Sei $e\in G$ das neutrale Element von $G$.

$\Rightarrow e\in U$, da $U$ die Untergruppe von $G$ ist.

${\tilde {a}}={\tilde {a}}*e\in {\tilde {a}}*U$.

Damit ist jedes beliebige ${\tilde {a}}\in G$ ein Element von ${\tilde {a}}*U\subseteq \bigcup \limits _{a\in G}a*U=G$.

Damit wissen wir, dass wir $G$ in die Nebenklassen $a*U$ zerlegen können.

• Zerlegung von $G$ in paarweise disjunkte Nebenklassen

Seien $T_{a}=a*U$ und $T_{b}=b*U$ mit $a,b\in G$ beliebig gewählte Nebenklassen.

z.z: $T_{a}\neq T_{b}\Rightarrow T_{a}\cap T_{b}=\emptyset$

Beweis:

Sei $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})$.

Wir zeigen nun, dass $a*U=b*U$.

• "$\subseteq$":

Sei $u\in U$ beliebig gewählt mit $a*u\in a*U$.

Mit $a*u_{1}=s=b*u_{2}$ gilt $a=(b*u_{2})*u_{1}^{-1}=b*(u_{2}*u_{1}^{-1})$.

Da $(U,*)$ eine Untergruppe von $(G,*)$ ist, gilt mit $u_{1}\in U$ auch $u_{1}^{-1}\in U$.

Ferner gilt auch $u_{2}*u_{1}^{-1}\in U$, weil $*$ einen innere Verknüpfung in $(U,*)$.

$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$.

• "$\supseteq$":

Sei $u\in U$ beliebig gewählt mit $b*u\in b*U$.

Mit $a*u_{1}=s=b*u_{2}$ gilt $a=(a*u_{1})*u_{2}^{-1}=a*(u_{1}*u_{2}^{-1})$.

Analog gilt auch $u_{1}*u_{2}^{-1}\in U$ wegen der Untergruppeneigenschaft von $(U,*)$.

$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$.

Insgesamt gilt also $a*U=b*U$, da wir beide Teilmengenbeziehungen $a*U\subseteq b*U$ und $a*U\supseteq b*U$ gezeigt haben.

Insbesondere heißt das für die Nebenklassen $a*U$, dass zwei Nebenklassen entweder gleich oder disjunkt sind.

• Zerlegung von $G$ in paarweise disjunkte gleichmächtige Nebenklassen

Wir definieren eine bijektive Abbildung zwischen $U$ und einer beliebigen Nebenklasse $a*U$:

$\varphi :U\rightarrow a*U;u\mapsto a*u,a\in G$ beliebig gewählt.

z.z.: $\varphi \ surjektiv\wedge \ \varphi \ injektiv$

• $\varphi \ surjektiv$:

z.z: $\forall y\in a*U\exists x\in U:\varphi (x)=y$

Sei $y\in a*U$ beliebig gewählt.

$\Rightarrow \exists u_{y}\in U:y=a*u_{y}$

$\Rightarrow \exists (x:=u_{y})\ wedge(\varphi (x)=\varphi (u_{y})=a*u_{y}=y)$

• $\varphi \ injektiv$:

z.z: $\forall x_{1},x_{2}\in U:\varphi (x_{1})=\varphi (x_{2})\Rightarrow x_{1}=x_{2}$

Seien $x_{1},x_{2}\in U$ so gewählt, dass $varphi(x_{1})=\varphi (x_{2})$ gilt.

$\Rightarrow varphi(x_{1})=a*x_{1}=a*x_{2}=varphi(x_{2})$

$\Rightarrow a*x_{1}=a*x_{2}$ mit $a\in G$ und $a^{-1}\in G$, da $(G,*)$ Gruppe.

$\Rightarrow a^{-1}*(a*x_{1})=a^{-1}*(a*x_{2})$

${\stackrel {AG}{\Rightarrow }}(a^{-1}*a)*x_{1}=(a^{-1}*a)*x_{2}$

${\stackrel {IE}{\Rightarrow }}e*x_{1}=e*x_{2}$

${\stackrel {NE}{\Rightarrow }}x_{1}=x_{2}$

Also ist $\varphi$ auch injektiv.

• Untersuchung der Teilbarkeitseigenschaften

Wir suchen nun ein Repräsentantensystem $V$ für die Faktorgruppe $G/U=\{a*U\mid a\in G\}$.

Für $V$ $(a,b\in V)\wedge (a\ neqb)\Rightarrow a*U\neq b*U$

$G/U=\{a*U\mid a\in V\}$

Wir benötigen das Repräsentantensystem, damit wir Nebenklassen nicht mehrfach zählen.

• Sei $|G|=\infty \wedge |U|\geq 1\wedge |U|<\infty$.

$\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|$.

Mit $|G|=\infty$ gilt auch $|V|=\infty$ und somit $|G|=|V|\cdot |U|=\infty$.

Mit $|G|=\infty$ und $|U|=\infty$ gilt insbesondere $|V|\geq 1$, da es mindestens eine Nebenklasse $e*U$ gibt, $e$ neutrales Element in $G$.

Damit gilt auch $|G|=|U|\cdot |V|=\infty$.

• Für endliche Gruppen gilt:

$k=|G|\geq |U|>1,|G|\geq |V|\geq 1$.

$|G|=|\bigcup \limits _{a\in V}a*U|=\sum \limits _{a\in V}|a*U|=\sum \limits _{a\in V}|U|=|V|\cdot |U|$

$\Rightarrow |U|||G|$.

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

Beweis:
z.z.: $m^{e\cdot d}\mod n\equiv m\mod n$.

$m^{e\cdot d}\mod n$

$\equiv m^{1+k\cdot \varphi (n)}\mod n$
$\equiv m^{1}\cdot m^{k\cdot \varphi (n)}\mod n$
$\equiv m^{1}\cdot (m^{\varphi (n)})^{k}\mod n$
$\equiv m\cdot ((m^{Ord(m)})^{\frac {\varphi (n)}{Ord(m)}})^{k}\mod n$
$\equiv m\cdot (1^{\frac {\varphi (n)}{Ord(m)}})^{k}\mod n$
$\equiv m\cdot 1^{k}\mod n$
$\equiv m\mod n$

Grundlegende Definitionen

Definition: Relation

Eine Relation $R$ zwischen zwei Mengen $A$ und $B$ ist eine Teilmenge des kartesischen Produkts $A\times B=\{(a,b)\mid a\in A,b\in B\}\colon$

$R\subseteq A\times B.$

Definition: Äquivalenzrelation

Eine Äquivalenzrelation auf einer Menge $M$ ist eine Teilmenge $R\subseteq M\times M$, welche folgende Bedingungen erfüllt:

• Reflexivität: Für alle $a\in M$ ist $(a,a)\in R$.
• Symmetrie: Für alle $a,b\in M$, für die $(a,b)\in R$ gilt, ist auch $(b,a)\in R$.
• Transitivität: Für alle $a,b,c\in M$ mit $(a,b)\in R$ und $(b,c)\in R$ gilt, dass auch $(a,c)\in R$.
  

Definition: Äquivalenzklasse

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

Definition: Teilbarkeit

$a|b\Leftrightarrow \exists k\in \mathbb {Z} :b=k\cdot a.$

Definition: Kongruenzrelation

Für $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$ wird definiert:
$a\equiv b\mod m:\Leftrightarrow m|(a-b).$

Satz: Kongruenzrelation

Es gilt: $a\equiv b\mod m\Leftrightarrow \exists q\in \mathbb {Z} :a=b+q\cdot m.$

Definition: Restklasse

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

Allgemeine Formel für Modulo-Rechnungen

Abbildung Formel_für_Modulo-Rechnen.png

Quellen zu Kryptologie im Schulunterricht

• Schriftliche Ausarbeitung einer Unterrichtsreihe zum Thema Kryptologie (von Mina Ghomi)
• Codes und Verschlüsselungen integrativ im Mathematikunterricht: Vorschlag für ein Curriculum (von Thomas Borys)
• Codierungen im Spiegel der fundamentalen Ideen der Mathematik (von Thomas Borys)
• Welche Vernetzungsmöglichkeiten bietet die Kryptologie? (von Thomas Borys)
• Zauberhogwarts

Lernen durch Autorentätigkeit

Diese Seite entsteht nach dem Prinzip Lernen durch Autorentätigkeit in Wikiversity (siehe Learner being an Author).