<<

. 5
( 9)



>>

Bemerkung
Die Wohlde¬niertheit ist die Umkehrung der Injektivit¤t.

Wir machen uns klar, was die Surjektivit¤t der Abbildung ψ in Lemma 7.3 besagt:
Zu beliebigen a1 , . . . , an ∈ Z gibt es ein x ∈ Z mit

x + r1 Z = a1 + r1 Z , . . . , x + r n Z = a n + r n Z

oder anders geschrieben

x ≡ a1 (mod r1 ) , . . . , x ≡ an (mod rn ) .

Dies besagt, dass man ein System von Kongruenzgleichungen zu teilerfremden
Moduln simultan lösen kann. Das war bereits Sun-Tsu im 1. Jahrhundert unserer
Zeitrechnung bekannt.

Satz 7.4 (Chinesischer Restsatz)
Sind r1 , . . . , rn ∈ Z paarweise teilerfremd, so existiert zu beliebigen a1 , . . . , an ∈ Z ein
x ∈ Z mit
x ≡ ai (mod ri ) für alle i = 1, . . . , n .

Man beachte, dass dies eine Existenzaussage ist. Es gibt ein solches x. Wir zeigen
nun, wie wir die Menge aller solchen x explizit bestimmen können.


7.2.2 Lösen eines Systems von Kongruenzgleichungen

Für das konstruktive Lösen eines Systems von Kongruenzgleichungen der Form

X ≡ a1 (mod r1 ) , . . . , X ≡ an (mod rn )

mit paarweise teilerfremden r1 , . . . , rn ∈ Z und beliebigen a1 , . . . , an ∈ Z beachte
man die folgenden Schritte:
7.2 Der chinesische Restsatz 119

Setze m := r1 · · · rn und si := für i = 1, . . . , n.
m
ri

Bestimme xi ∈ Z mit xi si ≡ 1 (mod ri ) für i = 1, . . . , n.
Es ist dann
x = x1 s1 a1 + · · · + x n s n a n
eine Lösung des obigen Systems von Kongruenzengleichungen, und die Lö-
sungsmenge ist x + m Z.
Die Begründung ist einfach: Satz 4.20 garantiert, dass solche xi existieren, da ri
und si für alle i = 1, . . . , n teilerfremd sind “ man kann also x1 , . . . , xn mit dem
euklidischen Algorithmus bestimmen.
Weil für i = j das Element ri ein Teiler von s j ist, ist das angegebene x tats¤chlich
eine Lösung der n Kongruenzgleichungen. Für jedes i = 1, . . . , n gilt n¤mlich
n
‘ x j s j a j ≡ xi si ai ≡ ai (mod ri ) .
x=
j=1

Ist y neben x eine weitere Lösung des Systems, so gilt

x ≡ y ≡ ai (mod ri ) für alle i = 1, . . . , n ’ ri | x ’ y für alle i = 1, . . . , n
’ m | x ’ y , d. h. x ≡ y (mod m) ,
folglich gilt y ∈ x + m Z. Andererseits ist jedes Element aus x + m Z Lösung des
Systems, sodass x + m Z die Lösungsmenge ist.

Beispiel
Gesucht ist die Lösungsmenge des Kongruenzensystems

X ≡ 2 (mod 5) , X ≡ 3 (mod 7) , X ≡ 2 (mod 4) .

Es ist also m = 140, s1 = 28, s2 = 20, s3 = 35.
Wir bestimmen nun x1 , x2 , x3 ∈ Z mit

28 x1 ≡ 1 (mod 5) , 20 x2 ≡ 1 (mod 7) , 35 x3 ≡ 1 (mod 4) .

Offenbar kann man x1 = 2, x2 = ’1, x3 = ’1 w¤hlen. Wenn dies nicht so
offensichtlich ist, wende man den euklidischen Algorithmus an. Damit haben wir
die Lösung:

x = 2 · 28 · 2 + (’1) · 20 · 3 + (’1) · 35 · 2 = ’18 .

Die Lösungsmenge lautet ’18 + 140 Z.

Bemerkung
Man erkennt, dass man nicht immer den kleinsten positiven Vertreter der Rest-
klasse ¬ndet. Ist das gewünscht, muss man noch eine Division mit Rest durch-
führen: ’18 + 140 Z = 122 + 140 Z.
120 7 Das RSA-Verfahren

7.2.3 Produktdarstellung der primen Restklassengruppen

Für die Abbildung ψ aus Lemma 7.3 und r := r1 · · · rn gilt
— —
ψ(k + r Z) ∈ Zr1 — · · · — Zrn ” ggT(k, ri ) = 1 für i = 1, . . . , n

” ggT(k, r) = 1 ” k + r Z ∈ Zr .

Somit ist die Einschr¤nkung ψ|Zr auf die (multiplikative) Gruppe Zr der inver-

tierbaren Elemente von Zr wegen Lemma 7.3 ein Gruppenisomorphismus von
— — —
Zr auf Zr1 — · · · — Zrn :

Lemma 7.5
(a) Für paarweise teilerfremde r1 , . . . , rn und r := r1 · · · rn ist

ψ|Zr : k + r1 · · · rn Z ’ (k + r1 Z, . . . , k + rn Z)


— — —
ein (multiplikativer) Isomorphismus von Zr1 ···rn auf Zr1 — · · · — Zrn .
ν
(b) Ist m = p11 · · · pνn die kanonische Primfaktorzerlegung von m > 1 aus N, so gilt
n

Z — ∼ Z —ν1 — · · · — Z —νn .
m= p
p1 n


Nach dem Fundamentalsatz 4.14 der Arithmetik kann jedes m ∈ N ≥2 als Produkt
von Primzahlpotenzen dargestellt werden:
ν
m = p11 · · · pνn .
n

Wegen Lemma 4.16 folgt für die Euler™sche •-Funktion (siehe Seite 75):
n n n n
1 1
ν ν
•(m) = |Z — | = ∏ |Z—νi | = ∏ •(pi i ) = ∏ pi i ∏
1’ =m 1’ .
m
pi pi
pi
i=1 i=1 i=1 i=1

Wir fassen zusammen:

Lemma 7.6
(a) Für paarweise teilerfremde s1 , . . . , sn ∈ N gilt

•(s1 · · · sn ) = •(s1 ) · · · •(sn ) .

