Cryptography Reference
In-Depth Information
Bemerkung
Durch die Tatsache, dass die Primzahl
p
beim ElGamal-Verfahren in
Z
p
etwa von
der Größenordnung von
n
beim RSA-Verfahren ist, ist das ElGamal-Verfahren in
Z
p
g
b
und
c
A
b
=
=
N
aufwändiger als das RSA-Verfahren, da
B
zu berechnen
e
zu berechnen. Implementiert man
aber das Verfahren von ElGamal auf einer elliptischen Kurve, wobei man etwa
die gleichen Sicherheitsanforderungen stellt, so ist ElGamal sogar effizienter als
RSA, weil man mit deutlich kleineren Parametern auskommt.
sind. Beim RSA-Verfahren ist hingegen
nur
N
9.2.5 Ein Angriff
N
Wird der Exponent
b
, den der Sender zum Chiffrieren seiner Nachricht
be-
nutzt, mehrfach zur Verschlüsselung von Nachrichten verwendet, so kann ein
Klartext durch einen
Known-Plain-Text
-Angriff ermittelt werden. EinemAngreifer
A
ist ein zusammengehöriges Klartext-Geheimtext-Paar
(
N
,
C
)
bekannt. Folglich
A
b
=
N
kennt
A
auch das Element
c
. Damit kann
A
aus einem weiteren Ge-
C
=(
B
,
c
)
heimtext
, der mit demselben
b
erzeugt wurde, den dazugehörigen
N
aus
c
=
A
b
N
ermitteln; er berechnet dazu:
Klartext
c
−
1
c
=
A
−
b
N
−
1
A
b
N
=
N
.
N
N
N
aus
c
,
c
und
Folglich kann
N
ermittelt werden. Es ist also bei jedem Durch-
{
−
}
gang ein neues
b
aus der Menge
zu wählen. Das hat einen wei-
teren Vorteil: Man kann zweimal denselben Klartext verschicken, ohne dass ein
Angreifer das merkt. Die Geheimtexte sind verschieden.
2, . . . ,
p
2
9.3 Das Rabin-Verschlüsselungsverfahren *
Das Problem, eine natürliche Zahl in ein Produkt von Primzahlen zu faktorisie-
ren, wird als außerordentlich schwierig angesehen. Ist
n
ein Produkt von zwei
Primzahlen
p
und
q
der Größenordnung 512 Bit, wie sie beim RSA-Verfahren
verwendet werden, so braucht ein moderner Rechner unvertretbar lange Zeit, um
die Primzahlen
p
und
q
zu ermitteln. Wir werden moderne und effiziente Faktori-
sierungsalgorithmen in Kapitel 11 vorstellen. Es ist aber offen, ob nicht bereits in
nächster Zukunft ein Verfahren entdeckt wird, mittels dessen die Faktorisierung
deutlich effizienter möglich ist.
Das Verfahren von Rabin ist ein Public-Key-Verfahren mit einem öffentlichen
Schlüssel
n
, der ein Produkt zweier Primzahlen ist. Das Verfahren zu brechen
ist algorithmisch äquivalent zur Faktorisierung der Zahl
n
.
9.3.1 Quadratwurzeln modulo
n
∈
Z
n
∈
N
Es sei
n
. Ein Element
b
heißt eine
Quadratwurzel
modulo
n
von
∈
Z
n
, falls
b
2
a
=
a
; das Element
a
nennt man dann ein
Quadrat
modulo
n
.
