<< . .

. 18
( : 33)



. . >>

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) .

<< . .

. 18
( : 33)



. . >>