Diskrete Mathematik 2. Semester

Eine Gruppe ist ein Zweitupel (G, •), bestehend aus der nichtleeren Menge G und der zweistelligen Operation •, das ein Monoid ist und ein inverses Element enthält. b e G ist inverses Element von a e G, wenn a • b = e (neutrales Element).

Ein abelsche/kommutative Gruppe ist ein Zweitupel (G, •), bestehend aus der nichtleeren Menge G und der zweistelligen Operation •, das eine Gruppe ist und kommutativ ist (a • b = b • a).

Die Mächtigkeit / Kardinalität |G| der Trägermenge G einer Gruppe (G,•) bezeichnet die Ordnung der Gruppe. Ist |G| < unendlich, so spricht man von einer endlichen Gruppe und die Ordnung der Gruppe entspricht der Anzahl der Elemente der Gruppe.

Eine Teilmenge H von G heißt Untergruppe von (G,•), wenn H bezüglich • selbst eine Gruppe ist. Das neutrale Element e ist Element aller Untergruppen. (G,•) und ({e},•) werden triviale Untergruppen genannt.

Eine Gruppe heißt zyklisch, wenn sie von einem einzelnen Element erzeugt wird, also aus Potenzen eines einzelnen Elementes besteht.

Es sei G eine beliebige Gruppe und a∈G. Für jedes a ist ⟨a⟩ = ({aⁿ | n e Z}, •) eine Untergruppe von G. ⟨a⟩ heißt die von a erzeugte Untergruppe. Gibt es in G ein Element a so, dass ⟨a⟩ = G, so wird a erzeugendes Element der Gruppe genannt.

Ein Ring ist ein Tripel (R, +, •) bestehend aus der nicht-leeren Menge R und den beiden zweistelligen Operationen + und •.

(R,+) ist eine kommutative Gruppe (0 als neutrales Element), (R,•) ist eine Halbgruppe und es gilt das Distributivgesetz.

Ein Körper ist ein Tripel (K, +, •) bestehend aus der nicht-leeren Menge K und den beiden zweistelligen Operationen + und •.

(K,+) ist eine kommutative Gruppe (0 als neutrales Element), (K\{0},•) ist eine kommutative Gruppe (1 als neutrales Element) und es gilt das Distributivgesetz.

Phi(n) gibt die Anzahl der zu n teilerfremden natürlichen Zahlen zwischen 1 und n an (ggT(a,n) = 1 mit a e N).

Phi(2) ist daher 1, da ggT(1,2) = 1 und damit nach Definition teilerfremd (gewissermaßen Sonderstellung der 1).

Phi(p) = p-1

Eine Potenz p^k aus einer Primzahl p und einer natürlichen Zahl k ist nur zu Vielfachen von p nicht teilerfremd. Es gibt p^k-1 Vielfache von p, die kleiner oder gleich p^k sind.

Phi(p^k) = p^k - p^k-1 = p^k (1 - 1/p)

Phi(m*n) = Phi(m) * Phi(n)

Sei a,n e N und sei ggT(a,n) = 1. Dann gilt a^Phi(n) = 1 mod n (n teilt a^Phi(n) -1).

Sei p eine Primzahl und a e N mit 1<= a <= p-1. Dinn gilt a^p-1 = 1 mod p. (Satz von Euler für den Spezialfall, dass n eine Primzahl ist.)

- 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