Cryptography Reference
In-Depth Information
Lemma 7.7
Es sei v
−
ed
1
∈
N
=
∈
N
∈
Z
so gewählt, dass k
:
ungerade ist. Gilt für ein a
mit
2
v
ggT
(
a
,
n
)=
1
:
a
k
a
k
o
(
)
mod
p
=
o
(
)
mod
q
,
a
2
t
k
so existiert ein t
∈{
0, 1, . . . ,
v
−
1
}
mit
1
<
ggT
(
−
1,
n
)
<
n. Insbesondere gilt
a
2
t
k
a
2
t
k
=
(
−
)
=
(
−
)
p
ggT
1,
n
oder q
ggT
1,
n
.
Beweis.
Wegen
ed
≡
1
(
mod
ϕ
(
n
))
existiert ein
r
∈
Z
mit
ed
−
1
=
r
ϕ
(
n
)
. Also
gilt nach dem Satz 6.9 von Euler:
2
v
a
2
v
k
a
k
a
ed
−
1
a
r
ϕ
(
n
)
≡
(
a
ϕ
(
n
)
)
r
(
)
≡
≡
≡
≡
1
(
mod
n
)
.
2
v
a
k
Das heißt aber
n
|
(
)
−
1, wegen
n
=
pq
folgt
2
v
2
v
a
k
a
k
(
)
≡
(
)
(
)
≡
(
)
1
mod
p
und
1
mod
q
.
a
k
a
k
(
)
mod
p
und
o
(
)
mod
q
Potenzen von 2 kleiner oder
Damit sind die Ordnungen
o
gleich 2
v
(beachte Lemma 6.1 (b)).
1. Fall. o
a
k
a
k
2
v
: Dann existiert ein
t
(
)
mod
p
<
(
)
mod
q
≤
∈{
−
}
o
0, 1, . . . ,
v
1
mit
a
k
2
t
. Wir erhalten:
o
(
)
mod
p
=
a
2
t
k
2
t
a
2
t
k
a
k
≡
(
)
≡
1
(
mod
p
)
⇒
p
|
−
1,
a
2
t
k
2
t
a
2
t
k
a
k
≡
(
)
≡
(
)
⇒
−
1
mod
q
q
1.
a
2
t
k
Folglich gilt ggT
(
−
1,
n
)=
p
.
a
2
t
k
a
k
a
k
2
v
: Man erhält analog ggT
2. Fall. o
(
)
mod
q
<
o
(
)
mod
p
≤
(
−
1,
n
)=
q
.
Das Lemma zeigt, dass die Kenntnis von
n
,
e
und
d
eines RSA-Systems eine Fak-
torisierung von
n
erlaubt, falls man nur ein
passendes a
findet. Man gehe wie folgt
vor:
ed
−
1
∈
N
=
Bestimme
v
, sodass
k
2
v
ungerade ist.
∈
Z
<
<
Wähle ein
a
mit 1
a
n
.
Ist ggT
(
a
,
n
)
>
1 - Stop!, sonst:
a
2
t
k
(
−
)
∈{
−
}
Bestimme ggT
1,
n
für
t
0, 1, . . . ,
v
1
.
Falls diese ggT alle gleich 1 oder
n
sind, so wähle man ein neues
a
. Ansonsten
ist eine Faktorisierung bestimmt.
Wir begründen nun, dass die Wahrscheinlichkeit, ein
passendes a
zu finden, sehr
groß ist:
