7.4.2 Diskussion von RSA

Wir haben schon weiter oben ein Prinzip besprochen, daß essentiell ist für die moderne Kryptographie, das Prinzip von Kerkhoffs: Die Sicherheit eines Verfahrens sollte nicht auf dessen Geheimhaltung beruhen. Dieser Satz mag sofort einleuchten, aber er erfordert eine nähere Betrachtung:

Natürlich muß irgendetwas an einem Verschlüsselungsverfahren geheimgehalten werden, das ist mehr als offensichtlich. Wir hatten deswegen unterschieden zwischen dem allgemeinen Verfahren und dem Schlüssel. Diese Trennung soll nun spezifiziert werden.

Wenn man von Verfahren im Sinne von Algorithmus spricht, also von einer detailgenauen Anweisungsfolge, dann stimmt das Kerkhoffs-Prinzip nicht oder nur eingeschränkt. Denn der Schlüssel ist ja integraler Bestandteil des Algorithmus, der im Computer abgearbeitet wird.

Das Kerkhoffs-Prinzip gilt also nur für das allgemein angewandte Prinzip, nicht für den konkreten Algorithmus.

Nun ist das bei symmetrischen Verfahren kein Problem; Ich erzähle zwar ungeniert, daß ich DES oder IDEA benutze, den Schlüssel aber behalte ich für mich, ebenso geht mein Kommunikationspartner vor.

Anders ist das bei RSA und anderen asymmetrischen Systemen. Hier erzähle ich nicht nur, daß ich RSA benutze, sondern ich gebe auch noch den Schlüssel bekannt, mit dem ich verschlüssele. Das ist ein qualitativer und signifikanter Unterschied zum Vorgehen bei symmetrischen Verfahren. Natürlich ist es zunächst einmal schwierig bis unmöglich, das auszunutzen; aber es ist wichtig, daß dieser Unterschied realisiert wird!

RSA stützt seine gesamte Sicherheit darauf, daß aus dem Modulus n und dem öffentlichen Schlüssel e keine Rückschlüsse auf den geheimen Schlüssel d gezogen werden können und daß die Faktorisierung größenordnungsmäßig so schwierig bleibt, wie sie heute ist. Dummerweise ist noch nicht einmal beweisbar, daß RSA von der Komplexität her dem Faktorisieren oder ähnlichen Problemen äquivalent ist.

Um einem Angriff durch Faktorisierung zu entgehen, muß n selbstverständlich sehr groß gewählt werden. Da mit durchschnittlichen Mitteln und nur als Abfallprodukt eine 129-stellige Zahl (das entspricht 429 Bit) erfolgreich faktorisiert wurde (rsa-129), gilt heute als unterste Grenze eine Schlüssellänge von mindestens 200 Dezimalstellen (666 Bit), oft wird aber eine noch größere Länge gefordert (1024 Bit).

Außerdem müssen sich die beiden Primfaktoren p und q, aus denen n gebildet wird, um einige wenige Stellen in der Länge unterscheiden. Beide Zahlen dürfen nicht gleichviele Stellen besitzen. Das liegt daran, daß man sonst eine exhaustive Suche nach einer Darstellung von n als Differenz von Quadraten durchführen könnte. Auch wenn eine der beiden Zahlen extrem klein ist, kann man eine Faktorisierung recht flott durchführen [22].

Benutzt man die Ergebnisse des RSA-129-Projekts, so kann man berechnen, wie lange man zur Faktorisierung längerer Schlüssel benötigt. Der Kryptologe Schneier hat dazu eine Formel aufgestellt, die hier Anwendig findet. Dabei muß bedacht werden, daß sich diese Werte auf das im RSA-129-Projekt benutzte Verfahren beziehen, welches nicht das beste ist. Für bessere Verfahren verkürzen sich die Zeiten entsprechend.

Schlüssellänge   Zeitfaktor relativ zu RSA-129
       429               1.0
       512               7.66719
      1024               1.05473 * 1005
      2048               2.97180 * 1010
      4096               4.28061 * 1017
      8192               1.02939 * 1027
     16348               1.90839 * 1039

Ein weiteres großes Problem ergibt sich, wenn man die in RSA benutzten Methoden anwendet. Wir wollen das an einem Beispiel demonstrieren:

Nehmen wir an, wir haben eine natürliche Zahl m und sie soll der Beginn einer Reihe von Zahlen sein, die durch Exponentbildung wie in RSA entstehen; wir benutzen dabei einen beliebigen Modulus n:

c0 = m; c1 = c = (m * e) mod n

Nun wird ci+1 gebildet:

ci+1 = (ci * e) mod n für i aus {1,2,3,...}

Wenn i einen bestimmten Wert k überschritten hat, dann gilt:

ck+1 = c1

Das bedeutet, daß nach k Schritten wieder der ursprüngliche Wert wieder zum Vorschein kommt.

Ein Beispiel dazu:

   (e, d) = (17, 157), n = 47 * 59 = 2773;
   &phgr;(n) = 2668

c0 = m = 0518 c1 = c = 051817 mod 2773 = 1787 c2 = 178717 mod 2773 = 0894 c3 = 051817 mod 2773 = 1364 c4 = 051817 mod 2773 = 0518

Damit erhalten wir nach 4 Runden wieder den Klartext, ohne den geheimen Schlüssel d wissen zu müssen!

Um diesen Iterationsangriff abzuwehren, werden einige Bedingungen an p, q und ihr Verhältnis gestellt:

1. (p-1) und (q-1) müssen große Primfaktoren enthalten.

2. ggt ( (p-1), (q-1) ) muß sehr klein sein.

3. (p'-1)/2 und (q'-1)/2 müssen große Primfaktoren enthalten.

4. ggt (p' - 1, q' - 1) muß sehr klein sein.

Dabei bedeuten:

   ggt      Größter gemeinsamer Teiler; z.B.:
            ggt ( 5,  10) = 5,
            ggt ( 6,  16) = 2,
            ggt (17, 100) = 1.
   p', q'   p' := (p-1) / 2,
            q' := (q-1) / 2

Primzahlen, die die beiden ersten Bedingungen erfüllen, heißen sichere Primzahlen. Eine Primzahl p ist sicher, wenn mit p auch (p-1)/2 eine Primzahl ist. Beispiele: 5, 7, 11, 23, 47.

Außer 5 und 7 haben alle sicheren Primzahlen die Form

p = (12 * a - 1) mit a aus {1,2,3, ...}

Primzahlen, welche die beiden letzten Bedingungen erfüllen, heißen doppelt sichere Primzahlen. Eine Primzahl p ist doppelt sicher, wenn mit p auch p' eine sichere Primzahl ist. Beispiele sind 11, 23, 47, 167.

Außer 11 haben alle doppelt sicheren Primzahlen die Form

p = (24 * a - 1) mit a aus {1,2,3,...}

Wie man hier sehr deutlich sieht, müssen die beiden Primzahlen p und q extrem sorgfältig ausgewählt werden, um das Verfahren optimal sicher zu machen und die Eigenschaften zu nutzen, die dessen Autoren ihm zugedacht haben.

Auch ein kleines e, was intuitiv einen Vorteil beim Rechnen verspricht, sollte vermieden werden. Vor allem beim Einsatz von Chipkarten möchte man diesen Vorteil erreichen. Verschickt man nun aber denselben Text an verschiedene Empfänger mit verschiedenen Empfängerschlüsseln, so lassen sich mit Hilfe des sogenannten "Chinesischen Restsatzes" (z.B. [28]) relativ leicht Rückschlüsse auf den Klartext ziehen.

Schwierig wird es, wenn RSA tatsächlich in großem Maßstab eingesetzt wird. Dann bekommt man einige Probleme, genügend viele und genügend große Primzahlen zu finden, denn Primzahlen kommen nicht regelmäßig vor - man muß sie suchen. Weil das sehr aufwendig ist, benutzt man häufig statistische Verfahren, um Zahlen zu bekommen, von denen man mit einer gewissen Wahrscheinlichkeit sagen kann, daß sie Primzahlen sind. Man nennt solche Zahlen Pseudoprimzahlen.

RSA gilt durchaus als praktisch sicher, wenn die genannten Bedingungen erfüllt sind. Werden jedoch Pseudoprimzahlen eingesetzt, können die Rahmenbedingungen aufgeweicht werden. Das sollte man bedenken, wenn man RSA einsetzt.