ALGORYTMY RSA

[ Pobierz całość w formacie PDF ]
PunktystałeRSA
Punkty stałe RSA
Andrzej Chmielowiec
14 marca 2008
Streszczenie
Artykuł ten poświęcony jest punktom stałym algorytmu RSA. Jest to ważny problem
z punktu widzenia każdego kryptosystemu. Duża liczba takich punktów jest bowiem bar
dzo nieporządana. Artykuł opisuje w jaki sposób można estymować wartość oczekiwaną
punktów stałych dla losowo wybranych parametrów systemu. Okazuje się, że prawdopo
dobiestwo znalezienia takiego punktu jest rzędu
O(
ln
2
n/n)
, gdzie
n
jest modułem RSA.
Oznacza to, że jest ono zaniedbywalnie małe dla praktycznych zastosowań.
1 Wstęp
Algorytm RSA odgrywa bardzo ważną rolę wśród systemów klucza publicznego (PKI). Dla
tego też statystyczne własności jego parametrów są ważnym elementem analizy. Problemy
takie poruszane są między innymi w artykułach [
], [
], [
], [
] i dają nam możliwość oceny
bezpieczeństwa tego systemu. W artykule rozważany jest problem punktów stałych algorytmu
szyfrującegoRSA.Pokażemy,żeichliczbadlalosowowygenerowanegokluczajestbardzomała
i nie wpływa na bezpieczeństwo.
W artykule będziemy wykorzystywali standardową notację. Przyjmujemy zatem, że moduł
RSA
n
jest iloczynem dwóch liczb pierwszych
p
i
q
o tej samej liczbie bitów. Oznacza to, że
n = pq
i
⌊
log
2
(p) + 1⌋=⌊
log
2
(q) + 1⌋
. Prywatnywykładnikszyfrującybędzieoznaczanyprzez
d
, a odpowiadający mu wykładnik deszyfrujący przez
e
.
Denicja 1
Powiemy, że element
x∈
Z
n
jest punktem stałym operacji szyfrującej RSA jeśli
x
e
≡x mod n.
€
CentrumModelowaniaMatematycznegoSigma
1
PunktystałeRSA
Oznacza to, że element
x∈
Z
n
jest punktem stałym RSA jeśli jest pierwiastkiem wielomianu
S(X) = X
e
−X∈
Z
n
[X]
.Ponieważ
n = pq
,to
Z
n
≃
Z
p
×
Z
q
ikażdypierwiastek
r
wielomianu
S∈
Z
n
[X]
możebyćreprezentowanyzapomocąpary
(r
1
, r
2
)∈
Z
p
×
Z
q
.Namocytwierdzenia
chińskiego mamy
S(r)≡0 mod n
wtw.
S(r
1
)≡0 mod p,
S(r
2
)≡0 mod q.
Lemat 1
Wielomian
S(X) = X
e
−X = X(X
e−1
−1)∈
Z
p
[X]
ma dokładnie
1 +
NWD
(e−
1, p−1)
pierwiastków.
Dowód:
Oczywiście
S(X)
majedenpierwiastekrówny
0
.Pozostałerozwiązaniasąelementami
cyklicznej grupy multiplikatywnej
Z
p
=g
. Każde rozwiązanie równania
X
e−1
≡1 mod p
(1)
możnazatemwyrazićwsposóbjednoznacznyjako
g
x
,gdzie
x∈{0, 1, . . . , p−2}
.Ale
g
x
jest
rozwiÄ…zaniem (
wtedy i tylko wtedy, gdy
x(e−1)≡0 mod (p−1).
(2)
Ze stwierdzenia 3.3.1
] wiemy, że
ma dokładnie NWD
(e−1, p−1)
rozwiązań.
€
Powyższy lemat pokazuje, że wielomian
S(X) = X
e
−X = X(X
e−1
−1)∈
Z
p
[X]
ma
Z
q
[X]
madokładnie
1+
NWD
(e−1, q−1)
pierwiastków.DlategocałkowitaliczbapunktówstałychRSAjestrówna
(1 +
NWD
(e−1, p−1))(1 +
NWD
(e−1, q−1)).
W następnej części wyznaczymy wartość oczekiwaną liczby stałych punktów RSA dla losowo
wybranych parametrów
p
,
q
i
e
.
2 NWD losowych liczb całkowitych
Niech
N
i
M
będą nieujemnymi liczbami całkowitymi takimi, że
N≤M
. Dla tych liczb
deniujemy dwa zbiory
U ={1, 2, . . . , N}
i
V ={1, 2, . . . , M}
. Najpierw przypomnimy kla
syczny wynik opublikowany przez Diriechlet [
], który wyznaczaprawdopodobieństwo tego, że
NWD
(u, v) = 1
dla
(u, v)∈U×V
. W artykule przedstawimy kompletny dowód, gdyż jego
elementy będą niezbędne w dalszych rozważaniach. Zacznijmy od następującego lematu
Lemat 2
Prawdziwe są następujące tożsamości:
M
1
k
≤ln M + 1,
(3)
k=1
CentrumModelowaniaMatematycznegoSigma
2
×
dokładnie
1+
NWD
(e−1, p−1)
pierwiastków.Podoniewielomian
S(X)∈
   PunktystałeRSA
