<< . .

. 16
( : 33)



. . >>

7.2 Der chinesische Restsatz 121

7.2.4 Optimierung des Entschlüsselns mit dem chinesischen Restsatz
Erh¤lt der Empf¤nger R den Geheimtext c = C ∈ Z n , n = p q, so entschlüsselt
dieser den Geheimtext mit seinem geheimen Schlüssel d zu dem Klartext N , in-
dem er die Potenz C d = N in Z n bildet. Dabei bestimmt R die kleinste positive
Zahl a ∈ N mit a = N :
cd ≡ a (mod n) .
Die Zahl n ist beim RSA-Verfahren üblicherweise mindestens 1024 Bit lang, daher
ist diese Rechnung sehr aufw¤ndig. Mithilfe des chinesischen Restsatzes können
wir das Entschlüsseln ef¬zienter gestalten:
Berechne die kleinsten positiven Zahlen a p , aq mit

cd ≡ a p (mod p) und cd ≡ aq (mod q) .

Bestimme mit dem Lösungsverfahren für Systeme von Kongruenzgleichun-
gen die kleinste positive Lösung x des Systems

X ≡ a p (mod p) und X ≡ aq (mod q) .

Die Lösung x liefert den Klartext, d. h. x = N .
Denn: Aus x ≡ a p (mod p) und x ≡ aq (mod q) folgt

x ≡ cd (mod p) und x ≡ cd (mod q) ,

und daher gilt p | x ’ cd und q | x ’ cd , wegen der Teilerfremdheit von p und q
folgt n = p q | x ’ cd , d. h. x = cd = C d = N .

Bemerkung
Ist n eine k-Bit-Zahl, so haben p und q etwa k/2 Bit. Modulo n kostet das Ent-
schlüsseln
(c k) (C k2 ) = c C k3 , c , C ∈ R >0 , 1.5 ¤ c ¤ 2 ,
Grundoperationen. Nach den Lemmata 6.15 und 4.3 sind n¤mlich bei der schnel-
len Exponentiation c k Multiplikationen, die je C k2 Grundoperationen (C eine
Konstante) benötigen, durchzuführen. Die Absch¤tzung für c ergibt sich aus der
Bemerkung gleich im Anschluss an den Beweis von Lemma 6.15.
Dechiffriert man nun wie geschildert mit dem chinesischen Restsatz, so sind zwei
Potenzen modulo p und q zu bilden, die Kosten dafür sind
2
k3
k k
= cC
2 ,
c C
2 2 4

Grundoperationen. Dabei haben wir das Anwenden des chinesischen Restsatzes
vernachl¤ssigt, weil er “ wie der euklidische Algorithmus “ O(k2 ) Laufzeit hat.
Durch diese (grobe) Analyse erhalten wir, dass das Entschlüsseln einer Nachricht
mit dem chinesischen Restsatz um etwa den Faktor 4 schneller ist.
122 7 Das RSA-Verfahren

7.3 RSA und das Faktorisierungsproblem *
Es seien in diesem Abschnitt stets n = p q mit verschiedenen Primzahlen p, q
und Zahlen e, d so gew¤hlt, dass ggT(e, •(n)) = 1 und e d ≡ 1 (mod •(n)) er-
füllt sind. Kurz: Es seien n, p, q, e, d wie beim RSA-Verfahren gegeben. Ohne
Einschr¤nkung setzen wir e = 1 voraus; es w¤re sonst d = 1 der geheime Schlüs-
sel, und das w¤re auch jedem Angreifer klar. Wir begründen, dass die beiden
Probleme, n¤mlich

• die Zahl n in seine Primfaktoren p und q zu zerlegen und

die Bestimmung von d aus dem öffentlichen Schlüssel (n, e),


algorithmisch ¤quivalent sind (siehe Seite 64). Dazu werden wir jeweils einen
polynomialen Algorithmus angeben, der das eine auf das andere Problem zu-
rückführt.
Das Faktorisierungsproblem wird seit vielen Jahrhunderten als ein schwieriges Pro-
blem angesehen, d. h., man vermutet, dass es nicht in der Komplexit¤tsklasse P
liegt. Ist das der Fall, dann ist es auch schwierig, den geheimen Schlüssel d aus
dem öffentlichen Schlüssel (n, e) zu bestimmen.
Man erkennt, dass die Sicherheit von RSA eng mit der Schwierigkeit der Faktori-
sierung ganzer Zahlen verknüpft ist.


Kenntnis von p und q liefert d
7.3.1
Bekannt ist der öffentliche Schlüssel (n, e). Wenn man die Zahl n faktorisieren
kann, d. h., wenn man die Primzahlen p und q mit n = p q bestimmen kann, so
erh¤lt man hieraus den geheimen Schlüssel d wie der legitime Anwender.

Bestimme zuerst •(n) = (p ’ 1) (q ’ 1).

Löse die Kongruenz e X ≡ 1 (mod •(n)).

Die Lösung d mit 1 ¤ d ¤ •(n) ist der geheime Schlüssel.

Im n¤chsten Abschnitt zeigen wir die Umkehrung: Kennt man den geheimen
Schlüssel d, so erh¤lt man aus dem öffentlichen Schlüssel (n, e) die Faktorisie-
rung n = p q von n.



Kenntnis von d liefert p und q
7.3.2

Wir schicken dem wesentlichen Ergebnis einen Hilfssatz voran. Wir schreiben für
Zahlen a, m ∈ Z mit ggT(a, m) = 1 im Folgenden o(a)mod m für die Ordnung von
a = a + m Z ∈ Z— .
m
7.3 RSA und das Faktorisierungsproblem * 123

Lemma 7.7
Es sei v ∈ N so gew¤hlt, dass k := ed’1 ∈ N ungerade ist. Gilt für ein a ∈ Z mit
2v
ggT(a, n) = 1:
o(ak )mod p = o(ak )mod q ,
t
so existiert ein t ∈ {0, 1, . . . , v ’ 1} mit 1 < ggT(a2 k ’ 1, n) < n. Insbesondere gilt
t t
p = ggT(a2 k ’ 1, n) oder q = ggT(a2 k ’ 1, n) .

Beweis. Wegen e d ≡ 1 (mod •(n)) existiert ein r ∈ Z mit e d ’ 1 = r •(n). Also
gilt nach dem Satz 6.9 von Euler:

≡ aed’1 ≡ ar•(n) ≡ (a •(n) )r ≡ 1 (mod n) .
v vk
(ak )2 ≡ a2
v
Das heißt aber n | (ak )2 ’ 1, wegen n = p q folgt
v v
(ak )2 ≡ 1 (mod p) und (ak )2 ≡ 1 (mod q) .

Damit sind die Ordnungen o(ak )mod p und o(ak )mod q Potenzen von 2 kleiner oder
gleich 2v (beachte Lemma 6.1 (b)).
1. Fall. o(ak )mod p < o(ak )mod q ¤ 2v : Dann existiert ein t ∈ {0, 1, . . . , v ’ 1} mit
o(ak )mod p = 2t . Wir erhalten:
t t t
a2 k ≡ (ak )2 ≡ 1 (mod p) ’ p | a2 k ’ 1 ,
t t t
a2 k ≡ (ak )2 ≡ 1 (mod q) ’ q a2 k ’ 1 .
t
Folglich gilt ggT(a2 k ’ 1, n) = p.
t
2. Fall. o(ak )mod q < o(ak )mod p ¤ 2v : Man erh¤lt analog ggT(a2 k ’ 1, n) = q.
Das Lemma zeigt, dass die Kenntnis von n, e und d eines RSA-Systems eine Fak-
torisierung von n erlaubt, falls man nur ein passendes a ¬ndet. Man gehe wie folgt
vor:

Bestimme v ∈ N, sodass k = ed’1
ungerade ist.
2v

W¤hle ein a ∈ Z mit 1 < a < n.

Ist ggT(a, n) > 1 “ Stop!, sonst:
t
Bestimme ggT(a2 k ’ 1, n) für t ∈ {0, 1, . . . , v ’ 1}.

Falls diese ggT alle gleich 1 oder n sind, so w¤hle man ein neues a. Ansonsten
ist eine Faktorisierung bestimmt.

Wir begründen nun, dass die Wahrscheinlichkeit, ein passendes a zu ¬nden, sehr
groß ist:
124 7 Das RSA-Verfahren

Lemma 7.8
Es seien p, q = 2 verschiedene Primzahlen, und es sei v ∈ N so gew¤hlt, dass k :=
2v ∈ N ungerade ist. Dann gilt
ed’1


•(n)
a ∈ Z ; 1 < a < n, ggT(a, n) = 1, o(ak )mod = o(ak )mod q ≥ .
p
2

Beweis. Es seien g p und gq ganze Zahlen mit der Eigenschaft, dass g p ∈ Z — eine
p
— eine solche modulo q sind, d. h., es gilt
Primitivwurzel modulo p und gq ∈ Z q
g p = Z — und gq = Z — (zur Existenz siehe Satz 6.12).
p q
Nach dem chinesischen Restsatz 7.4 hat das Kongruenzgleichungssystem

X ≡ g p (mod p) , X ≡ gq (mod q)

eine Lösung g ∈ Z. Es ist damit g + p Z eine Primitivwurzel modulo p und
g + q Z eine Primitivwurzel modulo q.
1. Fall: o(gk )mod p > o(gk )mod q . Es seien ± ∈ {1, . . . , p ’ 1} ungerade und
β ∈ {0, . . . , q ’ 2}. Mit dem chinesischen Restsatz 7.4 erhalten wir zu (±, β) eine
Lösung a ∈ {2, . . . , n ’ 1} des Kongruenzgleichungssystems

X ≡ g± (mod p) , X ≡ g β (mod q) .
(—)

Wegen a = g± ∈ Z — und a = g β ∈ Z — sind a und n teilerfremd. Und wegen
p q
k )2v ≡ 1 (mod p) (beachte den Satz 6.9 von Euler) ist o(gk )
(g mod p eine Potenz
von 2. Da 2 ±, gilt mit Lemma 6.2:

= o((gk )± )mod p = o(gk )mod p .
o(ak )mod p

Damit erhalten wir (man beachte erneut Lemma 6.2):

o(ak )mod q = o((gk ) β )mod q ¤ o(gk )mod q < o(gk )mod = o(ak )mod p .
p

Aufgrund der Tatsache, dass g eine Primitivwurzel modulo p und q liefert, er-
halten wir für (± , β ) = (±, β) mit ± ∈ {1, . . . , p ’ 1} ungerade und β ∈
{0, . . . , q ’ 2} auch ein anderes a als Lösung zu dem Kongruenzgleichungssys-
tem in (—). Weil es insgesamt (p ’ 1) (q ’ 1)/2 = •(n)/2 verschiedene solche
Paare (±, β) gibt, gibt es auch •(n)/2 verschiedene solche Zahlen a.
2. Fall: o(gk )mod < o(gk )mod q . Dieser Fall geht analog zum ersten Fall.
p
3. Fall: o(gk )mod p = o(gk )mod q . Es seien ± ∈ {1, . . . , p ’ 1}, β ∈ {1, . . . , q ’ 1} mit
± ≡ β (mod 2), d. h., ± und β seien nicht beide zugleich gerade oder ungerade,
und a ∈ {2, . . . , n ’ 1} sei eine Lösung des Systems in (—). Wie im 1. Fall folgt:
Die Zahlen a und n sind teilerfremd und es existieren (p ’ 1) (q ’ 1)/2 = •(n)/2
verschiedene solche a.
Falls 2 ± gilt, so folgt 2 | β und damit (beachte Lemma 6.2):

o(ak )mod q = o((gk ) β )mod q < o(gk )mod q = o(gk )mod = o(ak )mod p .
p
7.3 RSA und das Faktorisierungsproblem * 125

Falls 2 β gilt, so folgt 2 | ± und damit analog zum obigen Fall:
= o((gk )± )mod p < o(gk )mod p = o(ak )mod q .
o(ak )mod p

In jedem Fall gilt also o(ak )mod = o(ak )mod q .
p

Die Wahrscheinlichkeit dafür, dass man nach r Iterationen (bei zuf¤lliger Wahl
von a) einen Faktor von n gefunden hat, ist also größer als 1 ’ 2r . Nach 10 Ite-
1

rationen hat man mit einer Wahrscheinlichkeit von mehr als 99.9 Prozent einen
Faktor von n bestimmt.
Tats¤chlich erh¤lt man mit dieser Methode nur sehr wahrscheinlich eine Faktori-
sierung der Zahl n. Aber die Wahrscheinlichkeit ist beliebig groß, man muss nur
hinreichend oft iterieren. Einen Algorithmus, der mit beliebig hoher Wahrschein-
lichkeit ein richtiges Ergebnis liefert, nennen wir probabilistisch.

Bemerkung
Ein probabilistischer Algorithmus kann auf zwei Weisen scheitern:
• Er ¬ndet kein Ergebnis oder
• er liefert ein falsches Ergebnis
“ beides mit kleiner Wahrscheinlichkeit.

Wir halten fest:

Korollar 7.9
Aus n, e und d können p und q in polynomialer Zeit ermittelt werden.

Wir haben begründet, dass die beiden Probleme,
d aus (n, e) zu bestimmen und

• n zu faktorisieren,
gleich schwer zu lösen sind. Weil das Problem, eine Zahl n zu faktorisieren, schon
seit Jahrhunderten als ein schwieriges Problem in der Mathematik erachtet wird
(evtl. nicht in der Komplexit¤tsklasse P liegt), haben wir hiermit gezeigt, dass
das Berechnen des geheimen Schlüssels d aus dem öffentlichen Schlüssel (n, e)
beim RSA-Verfahren ebenfalls als schwierig anzusehen ist. Es ist aber bisher nicht
gelungen zu zeigen, dass das Brechen des RSA-Verfahrens ¤quivalent zum Fak-
torisieren von n ist “ man kann ja eventuell ohne Kenntnis von d entschlüsseln.
Aber es wird vermutet, dass dem nicht so ist.

Bemerkung
Man sagt genauer, dass die beiden Probleme probabilistisch algorithmisch ¤qui-
valent sind. Nach [17] gibt es einen deterministischen, d. h. nicht probabilisti-
schen polynomialen Algorithmus, der aus der Kenntnis von d eine Faktorisierung
von n errechnet. Daher sind die beiden Probleme algorithmisch ¤quivalent.
126 7 Das RSA-Verfahren

Wahl der Parameter p, q, e und d bei RSA
7.4
Bereits in der Originalarbeit [22] wiesen die Autoren auf mögliche Angriffe und
wie sie abzuwenden seien hin. In der Folgezeit wurden viele weitere Vorschl¤ge
gemacht, das Verfahren zu brechen. Alle diese Vorschl¤ge resultierten letztlich
in Bedingungen an die Wahl der Parameter. Um vor den bis heute bekannten
Angriffen geschützt zu sein, müssen nicht nur die Primzahlen p und q speziell
gew¤hlt werden, auch die Schlüssel e und d dürfen nicht beliebig sein. Sie müs-
sen hinreichend groß sein. Andernfalls könnte der Low-Exponent-Angriff oder der
Wiener-Angriff erfolgreich sein.

Wahl von p und q
7.4.1
Wir geben ein paar Richtlinien dafür, wie man beim RSA-Verfahren die Primzah-
len p und q w¤hlen sollte:

• Größenordnung p, q mindestens 512 Bit, bei besonderes hohen Sicherheits-
anforderungen bis zu 1024 Bit;

p ’ 1 sollte einen großen Primteiler r haben und q ’ 1 einen großen Prim-

teiler s;

p + 1 und q + 1 sollten große Primteiler haben;


Die Zahlen r ’ 1 bzw. s ’ 1 sollten ebenfalls große Primteiler haben.


Sind diese Bedingungen für die Primzahlen p und q nicht erfüllt, so könnten be-
kannte Faktorisierungsalgorithmen, auf die wir im Kapitel 11 eingehen, erfolg-
reich sein, d. h., es könnte sein, dass ein Angreifer aus der öffentlich bekannten
Zahl n die Primteiler p und q ermitteln könnte. N¤here Informationen folgen im
angekündigten Kapitel.

Bemerkung
Mit dem Primzahlsatz (siehe Seite 142) können wir absch¤tzen, wie viele Prim-
zahlen mit 512 Bit es ungef¤hr gibt, n¤mlich

2512 2511
’ ≈ 1.9 · 10151 .
512 ) 511 )
ln(2 ln(2

Zum Vergleich: Die Anzahl der Atome im Universum wird auf weniger als 1080
gesch¤tzt.

Die Wahl von e
7.4.2

Die Zahl e sollte nicht zu klein gew¤hlt werden, sonst kann der Low-Exponent-
Angriff Anwendung ¬nden. Wie in der Praxis üblich, stellen wir einen Klartext
7.4 Wahl der Parameter p, q, e und d bei RSA 127

als natürliche Zahl N dar, die kleiner ist als jeder im System verwendete Modul
n. Bei Bedarf identi¬zieren wir die Zahl N mit einer Restklasse.
Wir gehen beispielhaft von der folgenden Situation aus: Drei Teilnehmer des
RSA-Verfahrens haben die drei öffentlichen Schlüssel (n1 , 3), (n2 , 3), (n3 , 3), d. h.,
jeder der drei Teilnehmer benutzt das gleiche öffentliche e = 3, mit paarweise
teilerfremden n1 , n2 , n3 . Wird nun ein und dieselbe Nachricht N bezüglich der
drei öffentlichen Schlüssel (n1 , 3), (n2 , 3), (n3 , 3) zu den Geheimtexten C1 , C2 , C3
verschlüsselt, d. h. C1 = N 3 ∈ Z n1 , C2 = N 3 ∈ Z n2 , C3 = N 3 ∈ Z n3 , so kann ein
Angreifer aus den Geheimtexten C1 , C2 , C3 mithilfe des chinesischen Restsatzes
auf die Nachricht N schließen, ohne den Schlüssel d zu kennen.

Lemma 7.10
Es seien paarweise teilerfremde natürlichen Zahlen n1 , . . . , ne , e ∈ N, gegeben. Für eine
natürliche Zahl a gelte 0 ¤ a < n1 , . . . , ne . Es seien c1 , . . . , ce mit
c1 ≡ ae (mod n1 ), . . . , ce ≡ ae (mod ne )
bestimmt. Dann gibt es genau ein c ∈ N mit 0 ¤ c < n1 · · · ne und c ≡ ci (mod ni )
für i = 1, . . . , e. Weiter gilt c = ae .

Beweis. Nach dem chinesischen Restsatz 7.4 ist das Kongruenzensystem
(—) X ≡ c1 (mod n1 ), . . . , X ≡ ce (mod ne )
lösbar. Ist x eine Lösung des Systems, so ist nach Abschnitt 7.2.2 die Menge x +
n1 · · · ne Z die Lösungsmenge. Daher gibt es genau eine Lösung c mit 0 ¤ c <
n1 · · · ne . Da außerdem ci ≡ ae (mod ni ) für i = 1, . . . , e gilt, erhalten wir c ≡
ae (mod ni ) für i = 1, . . . , e. Somit sind c und ae beides Lösungen des Systems
(—) mit 0 ¤ c, ae < n1 · · · ne . Es folgt c = ae .
Man beachte, dass genau die oben geschilderte Situation vorliegt. Ein Angreifer,
dem die Geheimtexte
c 1 = C1 = N e ∈ Z n1 , . . . , c e = C e = N e ∈ Z n e
vorliegen, die ein und dieselbe Nachricht N darstellen und die mit jeweils dem
gleichen Verschlüsselungsexponenten e erhalten wurden, kann mit dem chinesi-
schen Restsatz die natürliche Zahl c = ae bestimmen, für die gilt a = N . Ent-
scheidend ist, dass c eine e-te Potenz in N ist. Daher kann man die e-te Wurzel
in polynomialer Zeit numerisch ziehen (vgl. auch Aufgabe 8.6). So erh¤lt der An-
greifer die Zahl a und damit den Klartext N .

Bemerkung
Bei diesem Angriff ist es wesentlich, dass e Teilnehmer denselben Verschlüsse-
lungsexponenten e benutzen. Das ist umso leichter möglich, als e eine kleine Zahl
ist, daher der Begriff Low-Exponent-Angriff.
In der Frühzeit von RSA wurde e = 3 sogar als öffentlicher Exponent für alle
vorgeschlagen.
128 7 Das RSA-Verfahren

Beispiel
Ein Netzwerk bestehe aus drei Teilnehmern, die zur Verschlüsselung ihrer Kom-
munikation das RSA-Verfahren benutzen. Die öffentlichen Schlüssel der Teilneh-
mer seien (n1 , 3), (n2 , 3) bzw. (n3 , 3) mit

n1 = 205 , n2 = 319 , n3 = 391 .

Ein Klartext wird mit dem öffentlichen Schlüssel der drei Teilnehmer zu den Ge-
heimtexten C1 , C2 , C3 verschlüsselt und an diese gesandt. Dabei gelangen einem
Angreifer A die Geheimtexte

C1 = 102 , C2 = 193 , C3 = 121

in die H¤nde. Der Angreifer A berechnet hieraus mithilfe des chinesischen Rest-
satzes die eindeutig bestimmte Lösung des Kongruenzgleichungssystems

X ≡ 102 (mod n1 ) , X ≡ 193 (mod n2 ) , X ≡ 121 (mod n3 )

und erh¤lt c = 512. Durch Ziehen der dritten Wurzel aus c erh¤lt A die Zahl
a = 8. Das ist der Klartext.

Bemerkung
H¤u¬g wird e = 216 + 1 gew¤hlt. Diese Fermat™sche Primzahl ist ziemlich sicher
zu •(n) teilerfremd. Für die Berechnung von ae mit der schnellen Exponentiation
(siehe Abschnitt 6.3) werden nur 17 Multiplikationen benötigt.



Die Wahl von d
7.4.3

Die Zahl d ist bestimmt durch die Wahl von e. Aber man sollte beachten, dass
die Zahl d nicht zu klein ausf¤llt. Falls doch, so sollte ein anderes e gew¤hlt wer-
den. Bei kleinem d ist n¤mlich der sogenannte Wiener-Angriff ernst zu nehmen.
Wir erl¤utern diesen nach der hierzu notwendigen Einführung in die Theorie der
Kettenbrüche.



7.5 Kettenbrüche *

Der Wiener-Angriff auf RSA basiert auf der Theorie der Kettenbrüche. Ketten-
brüche liefern eigentlich ein Verfahren, reelle Zahlen durch rationale Zahlen zu
approximieren. Wir konzentrieren uns darauf, rationale Zahlen durch rationale
zu approximieren, daher werden wir mit meist mit endlichen Kettenbrüchen aus-

<< . .

. 16
( : 33)



. . >>