Cryptography Reference
In-Depth Information
6.4.1
Das RSA-Kryptoschema
Um das RSA-Kryptoschema zu definieren, führen wir zunächst RSA-Tupel ein.
Definition 6.4.1. Wir nennen ein Tupel
(
n, p, q, m, e, d
)
ein
RSA-Tupel
,wenn
p>
2
und
q>
2
verschiedene Primzahlen sind,
e
und
d
Elemente von
Z
∗
m
sind sowie
n
=
p
·
q
,
m
=
φ
(
n
)
,also
m
=(
p
−
1)(
q
−
1)
, und
e
·
d
mod
m
=1
gilt.
RSA-Kryptoschemen sind nun wie folgt definiert, wobei wir für eine natürliche Zahl
a
mit
|
2
die minimale Länge von
a
in Binärdarstellung bezeichnen.
Definition 6.4.2 (RSA-Kryptoschema). Es sei
l>
1
gerade. Das
l
-RSA-Kryptoschema
ist das Tupel
|
a
S
RSA
=(
X,K,G,E,D
)
mit
K
=
{
((
n, e
)
,
(
n, d
))
|
(
n, p, q, m, e, d
)
ist RSA-Tupel mit
|
p
|
2
=
|
q
|
2
=
l/
2
}
,
X
=
{
Z
n
}
(
n,e
)
∈K
pub
.
Der Schlüsselgenerierungsalgorithmus
G
wählt zunächst zufällig zwei verschiedene Prim-
zahlen
p
und
q
mit
|p|
2
=
|q|
2
=
l/
2
, etwa mit dem Algorithmus
ErzeugePrimzahl
aus Abschnitt 6.3, berechnet
n
=
p
Z
∗
m
mit
m
=
φ
(
n
)
. (Häufig wird
e
auch konstant gewählt.) Zu
e
bestimmt
G
,etwamitdemerwei-
terten Euklidschen Algorithmus, ein
d
·
q
und wählt dann zufällig ein Element
e
aus
∈
Z
∗
m
,sodass
e
d
mod
m
=1
gilt. Die Ausgabe
von
G
ist das Paar
((
n, e
)
,
(
n, d
))
, bestehend aus einem öffentlichen Schlüssel
(
n, e
)
und ei-
nem privaten Schlüssel
(
n, d
)
. Der Chiffrieralgorithmus
E
und der Dechiffrieralgorithmus
D
sind wie folgt definiert:
·
E
(
x,
(
n, e
)) =
x
e
mod
n,
D
(
y,
(
n, d
)) =
y
d
mod
n,
für alle
x, y ∈
Z
n
,
(
n, e
)
∈ K
pub
und
(
n, d
)
∈ K
priv
.
Wir müssen uns zunächst davon überzeugen, dass
S
RSA
tatsächlich ein asymmetri-
sches Kryptoschema gemäß Definition 6.1.1 ist:
Dazu untersuchen wir zunächst die Laufzeiten der Algorithmen in
S
RSA
.Esistklar,
dass mit Hilfe des iterierten Quadrierens (siehe Abschnitt 6.3) sowohl die Verschlüsselung
als auch die Entschlüsselung ezient durchgeführt werden kann. Beschränkt man, wie
in Definition 6.1.1 gefordert, die Laufzeit des RSA-Schlüsselgenerierungsalgorithmus
G
durch eine Konstante, so besteht eine gewisse Wahrscheinlichkeit dafür, dass
G
in der
vorgegebenen Zeit kein Schlüsselpaar erzeugen konnte, weil
G
bei der Suche nach Prim-
zahlen »Pech« hatte, d. h., für alle zufällig gewählten Zahlen stellte sich heraus, dass sie
keine Primzahlen sind. Wählt man allerdings die erlaubte Laufzeit für
G
groß genug in
Abhängigkeit von
l
, dann ist nach dem Primzahlsatz (Satz 6.3.14) die Wahrscheinlichkeit
dafür, dass
G
fehlschlägt klein. Wie nach Definition 6.1.1 besprochen, wollen wir einen
solchen Fehlschlag zulassen.
