RSA

3.1 RSA

Beim RSA-Algorithmus handelt es sich um das bekannteste asymmetrische Kryptoverfahren, benannt nach seinen Erfindern RIVEST-SHAMIR-ADLEMAN [RSA78, AR78].²⁰ Die mathematische Grundlage bilden Restklassenkörper, verbunden mit der Schwierigkeit große Zahlen zu faktorisieren.

3.1.1 Schlüsselgenerierung

Betrachten wir in der Voraussetzung zuerst die Schlüsselerzeugung, welche im Wesen folgendermaßen abläuft:²¹

Wähle zwei große Primzahlen , mit , welche das öffentliche Modul bestimmen.
Zahlentheoretische Erläuterungen:
- Bei der Restklasse $ℤn := {0,1,...,n − 1}$ handelt es sich um einen Ring, nicht um einen Körper.²²
- Im Gegensatz dazu bilden $ℤp$ und $ℤq$ jeweils einen Primzahlenkörper.
- Läßt man aus $ℤn$ nur solche Elemente zu, die keinen gemeinsamen Teiler mit dem Modul $n$ haben, wird ein Körper konstruierbar. Die Anzahl der Elemente $r$ in dessen multiplikativer Gruppe $∗ ℤn := {r ∈ ℤ |0< r < n,gcd(r,n)= 1}$ ergibt sich mit Hilfe von EULER’s Totient-Funktion zu $φ = ϕ(n)= (p − 1)(q − 1)$ .
Nun wird eine Zufallszahl erzeugt, die keinen gemeinsamen Faktor mit hat. Diese (auch als öffentlicher Exponent bezeichnete) Zahl bildet die Basis des öffentlichen Schlüssels .
Zahlentheoretische Erläuterungen:
- Wegen $gcd (e,φ) = 1$ gehört $e$ zum endlichen Körper $ℤφ$ .
- Aus $gcd [e,(p− 1)(q− 1)]= 1$ läßt sich als notwendige Voraussetzungen $gcd(e,p− 1) = 1$ und $gcd(e,q− 1)= 1$ ableiten.
- Da $p − 1$ und $q− 1$ gerade Zahlen sind, muß $e$ wegen des vorangegangenen Punktes auf jeden Fall ungerade sein.
Für den privaten Schlüssel wird jetzt eine weitere Zahl so berechnet,²³ daß ohne Rest durch teilbar ist.
Zahlentheoretische Erläuterungen:
- Ausgehend von
  
  kann man $d$ auch als Inverse des öffentlichen Exponents $e$ im Körper $ℤφ$ ansehen.

3.1.2 Algorithmus

Für die Verschlüsselung wird folgende Operation auf dem Plaintext-Block $m$ ausgeführt, wobei dieser als Zahl $m ∈ ℤn$ interpretiert wird:

Die inverse Operation der Entschlüsselung wird in gleicher Art und Weise vorgenommen:

Für den Beweis $′ m = m$ wendet man zuerst Gleichung 3.2 an und bezieht dann die Restklassendarstellung $de = 1+ kφ$ ( $k∈ ℕ$ ) ein.

Die weitere Argumentation beruht darauf, daß $mφ mod n = 1$ gilt und so:

Besitzen $m$ und $n$ keinen gemeinsamen Teiler ( $gcd(m, n)= 1$ , $m ∈ ℤ∗n$ ), dann kann man auf $m φ mod n$ einfach EULER’s Satz (nach Formel ??) anwenden und ist fertig.

Hat $m$ allerdings gemeinsame Teiler mit $n$ , dann gilt $gcd(m,n) ⁄= 1$ und deshalb $m ∕∈ ℤ∗n$ . Betrachtet man aber die Faktorisierung von $n$ , dann muß $m$ ein Vielfaches von $p$ oder $q$ sein (wegen $m < n$ jedoch nicht von $pq$ ). Unter dieser Voraussetzung wäre die Zerlegung $m = mp$ oder $m = mq$ möglich, wobei jeweils $gcd(m,n) = 1$ gilt. Im Fall $m = mp$ (für $m = mq$ ganz genauso) läßt sich die Modulo-Division $φ m mod n$ durch Kürzen von $p$ und unter Berücksichtigung von $-- m < q$ folgendermaßen vereinfachen:

Wegen $-- m ∈ ℤ ∗q$ kann nun wieder der Satz von EULER zur Anwendung kommen, was den Beweis vervollständigt.

3.1.3 Optimierung

Eine Beschleunigung des Verfahrens läßt sich (algorithmisch) vor allem beim Entschlüsseln erzielen.²⁴ Geht man dazu von

