Cryptography Reference
In-Depth Information
Aufgabe
6.7.3 (quadratische Reste)
.
Es seien
n>
0
und
a
∈
Z
ein
quadratischer Rest
modulo
n
, d. h., es gilt ggT
(
a, n
)=1
und es gibt ein
b ∈
Z
mit
b
2
mod
n
=
a
mod
n
.
∈
Z
n
gilt.
Aufgabe
6.7.4 (Lösen quadratischer Gleichungen)
.
Überlegen Sie sich unter Zuhilfenahme
des Eulertests, wie man in Polynomzeit feststellen kann, ob eine quadratische Gleichung
der Form
ax
2
+
bx
+
c
mit
a, b,c
Zeigen Sie, dass
b
mod
n
∈
Z
eine Nullstelle in
Z
p
für eine gegebene Primzahl
p>
2
hat.
Aufgabe
6.7.5
.
Beweisen Sie (6.3.4) und (6.3.5).
Aufgabe
6.7.6 (Anzahl Wurzeln von
1
in
q
für zwei verschiedene
Primzahlen
p
und
q
. Zeigen Sie mit Hilfe des Chinesischen Restsatzes (Satz 6.3.1), dass
1
∈
Z
n
genau vier Wurzeln besitzt.
Aufgabe
6.7.7 (quadratische Reste und Chinesischer Restsatz)
.
Es seien
n
=
p
Z
n
)
.
Es sei
n
=
p
·
q
,für
zwei verschiedene Primzahlen
p
und
q
, und
a ∈
Z
n
. Zeigen Sie mit Hilfe des Chinesischen
Restsatzes (Satz 6.3.1), dass
a
·
∈
QR(
n
)
genau dann, wenn
a
mod
p
∈
QR(
p
)
und
a
mod
q
QR(
q
)
.
Aufgabe
6.7.8 (quadratische Reste und Jacobi-Symbol)
.
Es sei
n
=
p
∈
·
q
für zwei ungerade
und verschiedene Primzahlen
p
und
q
. Weiter sei
J
+
n
=
∈
Z
n
|
{
a
J
n
(
a
)=1
}
und
J
−
n
=
{a ∈
Z
n
|
J
n
(
a
)=
−
1
}
. Zeigen Sie folgende Aussagen:
Z
n
=
J
+1
∪ J
−
1
n
|J
+1
n
|
=
|J
−
1
n
Z
n
a)
und
|
, d. h., die Hälfte der Elemente in
besitzt
n
Jacobi-Symbol
1
und die andere Hälfte Jacobi-Symbol
−
1
.
J
+
n
.
b)
QR(
n
)
⊆
|
QR(
n
)
|
=
|J
+
n
|/
2
.
Hinweis: Benutzen Sie Aufgabe 6.7.7 sowie die Multiplikativität des Jacobi-Symbols (Lem-
ma 6.3.6).
Aufgabe
6.7.9 (Beispiele Miller-Rabin-Test)
.
Führen Sie den Miller-Rabin-Test für die
Eingabe
n
=25
aus. Gehen Sie dabei davon aus, dass das zufällig gewählte
a
den Wert
2
hat. Geben Sie die Werte an, die
b
der Reihe nach annimmt.
Finden Sie ein
a
c)
∈{
2
,...,n
−
2
}
, für das der Miller-Rabin-Test (mit obigem
n
)eine
falsche Ausgabe liefert.
Aufgabe
6.7.10 (Chinesischer Restsatz und Exponentiation)
.
Es sei
n
=
p
q
,wobei
p
und
q
unterschiedliche Primzahlen seien. Wie kann man die Kenntnis von
p
und
q
ausnutzen,
um Exponentiationen der Form
·
y
d
mod
n
mit
y,d < n
schneller berechnen zu können? Schätzen Sie den E
zienzgewinn gegenüber der direkten
Berechnung mit schneller Exponentiation ab, wenn Sie für Addition und Multiplikation
modulo
n
die Rechenzeiten
a
(log(
n
))
2
für Konstanten
a, b
zugrunde legen
und davon ausgehen, dass
p
und
q
bzgl. ihrer Binärdarstellung halb so groß sind wie
n
.
Aufgabe
6.7.11 (RSA und das Jacobi-Symbol)
.
Ein Klartext
x
wurde mit dem öffentlichen
RSA-Schlüssel
(77
,
17)
zum Chiffretext
y
=70
verschlüsselt. Bestimmen Sie
x
, indem Sie
den öffentlichen Schlüssel »brechen«, d. h., den privaten Schlüssel bestimmen.
·
log(
n
)
bzw.
b
·
