Diskrete Mathematik 2. Semester

Sei R als Teilmenge von M x N eine beliebige Relation zwischen M und N. R heißt linkstotal genau dann, wenn für alle x e M gilt: Es gibt ein y e N für das gilt: (x,y) e R.

Sei R als Teilmenge von M x N eine beliebige Relation zwischen M und N. R heißt rechtstotal genau dann, wenn für alle y e N gilt: Es gibt ein x e M für das gilt: (x,y) e R.

Sei R als Teilmenge von M x N eine beliebige Relation zwischen M und N. R ist linkseindeutig genau dann, wenn für alle x1,x2 e M gilt: für alle y e N gilt: wenn (x1, y) e R und (x2, y) e R --> x1 = x2

Sei R als Teilmenge von M x N eine beliebige Relation zwischen M und N. R ist rechtseindeutig genau dann, wenn für alle x e M gilt: für alle y1,y2 e N gilt: wenn (x, y1) e R und (x, y2) e R --> y1 = y2

R•S ist links-/rechtstotal, wenn R und S links-/rechtstotal sind.

Andersherum funktioniert das nicht. R und S müssen nicht zwangsläufig links-/rechtstotal sein, wenn R•S links-/rechtstotal ist.

R•S ist links-/rechtseindeutig, wenn R und S links-/rechtseindeutig sind.

Andersherum funktioniert das nicht. R und S müssen nicht zwangsläufig links-/rechtseindeutig sein, wenn R•S links-/rechtseindeutig ist.

Sei R als Teilmenge von M x N eine beliebige Relation zwischen M und N. R heißt Abbildung (Funktion) genau dann, wenn R linkstotal und rechtseindeutig ist.

(Jedem x e M ist genau ein y e N zugeordnet.)

R linkstotal <=> R^-1 rechtstotal

R rechtstotal <=> R^-1 linkstotal

R linkseindeutig <=> R^-1 rechtseindeutig

R rechtseindeutig<=> R^-1 linkseindeutig

Eine algebraische Struktur besteht aus einer Menge von Rechenobjekten S und einer Rechenoperation O, die je zwei Rechenobjekten genau ein Verknüpfungsergebnis a•b e S zuordnet.

algebraische Struktur: (S, •)

Sei (S, •) eine algebraische Struktur. (S, •) erfüllt einen Existenzsatz für die Lösbarkeit von Gleichungen.

a) Für alle a,b e S gilt: Es gibt ein x e S für das gilt: a • x = b

b) Für alle a,b e S gilt: Es gibt ein x e S für das gilt: x • a = b

Sei (S, •) eine algebraische Struktur. (S, •) erfüllt einen Eindeutigkeitssatz für das Lösen von Gleichungen.

Für alle a,b e S gilt: Für alle x1,x2 e S gilt: a • x1 = b und a • x2 = b  =>  x1 = x2

Für alle a,b e S gilt: Für alle x1,x2 e S gilt: x1 • a = b und x2 • a = b  =>  x1 = x2

Sei (G,•) eine algebraische Struktur. (G,•) heißt Gruppe genau dann, wenn

1) das Assoziativgesetz gilt (für alle a,b,c e G gilt: (a • b) • c = a • (b • c) )

2) linksneutrale und linksinverse Elemente vorhanden sind. (Es gibt ein e e G, sodass für alle a e G gilt: e • a = a und für alle a e G gilt: es gibt ein a' e G für das gilt: a' • a = e

1.) Berechne ggT(a,m) mit dem euklidischen Algorithmus.

2.) Falls ggT(a,m) kein Teiler von b ist, gibt es keine Lösung. Falls es ein Teiler von b ist, gibt es eine Lösung und es geht mit 3.) weiter.

3.) Berechne a', m', sodass a _* a' + m _* m' = ggT(a,m). a' ist das ggT(a,m)-Gegengleich zu a.

4.)

