Diskrete Mathematik 2. Semester

- voheriger (geheimer) Schlüsselaustausch nötig

- stark steigende Schlüsselanzahl bei vielen Kommunikationsteilnehmern (n Teilnehmer --> n*(n-1)/2 Schlüssel, damit jeder mit jedem kommunizieren kann)

- keine Unterstützung digitaler Signaturen

1.) Wahl von zwei (großen) Primzahlen p und q

2.) Berechnung von n: n = p*q

3.) Berechnung von Phi(n): Phi(n) = (p-1) * (q-1)

4.) Wahl einer zu Phi(n) teilerfremden Zahl e mit 1 < e < Phi(n)

5.) (n,e) ist der öffentliche Schlüssel, die zur Berechnung benötigten Werte werden geheim gehalten

1.) Berechne d als das multiplikative Inverse zu e in Z_Phi(n): e*d = 1 mod Phi(n)

2.) (n,d) ist der private Schlüssel

Codierung der Nachricht zunächst als Zahlenfolge

Verschlüsselung: c = m^e mod n

Entschlüsselung: m = c^d mod n

1.) k wird als Dualzahl aufgeschrieben: 101

2.) Durchgehen der Dualzahl von links nach rechts. Ist die Ziffer eine 0, wird der bisher aufgeschriebene Term quadriert. Bei einer 1 wird der Term quadriert und anschließend mit der Basis g multipliziert: ((1² * 4)²) ² * 4 = (4²)² * 4 = 16² *4 = 256 * 4 = 1024

Die Potenz wird wie zuvor zerlegt (als wenn kein modulo gefordert wäre):

k = 5 = 101

4⁵ = ((1² * 4)²)² * 4

Allerdings wird nun nach jeder Multiplikation (also auch nach dem Quadrieren) modulo gerechnet:

(((1*4 mod 5)² mod 5)² mod 5) * 4 mod 5 = ((4² mod 5)² mod 5) * 4 mod 5 = (1² mod 5) * 4 mod 5 = 4 mod 5 = 4

Zur Entschlüsselung von Nachrichten wird der private Schlüssel d benötigt. Zur Berechnung von diesem wird jedoch Phi(n) benötigt, wobei sich n aus zwei Primfaktoren zusammensetzt. Es ist bislang jedoch kein effizientes Verfahren bekannt, sehr große Zahlen (~2048 Bit) zu faktorisieren.

Sei n eine ungerade natürliche Zahl, für die überprüft werden soll, ob sie eine Primzahl ist.

1.) Wahl einer zufälligen Zahl a mit 1 < a < n

2.) Berechnung des ggT(a,n), wenn dieses ungleich 1 ist (nicht teilerfremd also), dann ist n keine Primzahl

3.) Wenn a^n-1 mod n ungleich 1 ist, ist n keine Primzahl

4.) Andernfalls ist n wahrscheinlich eine Primzahl, aber nicht zwangsweise. Es könnte auch noch eine fermatsche Pseudoprimzahl sein (Wahrscheinlichkeit dafür höchstens 50%).

5.) Zur Senkung der Fehlerwahrscheinlichkeit kann der Test mit einem anderen a wiederholt werden.

Carmichael Zahlen sind fermatsche Pseudoprimzahlen zu allen Basen ae {2,...,n-1} mit ggT(a,n)=1 ist.

1.) Wahl einer zufälligen Zahl a mit 1 < a < n-1

2.) Berechnung des ggT(a,n), wenn dieses ungleich 1 (also a und n nicht teilerfremd) ist, ist n keine Primzahl.

3.) Zerlege n-1 in eine ungerade Zahl s und eine Potenz mit Basis 2: n-1 = 2^r * s

4.) Wenn a^s = 1 mod n oder es ein r gibt, mit dem a^{s*(2)^r = -1 mod n} gilt, dann ist n wahrscheinlich eine Primzahl.

Ein Problem beim Miller-Rabin-Test sind starke Pseudoprimzahlen, die für manche Basen a auch diesen Test bestehen. Allerdings ist jede Zahl n für höchstens ein Viertel der Basen, die kleiner als n sind, stark pseudoprim. Eine wiederholte Ausführung des Tests mit verschiedenen Basen erhöht also auch hier die Zuverlässigkeit. Die Fehlerwahrscheinlichkeit bei k verschiedenen gewählten Basen beträgt (1/4)^k.

Sei p eine Primzahl und g ein erzeugendes Element des endlichen Körpers Z_p. Die kleinste natürliche Zahl x mit y = g^x mod p heißt der diskrete Logarithmus von y zur Basis g.

Notation: x = dlog_g(y)

