Das RSA-Verfahren, benannt nach seinen Erfindern Ron Rivest, Adi Shamir und Leonard Adleman, ist das bekannteste und verbreitetste Verfahren unter den Public-Key-Algorithmen. Der Algorithmus entstand 1978 bei dem Versuch aufzuzeigen, dass Public-Key-Kryptographie unmöglich ist.
Das Konzept der Public-Key-Kryptographie wurde erst zwei Jahre zuvor von Whitfield Diffie und Martin Hellman entwickelt. Bei Public-Key-Algorithmen, auch asymmetrische Algorithmen genannt, unterscheiden sich Chiffrier- und Dechiffrierschlüssel. Der Chiffrierschlüssel wird oft öffentlicher Schlüssel und der Dechiffrierschlüssel privater Schlüssel genannt. Von besonderer Bedeutung für Public-Key-Algorithmen ist die Eigenschaft, dass aus der Kenntnis des öffentlichen Schlüssels der private Schlüssel nicht hergeleitet werden kann. Daher kann der öffentliche Schlüssel frei zugänglich gemacht werden und ein verschlüsselter Informationsaustausch wird ermöglicht, ohne zuvor eine geheime Schlüsselvereinbarung getroffen zu haben.
Public-Key-Algorithmen basieren in der Regel auf sogenannten Trapdoor-Einwegfunktionen. Eine Trapdoor-Einwegfunktion ist eine außerordentlich schwer zu invertierende Funktion (Einwegfunktion), zu der es aber eine Geheiminformation ("Falltür", englisch "trapdoor") gibt, mit Hilfe derer man die Funktion leicht invertieren kann.
Das RSA-Verfahren benutzt als Trapdoor-Einwegfunktion die Potenzfunktion
x → xe mod n
wobei sich n aus dem Produkt zweier Primzahlen p und q ergibt. Die Trapdoorinformation ist in diesem Fall die Faktorisierung von n bzw. die Faktoren p und q. Die Einwegfunktion besteht in dem Problem sehr große Zahlen zu faktorisieren.
Die Struktur Zn* = {a aus Zn | ggT(a, n) = 1} bildet zusammen mit der Multiplikation a * b := (a · b) mod n eine multiplikative Gruppe (d.h. die Struktur ist abgeschlossen, assoziativ, besitzt ein neutrales Element und jedes Element der Struktur hat ein Inverses). Von besonderer Relevanz für das RSA-Verfahren ist das multiplikative Inverse eines Elements, das mit Hilfe der Vielfachsummendarstellung berechnet werden kann.
Es gilt:
Ist ggt(a, n) = 1 = sa + tn, so ist a' := s mod n die multiplikative Inverse aus Zn* von a.
Die Anzahl der Elemente von Zn* wird mit φ(n) bezeichnet. Mit anderen Worten: φ(n) ist die Anzahl der zu n teilerfremden natürlichen Zahlen, die kleiner n sind. Man kann φ(n) mittels einer Formel berechnen, wenn man die Faktorisierung von n kennt. Es gilt:
φ(p) = p - 1 für jede Primzahl p φ(p·q) = (p - 1)(q - 1) für je zwei verschiedene Primzahlen p und q
Für alle Zahlen a, die teilerfremd zu n sind, gilt: aφ(n) ≡ 1 (mod n).
Sei g = ggT(a,b). Dann gibt es ganze Zahlen s und t mit g = sa + tb.
Das Lemma besagt, dass der größte gemeinsame Teiler zweier Zahlen durch eine Linearkombination der Zahlen mit ganzzahligen Koeffizienten dargestellt werden kann. Zur Berechnung von s und t benutzt man eine erweiterte Version des euklidischen Algorithmus. Dieser Algorithmus basiert auf einer Rekursionsformel für den Rest der n-ten Iteration bei der Berechnung des ggT: rn = rn-2 - qn-1· rn-1 mit qn = rn - 1 / rn (für den "einfachen" Euklidischen Algorithmus wird die äquivalente Berechnung rn = rn - 2 mod rn - 1 angewandt). Die Koeffizienten s und t ergeben sich rekursiv aus rn = sn· a + tn· b.
void bezout(long a, long b, long& g, long& s, long& t) {
if (a == 0) {
g = b; s = 0; t = 1;
} else if (b == 0) {
g = a; s = 1; t = 0;
} else {
long s1, s2, t1, t2;
s1 = 1; s2 = 0; s = 0;
t1 = 0; t2 = 1; t = 1;
while (a % b) {
long q = a / b;
long r = a % b;
s = s1 - q * s2;
t = t1 - q * t2;
s1 = s2; s2 = s;
t1 = t2; t2 = t;
a = b; b = r;
}
g = b;
}
}
|
Sei n = p·q das Produkt zweier verschiedener Primzahlen p und q. Dann gilt für jede natürliche Zahl m ≤ n und jede natürliche Zahl k die Gleichung
mk·(p - 1)(q - 1) + 1mod n = m.
Zur Realisierung des RSA-Algorithmus wählt man zwei natürliche Zahlen e und d, deren Produkt von der Form
e·d = k·(p - 1)(q - 1) + 1
mit k aus N ist. Dann gilt:
(me)d mod n = m
und
(md)e mod n = m.
(me)d = (md)e = me·d = mk·(p - 1)(q - 1) + 1 = m·mk·(p - 1)(q - 1) = m·mk·φ(n) = m·1 = m ; alles modulo n.
Bevor das Verschlüsselungsverfahren angewendet werden kann, müssen zunächst der öffentliche (e, n) und der private Schlüssel (d, n) erzeugt werden. Nachdem eine Größenordnung für der Modul n festgelegt worden ist, werden zwei Primzahlen p und q gewählt, deren Produkt n bildet. Die Kandidaten für die Primzahlen p und q werden durch Zufallszahlengeneratoren gewählt und anschließend mit Hilfe probabilistischer Tests, etwa dem Rabin-Miller-Test, verifiziert.
Das Rabin-Miller-Verfahren verwendet für den Primzahltest den Satz von Euler-Fermat und den aus der Regel
a·b ≡ 0 mod p (prim) ↔ a ≡ 0 oder b ≡ 0 mod pabgeleiteten Hilfssatz
d2 ≡ 1 mod p (prim) ↔ d ≡ 1 oder d ≡ -1.
Sei p der Primzahlkandidat und a eine beliebige Zahl kleiner als p, dann wird beginnend mit der größten Quadratwurzel von ap - 1 auf Gleichheit mit -1 und 1 getestet. Wird eine übereinstimmung gefunden, dann gilt der Test als bestanden. Ansonsten werden solange die Quadrate der Wurzel auf Gleichheit mit -1 getestet bis eine übereinstimmung gefunden oder p - 1 erreicht wird. Die Quadrate der Wurzel dürfen nun auch nicht mehr kongruent zu 1 sein, da für den Fall dass p prim ist, der Test durch die Wurzel bestanden und beendet wird.
bool rabin_miller_test(long p) {
long b = 0;
long m = p - 1;
while (!(m & 0x01)) { // p = 1 + (2 ^ b) * m
++b; m>>= 1;
}
if (b == 0) return false; // keine ungerade Zahl
long a = random(1, p - 1); // Zufallszahl < p
long z = potenz_modulo(a, m, p); // z = (a ^ m) % p
if (z == 1) return true;
for (long j = 0; (j < b) && (z != p - 1); ++j) {
z = potenz_modulo(z, 2, p);
if (z == 1) return false;
}
if (z != p - 1) return false;
return true; // a ist Zeuge für "p ist prim"
}
|
Durch die Wahl der Testdurchläufe können falsche Primzahlen mit beliebig hoher Wahrscheinlichkeit ausgeschlossen werden. Für den Rabin-Miller-Test liegt die Fehlerwahrscheinlichkeit für eine Zahl der Länge 256 Bit bei sechs Durchläufen unter 2-51.
Nachdem nun n und dessen Faktorisierung (p, q) bekannt sind, werden die Potenzen e und d bestimmt, welche zusammen mit n die Schlüssel bilden. Für die Potenz e wählt man eine beliebige, zu φ(n) teilerfremde Zahl. Da die Potenz d das multiplikative Inverse zur Zahl e bzgl. der Gruppe (Zφ(n)*, *) ist, kann dieses leicht mittels der Vielfachsummendarstellung berechnet werden.
Sei ggT(e, φ(n)) = 1 = se + tφ(n), dann ist d = s mod φ(n).
Die Herleitung von d aus e steht nicht im Widerspruch zur vorhergehenden Aussage, dass innerhalb von Public-Key-Verfahren der private Schlüssel nicht aus dem öffentlichen Schlüssel ableitbar sein darf. Der Wert d kann nur mittels dem Funktionswert φ(n) ohne massiven Rechnenaufwand bestimmt werden und ohne die Kenntnis von p und q ist der Berechnungsaufwand zur Bestimmung von φ(n) äquivalent zur Faktorisierung von n. Daher dürfen p und q nie an die Öffentlichkeit gelangen; entweder werden sie nach der Schlüsselerzeugung zerstört, da sie nicht mehr zwingend erforderlich sind, oder sie müssen ebenso sicher wie der private Schlüssel (d, n) verwahrt werden.
Verglichen mit der Schlüsselgenerierung gestaltet sich die Ver- und Entschlüsselung sehr einfach. Eine zu verschlüsselnde Nachricht m wird zuerst in numerische Blöcke, die kleiner als n sind, zerlegt (d.h. Anzahl der Bits eines Informationsblocks < Anzahl der Bits von n).
m → (m1, m2, ..., mk), für jedes i mit 1 ≤ i ≤ k: mi < n
(m1, m2, ..., mk) → (c1, c2, ..., ck) , für jedes i mit 1 ≤ i ≤ k: ci = mie mod n
(c1, c2, ..., ck) → (m1, m2, ..., mk) , für jedes i mit 1 ≤ i ≤ k: mi = cid mod n
Für die Berechnung einer Potenz modulo n kann das Verfahren der Verkettung bzw. des binären Quadrierens und Multiplizierens angewandt werden. Ohne Berücksichtigung der Modulo-Operation kann das Ergebnis der Potenz-Operationen unhandbar große Ergebnisse liefern. Durch die Anwendung der Modulo-Operationen auf sämtliche Zwischenergebnisse kann deren maximale Länge auf die doppelte Länge von n beschränkt werden.
long potenz_modulo(long x, long y, long n) {
long res = 1;
while(y) {
if (y & 0x01) res = (res * x) % n;
y>>= 1;
x = (x * x) % n;
}
return res;
}
|
Die Vorgänge zur Schlüsselerzeugung und die Ver- bzw. Entschlüsselung werden nun an einem kleinen Beispiel verdeutlicht. Ziel des Beispiels ist es den Text "Geheim" in verschlüsselter Form zu versenden.
Zunächst muß der potenzielle Empfänger der Botschaft seinen öffentlichen Schlüssel bekannt gegeben haben. In diesem Fall hatte sich der Empfänger für die sehr unsichere Schlüssellänge von 17 Bits entschieden (ermöglicht Informationsblöcke von 16 Bit). Für n testete er die zufälligen Primzahlkandidaten 503 (9 Bit), 209 (8 Bit) und 193 (8 Bit) mittels des Rabin-Miller-Tests.
Rabin-Miller-Test mit 209:
→ Test nicht bestanden
209 = 1 + 24·13 j 0 1 2 3 4 a = 43 131 23 111 199 100
Rabin-Miller-Test mit 193:
→ Test bestanden
193 = 1 + 26·3 j 0 1 2 3 4 5 6 a = 150 9 81 192 a = 21 190 9 81 192 a = 93 126 50 184 81 192 a = 62 166 150 9 81 192 a = 7 150 9 81 192
Nachdem sich der Empfänger für p = 509 und q = 193 entschieden hatte, ergab sich für n 97079 und φ(n) = (p - 1)(q - 1) = 96384. Als Potenz e wählte er die Primzahl 17, die teilerfremd zu φ(n) ist. Die Anwendung des erweiterten Euklidischen Algorithmus ergab die Vielfachsummendarstellung:
ggt(17, φ(n)) = 1 = 17009·17 + (-3)·φ(n) → d = 17009
Seitdem der öffentliche Schlüssel (17, 97079) publik gemacht wurde, können dem Empfänger verschlüsselte Nachrichten zugesandt werden:
Text Ge he im Ascii-Code 18277 26725 26989 Verschlüsselung ci = mie mod n 825 71160 3762 Ungesicherter Kommunikationsweg Verschl. Nachricht 825 71160 3762 Entschlüsselung mi = cid mod n 18277 26725 26989 Text Ge he im
Die Sicherheit von Chiffrierverfahren drückt den Aufwand aus, den Personen (Gegner) mit kryptoanalytischen Angriffen betreiben müssen, um den Klartext oder den Schlüssel (bei Public-Key-Verfahren, privater Schlüssel) zu ermitteln. In Abhängigkeit der Mittel und den Informationen die den Gegnern zur Verfügung stehen (z.B. nur der verschlüsselte Text oder der verschlüsselte Text und der dazugehörige Klartext), werden die Angriffe verschiedenen Arten zugeordnet: z.B. Ciphertext-only-, Known-plaintext-, Chosen-plaintext- und Chosen-ciphertext-Angriff (siehe [BS]). Sind bei einigen Angriffsarten unter besonderen Konstellationen von Klartext, Chiffriertext und Schlüssel Schwächen vorhanden, kann das Chiffrierverfahren dennoch angewandt werden, falls das Protokoll, in welches das Verfahren eingebettet ist, diese Sicherheitslücken schließt.
Zunächst soll der Angriff auf einen willkürlichen privaten Schlüssel betrachtet werden, bei dem lediglich der öffentliche Schlüssel bekannt ist.
Man vermutet, dass die Sicherheit von RSA auf dem Problem der Faktorisierung großer Zahlen basiert. Ist die Faktorisierung von n bekannt (p und q), kann mittels φ(n) der private Schlüssel berechnet werden (siehe Schlüsselerzeugung).
Zu den schnellsten Faktorisierungsalgorithmen zählen das Zahlenkörpersieb und das Quadratische Sieb, wobei das Zahlenkörpersieb für Zahlen mit mehr als 110 Dezimalstellen schneller ist als das Quadratische Sieb. Die Komplexitätsabschätzung des Zahlenkörpersiebs lautet:
Die Primzahlfaktoren von n (p und q) werden üblicherweise durch Zufallszahlengeneratoren erzeugt. Die wichtigste Eigenschaft von p und q für das Erschweren der Faktorisierung ist, dass p und q etwa die gleiche Größe besitzen.
Neben der Voraussetzung, dass p und q prim sind, wird oft auch gefordert, dass sie starke Primzahlen sind. Eine Primzahl x wird als stark bezeichnet, falls die Faktorisierung von x - 1 bestimmten Einschränkungen unterliegt (siehe [BS]). Die Forderung nach starken Primzahlen begründet sich durch einige ältere Faktorisierungsalgorithmen, die Produkte von Primzahlen ohne diese Eigenschaft schneller faktorisieren.
Bei den zur Zeit schnellsten Algorithmen unterscheiden sich die Berechnungszeiten nicht in Abhängigkeit dieser Eigenschaft. Daher kann nach heutigem Stand auf starke Primzahlen zugunsten höherer Modullänge verzichtet werden. Dies kann sich bei neuen Algorithmen wieder ändern.
Die RSA-Verschlüsselung erfolgt wesentlich schneller, wenn man den Wert von e geschickt wählt. Die gebräuchlichsten Werte sind 3, 17 und 65537. Je weniger binäre Einsen die Zahl enthält, desto schneller ist die Verschlüsselung (siehe Chiffrierung). Die Verwendung von kleinen Exponenten birgt jedoch auch ein Sicherheitsrisiko. Für den Exponenten 3 gilt z.B. folgendes: wird ein und dieselbe Nachricht mit drei verschiedenen öffentlichen Schlüsseln chiffriert, kann mittels des Chinesischen Restsatzes aus den Kryptogrammen der Klartext ermittelt werden (Der chinesische Restsatz und dieser Chosen-ciphertext-Angriff werden an dieser Stelle nicht näher erläutert, siehe [BSW]).
Es ist nicht das Ziel dieses Abschnitts die Berechnung des Klartextes durch die aufgezeigte Sicherheitslücke zu erläutern, sondern aufzuzeigen, wie durch ein Protokoll die Sicherheitslücke geschlossen werden kann. Durch das Hinzufügen von Zufallszahlen zu den Klartexten wird die oben genannte Gefahr gebannt. Die meisten existierenden Protokolle, die das RSA-Verfahren verwenden, z.B. PGP, tun dies.
Für eine gesicherte Übertragung von Informationen zwischen zwei Partnern ist die Einigung auf ein Verschlüsselungsverfahren nicht ausreichend. Sie müssen ein Protokoll aufstellen, das festlegt, welche Aktionen ein Partner zu einem bestimmten Zeitpunkt durchzuführen hat.
Häufig wird in Protokollen nicht nur ein kryptographischen Algorithmus verwendet, sondern mehrere, da sich für einige Protokollphasen (z.B. Schlüsselverteilung, Kommunikationsaufbau, Kommunikation) unterschiedliche kryptographische Algorithmen am Besten eignen.
Public-Key-Algorithmen und somit auch das RSA-Verfahren sind bedeutend langsamer als Symmetrische Verfahren. Daher wird in vielen Protokollen das RSA-Verfahren zur Vereinbarung eines geheimen Sitzungsschlüssels in der Kommunikationsaufbauphase angewandt, anschließend wird die Nachricht jedoch mit einem symmetrischem Verfahren (z.B. DES, RC4, IDEA) und dem Sitzungsschlüssel chiffriert.
Die Echtheit eines öffentlichen Schlüssels (d.h. der zugehörige private Schlüssel ist in Besitz des beabsichtigten Empfängers) wird oft durch Zertifikate bestätigt. Zertifikate sind Informationsblöcke aus einem öffentlichen Schlüssel und deren Besitzer, die mit einem in der Regel bekannterem öffentlichen Schlüssel chiffriert sind (siehe [BS]).
Beispiele für Protokolle, die das RSA-Verfahren verwenden sind:
![[Universität Karlsruhe]](/images/ico_uni.png)
|
![[Institut für Technische Informatik]](/images/ico_home.png)
|
![[E-Mail an Autor]](/images/ico_mail.png) |
| Letzte Änderung: 2000-02-18 16:09:52 |