aus, dann lassen sich (durch Modulo-Division nach $p$ und $q$ ) die folgenden zwei Kongruenzen formulieren:

Diese legen eine Anwendung des Chinesischen Restsatzes entsprechend Anhang ?? nahe [Gro00, Wel01].²⁵

Als Voraussetzung benötigt man die Koeffizienten $α$ und $β$ in der BéZOUT-Darstellung des größten gemeinsamen Teilers (vgl. Formel ?? in Anhang ??)

gcd(p,q)= αp + βq = 1,

welche z. B. mit Hilfe des erweiterten euklidischen Algorithmus berechnet werden können.²⁶ Sie stellen, wenn man vorangegangene Gleichung nach $p$ und $q$ modulo-dividiert, gleichzeitig die Inversen

im Körper $ℤq$ und $ℤp$ dar. Durch Anwendung des Chinesischen Restsatzes für zwei Kongruenzen kann man nun $m′$ berechnen:

m′ = (αmqp + βmpq ) mod n .

(3.4)

Der Vorteil liegt darin, daß die modulare Exponentiation modulo $n$ , welche die Komplexität $O (log3n)$ hat,²⁷ auf zwei Operationen gleicher Art, aber mit verringerter Anzahl von Stellen verteilt.

Die weitere Optimierung kann in drei Schritten erfolgen:

Wendet man den Chinesischen Restsatz in der Variante nach H. L. GARNER an, so werden weitere Vereinfachungen möglich [Gar59]. Denn aus der Restklassendarstellung

läßt sich eine lineare diophantische Gleichung ableiten (siehe auch Anhang ??):

welche die Lösungsmenge

besitzt. Üblicherweise benutzt man zur Berechnung von $m ′$ die Lösungen für $xk$ und erhält in geschlossener Darstellung:²⁸

Unter der Voraussetzung $′ ′ m = m mod n$ kann man vorangegangene Gleichung noch weiter reduzieren, wenn die allgemeingültige Beziehung $(rq) mod (pq )= q(r mod p)$ berücksichtigt wird.

Die Vorteile dieser Darstellung liegen vor allem darin, daß
- eine finale Modulo-Division durch $n$ nicht mehr nötig ist;
- nur ein BéZOUT-Kofaktor überhaupt benötigt wird;
- wegen der Zwischenreduktion modulo $p$ die Speicherplatzanforderungen reduziert sind.
Man kann aber noch weitergehen, indem die Berechnung von $mp$ und $mq$ vereinfacht wird. Eine wesentliche Zeitersparnis kommt zustande, wenn man $c$ vor dessen Potenzierung in der Länge reduziert.
Eine letzte Optimierung bezieht sich auf den Exponenten $d$ , welcher ebenfalls reduziert werden kann. Dazu muß man sich nur klarmachen, daß durch die Reduktion von $c$ in Punkt 2 das Ergebnis der Potenzierung jeweils in $ℤp$ oder $ℤq$ und insbesondere in der zugehörigen multiplikativen Gruppe liegt. Da diese zyklisch ist, wiederholen sich beim Potenzieren die Werte mit der Gruppenordnung $∗ |ℤ p|= p− 1$ bzw. $∗ |ℤq|= q− 1$ . Aus diesem Grund kann man $d$ auf die Gruppenordnung reduzieren (vgl. auch Anhang ??).

Zu der privaten Schlüsseldarstellung $(n,d)$ gibt es deshalb zwei Optionen:

ein Tripel $(p,q,d)$ , was wegen $n = pq$ trivial erscheint;
oder die Darstellung als Quintupel $(p,q,d ,d ,q ) p q inv$ , mit $d = d mod (p − 1) p$ , $dq = d mod (q− 1)$ und $−1 qinv = q (mod p)$ .

Wegen der signifikanten Geschwindigkeitsvorteile wird fast immer die Quintupel-Variante verwendet [IEE00, ISO06a, PKC02].²⁹

3.1.4 Verschlüsselung nach PKCS #1

Um den RSA-Algorithmus praktisch auf die Verschlüsselung von Daten anzuwenden, müssen diese zuerst geeignet aufbereitet werden. Der Prozeß dieser Formatierung wird in [IEE00, PKC02] als Message Encoding Operation bezeichnet, in [PKC93a] hingegen als Encryption Block Formatting.

PKCS #1 v1.5 Mit der Methode nach [PKC93a, Kal98] gestaltet sich die Formatierung noch relativ einfach.³⁰ Der Datenblock D wird entsprechend Abbildung 3.1 in die Struktur des sogenannten Encryption Block EB eingebunden. Auf den Encryption Block EB wird letztlich der RSA-Algorithmus nach Formel 3.2 angewendet.³¹