Verfahren zum Austausch eines symmetrischen Schlüssels über ein unsicheres Medium (http://www.karllorey.de/2012/02/29/der-diffie-hellman-schlusselaustausch-verstandlich-erklart/)

1.) gemeinsame öffentliche Wahl einer großen Primzahl p und eines erzeugenden Elements g<p von Z_p durch beide Personen

2.) Wahl einer geheimen Zahl a<p durch Alice, Bildung von x=g^a mod p und Versand von x an Bob

3.) Wahl einer geheimen Zahl b<p durch Bob, Bildung von y=g^b mod p und Versand von y an Alice

4.) Berechnung des geheimen Schlüssels:

Alice: z = y^a mod p mit y = g^b, womit sie eigentlich z=g^a*b mod p berechnet

Bob: z = x^b mod p mit x = g^a, womit er eigentlich z=g^a*b mod p berechnet

Asymmetrische Nachrichtenverschlüsselung durch Multiplikation mit Diffie-Hellman-Schlüssel

1.) Bob verschlüsselt Nachricht m nach Berechnung des Diffie-Hellman-Schlüssels mit diesem: c = m*z = m*x^b mod p

2.) Bob schickt c und y (seinen öffentlichen Schlüssel) an Alice

3.) Alice entschlüsselt Nachricht c: m = c*z^-1 mod p = c * y^(p-1-a) mod p

Algorithmus zur effizienteren Berechnung des diskreten Logarithmus

1.) Gegeben: Primzahl p und erzeugendes Element g von Z_p, Gesucht: x = dlog_g(y) mit g^x = y mod p

2.) Zerlegen von x in x = q*s + r mit \(s \geq \sqrt{p-1}\) und r<s, sodass gilt: g^(qs+r) = y

3.) Berechnung von s (kleinste ganze Zahl, die größer oder gleich der Wurzel aus p-1 ist)

4.) Berechnung der Giant-Steps: g^qs mod p

5.) Berechnung der Baby-Steps, bis ein Wert einem Giant-Wert entspricht: y*(g^-1)^r mod p

6.) Ermittlung von x = qs+r mit r aus dem Baby-Step und s aus dem zugehörigen Giant-Step

Sie sind genau dann gleich, wenn a1=a2 und b1=b2.

Seien M und N beliebige Mengen. M x N = { (x,y) | x e M und y e N }

Bsp.: M = {1,2}, N = {2,3}

M x N = { (1,2), (1,3), (2,2), (2,3) }

M x N = {}

Per Definition ist M x N = { (x,y) | x e M und y e N}, da N aber keine Elemente besitzt, kann y kein Element von N sein. Damit erhält man die leere Menge.

wenn M=N oder
M = {} oder
N = {}

Seien M und N beliebige Mengen. Eine Relation R zwischen M und N ist eine Teilmenge des kartesischen Produktes M x N.

Bemerkung: Relationen entsprechen zweistelligen Prädikaten.

R1 = { (Tom, Lisa), (Tom, Paula) } = x ist befreundet mit y

R2 = { (Paul, Paula) } = x ist verwandt mit y

Sei R als Teilmenge von M x N eine beliebige Relation zwischen M und N. R^(-1) = { (x,y) | (y,x) e R } ist eine Relation zwischen N und M (inverse Relation).

R1^(-1) = y hat zum Vater x

R2^(-1) = y ist verheiratet mit x

Seien R1 als Teilmenge von M1 x M2 und R2 als Teilmenge von M2 x M3 beliebige Relationen. Die Verkettung von R1 mit R2 ist die Relation R1 • R2 = { (x,z) | x e M1 und z e M3 und es gibt ein y e M2, für das gilt: (x,y) e R1 und (y,z) e R2 }

R1 • R2 = x ist Mutter von z

R3 • R4 = x ist Schwiegervater von z

R heißt reflexiv genau dann, wenn die Identitätsmenge eine Teilmenge der Relation ist, also für alle x e M gilt: (x,x) e R

R heißt irreflexiv genau dann, wenn für alle x e M gilt: (x,x) nicht e R, die Schnittmenge der Identitätsmenge und R also die leere Menge ist.

Bemerkung: Keine Relation ist gleichzeitig reflexiv und irreflexiv. Es gibt allerdings Relationen, die weder reflexiv noch irreflexiv sind.

R heißt symmetrisch genau dann, wenn für alle x und y e M gilt: (x,y) e R --> (y,x) e R, also R eine Teilmenge der inversen Relation von R ist.

Ja. Sie hat keine Elemente, damit ist die Voraussetzung falsch und die Folgerung wahr.