Hallo Steem-Welt,
heute geht in das nächste Kapitel der Kryptographie: Die asymmetrische Kryptographie
Auch diesen Bereich werde ich wieder in vorraussichtlich 5 Teile aufteilen, da der Bereich doch recht komplexe Algorithmen beinhaltet.
Wenn ihr die ersten Teile verpasst habt, und euch die Kryptographie interessiert, findet ihr im Folgenden die Auflistung der vorangegangenen Posts.
Teil 1: Einleitung & klassische Kryptographie
Teil 2: Modulare Arithmetik
Teil 3: Symmetrische Kryptographie #1
Teil 4: Symmetrische Kryptographie #2
Asymmetrische Chiffren ermöglichen das Sicherheitsziel Confidentiality(Vertraulichkeit)
Digitale Signaturen ermöglichen die Sicherheitsziele Data Origin Authentication, Integrity Protection, Non-Repudation
Definition 26: Euklidischer Algorithmus (ggT)
Der größte gemeinsame Teiler ist das positive Produkt zweier gemeinsamer Primzahlen
Beispiel:
126 = (2*3)*3*7
30 = (2*3) * 5
ggt(126,30) = 6
Berechnung:
Idee 1: Wir nehmen an, dass a > b
Dann wird aus ggT(a,b) = g <=> ggT(a-b, b) = g
Dann wird a= ij und b= jg => ggt(ij,jg) = g <=> ggt(i-jg, jg) = g
Idee 2: Wir nehmen an, dass a > k*b
ggT(a-b,b) =
Funktionsweise
WHILE a != 0
a = a mod b
swap(a,b)
END
RETURN a
Definition 27: Erweiterter Euklidischer Algorithmus (eggT)
Der weitere Algorithmus berechnet zusätzlich die Quotienten p,q der diaphantischen Gleichenung
ggT(a,b) = p*a + q*b = g
Berechnung
Zuerst ggT(a=387, b=154) mit Nebenrechnung
ggT(387,154) | 387 = 2*154 + 79
= ggT(154, 79) | 154 = 1*79 + 75
= ggT(79, 75) | 79 = 1*75 + 4
= ggT(75, 4) | 75 = 18*4 + 3
= ggT(4, 3) | 4 = 1*3 + 1
= ggT(3,1) | 3 = 3*1 + 0
= ggT(1,0) = 1
Rückwärts zusammenrechnen
1 = 1
1 = 4-1*3
1 = 4-1*(75-18*4)
1 = 4-1*(75-18*(79-1*75)))
1 = 4-1*(75-18*(79-1*(154-1*79)))
1 = 4-1*(75-18*(79-1*(154-1*(387-2*154)))) = 39*387 - 98 * 154
=> Der ggT(387,154) => a = 387, b = 154, p=39, q=98
Berechnung der multiplikativen Inversen in 𝐙m
Gesucht: a⁻¹ mit a*a⁻¹ ≡ 1 mod m
ggT(a,m) = p*a + q*m = 1
=> p*a + q*m ≡ 1 mod m
<=> p*a ≡ 1 mod m
<=> p ≡ a⁻¹ mod m
Definition 28: Eulersche phi-Funktion
Die eulersche Phi-Funktion berechnet die Anzahl der Elemente der Menge 𝐙m={0,1,..,m-1,m}, die
teilerfremd (relativ prim) mit dem Modulus m sind.
Beispiel: (m=6)
ggT(0,6) = 6 ggT(3,6) = 3
ggT(1,6) = 1 ggT(4,6) = 2
ggT(2,6) = 2 ggT(5,6) = 1
=> 𝚽(6) = 2
Allgemeine Berechnung:
m habe die kanonische Faktorisierung
m = p1^(e1) * p2^(e2) * ... * pn^(en)
mit n unterschiedlichen Primzahlen p. Es gilt:
𝚽(m) = n || c=1 (pi(ei)-pi(ei-1))
Beispiel: (m=24)
24 = 2*2*2*3 = 2³*3 => p1=2, e1=3, p2=3, e2=1
𝚽(24) = 2||c=1 (pi^(ei) - pi^(ei-1)) = (2³-2²)(3¹-3⁰) = (8-4)(3-1) = 8
Definition 29: Satz von Euler
ggT(a,m)=1, dann gilt:
a^𝚽(m) ≡ 1 mod m
Anwendungen
Ausblick
In den nächsten Teilen zur asymmetrischen Kryptographie werde ich das RSA-Verfahren näher betrachten. Weiterhin ein bisschen in die Gruppentheorie einsteigen und darauf aufbauend über Diffie Hellman und El-Gamal Verschlüsselungen berichten.
Wie immer freue ich mich über Feedback und natürlich, wenn es euch gefallen hat, über einen Upvote / Resteem :)