Der RSA-Algorithmus

Die Verschlüsselung ist eine Kerntechnologie im Rahmen der IT-Sicherheit. 1976 wurde das Konzept der asymmetrischen Chiffrieralgorithmen oder auch public-key-Algorithmen von Rivest, Shamir und Adleman (RSA) vorgestellt. Damit wurde quasi der bis heute gültige state-of-the-art Verschlüsselungsstandard geschaffen, der vor allem durch das beliebte Programm Pretty Good Privacy (PGP) berühmt wurde — das wohl bekannteste Verschlüsselungsprogramm für den Computer. Bei PGP wird zur Verschlüsselung und dem Signieren von Nachrichten ein Schlüsselpaar (e, d) benutzt, das über ein komplexes mathematisches Verfahren miteinander verbunden ist. Das Schlüsselpaar wird durch den Benutzer geheim erzeugt. Der Schüssel e ist der öffentliche Schüssel und dient zum Verschlüsseln von Nachrichten und der Verifikation von signierten Dokumenten. Der Schlüssel d bleibt beim Benutzer geheim und dient zur Entschlüsselung und dem Signieren von Nachrichten.

Wichtig: Für den praktischen Einsatz von asymmetrischen kryptographischen Methoden ist es wichtig, dass der öffentliche Schlüssel e den Teilnehmern authentisch und integer übermittelt wird. Hierzu werden Zertifikate und Public-Key Infrastrukturen benötigt.

Mathematisch basiert die Idee zum Ver- und Entschlüsseln darauf, dass zwei möglichst große Primzahlen P und Q gewählt werden (durch ein Zufallsverfahren). Groß bedeutet hier mindestens 62 Stellen. Mithilfe dieser werden die beiden Schlüssel berechnet, und zwar durch zwei unterschiedliche Rechenverfahren. Multipliziert ergeben P und Q eine öffentliche, aber immens große Zahl n, die nur unter sehr hohem Rechenaufwand wieder in ihre Primfaktoren zerlegt werden kann. Dieser Rechenaufwand ist die Sicherheit, die der RSA-Algorithmus bietet.

Man bezeichnet dieses Prinzip von der nur sehr schwer zu berechnenden Umkehrfunktion auch als “Einwegfunktion”. Ein Beispiel für so eine Einwegfunktion ist ein klassisches Papier-Telefonbuch: Kennt man den Namen einer Telefonnummer, dann findet man sehr schnell die dazugehörige Telefonnummer. Kennt man jedoch nur eine unbekannte Telefonnummer, so ist es sehr aufwendig, der Telefonnummer einen Namen zuzuordnen.

Im Detail gilt für den RSA-Algorithmus: Der Klartext wird als Binärzahl m der Länge n aufgefasst. Ist der Klartext zu lang, so wird er in mehrere Stücke zerlegt, die jeweils für sich verschlüsselt werden. Es sind:

n      =   P  ·  Q   : öffentliche Zahl
phi(n) = (P-1)·(Q-1)
m < n                : Klartext
e                    : öffentlicher Schlüssel
c = m^e mod n        : Geheimtext
d                    : privater Schlüssel

Der öffentliche Schlüssel e ist eine beliebige Zahl, die mehrere Bedingungen erfüllen muss:

• e muss kleiner als n sein.
• e darf keine gemeinsamen Faktoren mit dem Produkt phi(n) = (P-1)·(Q-1) haben.
• e muss ungerade sein.

Zusammen mit der bekannten Zahl n wird mit e aus dem Klartext m der Codetext c erzeugt. Auch der private Schlüssel d wird mithilfe von e und n erzeugt, denn es gilt:

d·e mod phi(n) = 1

oder anders gesagt

d·e  =  k·phi(n) + 1

für irgendein ganzzahliges, positives k

Im Klartext bedeutet dies, dass man ein k finden muss, welches für die nach d aufgelöste Gleichung ein ganzzahliges Ergebnis liefert. Dafür steht keine Gleichung zur Verfügung, lediglich zwei Unbekannte (d und d). Zur Entschlüsselung wird genau dieselbe Gleichung angewandt wie zum Verschlüsseln. Benötigt wird wieder die öffentliche Zahl n sowie natürlich der private Schlüssel und der Codetext:

m = c^d mod n

Dass dieses funktioniert, wird durch einen Satz von Euler (benannt nach Leonhard Euler und Pierre de Fermat) belegt, der besagt: Ist n = P·Q, so gilt für alle Zahlen m mit m < n und alle natürlichen Zahlen k:

m^(k·phi(n)+1) mod n  =  m

Somit gilt:

c^d mod n  =  m^(de) mod n
           =  m^(k·phi(n) + 1) mod n
           =  m

Die Hauptsicherheit des RSA-Algorithmus liegt darin, dass es praktisch unmöglich ist, den privaten Schlüssel d aus dem öffentlichen Schlüssel e zu berechnen oder phi(n) irgendwie zu bestimmen. Beides ist so schwer wie die Primfaktorzerlegung n = P·Q zu berechnen. Dieses ist zu rechenaufwendig. Gleiches gilt für die Berechnung der e-te Wurzel aus c (modulo n).

Bis heute ist es noch nicht gelungen, den RSA-Algorithmus zu entschlüsseln (ohne Kenntnis des privaten Schlüssels). Die Gesetzmäßigkeit des “Mooresche Gesetz“ besagt, dass sich die Rechenleistung alle 12–24 Monate verdoppelt. Berücksichtigt man diese Tatsache, wird der derzeit verwendete RSA-Algorithmus in wenigen Jahren von Großrechnern zu entschlüsseln sein.

Während der asymmetrische Verschlüsselungsalgorithmus einen Schlüssel zum Verschlüsseln der Daten und einen anderen zum Entschlüsseln verwendet, verwendet der symmetrische Verschlüsselungsalgorithmus nur einen Schlüssel — sowohl für die Ver- als auch die Entschlüsselung. Die darauf basierenden Produkte sind demzufolge weniger für den sicheren Datenaustausch spezialisiert als darauf, Verzeichnisse eines Computers zu verschlüsseln. Fast alle symmetrischen Verschlüsselungsverfahren nutzen dabei die Technik der Blockchiffrierung, wobei der Klartext in eine feste Anzahl Blöcke zerlegt und verschlüsselt wird.

https://www.rene-hifinger.de/ — https://twitter.com/rene_hif