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

RSA

Berechnung der RSA-Schlüssel

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

RSA Verschlüsselung

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

RSA-Signatur

Signatur über m mit SK = d
𝛔 ≡ m^d mod n

Verifikation von (m,𝛔) mit PK=(n,e)
m ?≡ 𝛔^e mod n
≡ (m^d)e ≡ m ^ (d*e mod 𝚽(m)) mod n

Die Sicherheit von RSA basiert auf der Schwierigkeit der Faktorisierung von n.

Angriff

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)

Effizienz von RSA

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)

Chinesischer Restsatz (CRT)

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