Wstęp
Algorytm szyfrowania RSA to jedna z najpopularniejszych i bardzo często stosowanych form zabezpieczania komunikacji w sieci. Zapewnia on wysoki poziom bezpieczeństwa oraz dużą funkcjonalność dzięki temu, że jest oparty na kryptografii asymetrycznej.
Czym jest kryptografia asymetryczna ?
Kryptografia asymetryczna to technologia szyfrująca wykorzystująca parę kluczy w ramach jednego rodzaju szyfrowania i deszyfrowania.
- klucz publiczny - umożliwiający zaszyfrowanie informacji, które mają być niejawne
- klucz prywatny - umożliwiający odszyfrowanie informacji, zaszyfrowanych wcześniej kluczem publicznym z tej samej pary
Dzięki temu można w sposób jawny wysłać informacje o sposobie zaszyfrowania (klucz publiczny) mających zostać przesłanych poufnych danych, nie ryzykując ich rozszyfrowania przez inną osobę niż twórca klucza publicznego (bo tylko on posiada klucz prywatny).
Bezpieczeństwo szyfru RSA:
Żeby system oparty na 2 kluczach był sensowny nie może dojść do sytuacji, w której na podstawie jawnie podanego klucza publicznego można odtworzyć deszyfrujący klucz prywatny. Jest to w zasadzie esencja działania i dowód bezpieczeństwa funkcjonowania algorytmu, dlatego żeby obliczyć klucze prywatny i publiczny potrzebne jest wyliczenie funkcji Eulera.
Funkcja Eulera zwraca ilość liczb dodatnich, całkowitych, nie większych niż podana liczba i nie mających z nią innych wspólnych dzielników niż 1.
Kilka przykładów:
- f(10) = 4, ponieważ powyższe warunki spełniają liczby: 1,3,7,9
- f(15) = 8, ponieważ powyższe warunki spełniają liczby: 1,2,4,7,8,11,13,14
Obliczanie wartości funkcji Eulera jest zadaniem stosunkowo trudnym, do tego stopnia, że przy dużych liczbach (takich na kilkadziesiąt/kilkaset cyfr) nawet komputery nie dają rady dojść do wyniku w sensownym czasie. Istnieje jednak wyjątek od tej reguły jakim są liczby pierwsze, które ze względu na swoją naturę nie mają żadnych dzielników oprócz 1, dlatego też sposób określania dla nich wartości funkcji Eulera jest bardzo prosty.
- f(13) = 12, pasujące liczby: 1,2,3,4,5,6,7,8,9,10,11
- f(5) = 4, pasujące liczby: 1,2,3,4
- f(97) = 96 …
- f(n) = n - 1
Ostatnią rzeczą potrzebną do zrozumienia wstępnego etapu działania algorytmu i jego “siły” jest zależność:
f(a * b) = f(a) * f(b)
czyli np:
f(12) = f(3 * 4) = f(3) * f(4) = 2 * 2 = 4
Algorytm w początkowej fazie działania zachowuje się w sposób następujący:
- Wyszukuje 2 liczby pierwsze p1 i p2 (im większe, tym całość działania algorytmu jest bezpieczniejsza)
- Wymnaża je i zapisuje jako wartości N
- Oblicza wartości funkcji Eulera z N dzięki zależności:
f(N) = f(p1 * p2) = f(p1) * f(p2) = (p1 - 1) * (p2 - 1)
Dzięki temu uzyskuje się następującą zależność:
- Osoba, która zna tylko i wyłącznie wartość N nie jest w stanie w żaden szybki i efektywny sposób obliczyć wartości funkcji Eulera, ani poprzez obliczenie jej bezpośrednio, ani poprzez próbę rozłożenia N na iloczyn liczb pierwszych.
- twórca wartości N wykorzystując trik matematyczny z pkt.3 i wiedzę na temat tego jak wartość N została wygenerowana może bez problemu wyznaczyć wartość tej funkcji
Wygenerowanie klucza prywatnego i publicznego:
Kolejnym etapem działania algorytmu jest wygenerowanie klucza publicznego i prywatnego. Aby wygenerować klucz publiczny należy wybrać dowolną liczbę większą od 1 i mniejszą od funkcji Eulera z N, która jednocześnie nie ma żadnego wspólnego dzielnika oprócz 1 z wartością funkcji Eulera z N.
np.
N = 21
f(N) = 12
e = 5 (przykładowa liczba klucza publicznego)
Bazując na kluczu publicznym i informacji o wartości funkcji Eulera z N można wygenerować klucz prywatny. Robi się to przy wykorzystaniu twierdzenia Eulera:
m^(f(N)) mod N = 1
po przekształceniu:
m^(K * f(N) + 1) mod N = m (K jest dowolną liczbą całkowitą, dodatnią)
tworząc klucz prywatny dąży się do uzyskania zależności:
e * d = K * f(N) + 1
po przekształceniu:
e * d mod (f(N)) = 1
Wartości d (klucza prywatnego) spełniającej to równanie szuka się metodą iteracyjną, poprzez sprawdzenie wszystkich możliwych liczb do momentu znalezienia pasującej.
5 * 1 mod 12 = 5 (nie pasuje)
5 * 2 mod 12 = 1 (pasuje czyli d = 2)
Proces szyfrowania/deszyfrowania:
m - poufne dane np. 4 (w postaci jawnej/niezaszyfrowanej)
C - zaszyfrowane poufne dane
Szyfrowanie przy użyciu klucza publicznego, czyli wartości N,e:
m^e mod N = C
4^5 mod 21 = 1024 mod 21 = 16
Deszyfrowanie przy użyciu klucza prywatnego, czyli wartości N,d:
C^d mod N = m
16^2 mod 21 = 256 mod 21 = 4
Jak wyszło ?
Da się z tego coś zrozumieć ?
Dajcie znać w komentarzach
Do twierdzenia Eulera bez problemu, a potem z grubsza, pewnie gdybym musiał i samemu zaczął to sobie liczyć to by dotarło ;)
Congratulations @kraken14! You have completed the following achievement on the Hive blockchain and have been rewarded with new badge(s) :
You can view your badges on your board and compare yourself to others in the Ranking
If you no longer want to receive notifications, reply to this comment with the word
STOP