Frage 8: Was ist RSA?

RSA ist ein asymmetrisches Kryptosystem, daß sich zum Verschlüsseln und zur Authentifikation eignet. Es wurde 1977 von Ron Rivest, Adi Shamir und Leonard Adleman [RSA78] erfunden. Es funktioniert folgendermaßen:

• Man nehme 2 große Primzahlen p und q.
• Bilde deren Produkt n=p*q, welches Modul genannt wird.
• Man wähle eine Zahl e die kleiner als n und teilerfremd (relativ prim) zu p-1 und q-1 ist.
• Finde eine Zahl d, so daß (e*d)-1 durch (p-1)*(q-1) teilbar ist. Die Werte e und d werden öffentlicher und privater Exponent genannt.
• Der öffentliche Schlüssel ist das Paar (n,e), der private Schlüssel ist das Paar (n,d).
• Die Faktoren p und q werden sicher vernichtet oder mit dem privaten Schlüssel zusammen aufbewahrt.

Es wird angenommen, daß es schwierig ist, den privaten Exponenten d aus dem öffentlichen Schlüssel (n,e) zu berechnen. Sollte jemand n in p und q faktorisieren, so kann er natürlich d berechnen. Deshalb ist die Sicherheit von RSA mindestens an die Annahme geknüpft, Faktorisierung sei schwierig. Ein leichter Faktorisierungsalgorithmus oder ein anderer funktionierender Angriff würde RSA "brechen" (Siehe Frage 10 und Frage 46).

Im folgenden wird beschrieben, wie man RSA zur Geheimhaltung und Authentifizung einsetzen kann (Praktisch sieht das leicht anders aus, siege Frage 16 und Frage 17).

RSA Verschlüsselung

Alice möchte eine Nachricht m an Bob schicken. Alice erstellt den Chiffretext c durch modulare Potenzierung: c = m^e mod n, wobei (n,e) Bobs öffentlicher Schlüssel ist. Sie sendet c an Bob. Um dies zu dechiffrieren potenziert Bob ebenfalls: c^d mod n = (m^e*d mod n = m^{(p-1)*(q-1)-1} mod n =) m. (Die letzte Identität ist ein zahlentheoretischer Satz, nämlich die Eulersche Verallgemeinerung des kleinen Satzes von Fermat.) Da nur Bob d kennt, kann nur Bob c entschlüsseln.

RSA Authentifizung

Alice möchte eine Nachricht m an Bob unterschreiben, so daß Bob sicher sein kann, daß diese Nachricht authentisch und von Alice ist. Alice erstellt eine elektronische Unterschrift durch Potenzieren: s = m^d mod n, wobei (n,d) der private Schlüssel von Alice ist. Sie sendet m und s an Bob. Dieser prüft die Unterschrift durch eine Potenzierung: s^e mod n muß mit m übereinstimmen, wenn (n,e) Alice öffentlicher Schlüssel ist.

So ist Verschlüsselung und Authentifizung ohne Teilung eines Geheimnisses möglich: Jede Person hat nur die öffentlichen Schlüssel der anderen und seinen eigen privaten Schlüssel. Jeder kann Nachrichten verschlüsselt senden oder Unterschriften prüfen, aber nur derjenige, der den richtigen privateb Schlüssel hat, kann Nachrichten entschlüsseln oder unterschreiben.

[Zurück zur Titelseite]