Liebe Steem-World,
heute geht es mit der asymmetrischen Kryptographie in die zweite Runde.
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
1. Wähle 2 große Primzahlen p, q
2. Berechne n = p*q (|n| = Schlüssellänge RSA ( 2048 Bit ))
3. Berechne 𝚽(n) = (p-1) * (q-1)
4. Wähle e mit folgenden Bedingungen:
a) 0 < e < 𝚽(n)
b) ggT(e, 𝚽(n)) = 1
5. Berechne d ≡ e⁻¹ mod 𝚽(n) || e*d ≡ 1 mod m
Public Key: PK = (n,e)
Private/Secret Key: SK = d
Verschlüsselung von m mit PK = (n,e)
c ≡ m^e mod n
Entschlüsselung von c mit SK = d
m ≡ c^d mod n
≡ (m^e)^d ≡ m^(e*d) ≡ m^(e*d mod 𝚽(n)) ≡ m⁻¹ mod n
Signatur über m mit SK = d
𝛔 ≡ m^d mod n
Verifikation von (m,𝛔) mit PK=(n,e)
m ?≡ 𝛔^e mod n
≡ (md)e ≡ m ^ (d*e mod 𝚽(m)) mod n
Die Sicherheit von RSA basiert auf der Schwierigkeit der Faktorisierung von n.
Verschlüsselung: c ≡ m^e mod n
Manipulation: c'≡ c * x^e mod n
Entschlüsselung: m*x ≡ c'^d mod n
Eine Gegenmaßnahme ist Padding, z.B. m' = m||hash(m)
Die Exponentiation m^d mod n bei RSA ist teuer. Square-and-multiply (𝛔 ≡ m^d mod n) erleichtert die
Berechnung:
σ = 1
FOR i=#Bits(d) TO 0
σ = σ * σ mod n (SQ)
IF Bit(di) = 1 THEN
σ = σ m mod n (M)
END
Beispiel: 2¹¹ mod 7
11 = 1011
σ = 1
σ * σ = 1
σ * m = 1*2 = 2 i=3
σ * σ = 4 i=2
σ * σ = 16 = 2
σ * m = 4 i=1
σ * σ = 16 = 2
σ * m = 4 i=0
Ergebnis = 4 2¹¹ = 2048 mod 7 = 4
Ein zufäliger 1024 Bit-Schlüssel (ca 50% 1-Bits) führt mit Square-and-multiply zu 1,5*1024 = 1536 Multiplikationen mit 1024 Bit.(Multiplikation hat einen quadratischen Aufwand)
Vorbereitung (günstig):
mp ≡ = m mod p mq ≡ m mod q dp ≡ d mod (p-1) dq = d mod (q-1)
Hauptberechnung (21,5512 = 1536 Multiplikationen mit 512 Bit)
σp ≡ mp^dp mod p
σq ≡ mq^dq mod q
Nachbereitung (günstig)
rp ≡ q⁻¹ mod p rq ≡ p⁻¹ mod q
Ergebnis: (σ ≡ m^d mod n)
σ ≡ [qrp] * σp + [prq] * σq mod m
Der chinesische Restsatz benötigt ebenfalls 1536 Multiplikationen, allerdings mit 512 Bit (quadr. Aufwand).
Damit ist CRT ungefähr 4 mal effizienter als Square-and-multiply.
Fault-Angriff auf RSA mit CRT
Gegeben: 2 Signaturen σ, σ' von m
Bei σ' ist einer der beiden Expontentiationen ein Fehler aufgetreten:
σp' = f mod p
-> σ' ≡ [q*rp] * f + [p*rq] * σq mod m
Die Berechnung ggT(σ - σ', n) ergibt q oder p
Der ggT(σ - σ', n) = q
=> ggT([q*rp]*σp + [p*rq]*σq - ([q*rp]*f + [p*rq]*σq),p*q) = q
=> ggT([q*rq]*(σp-f), p*q) = q
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 :)