RSA Standard

Allgemein

Der RSA-Standard gehört zur Gruppe der asymmetrischen Kryptographie-Verfahren, d.h. es gibt 2 Schlüssel um einen Datensatz zu verschlüsseln bzw. einen chiffrierten Text zu entschlüsseln. Man unterscheidet hierbei den öffentlichen Schüssel und den privaten Schlüssel. Die Schlüssel sind mathematisch so konstruiert, das sie jeweils die Umkehroperation des anderen darstellen. Aus diesem Grund eignet sich das RSA-Verfahren sowohl für das Verschlüsseln von Daten als auch das digitale Signieren. RSA ist ein deterministisches Verfahren, d.h. gleiche Eingaben erzeugen stets gleiche Ausgaben. Aufgrund dieser Eigenschaft, zusammen mit Problemen bei sehr kurzen Nachrichten oder kleinen Exponenten, wird RSA in der Praxis durch weitere Schemata ergänzt.

Geschichte

Das RSA-Verfahren ist nach seinen Entwicklern Ron Rivest, Adi Shamir und Leonard Adleman benannt. Es wurde 1977 erstmalig am MIT veröffentlicht und war eine der ersten größer angelegten Entwicklung im Bereich der asymmetrischen Kryptographie. 1983 wurde dem MIT das US Patent anerkannt. RSA ist bis heute weit verbreitet im Einsatz. Modernere Verfahren, die für spezielle Anwendungsbereiche konzipiert sind, ergänzen bzw. ersetzen RSA , z.B. Elliptic Curve DSA (ECDSA) welches bei vergleichbarer Sicherheit erheblich weniger Ressourcen für Berechnung und Speicherung benötigt.

Schlüsselerzeugung

Als asymmetrisches Verfahren nutzt RSA ein Schlüsselpaar, bestehend aus einem öffentlich zugänglichen Schlüssel und dem dazu gehörigen geheimen privaten Schlüssel. Üblicherweise erzeugt ein Pseudo-Zufallsgenerator mindestens 2 sehr große Primzahlen, mit deren Hilfe dann die Schlüssel berechnet werden.

Der öffentliche Schlüssel besteht aus 2 Komponenten:

• n   RSA modulus, mit $n\in N^{+}$
• e   RSA öffentlicher Exponent, mit $e\in N^{+}$

n ist das Produkt von u verschiedenen geheimen Primzahlen r_i, so das gilt:

$n=\prod _{i}^{u}r_{i},\ r_{i}=1,2\cdots u$ für $u\geq 2$

e ist eine ganze Zahl im Bereich $3\leq e\leq n-1$ und es muss gelten:

ggT$(e,\lambda (n))=1\ mit\ \lambda (n)=$kgv$(r_{1}-1,\cdots ,r_{u}-1)$

In der einfachsten Ausführung werden nur 2 Primzahlen für die Bildung von n verwendet. r₁ und r₂ werden dann auch als p bzw. q bezeichnet. Heute übliche Schlüssellängen sind im Bereich von 1024-4096 bit.

Es gibt 2 gängige Darstellungen für den privaten Schlüssel. Die Erste besteht wieder aus 2 Komponenten:

• n   RSA modulus, mit $n\in N^{+}$
• d   RSA privater Exponent, mit $d\in N^{+}$

Der private Exponent d wird aus den zuvor gewählten geheimen Primzahlen berechnet, so das gilt:

$e*d\ {\bmod {\ }}\lambda (n)=1$

Die zweite Darstellung verwendet ein Quintuple $(p,q,dP,dQ,qInv)\$ sowie eine Sequenz aus Triplets $(r_{i},d_{i},t_{i})i=3\dots u$ für jede weitere Primzahl. Weiterhin soll gelten:

$e*dP\ {\bmod {\ }}(p-1)=1,\ e*d_{i}\ {\bmod {\ }}(r_{i}-1)=1$

$e*dQ\ {\bmod {\ }}(q-1)=1,\ R_{i}*t_{i}\ {\bmod {\ }}r_{i}=1\ mit\ R_{i}=r_{1}*r_{2}*\cdots *r_{i-1}$

$q*qInv\ {\bmod {\ }}p=1$

Signieren & Verifizierung

Beim Signieren mit RSA nutzt der Absender seinen eigenen privaten RSA-Schlüssel K, um aus der Nachricht m eine Signatur s zu erzeugen. Zuerst wird die Nachricht m dabei in ein String aus ganzen Zahlen umgewandelt. Bei Signaturen wird meist noch zusätzlich ein Hashwert über die gesamte Nachricht gebildet, da eine Rekonstruktion der Nachricht nicht erforderlich ist. Es soll nur die Authentizität der Nachricht sicher gestellt sein. Für die Nachricht m muss in jedem Fall die Eigenschaft $0\leq m\leq n-1$ erfüllt sein, sonst wäre eine Dechiffrierung mit dem öffentlichen Schlüssel nicht möglich.

Bei nur 2 Primfaktoren und dem Schlüssel $K\ =(n,d)$ gilt:

$s=m^{d}\ {\bmod {n}}$

Für beliebig viele Primfaktoren und $K=(p,q,dP,dQ,qInv),(r_{i},d_{i},t_{i})\ mit\ i=3\cdots u$ kann folgender Algorithmus verwendet werden:

1. $s_{1}=m^{d}P\ {\bmod {p}}\ und\ s_{2}=m^{d}Q\ {\bmod {q}}$
2. $Wenn\ u>2,s_{i}=m^{d_{i}}\ {\bmod {r}}_{i}$
3. $h=(s_{1}-s_{2})*qInv\ {\bmod {p}}$
4. $s=s_{2}+q*h\$
5. $Wenn\ u>2,R=r_{1}\ und\ for\ i=3\cdots u\ do$
   1. $R=R*r_{i-1}\$
   2. $h=(s_{i}-s)t_{i}\ {\bmod {r}}_{i}$
   3. $s=s+R*h\$

Für die Verifizierung der Signatur nutzt der Empfänger den öffentlichen Schlüssel des Absenders $K\ =(n,e)$. Es wird einfach die Umkehroperation auf die Signatur s ausgeführt, um die Nachricht m wieder herzustellen.

$m=s^{e}\ {\bmod {n}}$

Zur Veranschaulichung ist hier nochmal der ganze Ablauf für 2 Primfaktoren p und q dargestellt.

Schemata für Signaturen

Durch die Einfachheit der grundlegenden mathematischen Operation ist RSA allein nur bedingt anwendbar. Zu klein gewählte Exponenten oder Nachrichtenlängen könnten die Modulo-Operation negieren. Die e^th Wurzel zu berechnen würde in dem Fall schon eine Lösung bedeuten. Auch ist das rein deterministische Verhalten ein möglicher Angriffspunkt. In der Praxis wird RSA deshalb mit weiteren Algorithmen, sgn. Signaturenschemata kombiniert. Diese erzeugen mit Hilfe von z.B. Hashfunktionen und Zufallselementen aus den Nachrichten Zeichenketten passender Größe, welche dann mit RSA signiert werden können.

Ein rein deterministischen Ansatz stellt das EMSA-PKCS1-v1_5 Schema dar. Er eignet sich für sehr große Nachrichten, je nach gewählter Hashfunktion z.B. SHA-1: 2⁶⁴-1 bits. Die Signatur wird nicht direkt aus der zu signierenden Nachricht M erzeugt. Es wird erst eine Encoded Message EM generiert (siehe Abbildung), welcher die ursprüngliche Nachricht nur noch als Hashwert enthält.

DER steht für Distinguished Encoding Rules, ein je nach Implementierung festgelegtes Informationsset, welches die verwendete Hashfunktion und andere Informationen enthält. Um die Nachricht verifizieren zu können, wird neben dem obligatorischen öffentlichen Schlüssel auch die Nachricht selbst benötigt, da hier keine Nachrichtenrekonstruktion möglich ist. Zuerst wird aus der Signatur die EM berechnet. Mit Hilfe der bekannten Nachricht M und der bekannten Hashfunktion wird eine neuer Encoded Message EM´ erzeugt und anschließend mit EM verglichen. Bei gültiger Signatur sollten beide gleich sein.

Das EMSA_PSS Schema nutzt eine Zufallskomponente bei der Erstellung der EM für zusätzliche Sicherheit. Erst wird wieder ein Hashwert aus der Nachricht M erzeugt. Kombiniert mit einem Zufallswert (salt) wird ein zweites Mal ein Hashwert H berechnet, welcher dann den ersten Teil des EM bildet. Der Zufallswert selbst wird mit Hilfe einer sgn. Mask Generation Function MGF und dem zweiten Hashwert H verschlüsselt.(Abbildung)

Bei der Verifikation wird zuerst mit Hilfe der rekonstruierten EM der Zufallswert (salt) zurück gerechnet. Anschließend wird wie beim Signieren ein Hashwert H´ berechnet und mit H verglichen. Auch hier ist für die Verifikation die unverschlüsselte Nachricht nötig.

Sicherheit von RSA

Die Sicherheit von RSA basiert auf 2 mathematischen Problemen. Zum einen ist das die Faktorisierung, also das zerlegen sehr großer Zahlen in ihre Primfaktoren. Zum anderen besteht das Problem, die e^th Wurzel modulo n zu finden. Bis jetzt ist kein Algorithmus bekannt, der diese Probleme in polynomialer Zeit lösen könnte. 2005 gelang es, eine 663bit große Zahl in ihre Primfaktoren zu zerlegen. Hierfür war jedoch ein erheblicher Aufwand und Zeit nötig, der in keiner Relation zu den gängigen Zeiten steht, die ein bestimmter RSA-Schlüssel gültig ist. Auch wenn die Entwicklung immer schnellerer Rechner abzusehen ist, dürfte die Faktorisierung auch weiterhin ein Problem sein. Nicht zuletzt besteht immer die Möglichkeit, die Schlüssellängen weiter zu erhöhen, so das eine Lösung für den Dauer der geplanten Verwendung eines bestimmten Schlüssels auszuschließen ist. Was neue Algorithmen oder technische Entwicklungen (z.b. Quantencomputing) betrifft, bestehen hier mittel- und langfristig gewisse Risiken.

Allerdings haben diverse Angriffe in der Vergangenheit gezeigt, das eine Dechiffrierung auch ohne Wissen der Primfaktoren möglich ist. RSA zeigt eine gewisse Verwundbarkeit gegenüber Chosen ciphertext attacks. Dabei werden gefälschte chiffrierte Nachrichten generiert . Durch Analyse der entschlüsselten Fälschungen wird versucht, Informationen über den verwendeten Schlüssel zu gewinnen.

Quellen

• PKCS#1 v2.1 RSA Cryptography Standard
• Wikipedia:RSA
• Albrecht Beutelspacher, Jörg Schwenk, Klaus-Dieter Wolfenstetter: Moderne Verfahren der Kryptographie. Von RSA zu Zero-Knowledge, 2006
• Spektrum der Wissenschaft, Extras-Ausgabe: Kryptographie, 2001