[Kryptographie] Asymmetrische Kryptographie #3
Liebe Steem-World,
heute geht es mit der asymmetrischen Kryptographie in die dritte Runde.
Durch die Anwendung von Diffie Hellman & El-Gamal werden Beispiele gezeigt, die auch heute noch verwendet werden und auch in der Weiterentwicklung eine große Rolle spielen.
Wer die vorangegangenen Posts nicht mitbekommen hat, kann diese hier nachlesen:
Teil 1: Einleitung & klassische Kryptographie
Teil 2: Modulare Arithmetik
Teil 3: Symmetrische Kryptographie #1
Teil 4: Symmetrische Kryptographie #2
Teil 5: Asymmetrische Kryptographie #1
Teil 6: Asymmetrische Kryptographie #2
Diffie Hellman
Wir benötigen eine Einwegfunktion für Kryptographische Funktionalität.
Einwegfunktion bedeutet:
- f(*) muss leicht zu berechnen sein
- f⁻¹(*) darf nur sehr schwer zu berechnen sein
Definition 36: Diskretes Logarithmus Problem (DLP)
Gegeben ist eine zykliche endliche Gruppe (Zp,) und ein Generator der Gruppe G (<g> = Zp*)
- f(x) ≡ g * g * ... * g ≡ g^x ≡ y mod p ist leicht zu berechnen
- f⁻¹(y) ≡ log_g(y) ≡ x mod p ist das DLP
und wird als sicher angenommen
Beispiel <3> = Z7*
= 3⁴ ≡ 4 mod 7
= log_3(4) ≡ ln(4)/ln(3) ≡ 1,26 ∉ Z7*
Diffi-Hellman Schlüsselaustausch
Bekannt auf beiden Seiten ist p und <g>=Zp*
∈R = Element Random
Alice(Schlüssel a∈R Zp*) Bob (Schlüssel b∈R Zp*)
A ≡ g^a mod p --------------------------> KAB ≡ A^b ≡ g^(a*b) mod p
KAB ≡ B^a ≡ g^(b*a) mod p <-------------------------- B ≡ g^b mod p
--------------------------------------------------------------------------------------
KAB
--------------------------->
Symmetrische Verschlüsselung
Beispiel: p=13 und g=<2>=Z13*
Alice (Schlüssel a=3 ∈R Z13*) BoB (Schlüssel b=4 ∈R Z13*)
A = 2³ ≡ 8 mod 13 --------------------------> KAB = 8⁴ ≡ 3²*⁴ ≡1 mod 13
KAB ≡ 3³ ≡ 2⁴*³ ≡ 1 mod 13 <-------------------------- B ≡ 2⁴ ≡ 3 mod 13
Man in the Middle (MitM)
p = 13. g=<2>=Z13*
Alice(a=3) Oscar(o=5) Bob(b=4)
A = 2³ ≡ 8 mod 13 -----------> KAB^ = 8⁵ ≡ 8 mod 13
A^, B^ = 2⁵ ≡ 6 mod 13 --------> KA^B = 6⁴ ≡ 9 mod 13
KAB^ = 6³ ≡ 8 mod 13 <----------- KA^B = 3³ ≡ 9 mod 13 <-------- B = 2⁴ ≡ 3 mod 13
Gemeinsamer Schlüssel nun 8, nicht 1
Beide Parteien haben mit Oscar einen Schlüssel vereinbart, nicht mit sich selber
El-Gamal
El Gamal Verschlüsselung
Alice Bob
. Wählt große Primzahl p
- Wählt Generator <g> = Zp*
- Wählt einen SecretKey b∈R Zp*
(p,g,B) - Berechne publicKey B = g^b mod p
<--------------------------------------
- Wähle a ∈R Zp*
- Berechne temp Schlüssel
A ≡ g^a mod p
- Berechne Session Key
KAB ≡B^a mod p
- Verschlüsselung (m)
c ≡ m * KAB mod p (A,c)
--------------------------------------> - Berechne Session Key
KAB ≡ A^b mod p
- Entschlüsselung (c)
m ≡ c * kAB⁻¹ mod p
El Gamal Signatur
Public Key von Alice ist bekannt (p,g,A)
Außerdem H(*) = Hash-Funktion
Alice Bob
- Wählt k mit 0<a<p-1 und
ggT(k,p-1) = 1
- Berechnet r ≡ g^k mod p
- Berechnet s != 0
S ≡(Hm)-a*r)*k⁻¹ mod p-1
- 𝛔 = (r,s) (m, 𝛔)
-----------------------> - Prüfe, ob
0 < r < p und
0 < s < p - 1
- Verifiziere 𝛔
g^(H(m)) ≡? A^r*r^s mod p
Verifikationsgleichung
g^H(m) ≡? A^r * r^s mod p
=> g^H(m) ≡? g^(ar) * g^(k(H(m)-ar)k⁻¹) mod p
<=> g^H(m) ≡? g^(ar) * g^(H(m)-ar) mod p
<=> g^H(m) ≡? g^(ar - ar) * g^H(m) mod p
<=> g^H(m) ≡? g^H(m) mod p
Ausblick
In der nächsten Runde geht es dann schon um die Elliptischen Kurven, die Art von Kryptographie, die heutzutage größtenteils angewendet wird, und in Kombination mit Diffie Hellman auch in den Kryptowährungen zur Anwendung kommt.
Wie immer danke ich dir für dein Interesse. Wenn du Fragen zu einem Punkt hast, immer raus damit... Aufgrund der Komplexität des Themas ist es schwierig, dass in entsprechendem Umfang zu vermitteln, ohne den Rahmen komplett zu sprengen...
Natürlich bin ich immer froh über entsprechendes Feedback und natürlich auch ein Vote :)