ALGORYTMY RSA.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 [ 1 ], [ 3 ], [ 5 ], [ 6 ] 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

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 ( 1) wtedy i tylko wtedy, gdy

x(e−1)≡0 mod (p−1).

(2)

Ze stwierdzenia 3.3.1 [4 ] wiemy, że (2) 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 [ 2 ], 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:

≤ln M + 1,

(3)

k=1

CentrumModelowaniaMatematycznegoSigma

dokładnie 1+ NWD (e−1, p−1) pierwiastków.Podoniewielomian S(X)∈

PunktystałeRSA

k 2

≤ 1

≤

M−1 .

(4)

k=M

Dowód: Dlakażdejnieujemnej,malejącejfunkcji f (x) mamy

k+1

f (x)dx≤f (k)≤

k−1 f (x)dx .

Stosując powyższą zależność do funkcji f (x) =

x mamy

= 1 +

≤1 +

= 1 +

= ln M + 1.

k−1

k=1

k=2

Wykorzystując funkcję x 2 możemy udowodnić drugą część lematu. Ponieważ x 2 jest malejąca

dla liczb dodatnich to mamy

k 2

x 2

B .

≤

k−1

k=B+1

Podobną nierówność otrzymujemy dla dolnego ograniczenia

k 2

k+1

x 2

B + 1 .

≥

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 ) =

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−

p 1

p 1 p 2

−. . . ,

p 1

p 1 <p 2

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

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

q(N, M ) =

µ(k)

k=1

Jeśli {x}= x−⌊x⌋ to możemy zapisać

q(N, M )

N M

µ(k)

−

k=1

µ(k)

k 2

−A(M )−A(N ) + B(N, M ),

k=1

gdzie

µ(k)

A(N ) =

k=1

N M

B(N, M ) =

µ(k)

k=1

Na podstawie zależności (3) i ( 4) mamy

|A(N )|≤ 1

µ(k)

µ(k)N

k 2

k=1

k=N +1

≤ 1

k +

k 2

≤ ln N + 1

k 2

≤ ln N + 2

k=1

k=N +1

CentrumModelowaniaMatematycznegoSigma

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

µ(k)

k=1

N M

µ(k)N M

k 2

µ(k)

k=1

k=M +1

≤ 1

k 2

≤ 1

≤ 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

µ(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

≤12 ln 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

µ(k)

k 2

m 2

n 2

µ(d)

= 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

k 2

−1

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

wania na |A(N )| i |B(N, M )| możemy zapisać

µ(k)

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: