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 Kryptographie

Asymmetrische Chiffren ermöglichen das Sicherheitsziel Confidentiality(Vertraulichkeit)
Digitale Signaturen ermöglichen die Sicherheitsziele Data Origin Authentication, Integrity Protection, Non-Repudation

Zahlentheorie

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

• Reduktion im Exponenten 2¹⁰ mod 7
  2¹⁰ ≡ 2^(10mod𝚽(7)) ≡ 2^(10mod6) ≡ 2⁴ mod 7
• Berechnung multiplikativer Inversen
  a^𝚽(m) ≡ 1 mod m <=> a * a^(𝚽(m)-1) ≡ 1 mod m <=> a^(𝚽(m)-1) ≡ 1/a mod m

---

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 :)