Kryptologie - Mathematische Vertiefung (PH Freiburg SS 2017)

Aus Wikiversity
Zur Navigation springen Zur Suche springen

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.[1]

Mindmap mit Inhalten der Kryptologie
Definition: Text/ Nachricht ist ein Alphabet.
ist das -fache kartesische Produkt des Alphabets
sind die Nachrichtentexte der Länge .

sind alle Nachrichten aus Buchstaben des Alphabets .


Definition: Bijektiver Schlüssel
sind Alphabete. ist eine bijektive Abbildung.
Dann nennt man einen bijektiven Schlüssel für Nachrichten aus .


Bijektivität[Bearbeiten]

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 gegeben. Unter einer Abbildung von nach verstehen wir eine Vorschrift, die jedem Element genau ein Element zuordnet:


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

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

  • injektiv.
  • surjektiv.
  • bijektiv ist injektiv und ist surjektiv.

Symmetrische Verschlüsselung[Bearbeiten]

Definition: Symmetrische Verschlüsselung
Sender und Empfänger haben den gleichen Schlüssel.

Substitutionsalgorithmen[Bearbeiten]

Bei einem Substitutionsalgorithmus oder Verschiebechiffre behält jeder Buchstabe seine Position, wird aber durch einen anderen ersetzt.

Monoaplhabetische Substitution[Bearbeiten]

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 .
Die Caesar-Verschlüsselung ist ein Sonderfall der einfachen monoalphabetischen Substitution.

Caesar-Verschlüsselung[Bearbeiten]

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 und ein Geheimtextalphabet und es gilt . Die Mächtigkeit ist die Anzahl aller Elemente des Alphabets . Man nummeriert jedes Element des Alphabets mit den natürlichen Zahlen von bis mit Hilfe folgender Abbildung:





Bei der Caesar-Verschlüsselung handelt es sich um eine bijektive Abbildung

,

wobei der Schlüssel ist.
Entschlüsselt wird mit der Umkehrabbildung von .

,

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

Transpositionschiffre[Bearbeiten]

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[Bearbeiten]

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 . Die Positionen der Buchstaben sind bei Transpositionschiffren wichtig, die Positionen im Klartext stammen aus der Menge und sind folgendermaßen nummeriert: . Sei nun der Umfang des Stabs, der durch die Anzahl der Zeilen des Geheimtextes bestimmt wird und die Länge der Nachricht, wenn sie um den Stab gewickelt ist, die durch die Anzahl der Spalten des Geheimtextes bestimmt wird. Es gilt Dann wird durch folgende Abbildung verschlüsselt:


Entschlüsselt wird wiederum mit der Umkehrabbildung .

Gartenzaun-Chiffre[Bearbeiten]

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 . Die Positionen der Buchstaben sind bei Transpositionschiffren wichtig, die Positionen im Klartext stammen aus der Menge und sind folgendermaßen nummeriert (wir legen fest, dass unser Gartenzaun mit variabler Höhe und Anzahl der Spitzen und Täler mit stets folgende Form hat):

Form des Gartenzauns


Dann wird durch folgende Abbildung verschlüsselt:


Entschlüsselt wird wiederum mit der Umkehrabbildung .

Kryptoanalyse[Bearbeiten]

Systematische Schlüsselsuche[Bearbeiten]

Jeder Verschlüsselungsalgorithmus kann durch eine systematische Anwendung möglicher Schlüssel auf den Geheimtext gebrochen werden. Bei einer Anzahl von möglichen Schlüsseln, benötigt man höchstens Versuche, durchschnittlich allerdings nur Versuche. Je größer die Anzahl der möglichen Schlüssel, umso schwerer ist ein Verschlüsselungsalgorithmus zu knacken.