Abbildung 3.1:

Blockformatierung nach PKCS #1 v1.5

Die weiteren Elemente im Encryption Block haben folgende Bedeutung:

BT: Der Block Type zeigt die Verwendung des privaten oder öffentlichen Schlüssels (im anschließenden RSA-Algorithmus) an.

$00H$   Signieren (Verwendung des privaten Schlüssels);
$01 H$   genauso wie $00 H$ (der Unterschied liegt im Element PS);
$02H$   Verschlüsseln (Verwendung des öffentlichen Schlüssels).
PS: Ein Padding String dient der Anpassung an die Länge des Moduls $k = ∥n∥$ so, daß $∥PS∥+ ∥D ∥+ 3 = k$ gewährleistet ist. Die Länge von PS soll mindestens 8 Byte sein, was im Umkehrschluß die von D auf $k− 11$ Bytes beschränkt. Das Padding selbst hängt vom Typ des Blocks (BT) ab:

$00H$   alle Bytes sind $00H$ ;
$01H$   alle Bytes sind $FFH$ ;
$02H$   alle Bytes sind zufällig, aber ungleich $00H$ .

Der Inhalt von PS ist beim Entschlüsseln (Byte für Byte) auf konforme Kodierung zu prüfen [PKC93a, 9.4]. Für die Blocktypen $01H$ und $02H$ kann der Anfang (und damit auch die Länge) des Datenblocks D ermittelt werden, indem das $00H$ -Byte zwischen PS und D gesucht wird. Für den Blocktyp $00H$ ist dieses Verfahren nur geeignet, wenn das erste Byte in D immer ungleich $00H$ ist. Kann dies nicht vorausgesetzt werden, dann muß die Länge $∥D∥$ a priori bekannt sein.³²

PKCS #1 v2.1 Nicht zuletzt wegen des sehr erfolgreiche Angriffs nach [Ble98] wird die PKCS #1 v1.5 Formatierung heute nicht mehr empfohlen. Statt dessen sollte grundsätzlich Version 2.1 nach [PKC02, JK03, IEE00, ISO06a] zum Einsatz kommen, welche Optimal Asymmetric Encryption Padding (OAEP) verwendet [BR95].³³

Den Kern der Blockformatierung nach Abbildung 3.2 macht eine sogenannte Mask Generation Function (MGF, in Abbildung 3.2 mit F bezeichnet) aus, welche selbst wiederum eine Hash-Funktion H verwendet. Die MGF kann dasselbe leisten wie die Hash-Funktion, nämlich eine große Eingangsmenge auf eine kleine Ausgangsmenge abbilden (mit $∥H ∥$ soll im folgenden die Breite eines Hash-Wertes bezeichnet sein). Sie kann aber auch das Umgekehrte – eine kleine Eingangsmenge auf eine größere Ausgangsmenge „zerstreuen”. PKCS #1 v2.1 legt sich zwar in der Hash-Funktion nicht fest, definiert aber in [PKC02, B.2.1] eine konkrete Mask Generation Function, genannt MGF1.³⁴

Abbildung 3.2:

Blockformatierung nach PKCS #1 v2.1

Die einzelnen Kodierungsschritte können folgendermaßen beschrieben werden:

Ergänze die Nachricht M zuerst (und grundsätzlich) durch ein vorangestelltes Byte mit Wert $01 H$ .
Füge weitere $00H$ -Byte’s hinzu (Padding), so daß ein Datenblock DB der Länge $k − ∥H ∥− 1$ entsteht.³⁵
Bilde den Hash über ein vereinbartes, konstantes Label $L$ und stelle das Ergebnis als $lHash = H(L)$ an den Anfang des Datenblocks.³⁶
Erzeuge einen Zufallsstrom Seed der Länge $∥H ∥$ .
Berechne $maskedDB = DB ⊕ MGF (Seed)$ als Teil der Encoded Message (EM).
Berechne $maskedSeed = Seed⊕ MGF (maskedDB )$ , als höherwertigen Teil von EM.
Stelle ein führendes $00H$ -Byte an den Anfang von EM (gewährleistet auch hier wieder $EM < n$ ).

Im Gegensatz zu PKCS #1 v1.5 geht in die RSA-Verschlüsselung $e c = EM mod n$ hier nun ein Wert EM ein, der keinerlei Rückschlüsse auf den Datenblock DB zuläßt.³⁷