Cryptography Reference
In-Depth Information
7.4 Wahl der Parameter
p
,
q
,
e
und
d
bei RSA
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.
7.4.1 Wahl von
p
und
q
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
2
512
2
511
10
151
.
)
−
)
≈
·
1.9
(
2
512
(
2
511
ln
ln
Zum Vergleich: Die Anzahl der Atome im Universum wird auf weniger als 10
80
geschätzt.
7.4.2 Die Wahl von
e
Die Zahl
e
sollte nicht zu klein gewählt werden, sonst kann der
Low-Exponent-
Angriff
Anwendung finden. Wie in der Praxis üblich, stellen wir einen Klartext