Statistische Analyse[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Verschlüsseln mit Zufallsexperimenten[Bearbeiten]


Beispiel:
Gegeben sei das Klartextalphabet und der Klartext .
Das Häufigkeitsprofil dieses Textes sieht folgendermaßen aus:

Buchstabe Häufigkeit
A
N
S


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 und der Schlüssel zur Verschlüsselung des Klartextes sei folgendermaßen definiert:

Klartextbuchstabe Menge der zugeordneten Geheimtextbuchstaben Anzahl der zugeordneten Geheimalphabetbuchstaben Anteil
A
N
S


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


Definition: σ-Algebra
Sei eine nichtleere Menge und sei die Potenzmenge dieser Menge.

Ein Mengensystem , also eine Menge von Teilmengen von , heißt σ-Algebra (auf oder über ), wenn es die folgenden drei Bedingungen erfüllt:

  • (1) enthält die Grundmenge. Es gilt also
  • (2) ist stabil bezüglich der Komplementbildung. Ist also , so ist auch in enthalten.
  • (3) ist stabil bezüglich abzählbarenVereinigungen. Sind also Mengen
in enthalten, so ist auch in enthalten.


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

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



Definition: Wahrscheinlichkeitsraum
Sei (ein Alphabet) eine nichtleere Menge und eine σ-Algebra über .
Ferner gibt es eine Abbildung mit

  • (1)
.
ordnet jeder Menge einen Wahrscheinlichkeitswert zu.
  • (2) . Die Wahrscheinlichkeit, dass ein Buchstabe aus dem Alphabet stammt, ist 1.
  • (3) paarweise disjunkt



Beispiel: Münzwurf (einfaches Werfen mit einer fairen Münze).

Es gilt:

  • (1)




  • (2)
  • (3) Es gilt: und p.w.d.


Definition: Trägermenge, Wahrscheinlichkeitsverteilung
Sei ein diskreter Wahrscheinlichkeitsraum, dann definiert man den Träger wie folgt: .


Beispiel: Münzwurf (einfaches Werfen mit einer fairen Münze).
Sei mit , R: Rand der Münze. Dann ist .


Satz: Träger und Geheimtexte
Sei das Klartextalphabet und das Geheimtextalphabet. Ferner sei ein stochastischer Schlüssel


gegeben, dann sind alle Geheimtexte aus der Menge mit .

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

  • (1) für die Abbildung
  • (2) Für den Klartext gilt:
  • (3) Für den Chiffretext gilt:
mit
  • (4) Für die Trägermenge gilt:
  • (5) Daraus Folgt:




q.e.d.

Satz: Eindeutigkeit der Entschlüsselung mit stochastischen Schlüsseln
Sei das Klartextalphabet und das Geheimtextalphabet und


  • (1) Die Dechiffrierung ist genau dann eindeutig, wenn die Trägermenge für alle paarweise disjunkt sind.
  • (2) Gilt die Bedingung (1), existiert eine Abbildung

mit für die Entschlüsselung von Geheimtexten , die mit 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.

"" Seien für alle die Trägermengen paarweise disjunkt.

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


Das Klartextzeichen zu ist
Durch den stochastischen Schlüssel entsteht für jedes Klartextzeichen der Wahrscheinlichkeitsraum .

"" Sei die Entschlüsselung eindeutig.

Wir nehmen nun an, dass die Trägermengen nicht paarweise disjunkt sind und zeigen, dass dies zum Widerspruch führt.


Damit ist das durch Verschlüsselung mit und enstanden.
Es ist also nicht möglich dem eindeutig ein zuzuordnen.


(2) Für die zweite Aussage zeigen wir nun, dass so eine Abbildung (die jedem verschlüsselten wieder ein eindeutiges Klartextzeichen
zuordnet) existiert, falls Bedingung (1) erfüllt ist.

Seien für alle die Trägermengen paarweise disjunkt und .

Definiere also
falls

Verschlüsselung beliebiger digitaler Daten[Bearbeiten]

[Verwendung von GNU Octave.]


Definition: p-adisches Stellenwertsystem

Sei gegeben.
besitzt in dem -adischen Stellenwertsystem die Darstellung , wenn gilt: .
mit .


Beispiel: Umrechnung von in das Dezimalsystem

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





Ergebnis:


Beispiel: Umrechnung von 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).









Ergebnis:


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 gegeben.
stellt die Zahl wie folgt dar:
mit .


Verschlüsseln von digitalen Bytefolgen[Bearbeiten]

Bilder[Bearbeiten]

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[Bearbeiten]

Die Zuordnung von Buchstaben und Sonderzeichen (Alphabet ) nach erfolgt über eine bijektive Abbildung (Schlüssel):


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

Audio[Bearbeiten]

Definition: Digitalisierung eines Audiosignals

Sei ein analoges Audiosignal und eine äquidistante Unterteilung von mit und .

Ferner sei eine äquidistante Unterteilung von mit .


Videos[Bearbeiten]

Video entsteht aus einer Folge von Einzelbildern und einem Audiosignal.


Integrität von Daten[Bearbeiten]

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 ein Tupel aus natürlichen Zahlen. .
nennt man gewichtete Quersumme mit .

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 sei eine Ziffernfolge im p-adischen System. mit .
mit .
ist die gewichtete Quersumme bei Division durch .
ist die digitale Unterschrift für mit Schlüssel .
Die Gewichte der Quersumme sind periodisch.


Satz: Perioden in Quersummenregeln

Sei .
(Rest, den die Bündelungseinheit bei Division durch lässt.)
Dann gibt es ab einer bestimmten Indexschranke eine Periode in der Folge der .


Beweis: Perioden in Quersummenregeln
Seien die ersten m Reste aus .
Bei der Division durch m muss mindestens bei m+1 ein Rest doppelt auftreten, da die Anzahl der Reste endlich ist. Reste .
Ohne Einschränkung gelte: . mit .
(Wir gehen einfach davon aus, dass dieser Rest doppelt vorkommt.)

.
.

Man erhält mit auch .

.

Man erhält sukzessiv:
.
für alle .

Damit haben wir eine Periode der Länge .
q.e.d.

Asymmetrische Verschlüsselung[Bearbeiten]

Definition: Public-Key-Kryptosystem oder Asymmetrisches Kryptosystem

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

  • einen öffentlichen Schlüssel zur Verschlüsselung und
  • einen privaten Schlüssel zum Entschlüsseln,

die sich durch folgende entscheidende Public-Key-Eigenschaft auszeichnen:
Aus der Kenntnis des öffentlichen Schlüssels ist der private Schlüssel 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 gilt:
Wenn ist, dann gilt , d.h. .
Die mit verschlüsselte Nachricht wird mittels wieder korrekt entschlüsselt.

Der RSA-Algorithmus[Bearbeiten]

Das Verfahren[Bearbeiten]

Beispiel:

(1) Schlüsselerzeugung

(a)   p = 11 ; q = 13
(b)   N = p · q = 11 · 13 = 143
(c)   (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 (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    Ke mod N    723 mod 143
                          721 · 72 mod 143
                          (77)3 · 72 mode 143
                          63 · 72 mod 143
                          73 · 49 mod 143
                          2 mod 143

(3) Entschlüsseln der Geheimbotschaft c = 2

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

Die Mathematik hinter dem RSA-Algorithmus[Bearbeiten]

Definition: Eulersche -Funktion

mit .
gibt die Menge aller Zahlen mit an, die teilerfremd zu sind.


Satz: -Funktion und Primzahlen
b Sei eine Primzahl (), dann gilt: .

Beweis: -Funktion und Primzahlen
z.Z. =|
In können , also mögliche Zahlen liegen.
:={, }
Es gilt: , da (für ) gilt.
, da für alle gilt:
Für alle gilt ebenfalls , denn sonst wäre keine Primzahl und hätte den Teiler mit
Also gilt:


Satz: Multiplikativitätssatz der -Funktion

Seien gegeben, dann gilt .

Beweis: z.Z.: Seien Primzahlen: .

In können nur die Elemente also Elemente enthalten sein .

Nun schließen wir aus dieser Menge Elemente aus, die nicht in enthalten sein können:

Es gilt , da .

Es bleiben als mögliche Zahlen

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

also nicht Teilerfremde Zahlen aus

also nicht Teilerfremde Zahlen aus

Dabei kommt keine Zahl doppelt vor.

Damit folgt für die Anzahl der Elemente in .

Durch Umformung ergibt sich nun:


Definition: Gruppe

Eine Gruppe ist ein Paar bestehend aus einer Menge und einer (inneren) Verknüpfung auf .
Das heißt, durch wird die Abbildung beschrieben.
Erfüllt die Verknüpfung die folgenden Axiome, dann wird Gruppe genannt:[2]

  • (AG) Für alle Gruppenelemente , und gilt:
  • (NE) Es gibt ein neutrales Element , mit dem für alle Gruppenelemente gilt: .
  • (IE) Zu jedem Gruppenelement existiert ein inverses Element mit .


Definition: Abelsche Gruppe

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

  • (KG) Für alle Gruppenelemente und gilt .


Definition: Potenzen in Gruppen

Sei eine Gruppe. Dann definiert man:
für .
für .


Definition: Untergruppe
Sei eine Gruppe.
heißt Untergruppe von .

oder

Sei eine Gruppe und eine nicht leere Teilmenge von .
heißt Untergruppe von

  • (IV) Durch wird die Abbildung beschrieben.
  • (AG) Für alle Gruppenelemente , und gilt:
  • (NE) Es gibt ein neutrales Element , mit dem für alle Gruppenelemente gilt: .
  • (IE) Zu jedem Gruppenelement existiert ein inverses Element mit .


Satz: Neutrales Element der Untergruppe
Wenn Untergruppe der Gruppe ist, dann besitzt das gleiche neutrale Element wie .


Definition: Faktorgruppe
Sei eine Gruppe und eine Untergruppe von , dann nennt man Faktorgruppe (mit kommutativ). Die Faktorgruppe enthält folgende Elemente:
.
nennt man Nebenklasse von .


Satz von Euler bzw. kleiner Satz von Fermat
Seien gegeben mit .
Dann gilt:


Satz Gruppe bezüglich
Sei gegeben.
sei das multiplikative Verknüpfungsgebilde der Restklassen
, dann gilt:

ist eine abelsche Gruppe mit Elementen.
Die abelsche Gruppe nennt man reduziertes Restsystem.

Beweis:
z.z.: ist eine abelsche Gruppe.

  • (IV) z.z.: Durch wird die Abbildung beschrieben mit und .
Es muss also gezeigt werden: .
Vorüberlegungen:
  • Ohne Einschränkung können wir später für einen Repräsentanten aus wählen.
  • Zu zeigen ist: , bzw. dass für gilt: , denn dann gilt .
  • (Teilermenge von ). .
  • kann auch keine gemeinsamen Teiler mit besitzen, da
  • (AG) z.z.: Für alle Gruppenelemente gilt:
Das Assoziativgesetz ist in erfüllt, weil es in der Gruppe gilt.
  • (KG) z.z.: Für alle Gruppenelemente gilt:
Das Kommutativgestetz ist in erfüllt, weil es in der abelschen Gruppe gilt.
  • (NE) z.z.: Es gibt ein neutrales Element , mit dem für alle Gruppenelemente gilt: .
Sei . Es gilt: und , da .
  • (IE) z.z.: Zu jedem Gruppenelement existiert ein inverses Element mit .
Da für , kann man ein modulares Inverses bestimmen mit , also , und .

Insgesamt ist ist eine abelsche (multiplikative) Gruppe.


Bemerkung: hängt mit wie folgt zusammen: ist ein Repräsentantensystem für .


Definition: Repräsentantensystem
Sei mit gegeben.
Wir betrachten die Restklassen .
Sei und .
heißt Repräsentantensystem von .
Damit gilt insgesamt Gruppe.


Satz: Nachrichtenmenge
Mit dem RSA-Algorithmus können Mengen mit und verschlüsselt werden.

Beweis: Nachrichtenmenge
Nach der Methode der Schlüsselgenerierung wird mit als Produkt von zwei Primzahlen und erzeugt, wobei .
ist die Teilmenge von .

1.Fall: Alle Zahlen sind Teilerfremd zu und .
2.Fall: Alle Zahlen sind Teilbar zu und .
3.Fall: Muss nicht geprüft werden, da gilt. Trifft trotzdem zu.
Wenn , dann gilt: . Alle Zahlen sind Teilerfremd zu und .
, um und auszuschließen.
Dann gilt: und .


Definition: Ordnung eines Elements
Sei und mit Gruppe.
mit


Satz: Lagrange
Sei eine abelsche Gruppe und eine Untergruppe von , dann gilt:


Beweis:

Idee: Disjunkte Zerlegung von in gleichmächtige Mengen.

  • Zerlegung von in Teilmengen durch die Zerlegung in Nebenklassen
Wir betrachten die Nebenklassen mit und Untergruppe von .
z.z.:
Beweis:
  • "":
Da jede Nebenklasse eine Teilmenge von ist, ist auch die Vereinigung der Nebenklassen eine Teilmenge von .
  • "":
Sei das neutrale Element von .
, da die Untergruppe von ist.
.
Damit ist jedes beliebige ein Element von .
Damit wissen wir, dass wir in die Nebenklassen zerlegen können.
  • Zerlegung von in paarweise disjunkte Nebenklassen
Seien und mit beliebig gewählte Nebenklassen.
z.z:
Beweis:
Sei .
Wir zeigen nun, dass .
  • "":
Sei beliebig gewählt mit .
Mit gilt .
Da eine Untergruppe von ist, gilt mit auch .
Ferner gilt auch , weil einen innere Verknüpfung in .
.
  • "":
Sei beliebig gewählt mit .
Mit gilt .
Analog gilt auch wegen der Untergruppeneigenschaft von .
.
Insgesamt gilt also , da wir beide Teilmengenbeziehungen und gezeigt haben.
Insbesondere heißt das für die Nebenklassen , dass zwei Nebenklassen entweder gleich oder disjunkt sind.
  • Zerlegung von in paarweise disjunkte gleichmächtige Nebenklassen
Wir definieren eine bijektive Abbildung zwischen und einer beliebigen Nebenklasse :
beliebig gewählt.
z.z.:
  • :
z.z:
Sei beliebig gewählt.
  • :
z.z:
Seien so gewählt, dass gilt.
mit und , da Gruppe.
Also ist auch injektiv.
  • Untersuchung der Teilbarkeitseigenschaften
Wir suchen nun ein Repräsentantensystem für die Faktorgruppe .
Für
Wir benötigen das Repräsentantensystem, damit wir Nebenklassen nicht mehrfach zählen.
  • Sei .
.
Mit gilt auch und somit .
Mit und gilt insbesondere , da es mindestens eine Nebenklasse gibt, neutrales Element in .
Damit gilt auch .
  • Für endliche Gruppen gilt:
.
.


Satz: RSA-Algorithmus
Sei eine Klartextnachricht, die mit dem RSA-Algorithmus verschlüsselt wird. Sei sei der öffentliche Schlüssel und der private Schlüssel. Dann gilt:
.

Beweis:
z.z.: .









Grundlegende Definitionen[Bearbeiten]

Definition: Relation

Eine Relation zwischen zwei Mengen und ist eine Teilmenge des kartesischen Produkts



Definition: Äquivalenzrelation

Eine Äquivalenzrelation auf einer Menge ist eine Teilmenge , welche folgende Bedingungen erfüllt:

  • Reflexivität: Für alle ist .
  • Symmetrie: Für alle , für die gilt, ist auch .
  • Transitivität: Für alle mit und gilt, dass auch .


Definition: Äquivalenzklasse

Ist eine Äquivalenzrelation auf einer Menge , so nennt man für ein die Teilmenge

die Äquivalenzklasse von unter der Äquivalenzrelation .


Definition: Teilbarkeit



Definition: Kongruenzrelation

Für und wird definiert:


Satz: Kongruenzrelation

Es gilt:


Definition: Restklasse

Es sei eine von 0 verschiedene ganze Zahl und eine beliebige ganze Zahl. Die Restklasse von modulo ist die Äquivalenzklasse von bezüglich der Kongruenz modulo , also die Menge der ganzen Zahlen, die bei Division durch den gleichen Division mit Rest wie ergeben. Sie besteht somit aus allen ganzen Zahlen , die sich aus durch die Addition ganzzahliger Vielfacher von ergeben: .

Allgemeine Formel für Modulo-Rechnungen

Abbildung Formel_für_Modulo-Rechnen.png

Quellen zu Kryptologie im Schulunterricht[Bearbeiten]

Lernen durch Autorentätigkeit[Bearbeiten]

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

Literatur[Bearbeiten]

  1. 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).
  2. Siegfried Bosch: Algebra. 6. Auflage. Springer-Verlag, 2006, ISBN 3-540-40388-4, S. 11.