3. Schlüsseltypen (Key Types)

In den in diesem Dokument definierten Primitiven und Schemata werden zwei Schlüsseltypen verwendet: RSA-öffentlicher Schlüssel (RSA Public Key) und RSA-privater Schlüssel (RSA Private Key). Zusammen bilden ein RSA-öffentlicher Schlüssel und ein RSA-privater Schlüssel ein RSA-Schlüsselpaar (RSA Key Pair).

Diese Spezifikation unterstützt das sogenannte „Multi-Prim"-RSA (Multi-prime), bei dem der Modulus mehr als zwei Primfaktoren haben kann. Der Vorteil von Multi-Prim-RSA sind geringere Rechenkosten für die Entschlüsselungs- und Signaturprimitive, vorausgesetzt, dass der chinesische Restsatz (Chinese Remainder Theorem, CRT) verwendet wird. Bessere Leistung kann auf Einzelprozessorplattformen erreicht werden, aber in größerem Maße auf Multiprozessorplattformen, wo die beteiligten modularen Exponentiationen parallel durchgeführt werden können.

Für eine Diskussion darüber, wie Multi-Prim die Sicherheit des RSA-Kryptosystems beeinflusst, wird der Leser auf [SILVERMAN] verwiesen.

3.1. Öffentlicher RSA-Schlüssel (RSA Public Key)

Für die Zwecke dieses Dokuments besteht ein öffentlicher RSA-Schlüssel aus zwei Komponenten:

n        RSA-Modulus (RSA Modulus), eine positive ganze Zahl
e        öffentlicher RSA-Exponent (RSA Public Exponent), eine positive ganze Zahl

In einem gültigen öffentlichen RSA-Schlüssel ist der RSA-Modulus n ein Produkt von u verschiedenen ungeraden Primzahlen r_i, i = 1, 2, ..., u, wobei u >= 2, und der öffentliche RSA-Exponent e ist eine ganze Zahl zwischen 3 und n - 1, die GCD(e, λ(n)) = 1 erfüllt, wobei λ(n) = LCM(r_1 - 1, ..., r_u - 1). Per Konvention können die ersten beiden Primzahlen r_1 und r_2 auch als p bzw. q bezeichnet werden.

Eine empfohlene Syntax für den Austausch öffentlicher RSA-Schlüssel zwischen Implementierungen ist in Anhang A.1.1 angegeben; die interne Darstellung einer Implementierung kann davon abweichen.

3.2. Privater RSA-Schlüssel (RSA Private Key)

Für die Zwecke dieses Dokuments kann ein privater RSA-Schlüssel eine von zwei Darstellungen haben.

Darstellung 1

Die erste Darstellung besteht aus dem Paar (n, d), wobei die Komponenten folgende Bedeutungen haben:

n       RSA-Modulus (RSA Modulus), eine positive ganze Zahl
d       privater RSA-Exponent (RSA Private Exponent), eine positive ganze Zahl

Darstellung 2

Die zweite Darstellung besteht aus einem Quintupel (p, q, dP, dQ, qInv) und einer (möglicherweise leeren) Sequenz von Tripeln (r_i, d_i, t_i), i = 3, ..., u, eines für jede Primzahl, die nicht im Quintupel enthalten ist, wobei die Komponenten folgende Bedeutungen haben:

p      der erste Faktor, eine positive ganze Zahl
q      der zweite Faktor, eine positive ganze Zahl
dP     CRT-Exponent des ersten Faktors, eine positive ganze Zahl
dQ     CRT-Exponent des zweiten Faktors, eine positive ganze Zahl
qInv   der (erste) CRT-Koeffizient, eine positive ganze Zahl
r_i    der i-te Faktor, eine positive ganze Zahl
d_i    CRT-Exponent des i-ten Faktors, eine positive ganze Zahl
t_i    CRT-Koeffizient des i-ten Faktors, eine positive ganze Zahl

Gültigkeitsbedingungen

In einem gültigen privaten RSA-Schlüssel mit der ersten Darstellung ist der RSA-Modulus n derselbe wie im entsprechenden öffentlichen RSA-Schlüssel und ist das Produkt von u verschiedenen ungeraden Primzahlen r_i, i = 1, 2, ..., u, wobei u >= 2. Der private RSA-Exponent d ist eine positive ganze Zahl kleiner als n, die erfüllt:

e * d == 1 (mod λ(n))

wobei e der entsprechende öffentliche RSA-Exponent ist und λ(n) wie in Abschnitt 3.1 definiert ist.

In einem gültigen privaten RSA-Schlüssel mit der zweiten Darstellung sind die beiden Faktoren p und q die ersten beiden Primfaktoren des RSA-Modulus n (d.h., r_1 und r_2); die CRT-Exponenten dP und dQ sind positive ganze Zahlen kleiner als p bzw. q, die erfüllen:

e * dP == 1 (mod (p-1))
e * dQ == 1 (mod (q-1))

und der CRT-Koeffizient qInv ist eine positive ganze Zahl kleiner als p, die erfüllt:

q * qInv == 1 (mod p)

Wenn u > 2, enthält die Darstellung ein oder mehrere Tripel (r_i, d_i, t_i), i = 3, ..., u. Die Faktoren r_i sind die zusätzlichen Primfaktoren des RSA-Modulus n. Jeder CRT-Exponent d_i (i = 3, ..., u) erfüllt:

e * d_i == 1 (mod (r_i - 1))

Jeder CRT-Koeffizient t_i (i = 3, ..., u) ist eine positive ganze Zahl kleiner als r_i, die erfüllt:

R_i * t_i == 1 (mod r_i)

wobei R_i = r_1 * r_2 * ... * r_(i-1).

Eine empfohlene Syntax für den Austausch privater RSA-Schlüssel zwischen Implementierungen, die Komponenten aus beiden Darstellungen enthält, ist in Anhang A.1.2 angegeben; die interne Darstellung einer Implementierung kann davon abweichen.

Hinweise

Hinweis 1: Die Definition der CRT-Koeffizienten hier und die Formeln, die sie in den Primitiven in Abschnitt 5 verwenden, folgen im Allgemeinen Garners Algorithmus [GARNER] (siehe auch Algorithmus 14.71 in [HANDBOOK]). Für die Kompatibilität mit den Darstellungen privater RSA-Schlüssel in PKCS #1 v2.0 und früheren Versionen sind jedoch die Rollen von p und q im Vergleich zu den übrigen Primzahlen vertauscht. Daher ist der erste CRT-Koeffizient qInv als Inverses von q mod p definiert, nicht als Inverses von R_1 mod r_2, d.h. von p mod q.

Hinweis 2: Quisquater und Couvreur [FASTDEC] beobachteten den Vorteil der Anwendung des CRT auf RSA-Operationen.