Cryptography Reference
In-Depth Information
Dabei wird
d
mit dem euklidischen Algorithmus (siehe Satz 4.10) zu
e
∈
K
be-
stimmt.
In Lemma 7.1 zeigen wir, dass das Verfahren funktioniert, d. h. dass das Ent-
schlüsseln eines verschlüsselten Klartextes
N
N
wieder den Klartext
liefert:
e
ed
(
(
N
)) =
(
N
)=
N
=
N
f
d
f
e
f
d
.
Bemerkung
Die Zahlen
n
=
pq
und
e
sind öffentlich bekannt. Einem Angreifer darf die Zahl
ϕ
(
)=(
−
)(
−
)
(siehe das Beispiel auf Seite 75) nicht bekannt sein, er
kann sonst ebenso wie der Empfänger mithilfe des euklidischen Algorithmus den
geheimen Schlüssel
d
ermitteln.
Wählt man für die Zahlen
p
und
q große
Primzahlen, so ist es im Allgemeinen
schwierig
, aus der Kenntnis von
n
n
p
1
q
1
=
pq
die Primfaktoren
p
und
q
und damit
zu ermitteln. In der Praxis werden die Primzahlen
p
und
q
von der Größenordnung 512 Bit gewählt. Bei der Wahl der Primzahlen
p
und
q
sind noch weitere Aspekte zu berücksichtigen, auf die wir in Abschnitt 7.4.1
eingehen werden.
ϕ
(
n
)=(
p
−
1
)(
q
−
1
)
Man beachte, dass die Voraussetzungen des folgenden Lemmas genau die Situa-
tion im RSA-Kryptosystem wiedergeben:
Lemma 7.1
Es seien p
=
q Primzahlen, n
=
pq, d
,
e
∈
N
mit
ggT
(
e
,
ϕ
(
n
)) =
1
,ed
≡
(
ϕ
(
))
∈
Z
. Dann gilt a
ed
≡
(
)
1
mod
n
und a
a
mod
n
.
Beweis.
Wegen
ed
≡
1
(
mod
ϕ
(
n
))
existiert ein
r
∈
Z
mit
ed
=
1
+
r
ϕ
(
n
)=
+
(
−
)(
−
)
1
r
p
1
q
1
. Nach dem Satz 6.10 von Fermat gelten die folgenden Kon-
gruenzen:
a
ed
a
1
+
r
(
p
−
1
)(
q
−
1
)
≡
a
p
−
1
r
(
q
−
1
)
≡
≡
(
)
(
)
a
a
mod
p
,
a
1
+
r
(
p
−
1
)(
q
−
1
)
≡
a
q
−
1
(
−
)
≡
a
ed
r
p
1
≡
(
)
(
)
a
a
mod
q
.
a
ed
a
ed
Die erste Kongruenz besagt
p
|
−
a
, die zweite
q
|
−
a
.Da
p
und
q
verschi
e-
a
ed
a
,d.h.
a
ed
|
−
≡
(
)
dene Primzahlen sind, gilt somit auch
pq
a
mod
n
.
D
ie K
on
gruenz
a
ed
≡
a
(
mod
n
)
bedeutet aber nichts anders als die Gleichheit
a
ed
=
Z
n
. Damit folgt aus Lemma 7.1 die Korrektheit des RSA-Verfahrens:
Der Empfänger
R
erhält den Geheimtext
a
in
e
∈
Z
n
und berechnet mit seinem
geheimen Schlüssel
d
durch Potenzieren den Klartext:
C
=
N
d
ed
C
=
N
=
N∈
Z
n
.
