serious-cool

RSA ist ein asymmetrisches Verschlüsselungsverfahren auf Basis eines Public Key Systems. Wenn der potentielle Empfänger seinen öffentlichen Schlüssel bekannt gibt, ist es dem Sender möglich Nachrichten so zu verschlüsseln das nur der Empfänger sie entschlüsseln kann. Eine Analogie wäre ein Briefkasten. Der Sender wirft eine Nachricht durch den Briefschlitz, dieser ist öffentlich zugänglich, doch nur der Besitzer des Schlüssels kann die Nachricht aus dem Briefkasten holen. Dies unterscheidet den RSA von symmetrischen Kryptografischen Systemen bei denen Empfänger und Sender das gleiche geheime Passwort aushandeln müssen. RSA wurde nicht dazu konzipiert symmetrische Block-Chiffren abzulösen. Sondern viel mehr um Schlüssel für symmetrische Systeme sicher auszutauschen. Eine RSA Verschlüsselung ist um ein vielfaches langsamer als Block-Chiffren, dies lässt sich schon an den großen Exponenten, die zwischen 512 und 2048 Bit lang sind, erkennen.

Bemerkungen

• der Algorithmus wurde 1977 vorgeschlagen.
• entwickelt von Ron Rivest, Adi Shamir, Leonard Adleman.
• war bis 2000 patentiert in den USA.
• bis heute dominierendes Public Key Verfahren. 

RSA - Verschlüsselung

y = e_Kpublic( x ) = x^e mod n

RSA - Entschlüsselung

x = d_Kprivate ( y ) = y^d mod n

Der Algorithmus

Setup Phase

1. Wähle zwei große Primzahlen p, q
2. Berechne p * q = n
3. Berechne Phi ( n ) = Phi ( p * q ) = (p-1) * (q-1)
4. Wähle e so dass 0 < e < Phi ( n ) und ggT(e, Phi(n)) = 1 gilt.
5. Berechne d; d = e^-1 mod Phi( n )
6. K_private = d
7. K_public = (e, n)

  Basisprotokoll und Beispiel

Auswahl von p und q

p und q sind beides große Primzahlen mit 512 - 2048 Bit. Solche Primzahlen werden meist durch einfaches probieren gefunden. Es wird eine große Zahl zufällig ermittelt und geprüft ob es eine Primzahl ist. Die Wahrscheinlichkeit eine Primzahl zu erwischen ist 1 / ln ( p). p soll 1024 Bit lang sein, wir wählen eine solche Zahl, die Wahrscheinlichkeit dass p prim ist, ist 1 / ln(2¹⁰²⁴) = 1 / 1024 * ln( 2) = 1 / 710. Wir sehen also das selbst bei so großen Zahlen relativ einfach Primzahlen gefunden werden können.

Sicherheit von RSA

Ein Angreifer will folgende Rechnung lösen n = p * q. Er kennt nur n und e und y. Es wird Ihm also nicht möglich sein die Faktorisierung q * p = n zu berechnen. Eine solche Faktorisierung zu berechnen dauert bei 512 Bit langem p und q ca. 8000 Jahre. RSA gehört somit zu der Familie der Integer Faktorisierungs Verfahren.