1
M
1
1
k
2
≤
1
≤
M−1
.
(4)
k=M
Dowód:
Dlakażdejnieujemnej,malejącejfunkcji
f (x)
mamy
k+1
k
f (x)dx≤f (k)≤
k−1
f (x)dx
.
Stosując powyższą zależność do funkcji
f (x) =
x
mamy
M
1
k
M
1
k
M
k
dx
x
M
dx
x
= 1 +
≤1 +
= 1 +
=
ln
M + 1.
k−1
1
k=1
k=2
k=2
WykorzystujÄ…c funkcjÄ™
x
2
możemy udowodnić drugą część lematu. Ponieważ
x
2
jest malejÄ…ca
dla liczb dodatnich to mamy
1
1
k
2
1
k
dx
x
2
1
dx
x
2
1
B
.
≤
=
=
k−1
B
k=B+1
k=B+1
Podobną nierówność otrzymujemy dla dolnego ograniczenia
1
1
k
2
1
k+1
dx
x
2
1
dx
x
2
1
B + 1
.
≥
=
=
k
B+1
k=B+1
k=B+1
€
W ogólności twierdzenie Dirichleta wyznacza nam przwdopodobieństwo tego, że losowo
wybrane liczby całkowite są względnie pierwsze.
Twierdzenie 1 (G. Lejeune Dirichlet)
Niech
P (U, V )
oznacza prawdopodobieństwo tego,
żeNWD
(u, v) = 1
dlalosowowybranejpary
(u, v)∈U×V
.Wtedyprawdziwyjestnastępujący
zwiÄ…zek
P
1
= lim
|U|,|V|!1
P (U, V ) =
6
2
.
Dowód:
Niech
q(N, M )
oznacza liczbÄ™ par
(u, v)∈U×V
dla których NWD
(u, v) = 1
.
Stosując regułę włączeń i wyłączeń mamy następujące zależności:
q(N, M ) = N M−
N
p
1
M
p
1
+
N
p
1
p
2
M
p
1
p
2
−. . . ,
p
1
p
1
<p
2
1
N
p
1
p
2
p
r
M
p
1
p
2
p
r
= N M +
(−1)
r
.
r=1
p
1
<p
2
<···<p
r
Teraz wykorzystamy funkcjÄ™ Mobiusa
µ
która jest zdeniowana następująco
CentrumModelowaniaMatematycznegoSigma
3
k
1
  PunktystałeRSA
•µ(1) = 1
,
•µ(p
1
p
2
p
r
) = (−1)
r
jeśli
p
i
są różnymi liczbami pierwszymi,
•µ(n) = 0
jeśli
n
jest podzielne przez kwadrat pewnej lczby pierwszej.
Można zauważyć, że wyrażenie na
q(N, M )
zawiera w mianownikach tylko liczby bezkwadra
towe. Każdy taki mianownik pojawia się w tej sumie dokładnie raz. Wykorzystując denicję
funkcji Mobiusa mamy
1
N
k
M
k
q(N, M ) =
µ(k)
.
k=1
Jeśli
{x}= x−⌊x⌋
to możemy zapisać
q(N, M )
N M
1
N M
1
N
k
N
k
M
k
M
k
=
µ(k)
−
−
k=1
1
µ(k)
k
2
=
−A(M )−A(N ) + B(N, M ),
k=1
gdzie
1
N
1
µ(k)
k
N
k
A(N ) =
,
k=1
1
1
N M
N
k
M
k
B(N, M ) =
µ(k)
.
k=1
Na podstawie zależności
i (
mamy
|A(N )|≤
1
N
1
µ(k)
k
N
k
1
N
N
µ(k)
k
N
k
1
N
1
µ(k)N
k
2
=
+
k=1
k=1
k=N +1
≤
1
N
N
1
k
+
1
1
k
2
≤
ln
N + 1
N
1
1
k
2
≤
ln
N + 2
N
+
.
k=1
k=N +1
k=N +1
CentrumModelowaniaMatematycznegoSigma
4
PunktystałeRSA
Z powyższego wynika, że
lim A(N ) = 0
gdy
N
dąży do nieskończoności. Analogiczny wynik
otrzymujemy dla
B(N, M )
. Niech
N≤M
, wtedy
|B(N, M )|≤
1
N M
1
N
k
M
k
µ(k)
k=1
1
N M
M
N
k
M
k
1
N M
1
µ(k)N M
k
2
=
µ(k)
+
k=1
k=M +1
≤
1
N
1
1
k
2
≤
1
N
1
M
≤
2
+
+
N
.
k=M +1
Oznacza to, że
lim B(N, M ) = 0
gdy
N
i
M
dążą do nieskończoności. Ponieważ ciągi
A(N ), A(M )
i
B(N, M )
dążą do
0
to
q(N, M )
N M
1
µ(k)
k
2
P
1
= lim
N,M!1
=
.
k=1
Powyższa analiza daje możliwość oszacowania
q(N,M )
N M
dla
N > 1
. BiorÄ…c pod uwagÄ™ oszaco
P
1
−"
N
≤
q(N, M )
N M
≤P
1
+ "
N
,
(5)
gdzie
"
N
=|A(N )|+|A(M )|+|B(N, M )|≤
2 ln N + 6
N
≤12
ln N
N
. (6)
Abyzakończyćdowódmusimywyznaczyćdokładnąwartośćsumy
k
2
.Ponieważ
d|n
µ(d)
wynosi
0
dla wszystkich
n > 1
i
1
dla
n = 1
, to
0
1
1
1
1
µ(k)
k
2
1
m
2
1
n
2
=
@
µ(d)
A
= 1.
k=1
m=1
n=1
d|n
Wykorzystując powyższe równanie możemy wyrazić
P
1
w następujący sposób
1
1
k
2
−1
6
2
.
P
1
=
=
k=1
€
Powyższetwierdzeniepozwalanauzyskanieznacznieogólniejszego rezultatu,amianowicie
prawdopodobieństwa
P
B
, że NWD dwóch liczb całkowitych jest niewiększy niż
B
.
CentrumModelowaniaMatematycznegoSigma
5
wania na
|A(N )|
i
|B(N, M )|
możemy zapisać
µ(k)
   [ Pobierz całość w formacie PDF ]