[x]_m = \([{b \over ggT(a,m)} * a']\)_m

[x1] = \([x + {m \over ggT(a,m)}]\)_m

\([{m \over ggT(a,m)} * a]\)_m = \([m*{a \over ggT(a,m)}]\)_m = [0]_m

[x1 * a]_m = [x * a]_m + \([{m \over ggT(a,m)}]\)_m = [b]_m

Wenn das ggT > 1, gibt es keine oder mehrere Lösungen.

Wenn das ggT = 1, gibt es genau eine Lösung.

ggT(81,45)  = 9

81 = 1*45 + 36

45 = 1*36 + 9

36 = 4*9 + 0

21 / 9 = 2 Rest 3, da 21 also nicht durch 9 teilbar ist, ist die Restklassengleichung nicht lösbar.

ggT(81,45)  = 9

81 = 1*45 + 36

45 = 1*36 + 9

36 = 4*9 + 0

27 ist durch 9 teilbar, damit gibt es min. eine Lösung.

9 = 45*45' + 81*81'

9 = 45 - 1*36

9 = 45 - 1*(81 - 1*45) = 2*45 - 81 = 2*45 - 1*81

45' = 2 und 81'=-1

[45]₈₁ * [2]₈₁ = [9]₈₁

x = 27/9 * 2 = 3*2 = 6

Vertraulichkeit: Nachricht für Unbefugte nicht lesbar

Integrität: Nachricht nicht unbemerkt veränderbar

Authentizität: Nachricht stammt tatsächlich von der angegebenen Quelle

Nichtabstreitbarkeit / Verbindlichkeit: Versand/Empfang der Nachricht unleugbar

Anonymität: Absender/Empfänger/Kommunikationsbeziehung bleibt geheim

Ein kryptografisches System ist ein Quintupel (P,C,K,e,d) mit folgender Eigenschaft:

Für alle k e K gilt: es gibt ein k' e K für das gilt: für alle x e P gilt: d(e( x,k ), k') = x

Wobei P = Menge der Klartexte, C = Menge der Geheimtexte und K = Menge der Schlüssel, sowie e = Verschlüsselungsfunktion und d = Entschlüsselungsfunktion

Sender und Empfänger besitzen dasselbe Geheimnis, wer also verschlüsseln kann, kann auch entschlüsseln. k' (Schlüssel zum Entschlüsseln) ist aus k (Schlüssel zum Verschlüsseln) leicht ermittelbar.

k' (Schlüssel zum Entschlüsseln) aus k (Schlüssel zum Verschlüsseln) nicht in angemessener Zeit ermittelbar. k kann vom Empfänger öffentlich bekannt gegeben werden. Sender und Empfänger müssen kein Geheimnis austauschen.

Die Sicherheit eines Verschlüsselungssystems darf nur von der Geheimhaltung des Schlüssels abhängen, nicht von der Geheimhaltung des Verschlüsselungsverfahrens.

- Geheimhaltung: Verschlüsselungsfunktionen schwer geheim zu halten

- Reverse-Engineering: Verfahren aus Hard- oder Software-Implementierungen rekonstruierbar

- Ersetzbarkeit: Schlüssel leichter zu ersetzen

- Fehler durch Öffentlichkeit leichter zu entdecken

- Vertrauen: Hintertüren in nicht öffentlichen Verfahren möglich

- Erfahrung: geheime Verfahren erwiesen sich oft als unzulänglich

- Ciphertext Only: Angreifer kennt einen/mehrere Geheimtexte

- Probable/Known Plaintext: Angreifer kennt einen/mehrere Geheimtexte und zugehörige Klartexte/wahrscheinliche Klartextteile

- Chosen Plaintext: Angreifer kann ausgewählte Klartexte verschlüsseln lassen

- Chosen Ciphertext: Angreifer kann ausgewählte Geheimtexte entschlüsseln lassen

- Chosen Text: Chosen Plaintext + Chosen Ciphertext

- Adaptive Varianten: Angriff über längere Zeit/mehrere Runden möglich

Stab, auf den Band gewickelt wird. Band wird längs des Stabes beschriftet und anschließend abgewickelt übermittelt, Empfänger benötigt Stab mit gleichem Radius, um Nachricht lesen zu können.

Transpositionsverfahren: Zeichen des Klartextes bleiben erhalten, werden aber umsortiert.

Ersetzung der Klar- durch Geheimtextbuchstaben durch zyklische Rechtsverschiebung (Alphabet wird zweimal untereinander geschrieben, nur mit vorher festzulegender Verschiebung)

Monoalphabetisches Substitutionsverfahren: Abbildung von Klar- auf Geheimtextbuchstaben aufgrund eines einzigen Geheimtextalphabets (jeder Klartextbuchstabe wird immer durch den gleichen Geheimtextbuchstaben ersetzt)

Zuordnung der Klartextbuchstaben zu den Restklassen Z₂₆ mit A=0 und Z=25.

Für alle x e P und k e K gilt: e(x,k) = y e C mit y_i = x_i + k mod 26

Die sprachspezifischen Besonderheiten wie die Häufigkeitsverteilung von Buchstaben und Buchstabenkombinationen bleiben erhalten.

Gleichzeitige Verwendung mehrerer Caesar-Chiffren: Wahl eines Schlüsselwortes, das wiederholt wird, bis Länge des Klartextes erreicht ist. Für jeden Klartextbuchstaben wird die Caesar-Chiffre gewählt, die dem entsprechenden Schlüsselwortbuchstaben entspricht.

Polyalphabetisches Substitutionsverfahren: Abbildung von Klar- auf Geheimtextbuchstaben mit Hilfe mehrerer Geheimtextalphabete

Für alle x = x₀, x₁, ..., x_n-1 e P und k = k₀, k₁, ..., k_m-1 e K gilt: e(x,k) = y e C mit y_i = x_i + k_{i mod m} mod 26

Länge des Schlüsselwortes und Zufälligkeit der Buchstaben, da Schwachpunkt die Wiederholung des Schlüsselwortes ist (anfällig gegen Known Plaintext-Angriffe, Reduktion auf unsicheren Caesar-Chiffre bei bekannter Schlüssellänge)

Angreifer bekommt zwei beliebige Klartexte gleicher Länge und zu einem dieser den verschlüsselten Geheimtext. Der Angreifer soll entscheiden, zu welchem der beiden Klartexte der Geheimtext gehört. Liegt die Wahrscheinlichkeit für eine richtige Wahl bei 50%, gilt das Kryptosystem als perfekt sicher.

Klartext wird beibehalten, aber Buchstaben werden in andere Reihenfolge gebracht. Dies geschieht blockweise: Text wird in Blöcke eingeteilt, indem durch Teiler m geteilt wird (falls nicht teilbar, auffüllen mit zufällig gewählten Buchstaben). Chiffrieren innerhalb der Blöcke gemäß einer Vorschrift.

monoalphabetisches Substitutionsverfahren