Obliczanie bezpieczeństwa RSA i Krzywych Eliptycznych

Witam,

Pod koniec pracy dyplomowej stanąłem przed takim zagadnieniem - w pracy miałem zaimplementować nową metodę bazującą na RSA. Później miałem dokonać faktoryzacji n-liczb w danym przedziale bitowym. Później na podstawie zebranych informacji - wyznaczyć ile liczb nadaje się do algorytmu - właśnie tu jest mój problem, przyznam szczerze z matematyką u mnie kiepsko. Może się okazać, że rozwiązanie jest banalne a ja po prostu na nie nie wpadłem. (:

Jak wyszło nam, że 5% liczb spełnia warunki metody - to ile jest takich liczb np. 64 bitowych. (oczywiście, wszystko to szacowanie - faktoryzacja już 256-bitowych liczb była bardzo czasochłonna...)

Promotor co do RSA napisał mi coś takiego (pisze strasznie nieczytelnie - więc nie jestem tego pewien)
64 bit -> 16 bajtów(powinno być 8?),
5% -> 2^5
,czyli jest takich liczb 2^16 - 2^5 = 2^11
Czyli dla liczb 64 bitowych jest 2^11 liczb spełniające nasze kryteria.

I teraz mam się odnieść do krzywych eliptycznych. Niestety - z krzywymi eliptycznymi wyskoczył mi na sam koniec pracy - 2 tygodnie przed oddaniem jej. Więc nie mam wielkiego pojęcia o nich. Oczywiście, poinformowałem go o tym - to on mi zapisał jedynie na pracy na szybkiego jeden wzór - #(?) 2(p-1)

//---- Niestety nie wiem jak na waszym forum posługiwać się znakiem potęgowania. ):
My wiemy, ale też nie rozumiemy dlaczego ^ ma specjalne znaczenie w tekście (dzięki czemu psuje posty jak Twój) - msm

Dziękuję za wszelką pomoc. (:

Zacznij od zadania pytania...

Jak obliczyć gęstość liczb, jak wiemy że 20% liczb z 1000 testowanych spełnia warunki mojego algorytmu - więc ile jest takich liczb (oczywiście szacujemy) dla wszystkich liczb np. 64 bitowych.

Podobnie z krzywymi eliptycznymi - o których nie mam niestety pojęcia - ile jest liczb dla danego przedziału które spełniają warunki algorytmu - jak wspomniałem.

Na koniec muszę porównać, jakiej długości mam użyć klucza by zapewnić bezpieczeństwo porównywalne dla tego z krzywych eliptycznych - ale myślę, że z porównaniem poradzę sobie sam. (:

Czyli np. dla rsa klucz o długości 130 bitów daje takie same bezpieczeństwo jak w krzywych eliptycznych przy 50 bitach (cyfry wziąłem z kosmosu) (;

Jak obliczyć gęstość liczb, jak wiemy że 20% liczb z 1000 testowanych spełnia warunki mojego algorytmu - więc ile jest takich liczb (oczywiście szacujemy) dla wszystkich liczb np. 64 bitowych.

zapewne 20% ze wszystkich liczb 64-bitowych czyli 0.2 * 2^64

Shalom napisał(a):

Jak obliczyć gęstość liczb, jak wiemy że 20% liczb z 1000 testowanych spełnia warunki mojego algorytmu - więc ile jest takich liczb (oczywiście szacujemy) dla wszystkich liczb np. 64 bitowych.

zapewne 20% ze wszystkich liczb 64-bitowych czyli 0.2 * 2^64

Dzięki wielkie, to by było najbardziej oczywiste rozwiązanie - tylko nie wiem dlaczego mój promotor to w taki sposób rozpisał. Jeszcze muszę znać odpowiedź dotyczącą krzywych eliptycznych.