(b) Sind p1 , . . . , pn die verschiedenen Primteiler von m > 1 aus N, so ist
1 1
•(m) = m 1’ ··· 1’ .
p1 pn

Beispiel
Es gilt etwa
1246
•(33) = •(3) •(11) = 20 , •(420) = 420 · · · · = 96 .
2357
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-
kommen.
7.5 Kettenbrüche * 129

7.5.1 Kettenbruchdarstellungen

Für a0 , . . . , an ∈ R mit a1 , . . . , an > 0 setzen wir
1
[a0 ; a1 , . . . , an ] := a0 + ∈ R.
1
a1 +
1
a2 +
..
. + a1
n

Für a0 , . . . , an ∈ Z mit a1 , . . . , an > 0 nennen wir das (n + 1)-Tupel

a0 ; a1 , . . . , an := ([a0 ], [a0 ; a1 ], . . . , [a0 ; a1 , . . . , an ])

einen endlichen Kettenbruch mit dem Wert

x := [a0 ; a1 , . . . , an ] ∈ Q .

Für jedes k = 0, . . . , n nennen wir [a0 ; a1 , . . . , ak ] ∈ Q den k-ten N¤herungsbruch
von a0 ; a1 , . . . , an .

Beispiel
Es gilt:
62 10 1 1 1 1
= 4+ = 4+ = 4+ = 4+ = 4+
3 1 1
13 13 13/10
1+ 1+ 1+
1
10 10/3
3+
3
1
= 4+ .
1
1+
1
3+
1
2+
1
Also gilt
62
= [4; 1, 3, 3] = [4; 1, 3, 2, 1] ,
13
und es sind [4] = 4, [4; 1] = 5, [4; 1, 3] = 4.75, [4; 1, 3, 3] = 4.769... die N¤herungs-
brüche.

Allgemein gilt für jeden k-ten N¤herungsbruch eines Kettenbruchs im Fall ak ≥ 2
stets
[a0 ; a1 , . . . , ak ] = [a0 ; a1 , . . . , ak ’ 1, 1] .
Diese Nichteindeutigkeit können wir vermeiden, indem wir uns auf eigentliche Ket-
tenbrüche beschr¤nken: Wir nennen einen Kettenbruch a0 ; a1 , . . . , an eigent-
lich, wenn n = 0 oder an ≥ 2 gilt. Wir zeigen nun, dass sich jede rationale Zahl
eindeutig als eigentlicher Kettenbruch darstellen l¤sst.
130 7 Das RSA-Verfahren

7.5.2 Existenz und Eindeutigkeit von N¤herungsbrüchen

Wir benötigen eine Hilfsaussage.

Lemma 7.11
Es sei a0 ; a1 , . . . , an ein eigentlicher Kettenbruch mit dem Wert x ∈ Q. Dann gilt:

(i) n ≥ 1 ’ x = a0 + 1
.
[a1 ; a2 ,..., an ]

(ii) a0 = x .

Beweis. Die Aussage (i) ist klar. Im Fall n = 0 gilt a0 = x = x und somit (ii). Im
Fall n ≥ 1 ist x = a0 + [a ; a 1 a ] , und [a1 ; a2 , . . . , an ] > 1 wegen an ≥ 2, sodass
1 2 ,..., n
a0 ¤ x < a0 + 1, also a0 = x ; folglich gilt (ii) auch in diesem Fall.

Satz 7.12
Jede rationale Zahl besitzt genau eine Darstellung als eigentlicher Kettenbruch.

Beweis. Für x = b ∈ Q mit a ∈ Z und b ∈ N liefert der euklidische Algorithmus
a

ganze Zahlen a0 , a1 , . . . , an und r1 , . . . , rn mit:
« §a r1
0 ¤ rb1 < 1
0 ¤ r1 < b ⎪ ⎪ b = a0 + b ,
a = a0 b + r1 , ⎪b
⎪⎪
0 < r 2 < r 1 ⎪ ⎪ r1 = a 1 + r1 ,
r2
0 < r2 < 1
⎪⎪
b = a1 r1 + r2 , ⎪⎪
⎪ ⎪ r1 r1
⎪⎪
¬ ⎨ r = a 2 + r3 , 0 < r3 < 1
r1 = a2 r2 + r3 , 0 < r3 < r2 r2 r2

2
. . . . . .
⎪⎪
. . . . . .
⎪⎪
. . . . . .
⎪ ⎪r
⎪ ⎪ n’2
⎪⎪
rn’2 = an’1 rn’1 + rn , 0 < rn < rn’1⎪ ⎪ r ⎪ ⎪ n’1 = an’1 + rn’1 , 0 < rn’1 < 1
rn rn
⎭ ⎪r © n’1
rn’1 = an rn
rn = a n

Falls b | a, ist x = a0 . Es ist dann a0 mit a0 ∈ Z ein eigentlicher Kettenbruch mit
dem Wert x. Falls b a, folgt offenbar a1 , . . . , an ∈ N; und es ist a0 ; a1 , . . . , an ein
Kettenbruch mit Wert x. Wegen rn’1 > rn ist an ≥ 2. Folglich ist der Kettenbruch
eigentlich. Wir begründen die Eindeutigkeit: Es gelte

x = [a0 ; a1 , . . . , an ] = [b0 ; b1 , . . . , bm ]

mit a0 , b0 ∈ Z, ai , b j ∈ N für i, j ≥ 1 und an ≥ 2, bm ≥ 2, falls n, m ≥ 1. Ohne
Einschr¤nkung sei n ¤ m. Wir schließen mit vollst¤ndiger Induktion nach n. Im
Fall n = 0 gilt x = a0 = a0 ∈ Z. Lemma 7.11 liefert b0 = x = a0 = x, und es
gilt m = 0.
Es sei n ≥ 1, und die Behauptung sei für n ’ 1 richtig. Es folgt erneut mit Lemma
7.11, dass a0 = x = b0 und daher

[a1 ; a2 , . . . , an ] = [b1 ; b2 , . . . , bm ] .

Mit der Induktionsvoraussetzung folgt n = m und ai = bi für i = 1, . . . , n.
7.5 Kettenbrüche * 131

Bemerkung
Der zu b ∈ Q (existierende und eindeutig bestimmte) eigentliche Kettenbruch
a

a0 ; a1 , . . . , an kann also mithilfe des euklidischen Algorithmus ef¬zient berech-
net werden. Das wird für den Wiener-Angriff auf das RSA-Kryptosystem wichtig
sein.


7.5.3 Ermittlung der N¤herungsbrüche

Wir geben nun ein Verfahren an, mit dem wir die Z¤hler und Nenner der N¤he-
rungsbrüche [a0 ; a1 , . . . , ak ] aus der Kettenbruchdarstellung a0 ; a1 , . . . , an be-
stimmen können. Dazu benutzen wir die folgende Aussage:

Lemma 7.13
Es seien a0 ∈ Z und a1 , . . . , an ∈ N gegeben, und pk bzw. qk seien rekursiv erkl¤rt
durch
p1 := a1 a0 + 1 ; pk := ak pk’1 + pk’2 für k ≥ 2 ;
p0 := a0 ;
qk := ak qk’1 + qk’2 für k ≥ 2 .
q0 := 1 ; q1 := a1 ;

Dann gilt für alle möglichen k = 0, 1, . . .:
pk , qk ∈ Z, 1 = q0 ¤ q1 ; und qk < qk+1 , falls k ≥ 1; qk ≥ k.
(a)
pk+1 qk ’ qk+1 pk = (’1)k ,
(b)
pk+2 qk ’ qk+2 pk = (’1)k ak+2 ,
(c)
ak pk’1 +pk’2
Für jedes k ≥ 2 gilt [a0 ; a1 , . . . , ak ] =
(d) ak qk’1 +qk’2 .
pk
[a0 ; a1 , . . . , ak ] = und ggT(pk , qk ) = 1.
(e) qk ,

Beweis. (a) folgt direkt aus den De¬nitionen.
(b) stimmt für k = 0: p1 q0 ’ q1 p0 = (a1 a0 + 1) · 1 ’ a1 a0 = 1. Wenn die Aussage
für k ∈ N0 richtig ist, folgt

pk+2 qk+1 ’ qk+2 pk+1 = (ak+2 pk+1 + pk ) qk+1 ’ (ak+2 qk+1 + qk ) pk+1
= pk qk+1 ’ qk pk+1 = ’(’1)k = (’1)k+1 .
(c) Für jedes k ≥ 0 gilt

pk+2 qk ’ qk+2 pk = (ak+2 pk+1 + pk ) qk ’ (ak+2 qk+1 + qk ) pk
= ak+2 (pk+1 qk ’ qk+1 pk ) = (’1)k ak+2 .
(d) Für k = 2 gilt
a2 a0 a1 + a0 + a2 a p + p0
1
=21
[a0 ; a1 , a2 ] = a0 + = .
a2 a1 + 1 a2 q1 + q0
a1 + 1
a2
132 7 Das RSA-Verfahren

Die Behauptung sei richtig für ein k ≥ 2. Es folgt

(ak + ak+1 ) pk’1 + pk’2
1
1
[a0 ; a1 , . . . , ak+1 ] = [a0 ; a1 , . . . , ak + ]=
(ak + ak+1 ) qk’1 + qk’2
1
ak+1
ak+1 (ak pk’1 + pk’2 ) + pk’1 p + pk’1
a
= k+1 k
= .
ak+1 (ak qk’1 + qk’2 ) + qk’1 ak+1 qk + qk’1
Damit ist (d) bewiesen.
(e) Für k = 0 bzw. k = 1 besagt die erste Behauptung:
a a +1
1
a0 p p
= 0 bzw. [a0 ; a1 ] = a0 + =01 = 1.
[a0 ] = a0 =
1 q0 a1 a1 q1
+p
ap p
Im Fall k ≥ 2 erh¤lt man mit (d): [a0 ; a1 , . . . , ak ] = ak qk’1 +q k’2 = q k .
k k’1 k’2 k
Nach der Aussage in (b) existieren zu pk und qk ganze Zahlen r, s mit

r qk + s pk = 1 .

Nach Lemma 4.8 (d) folgt hieraus ggT(pk , qk ) = 1.
Die Berechnung der N¤herungsz¤hler pk und N¤herungsnenner qk führt man
zweckm¤ßigerweise in folgendem Schema durch:
···
ak a0 a1 a2 a3
a1 a0 + 1 a2 p1 + p0 a3 p2 + p1 ···
pk a0
a2 q1 + q0 a3 q2 + q1 ···
1
qk a1

Beispiel
Wir berechnen die N¤herungsbrüche von 2; 1, 2, 3, 1, 2, 1, 3, 4 :
2 1 2 3 1 2 1 3 4
ak
2 3 8 27 35 97 132 493 2104
pk
1 1 3 10 13 36 49 183 781
qk
Damit sind die N¤herungsbrüche der Reihe nach
2 3 8 27 35 97 132 493 2104
,,, , , , , , .
1 1 3 10 13 36 49 183 781
Der Wert des eigentlichen Kettenbruchs 2; 1, 2, 3, 1, 2, 1, 3, 4 ist
2104
= 2.69398... .
781
Für die N¤herungsbrüche gilt
2 2104 38 2104 27 35 2104 97 132 2104 493
< <,< < < < < <
, , .
1 781 13 781 10 13 781 36 49 781 183
Diese Absch¤tzungen werden immer besser. Das ist kein Zufall, wir gehen die-
sem Ph¤nomen im übern¤chsten Abschnitt nach.
7.5 Kettenbrüche * 133

7.5.4 Unendliche Kettenbrüche

Auch irrationale Zahlen sind durch Kettenbrüche darstellbar. Wir entwickeln die-
se Theorie nur so weit, wie wir sie benötigen.
Da jeder endliche Kettenbruch eine rationale Zahl darstellt, sind Kettenbrüche
irrationaler Zahlen zwangsl¤u¬g unendlich. Bei einer rationalen Zahl x = b fan-
a

den wir die Koef¬zienten a0 , . . . , an der Kettenbruchentwicklung durch sukzessi-
ve Division mit Rest (siehe den Beweis zu Satz 7.12). Bei einer irrationalen Zahl x
bestimmt man die Koef¬zienten wie folgt. Man setzt x0 := x und a0 := x0 ∈ Z
und rekursiv für i ≥ 0:
1
(—) ai+1 := xi+1 ∈ N .
xi+1 := und
xi ’ ai
Für die so erhaltene Folge (ai ) nennt man
a0 ; a1 , a2 , . . .
pk
:= [a0 ; a1 , . . . , ak ] für jedes k ∈ N
den unendlichen Kettenbruch von x und qk
den k-ten N¤herungsbruch von x.

Bemerkung
Berechnet man die Zahlen a0 , a1 , a2 , . . . auf die geschilderte Art für eine ratio-
nale Zahl x, so gibt es einen Index n mit xn ∈ N, es ist dann a0 ; a1 , a2 , . . . , an
ein (endlicher) Kettenbruch mit Wert x.
pk
Man kann zeigen, dass die Folge der N¤herungsbrüche gegen x konver-
qk
giert.

Wir benötigen in Kapitel 11 nur das folgende Ergebnis zu unendlichen Ketten-
brüchen.

Lemma 7.14
Ist a0 ; a1 , a2 , . . . der unendliche Kettenbruch zur irrationalen Zahl x, so gilt für jedes
k ∈ N0 :
x = [a0 ; a1 , . . . , ak , xk+1 ] ,
wobei die Zahlen xk+1 durch die Rekursion (—) gegeben sind.

Beweis. Für k = 0 gilt:
1
[a0 ; x1 ] = a0 + = a0 + (x0 ’ a0 ) = x0 = x .
x1
Ist die Behauptung für k ’ 1 ∈ N korrekt, so folgt
1
x = [a0 ; a1 , . . . , ak’1 , xk ] = [a0 ; a1 , . . . , ak’1 , ak + ] = [a0 ; a1 , . . . , ak , xk+1 ] .
xk+1
Damit ist die Behauptung bewiesen.
134 7 Das RSA-Verfahren

7.5.5 Absch¤tzungen

Aus Lemma 7.13 gewinnen wir wichtige Absch¤tzungen:

Korollar 7.15
Es sei a0 ; a1 , . . . , an ein Kettenbruch mit dem Wert x, und wir de¬nieren wie in Lemma
p
7.13 die Zahlen pk , qk und setzen zudem rk := q k für k = 0, . . . , n. Dann gilt:
k

(’1)k
rk+1 ’ rk = für alle 0 ¤ k < n.
(a) qk qk+1

|rk+1 ’ rk | < für alle 1 ¤ k < n.
1
(b) q2
k


r2(k’1) < r2k < r2l+1 < r2l’1 für alle k, l ≥ 1 mit 2 k, 2 l + 1 < n.
(c)

r2 k < x < r2 l+1 für alle k, l ≥ 0 mit 2 k, 2 l + 1 < n.
(d)

Beweis. (a) ergibt sich aus Lemma 7.13 (b) mit Division durch qk qk+1 .
(b) folgt aus (a), weil qk+1 > qk nach Lemma 7.13 (a) für jedes k ≥ 1.
(c) Aus Lemma 7.13 (c) folgt
a2k
r2k ’ r2(k’1) = (’1)2(k’1) > 0 , d. h. r2 (k’1) < r2k
q2(k’1) q2 k

und
a2l+1
r2l+1 ’ r2l’1 = (’1)2l’1 < 0 , d. h. r2l+1 < r2l’1 .
q2l’1 q2l+1
(a) (’1)2l
Im Fall k ¤ l folgt r2k ¤ r2l < r2l+1 , weil r2l+1 ’ r2l = > 0; und im Fall
q2l q2l+1
k > l analog r2k+1 ’ r2k > 0, und r2k+1 < r2l+1 .
(d) folgt aus (c).



7.5.6 Charakterisierung von N¤herungsbrüchen

Man kann N¤herungsbrüche für rationale Zahlen charakterisieren. Dazu benöti-
gen wir einen Hilfssatz.

Lemma 7.16
Es seien x ∈ Q \ Z und p ∈ Z, q ∈ N gegeben; weiter sei x = [a0 ; a1 , . . . , an ] mit
p
an ≥ 2 und n ≥ 2. Mit q k sei der k-te N¤herungsbruch von x bezeichnet (vgl. Lemma
k
p pk
7.13). Gilt q < qk+1 für ein k ∈ {0, . . . , n ’ 2} und = qk , so folgt
q

|qk x ’ pk | < |q x ’ p| .
7.5 Kettenbrüche * 135

pk pk+1
= ±1, sodass wegen der Cra-
Beweis. Nach Lemma 7.13 (b) gilt det
qk qk+1
mer™schen Regel Zahlen a, b ∈ Z existieren mit

(—) pk a + pk+1 b = p , qk a + qk+1 b = q .

Wegen q < qk+1 impliziert dies a = 0. Und es gilt b = 0, weil aus (—) andernfalls
p pk
q = qk folgte. Im Fall a b > 0, d. h. a, b > 0 oder a, b < 0, entstünde wegen
q < qk+1 ein Widerspruch zur zweiten Gleichung in (—). Somit gilt a b < 0.
Nach Korollar 7.15 (d) haben qk x ’ pk = 0 und qk+1 x ’ pk+1 = 0 verschiedene
Vorzeichen, sodass

a (qk x ’ pk ) = 0 und b (qk+1 x ’ pk+1 ) = 0

gleiches Vorzeichen haben. Mit (—) folgt

|q x ’ p| = |a (qk x ’ pk ) + b (qk+1 x ’ pk+1 )|
= |a| |qk x ’ pk | + |b| |qk+1 x ’ pk+1 | > |qk x ’ pk | .

Das ist die Behauptung.

Mit diesem Lemma können wir nun die folgende Charakterisierung von N¤he-
rungsbrüchen beweisen:

Satz 7.17
pk
Es sei x ∈ Q. Wir bezeichnen die (gekürzten) N¤herungsbrüche von x mit qk . Dann gilt:

(a) Von zwei aufeinanderfolgenden N¤herungsbrüchen für x erfüllt mindestens einer
die Absch¤tzung
1
p
x’ k < .
2 q2
qk k

p p p
Ist q ∈ Q vollst¤ndig gekürzt und gilt x ’ < 1
(b) , so ist ein N¤herungs-
2 q2
q q
bruch von x.

Beweis. (a) Aus

1 1
pk pk+1
x’ ≥ x’ ≥
und
2 q2 2 q2
qk qk+1
k k+1

pk+1
pk
’ x und x ’
folgt mit Korollar 7.15 (a), da nach Korollar 7.15 (d) gleiches
qk qk+1
Vorzeichen haben,

1 1 1
pk pk
p p
’ x + x ’ k+1 ’ x + x ’ k+1 ≥
= = +2
2 q2
qk qk+1 qk qk+1 qk qk+1 2 qk+1
k
136 7 Das RSA-Verfahren

2
und damit q1 ’ q 1 ¤ 0, d. h. qk = qk+1 , also gelten k = 0 (vgl. Lemma 7.13
k k+1
(a)) und Gleichheit anstelle von ≥ in obigen Ungleichungen:

1 1
p0
x= + 2 = a0 + = [a0 ; 2] ,
2
q0 2 q0

p1 p1
sodass x = im Widerspruch zur Annahme x ’ ≥ 1
.
2 q2
q1 q1
1
p
(b) Es gelte x ’ q < 2 1 2 , und es sei x = a0 ; a1 , . . . , an ein eigentlicher Ket-
q
tenbruch mit Wert x. Es bezeichnen pk und qk für k = 0, . . . , n die in Lemma 7.13
de¬nierten Größen.
1. Fall: q ≥ qn . Hier folgt

1 1
pn p p
|pn q ’ p qn | = ’ = x’ ¤ ,
2 q2
q qn qn q q
p p
also pn q ’ p qn = 0, folglich q = qn .
n

2. Fall: Es gibt ein k ∈ N0 mit qk ¤ q < qk+1 .
p p
Es sei q = q k angenommen. Mit Lemma 7.16 folgt
k


1
|qk x ’ pk | < |q x ’ p| < ,
2q

sodass

|p q ’ p qk |
1 1 1
p p p p
¤k = k’ ¤ x’ k + x’ < +2
2 q qk
q qk q qk qk q qk q 2q
p pk
< im Widerspruch zu qk ¤ q. Somit gilt =
1 1
und damit qk .
qk q q


Beispiel
Wir betrachten die N¤herungsbrüche für 62 = 4.76923.... Es gilt (vgl. das Beispiel
13
auf Seite 129):
62
= [4; 1, 3, 3] .
13
Wir erhalten die N¤herungsbrüche

4 1 5 1 17 62
[4] = , [4; 1] = 4 + = , [4; 1, 3] = 4 + = , [4; 1, 3, 3] =
1 + 1/3
1 1 1 4 13

und stellen nun fest:

62 4 62 5 62 17
1 1 1
’ > ’ < ’ >
, , .
2 · 12 13 1 2 · 12 13 2 · 42
13 1 4
7.6 Der Wiener-Angriff * 137

7.6 Der Wiener-Angriff *

Der Wiener-Angriff auf RSA wurde 1990 von Michael Wiener [30] vorgestellt. Ist
der geheime Schlüssel d beim RSA-Verfahren nur klein genug, so erh¤lt man even-
e
tuell den geheimen Schlüssel d als Nenner eines der N¤herungsbrüche von n
“ hierbei sind e und n die Zahlen des öffentlichen Schlüssels (n, e) beim RSA-
Verfahren. Man kann den geheimen Schlüssel in diesem Fall also einfach ermit-
teln. Der Angriff basiert auf dem folgenden Satz:

Satz 7.18
Es seien p, q Primzahlen mit q < p < 2 q, n := p q, 1 < d, e < •(n),
e d ≡ 1 (mod •(n)), d < 1 n1/4 . Dann ist d ein N¤herungsbruch für n , wobei
r e
3
r := ed’1 ∈ N.
•(n)

Beweis. Wegen q < p gilt q2 < p q = n, also q < n. Damit gilt

(—) n ’ •(n) = p q ’ (p ’ 1) (q ’ 1) = p + q ’ 1 < 3 q < 3 n.

Und aus e d = 1 + r •(n) erhalten wir r •(n) < e d < •(n) 1 n1/4 und somit
3

1 1/4
(——) r < n.
3
Es folgt nun mit (—) und (——):

r n ’ e d = r n ’ (1 + r •(n)) = r (n ’ •(n)) ’ 1 < r (n ’ •(n))

1
< n1/4 3 n = n3/4 .
3
Wir teilen diese Ungleichung durch n d und erhalten:
1 1 1
r e
’ < < < .
3 d2 2 d2
d n1/4
dn
Nun folgt mit Satz 7.17 (b) die Behauptung.
l¤sst sich als N¤herungsbruch ef¬zient berechnen. Wegen r =
r
Der Quotient d
ed’1
gilt
•(n)
e d ’ r •(n) = 1 ,
sodass die Zahlen r und d nach Lemma 4.8 (d) teilerfremd sind. Daher ¬ndet man
die Zahlen r und d mit Lemma 7.13 als Z¤hler und Nenner eines N¤herungs-
e
bruchs von n .
Wir schildern nun den Wiener-Angriff auf RSA. Dabei gehen wir davon aus,
dass die Primzahlen p und q und der geheime Schlüssel d die Voraussetzungen
des Satzes 7.18 erfüllen:
e
Der Angreifer bestimmt alle N¤herungsbrüche von n und testet, ob der N¤he-
rungsbruch k der gesuchte Bruch ist, d. h., ob k = r und = d gilt.
138 7 Das RSA-Verfahren

e ’1
Der Angreifer berechnet •n := k.

Er ermittelt mit •n und n die Nullstellen p0 und q0 des Polynoms

X 2 ’ (n ’ •n + 1) X + n

(beachte Lemma 7.2).

Sind p0 und q0 natürliche Zahlen mit n = p0 q0 , so gilt

= d , k = r , •n = •(n) , p0 = p , q0 = q .

Andernfalls w¤hlt der Angreifer den n¤chsten N¤herungsbruch.

Bemerkung
Der Angriff funktioniert manchmal auch, wenn die Voraussetzungen etwas ab-
geschw¤cht werden, siehe Aufgabe 7.9.




Aufgaben

7.1 Um eine Textnachricht mit RSA zu verschlüsseln, wandeln wir sie zun¤chst
wie folgt in eine Zahlenfolge um: Der Klartext wird so eingeteilt, dass je zwei
Buchstaben einen Block von vier Ziffern bilden: „a” = 00, „b” = 01, „c” = 02 usw.
Zum Beispiel wird die Nachricht „klar” zu 1011 0017. Diese Ziffernblöcke können
dann mit RSA verschlüsselt werden.
Es sei (n, e) = (3149, 563) der öffentliche Schlüssel beim RSA-Verfahren; hiermit
wurde der folgende Geheimtext erzeugt:

1263 0996 1102 3039 2177 2311 .

Wie lautet der geheime Schlüssel d? Bestimmen Sie den Klartext.

7.2 Der Chinese Sun-Tsu stellt in seinem Buch Suan“Ching u. a. folgende Auf-
gabe: „Wir haben eine gewisse Anzahl von Dingen, wissen aber nicht genau wie
viele. Wenn wir sie zu je drei z¤hlen, bleiben zwei übrig. Wenn wir sie zu je fünf
z¤hlen, bleiben drei übrig. Wenn wir sie zu je sieben z¤hlen, bleiben zwei übrig.
Wie viele Dinge sind es?“

7.3 Ein Angriff auf eine RSA-Variante
Es seien p = 123456791, q = 987654323, n = p q und e = 127. Der Klartext sei
a = 14152019010605.
7.6 Der Wiener-Angriff * 139

(a) Berechnen Sie ae (mod p) und ae (mod q). Berechnen Sie hieraus mithilfe des
chinesischen Restsatzes c ≡ ae (mod n).
(b) „ndern Sie eine beliebige Dezimalstelle von ae (mod p). Berechnen Sie
hieraus analog zu (a) mithilfe des chinesischen Restsatzes einen falschen Wert
f für ae (mod n). Angenommen, ein Angreifer hat sowohl c als auch f abge-
fangen. Wie kann er n faktorisieren?

7.4 Ein kleines Netzwerk besteht aus drei Teilnehmern, die zur Verschlüsse-
lung das RSA-Verfahren benutzen. Die öffentlichen Schlüssel der Teilnehmer sind
(n1 , 3), (n2 , 3) bzw. (n3 , 3) mit

n1 = 2469247531693 , n2 = 11111502225583 , n3 = 44444222221411 .

Ein Klartext N wird mit den öffentlichen Schlüssel der drei Teilnehmer zu den
Geheimtexten C1 , C2 , C3 verschlüsselt, wobei

C1 = 2404501406206 , C2 = 7400939843715 , C3 = 7706684000138 .

Bestimmen Sie den Klartext.

7.5 RSA “ Geheimhaltung und Authentizit¤t
Ein Vorschlag für ein Verfahren, um Geheimhaltung und Authentizit¤t zu ge-
w¤hrleisten: Es sei (nS , eS ) = (143, 11) bzw. (n E , eE ) = (35, 11) der öffentliche
Schlüssel des Senders bzw. Empf¤ngers. Um dem Empf¤nger zu beweisen, dass
die Nachricht tats¤chlich vom Sender stammt, verschlüsselt der Sender seinen
Klartext N , indem er zuerst seinen geheimen Schlüssel und dann den öffentli-
chen Schlüssel des Empf¤ngers anwendet. Der Empf¤nger wendet auf den erhal-
tenen Geheimtext dann zuerst seinen geheimen Schlüssel und dann den öffentli-
chen Schlüssel des Senders an.
Zeigen Sie, dass das Verfahren scheitert, indem Sie die Verschlüsselung und Ent-
schlüsselung für den Klartext N = 5 durchführen. Warum scheitert es?

7.6 Benutzt man zur Potenzbildung in einem RSA-System die Multiplikation
nach Karatsuba-Ofman (siehe Aufgabe 4.3), so ist die Ersparnis bei Anwendung
des chinesischen Restsatzes nur 1/3 “ warum?

7.7 Schreiben Sie a = 1735
als Kettenbruch. Geben Sie die zugehörigen N¤he-
341
rungsbrüche an.

Bestimmen Sie die Kettenbruchentwicklung von 15.
7.8

7.9 Wiener-Angriff
Ein RSA-System werde mit dem öffentlichen Schlüssel

(n, e) = (1966981193543797, 323815174542919)

betrieben. Bestimmen Sie mithilfe des Wiener-Angriffs:
140 7 Das RSA-Verfahren

(a) eine Faktorisierung von n,
(b) den öffentlichen Schlüssel d.

Anmerkung: Das ist ein Beispiel dafür, dass der Wiener-Angriff auch dann funk-
tionieren kann, wenn die Voraussetzungen von Satz 7.18 nicht erfüllt sind.
8 Primzahltests

Große Primzahlen sind für viele Verschlüsselungsverfahren von fundamentaler
Bedeutung. Es existieren auch beliebig große Primzahlen, da die Menge P aller
Primzahlen unendlich ist. Aber es ist bisher keine Konstruktionsmethode für Prim-
zahlen bekannt, also etwa eine ef¬zient berechenbare Funktion f : N ’ P mit
unendlicher Bildmenge.
Um eine große Primzahl zu ¬nden, w¤hlt man in der Praxis eine ungerade natür-
liche Zahl n der gewünschten Größenordnung und prüft diese Zahl n auf Prima-
lit¤t, d. h., man prüft, ob n eine Primzahl ist. Dazu benutzt man sogenannte Prim-
zahltests. Stellt sich bei einem solchen Test heraus, dass die Zahl n keine Primzahl
ist, so überprüft man eine zu n n¤chstgelegene ungerade natürliche Zahl. Dabei
garantiert der Primzahlsatz, dass in der N¤he von n mit hoher Wahrscheinlichkeit
eine Primzahl liegt.
Wir stellen in diesem Kapitel vier Primzahltests vor, die Probedivision, den Fermat-
Test, den Miller-Rabin-Test und den AKS-Test. Die Tests unterscheiden sich in ih-
rer Komplexit¤t und ihrer Genauigkeit: Zwei der Tests “ die Probedivision und
der AKS-Test “ beweisen das Vorliegen einer Primzahl. Die anderen beiden Tests
liefern bei positivem Ausgang des Tests nur Vermutungen darüber, ob eine Prim-
zahl vorliegt. Tats¤chlich liefern sie bei negativem Ausgang des Tests einen Be-
weis, dass n keine Primzahl ist, und sind also streng genommen Tests auf Zusam-
mengesetztheit.
Der Miller-Rabin-Test ist heutzutage für das Auf¬nden großer Primzahlen, wie
man sie etwa für das RSA-Verfahren benutzt, das Mittel der Wahl. Er ist ein pro-
babilistischer Test, d. h., liefert der Test die Aussage „n ∈ P“, so ist n tats¤chlich
nur mit einer gewissen Wahrscheinlichkeit eine Primzahl. Die Aussage „n ∈ P“
kann beim Miller-Rabin-Test mit einer gewissen, kontrollierbar kleinen Fehler-
wahrscheinlichkeit falsch sein.
Im Gegensatz dazu heißt ein Test deterministisch, wenn er stets ein korrektes
Ergebnis liefert, d. h., wenn der Test das Ergebnis „n ∈ P“ ausgibt, so ist n auch
ganz bestimmt eine Primzahl.
Wir bezeichnen die Menge aller Primzahlen stets mit P. Eine natürliche Zahl n
nennen wir zusammengesetzt, wenn es Zahlen a, b ∈ N >1 mit n = a b gibt. Die
zusammengesetzten Zahlen sind damit die natürlichen Zahlen ungleich 1, die
keine Primzahlen sind.
142 8 Primzahltests

8.1 Probedivision
Wir betrachten eine ungerade natürliche Zahl n.

8.1.1 Das Verfahren
Jeder praktische Primzahltest und auch jeder Faktorisierungsalgorithmus be-
ginnt mit Probedivisionen. Man prüft hierbei, ob die Zahl n durch kleine, be-
kannte Primzahlen 3, 5, 7, 11, 13 . . . teilbar ist. Das macht man ef¬zient mit der
Division mit Rest. Bleibt bei Division von n durch p kein Rest, so hat man einen
Teiler von n gefunden, d. h., n ist keine Primzahl.
Die kleinen Primzahlen führt man in einer Liste. Typischerweise ist diese Liste so
gestaltet, dass man alle Elemente in 16-Bit-Wörtern speichern kann. Ein andere
Weg ist es, das Produkt dieser Primzahlen zu speichern und den ggT mit n zu
bestimmen. Nur wenn dieser Test negativ ausf¤llt, es also keine kleinen Primteiler
gibt, f¤hrt man mit einem spezielleren Verfahren fort. Heute ist das meist der
Miller-Rabin-Test.

Beispiel
Wir teilen die Zahl n = 253 mit Rest nacheinander durch die Primzahlen 2, 3, 5, 7
und 11 und ¬nden die Zerlegung

n = 11 · 23 .

8.1.2 Probedivision für große Zahlen
Prinzipiell ist es möglich, die Zahl n auf Primalit¤t durch Probedivisionen zu

überprüfen. Dazu muss man aber alle Primzahlen kleiner gleich n durchpro-
bieren. Ist n¤mlich n keine Primzahl, dann gilt für den kleinsten echten Teiler p
von n √
p ¤ n.

Ist aber n eine große Zahl, so ist die Menge aller Primzahlen kleiner gleich n
sehr umfangreich, die Probedivision also sehr aufw¤ndig. Wir schildern dies et-
was genauer und bezeichnen dazu mit π die Primzahlfunktion:

π(x) = | {p ∈ P ; p ¤ x} | , x ∈ R >0 .

Der Primzahlsatz “ von A. Legendre und C. F. Gauß vermutet, aber erst um 1896
von J. S. Hadamard und C. de La Vall©e Poussin bewiesen “ besagt:

Für x ∈ R >0 gilt:
Der Primzahlsatz.

log x
x
π(x) ∼ lim π(x) · = 1.
, d. h.
log x x
x’∞
8.1 Probedivision 143

Der Beweis des Primzahlsatzes ist Thema der analytischen Zahlentheorie (man
vgl. etwa [5]).
Beim RSA-Verfahren benutzt man üblicherweise Primzahlen, die größer als 2512
sind. Nach dem Primzahlsatz existieren also etwa
2512/2
> 1074
512/2
log 2

Primzahlen kleiner oder gleich 2512 . Daran erkennt man, dass Probedivision
allein als Primzahltest für unsere Zwecke völlig unzureichend ist.
Der Primzahlsatz zeigt aber auch, dass die zuf¤llige Wahl einer ungeraden Zahl
und ein Test auf Primalit¤t eine Erfolg versprechende Strategie ist um Primzahlen
zu ¬nden. Es gilt n¤mlich für die gew¤hlte Zahl n ∈ N:
π(n) 1
≈ ,
log n
n
1
d.h., die Dichte der Primzahlen um die Zahl n herum ist ungef¤hr log n , sodass in
einem Intervall der L¤nge log n um n ungef¤hr eine Primzahl liegt. Gilt n ≈ 2512 ,
so sind also etwa log n ≈ 355 Zahlen zu überprüfen “ eine relativ kleine Anzahl.


8.1.3 Sichere und Mersenne™sche Primzahlen

Um sichere Primzahlen p ∈ P zu ¬nden (vgl. Seite 104), modi¬ziert man die in
der Einleitung beschriebene Strategie wie folgt: Man ermittelt zuerst eine Prim-
zahl q und testet dann, ob p := 2 q + 1 eine (dann sichere) Primzahl ist. Im All-
gemeinen ist es sehr schwierig, sichere Primzahlen zu bestimmen. Über sichere
Primzahlen ist nur wenig bekannt, man weiß nicht einmal, ob es unendlich viele
solche Primzahlen gibt.
Die größten bekannten Primzahlen sind die sogenannten Mersenne™schen Prim-
zahlen. Das sind Primzahlen der Form 2n ’ 1 mit n ∈ N. Damit die Zahl 2n ’ 1
eine Primzahl sein kann, muss auch der Exponent n eine Primzahl sein; andern-
falls w¤re für n = a b mit a, b ∈ N >1 die Zahl 2a ’ 1 ein echter Teiler von 2n ’ 1,
da gilt:
2n ’ 1 = 2ab ’ 1 = (2a )b ’ 1 = (2a ’ 1) ((2a )b’1 + · · · + 2a + 1) .
Man kennt bisher 47 Mersenne™sche Primzahlen, die größte ist
243.112.609 ’ 1 , sie hat 12 978 189 Dezimalstellen.
Für den neuesten Stand vgl. man http://www.mersenne.org/. Auch von den
Mersenne™schen Primzahlen ist nicht bekannt, ob es unendlich viele gibt.
Um zu testen, ob eine Zahl der Form 2n ’ 1 von solch riesiger Größenordnung
eine Primzahl ist, stehen spezielle Methoden zur Verfügung. Die im vorliegenden
Kapitel diskutierten Primzahltests versagen schon bei weit kleineren Zahlen.
144 8 Primzahltests

8.2 Der Fermat-Test

Obwohl er keine praktische Bedeutung hat, ist der Fermat-Test für das Verst¤ndnis
sehr hilfreich. Alle im weiteren Text beschriebenen Tests sind vom Fermat-Test
inspiriert.


8.2.1 Der Test

Es sei n eine natürliche Zahl ungleich 1. Wir wollen prüfen, ob n eine Primzahl
oder zusammengesetzt ist. Man beachte den Satz 6.10 von Fermat. Falls n eine
Primzahl ist, so gilt für alle a ∈ {1, . . . , n ’ 1} die Kongruenz

an’1 ≡ 1 (mod n) .

Damit können wir nun folgende Aussage formulieren:


Gilt an’1 ≡ 1 (mod n) für ein a ∈ {2, . . . , n ’ 1},
so ist n garantiert zusammengesetzt.


Mit dieser Aussage gewinnen wir den (probabilistischen) Fermat-Test:

W¤hle ein a ∈ {2, . . . , n ’ 1}.

Bestimme an’1 modulo n (vgl. Abschnitt 6.3 zur schnellen Exponentiation).

Ist an’1 ≡ 1 (mod n), so ist n keine Primzahl, gib „n ∈ P“ aus.

Ist an’1 ≡ 1 (mod n), so ist n eventuell eine Primzahl, gib „n ∈ P“ aus.

Es ist durchaus möglich, dass die Kongruenz an’1 ≡ 1 (mod n) erfüllt ist, ob-
wohl n keine Primzahl ist. Ist die Kongruenz an’1 ≡ 1 (mod n) aber für viele
verschiedene a erfüllt, so ist die Wahrscheinlichkeit dafür, dass n eine Primzahl
ist, groß.

Beispiel
Die Zahl n = 341 (= 11 · 31) ist keine Primzahl. Der Fermat-Test liefert mit a = 2
wegen
2340 ≡ 1 (mod 341) ,
zuerst das (falsche) Ergebnis „n ∈ P“. Mit a = 3 folgt dann aber wegen

3340 ≡ 56 ≡ 1 (mod 341) .

die (richtige) Aussage „n ∈ P“.
8.2 Der Fermat-Test 145

F¤llt der Fermat-Test für viele a ∈ {2, . . . , n ’ 1} positiv aus, d. h., es gilt
an’1 ≡ 1 (mod n), so ist n wahrscheinlich eine Primzahl. Würde man alle mög-
lichen Zahlen a testen, so w¤re der Test sogar deterministisch (aber aufw¤ndiger
als die Probedivision), das folgt aus:

Lemma 8.1
Für ein a ∈ {1, . . . , n ’ 1} gelte ggT(a, n) = 1. Dann gilt

an’1 ≡ 1 (mod n) .

Beweis. Angenommen, es gilt an’1 ≡ 1 (mod n). Dann gibt es ein r ∈ Z mit
an’1 + r n = 1. Nach Lemma 4.8 (d) gilt dann ggT(a, n) = 1.

Korollar 8.2
Ist die Kongruenzgleichung an’1 ≡ 1 (mod n) für alle a ∈ {1, . . . , n ’ 1} erfüllt, so
ist n eine Primzahl.

Beweis. Nach Lemma 8.1 sind für jedes a ∈ {1, . . . , n ’ 1} die Zahlen a und n
teilerfremd. Folglich ist n eine Primzahl.



8.2.2 Pseudoprimzahlen und Zeugen für Zusammengesetztheit

Gilt für eine zusammengesetzte Zahl n und ein a ∈ {2, . . . , n ’ 1} die Kongruenz

an’1 ≡ 1 (mod n) ,

so heißt n Pseudoprimzahl zur Basis a. Man beachte, dass Pseudoprimzahlen
keine Primzahlen sind. Genauer l¤sst sich sagen: Eine Pseudoprimzahl ist eine
natürliche Zahl n, die beim Fermat-Test f¤lschlicherweise „n ∈ P“ liefert.

Beispiel
Zur Basis a = 2 gibt es zwischen 2 und 2 000 nur die sieben Pseudoprimzahlen
341, 561, 645, 1 105, 1 387, 1 729 und 1 905.

Eine Zahl a, die an’1 ≡ 1 (mod n) erfüllt, nennt man auch Zeuge dafür, dass n
zusammengesetzt ist. So ist z. B. a = 3 ein Zeuge der Zusammengesetztheit von
341 (vgl. das Beispiel auf Seite 144). Man beachte, dass der Zeuge in unserem
Beispiel keinen Hinweis auf einen Primteiler von n gibt.

Bemerkung
Im Allgemeinen sind Zeugen mathematische Größen, mit denen eine Eigenschaft
ef¬zient bewiesen werden kann. H¤u¬g sind sie nicht leicht zu ¬nden.
146 8 Primzahltests

Es gibt ungerade zusammengesetzte natürliche Zahlen n, die für den Fermat-Test
besonders ungünstig sind. Diese sogenannten Carmichael-Zahlen haben die Eigen-
schaft, dass der Fermat-Test für alle a ∈ {1, . . . , n ’ 1}, die keinen gemeinsamen
Teiler mit n haben, positiv ausf¤llt. Carmichael-Zahlen sind also nach Lemma 8.1
die denkbar ungünstigsten Zahlen für den Fermat-Test.



8.2.3 Carmichael-Zahlen

Für eine Pseudoprimzahl n zur Basis a liefert der Fermat-Test „n ∈ P“, obwohl
n keine Primzahl ist. Eine natürliche Zahl n heißt Carmichael-Zahl, wenn sie
Pseudoprimzahl zu allen Basen a ∈ {2, . . . , n ’ 1} mit ggT(a, n) = 1 ist.

Beispiel
Es ist 561 = 3 · 11 · 17 eine Carmichael-Zahl. Es gilt n¤mlich für alle a ∈
{2, . . . , 560} mit ggT(a, 561) = 1 die Kongruenz an’1 ≡ 1 (mod 561).

<<

. 5
( 9)



>>