Cryptography Reference
In-Depth Information
7.1.2 Die Schlüsselerzeugung
Beim RSA-Verfahren sind die beiden Zahlen
n
und
e
öffentlich bekannt. Wir
fassen von nun an die beiden Zahlen zum öffentlichen Schlüssel
zusam-
men. Wir schildern die Schlüsselerzeugung, also die Erzeugung des öffentlichen
Schlüssels
(
n
,
e
)
(
n
,
e
)
und des geheimen Schlüssels
d
durch den Empfänger
R
:
R
wählt zwei Primzahlen
p
=
q
.
=
ϕ
(
)=(
−
)(
−
)
R
berechnet
n
:
pq
,
n
p
1
q
1
(siehe das Beispiel auf Seite 75).
∈
N
<
<
ϕ
(
)
(
ϕ
(
)) =
R
wählt ein
e
mit 1
e
n
und ggT
e
,
n
1.
R
berechnet
d
∈
N
mit
ed
≡
1
(
mod
ϕ
(
n
))
.
Es sind dann
der öffentliche Schlüssel von
R
und
d
der geheime Schlüssel
von
R
. Es sind auch die Größen
p
,
q
,
(
n
,
e
)
ϕ
(
)
geheim zu halten. Ist nämlich einem
Angreifer eine dieser drei Größen bekannt, so kann er
d
berechnen.
n
7.1.3 Die Verschlüsselung
C
N
Die Erzeugung des Geheimtextes
aus dem Klartext
ist einfach: Der Sender
S
besorgt sich den öffentlichen Schlüssel
(
n
,
e
)
des Empfängers
R
und geht wie
folgt vor:
N∈
Z
n
.
S
codiert seine Nachricht in den Klartext
e
C
=
N
∈
Z
n
.
S
berechnet den Geheimtext
:
S
sendet den Geheimtext
C
an
R
.
7.1.4 Die Entschlüsselung
Die Entschlüsselung
d
=
N
mit dem geheimen Schlüssel
d
klappt wegen Lemma 7.1.
C→C
Beispiel
Es seien
p
=
=
=
ϕ
(
)=
·
=
=
7 und
q
11. Dann gilt
n
77,
n
6
10
60. Die Wahl
e
13
(
)=
(
)=(
)
erfüllt ggT
e
,60
1. Damit hat
R
den öffentlichen Schlüssel
n
,
e
77, 13
.
Mit dem euklidischen Algorithmus berechnet
R
seinen geheimen Schlüssel
d
:
≡
·
(
)
1
37
13
mod 60
,
sodass
d
37.
Nun will
S
an
R
die Nachricht
=
N
=
∈
Z
77
senden. Dazu
b
esorgt sich
S
den
7
öffentlichen Schlüssel
(
n
,
e
)=(
77, 13
)
und verschlüsselt
N
=
7zu
7
13
e
C
=
N
=
=
35 .
