Cryptography Reference
In-Depth Information
Berechnen Sie zudem
J
n
(
y
)
und
J
n
(
x
)
mit Algorithmus 6.3 und überprüfen Sie so
exemplarisch, dass das Jacobi-Symbol, wie in Lemma 6.4.2 bewiesen, bei der RSA-
Verschlüsselung erhalten bleibt.
Aufgabe
6.7.12 (Unsicherheit von RSA und Jacobi-Symbol)
.
GebenSieeinenerfolgrei-
chen Angreifer auf das RSA-Kryptoschema an, der Lemma 6.4.2 ausnutzt. Berechnen Sie
den Vorteil Ihres Angreifers.
Aufgabe
6.7.13 (Äquivalenz: Berechnen von
φ
(
n
)
und Faktorisieren von
n
)
.
Es sei
n
=
p · q
für verschiedene Primzahlen
p
und
q
gegeben. Zeigen Sie, wie man aus
φ
(
n
)=
(
p
1)
und
n
, die Primzahlen
p
und
q
ezient berechnen kann.
Aufgabe
6.7.14 (Spezialfall von Bemerkung 6.4.1)
.
Wir wollen in dieser Aufgabe einen
Spezialfall von Bemerkung 6.4.1 beweisen: Geben Sie einen ezienten Algorithmus an,
der, bei Eingabe eines öffentlichen RSA-Schlüssels
(
n,
3)
und des zugehörigen privaten
RSA-Schlüssels
(
n, d
)
, die Primfaktoren
p
und
q
von
n
bestimmt. Wir betrachten also
lediglich den Spezialfall
e
=3
. Hinweis: Zeigen Sie, dass für
φ
(
n
)
nur wenige Zahlen in
Frage kommen.
Aufgabe
6.7.15 (Verallgemeinerter Angriff auf »Textbook RSA« mit kleinem Exponenten)
.
Es seien
(
n
1
,
3)
,
(
n
2
,
3)
und
(
n
3
,
3)
paarweise verschiedene öffentliche RSA-Schlüssel von
drei Parteien. Für alle drei Schlüssel ist also
e
=3
. Wir nehmen an, dass alle drei
Parteien die Nachricht
m<
min(
n
1
,n
2
,n
3
)
mit ihrem öffentlichen Schlüssel gemäß dem
RSA-Verfahren verschlüsseln. Ein Angreifer erhält also die Chiffretexte
c
1
=
m
3
mod
n
1
,
c
2
=
m
3
mod
n
2
sowie
c
3
=
m
3
mod
n
3
. Geben sie ein ezientes Verfahren an, mit dem
der Angreifer, bei Eingabe der drei Chiffretexte sowie der drei öffentlichen Schlüssel, die
Nachricht
m
berechnen kann.
Hinweis: Verwenden Sie, ohne Beweis, für den Fall, dass die Module
n
1
,
n
2
und
n
3
paarweise teilerfremd sind, eine verallgemeinerte Version des Chinesischen Restsatzes
(Satz 6.3.1): Es seien
n
1
,...,n
l
≥
−
1)
·
(
q
−
2
paarweise teilerfremd und es sei
n
=
n
1
···
n
l
.Dann
ist die Abbildung
h
:
Z
n
→
Z
n
1
×···×
Z
n
l
definiert durch
k
→
(
k
mod
n
1
,...,k
mod
n
l
)
n
n
i
ein Ring-Isomorphismus. Gilt
1=
r
i
· n
i
+
s
i
·
,für
r
i
,s
i
∈
Z
und alle
i ∈{
1
,...,l}
,
dann ist
(
a
1
,...,a
l
)
→
i
=1
a
i
· s
i
·
mod
n
die Umkehrabbildung
h
−
1
zu
h
.
Aufgabe
6.7.16 (RSA und CCA-Sicherheit)
.
Geben Sie zunächst, analog zu Definiti-
on 6.2.2, eine formale Definition für die CCA-Sicherheit asymmetrischer Kryptoschemen
an. Beweisen Sie dann, dass die am Anfang von Abschnitt 6.4.3 beschriebene Variante
vonRSA,inder
r
zufällig gewählt wird und dann
r
n
n
i
x
wie üblich mit dem RSA-Verfahren
verschlüsselt wird, keine CCA-Sicherheit bietet. Hinweis: Verwenden Sie die Multiplika-
tivitätseigenschaft von RSA, d. h.,
a
e
||
b
e
mod
n
=(
ab
)
e
mod
n
.
Aufgabe
6.7.17 (ElGamal)
.
Bestimmen Sie einen Erzeuger
g
von
·
Z
13
und ein ElGamal-
Z
13
und
g
. Verschlüsseln Sie dann den Klartext
x
=7
mit dem öffent-
lichen Schlüssel Ihres Schlüsselpaares.
Aufgabe
6.7.18 (Gleichverteilung auf zyklischen Gruppen)
.
Es sei
Schlüsselpaar für
eine zyklische Gruppe
der Ordnung
n
mit Erzeuger
g
. Zeigen Sie, dass die Abbildung, die
a
G
∈
Z
n
auf
g
a
∈G
abbildet, ein Gruppenisomorphismus von
ist. Damit
folgt direkt, dass durch die folgende Vorgehensweise ein Element zufällig gleichverteilt
aus
Z
n
mit Addition modulo
n
nach
G
Z
n
und gib
g
a
aus.
G
gewählt wird: Wähle
a
zufällig gleichverteilt aus
