Cryptography Reference
In-Depth Information
cken? Packen Sie Ihre Nachricht in eine Kiste, befestigen Sie das öffentlich zu-
gängliche Schloss von
R
an Ihre Kiste und schicken Sie die Kiste an
R
. Nur
R
hat
den Schlüssel, um das Schloss zu öffnen.
7.1.1 Das Kryptosystem
Das RSA-Verfahren ist wie das Pohlig-Hellman-Verfahren eine
Exponentiations-
chiffre
. Der Klartext
N
Z
n
,
n
∈
N
, wird durch den
Sender
S
verschlüsselt, indem mit dem öffentlichen Schlüssel
e
des Empfängers
R
eine Potenz von
, aufgefasst als Element von
N
gebildet wird:
e
C
=
N
∈
Z
n
S
R
(
)
n
,
e
Der Empfänger
R
hat
d
als geheimen Schlüssel so bestimmt, dass
d
e
d
C
=(
N
)
=
N
erfüllt ist. Man beachte, dass beide Schlüssel, also
e
zumVerschlüsseln und
d
zum
Entschlüsseln, vom Empfänger
R
stammen. Der Schlüssel
e
ist öffentlich zugäng-
lich, sodass jeder eine Nachricht mit
e
verschlüsseln kann. Aber nur
R
kennt den
geheimen Schlüssel
d
, und daher kann auch nur
R
den Geheimtext entschlüsseln.
Nicht einmal der Sender selbst kann seine eigene Nachricht entschlüsseln.
Wir werden genauer und erinnern an die Euler'sche
ϕ
-Funktion (siehe Seite 75).
Für
n
∈
N
gilt
)=
|
Z
n
|
=
|
{
ϕ
(
∈
N
≤
≤
(
)=
}
|
n
a
;1
a
n
, ggT
a
,
n
1
.
Gegeben sind zwei verschiedene Primzahlen
p
und
q
. Wir setzen
n
=
pq
und
(
Z
n
,
·
)
betrachten die (multiplikative) Halbgruppe
der Ordnung
n
. Das
RSA-
Verfahren
ist ein asymmetrisches Kryptosystem mit:
=
Z
n
.
•
Klartextmenge
P
•
Geheimtextmenge
C
=
Z
n
.
=
{
∈
N
(
ϕ
(
)) =
}
•
Schlüsselmenge
K
e
; ggT
e
,
n
1
(oft erwähnt man auch
n
in der Schlüsselmenge, d. h.
K
=
{
(
n
,
e
)
∈
N
×
N
; ggT
(
e
,
ϕ
(
n
)) =
1
}
).
e
∈
(
N
)=
N
•
Verschlüsselungsfunktionen
f
e
mit
e
K
definiert durch
f
e
für
N∈
P
.
d
∈
(
C
)=
C
•
Entschlüsselungsfunktionen
f
d
mit
d
K
definiert durch
f
d
für
C∈
C
, wobei
ed
≡
1
(
mod
ϕ
(
n
))
.