[Delfin17]

Szyfrowanie RSA to jeden z pierwszych asymetrycznych algorytmów kryptograficznych.
Algorytm może być stosowany do szyfrowania, oraz do podpisów cyfrowych, a jego bezpieczeństwo opiera się na trudności faktoryzacji dużych liczb złożonych.
Czym jest faktoryzacja?

Faktoryzacja liczby x polega na znalezieniu takich liczb które pomnożone przez siebie dadzą nam liczbę x. Przykład: Mamy liczbę 12 którą możemy rozłożyć na 2*3 warto dodać że faktoryzacja trywialna nie będzie nas interesować czyli 12*1 albo 2*3*1 itp.

Powróćmy teraz do RSA. Na samym początku musimy wygenerować pary liczb które będą odpowiednio kluczem publicznym, i kluczem prywatnym.
Jak zapewne się domyślacie klucz publiczny będzie służył do szyfrowania wiadomości, natomiast klucz prywatny do odszyfrowywania. Klucz publiczny jest ogólnie dostępny i każdy może za jego pomocą zaszyfrować wiadomość, jednak odczytać ją będzie mogła tylko osoba która jest w posiadaniu klucza prywatnego.

Przechodzimy do generowania kluczy.
Musimy wygenerować dwie losowe liczby pierwsze, najlepiej o podobnej ilości bitów (dane w komputerach zapisywane są w postaci zer, i jedynek. Każda taka cyfra to jeden bit).
Mamy więc dwie liczby pierwsze p,q. Wyznaczamy sobie ich iloczyn n=p*q.
Teraz musimy wyznaczyć wartość funkcji Eulera dla liczny n.
Co to jest funkcja Eulera?
Funkcja ta zwraca ilość liczb które są względnie pierwsze z liczbą którą podamy. Czyli ile jest liczb które nie mają wspólnego dzielnika z naszą liczbą.
Tutaj mamy mały problem ponieważ n jest gigantyczną liczbę, a my musimy znaleźć ilość liczb względnie pierwszych z nią. Jest to oczywiście wykonalne ale zajmie ogromne ilości czasu przez co wiadomość odszyfrowana po np. 30 latach będzie dla nas bezużyteczna.
My natomiast znamy liczby pierwsze z których powstała nasza liczba n.

Funkcja Eulera ma pewne własności np takie że φ(p*q) = φ(p) * φ (q) ale tylko wtedy kiedy x oraz y nie mają wspólnych dzielników tj. są ze sobą względnie pierwsze.
Nasze liczby p,q są pierwsze, więc dzielą się tylko przez 1 oraz przez siebie, a wiemy że nie są identyczne więc możemy z całą pewnością stwierdzić, że są ze sobą względnie pierwsze. W takim razie możemy wykorzystać tą własność do dalszych obliczeń.
Jeśli Funkcja Eulera zwraca ilość liczb względnie pierwszych z liczbą którą jej podamy, a my podaliśmy liczbę pierwszą to oznacza, że każda liczba mniejsza od niej jest z nią względnie pierwsza.
Wiemy w takim razie że funkcja Eulera z liczby pierwszej to ta liczba minus jeden φ(p)=p-1.
Możemy więc wyznaczyć wartość funkcji Eulera z n. φ(n) = (p-1) * (q-1). Nam zajęło to chwilę, a osobie która będzie próbowała sama wyliczyć tą wartość zajmie to lata, bądź setki lat przy odpowiednio dużych liczbach p,q.
Teraz będzie już z górki. Wybieramy dowolną liczbę e która będzie większa od 1 ale mniejsza od φ(n) i względnie z nią pierwsza.
Znajdujemy taką liczbę d która pomnożona przez e, i podzielona przez φ(n) da nam resztę 1

(d*e) / φ(n) = x +1

x nas wcale nie interesuje, potrzebujemy tylko takiego d który spełni to równanie.
Po obliczeniu d mamy już wszystko co potrzebujemy do szyfrowania, i deszyfrowania.

Para liczb (n,e) jest naszym kluczem publicznym, natomiast para (n,d) to klucz prywatny

Szyfrowanie, i deszyfrowanie będzie polegało na operacjach modulo, czyli reszcie z dzielenia.

11 mod 3 = 2 ponieważ 11/2 to 3, i zostaje 2 reszty.
Przechodzimy do szyfrowania.
Dzielimy naszą wiadomość na bloki o k wartości liczbowej (jak pisałem wyżej wszystko w komputerze to zera, i jedynki które możemy zamieniać na liczby). Istotnym faktem jest to, że k nie może być większe od n

Każdy blok szyfrujemy tak samo c = k^emod n
gdzie c to nasz zaszyfrowany blok
Jeśli chodzi o deszyfrację to każdy blok odszyfrowujemy w ten sposób
m = c^d mod n
gdzie m to nasza odszyfrowana wiadomość

Na koniec kilka ciekawostek z Wikipedii

Pierwszą udaną faktoryzację RSA zakończono 2 grudnia 1999 roku w ramach konkursu The RSA Factoring Challenge (Algorytm powstał w 1977 roku)

Dotychczas największym kluczem RSA, jaki rozłożono na czynniki pierwsze, jest klucz 768-bitowy. Liczby pierwsze zostały znalezione 12 grudnia 2009.

Na koniec chciałbym podziękować wszystkim którzy dotrwali do końca :)
To mój pierwszy taki długi wpis, więc spodziewam się że mój styl pisania jest zapewne ubogi, jednak bardzo chętnie przyjmę każdą konstruktywną krytykę

#informatyka #kryptologia #kryptolodzy #ciekawostki #matematyka

[clorox]

@Delfin17: TLDR: "Na koniec chciałbym podziękować wszystkim"...

Czuję się podziękowany.

[foxminator2000]

@Delfin17: nawet ładnie teraz prosimy o ECC - Elliptic Curve Cryptography

[jeronimo_martini]

@Delfin17: Warto wspomnieć, że RSA (i inne szyfry oparte na liczbach pierwszych) jest bezpieczna, ponieważ faktoryzacja liczb jest NP-trudna, ale w przyszłości nie musi to już być aż taki problem (komputery kwantowe mogłyby tu mieć zastosowanie). Wtedy trzeba będzie wpaść na inny pomysł na szyfrowanie danych, bo faktoryzacja liczb użytych do szyfrowania nie będzie zajmować 30 lat a kilka godzin/minut/sekund.

[Delfin17]

@jeronimo_martini: Wszystko zależy od mocy obliczeniowej komputerów ale też od długości klucza. Im dłuższy klucz tym więcej czasu zajmie jego złamanie, a czas potrzebny na złamanie nie rośnie liniowo z długością klucza, tylko raczej wykładniczo. Masz racje, że komputery kwantowe mogą sporo namieszać

[marcello_santi]

@jeronimo_martini: Wydaje mi się, że faktoryzacja nie jest problemem NP-trudnym (choć nie ma żadnego dowodu). Żaden z problemów NP-trudnych nie udaje się rozwiązać w czasie wielomianowym na komputerze kwantowym. Faktoryzacja i dlog już się dają.

[jeronimo_martini]

@marcello_santi: Rzeczywiście, plus już z tego co wiem istnieją szyfrowania na komputery kwantowe. Wydaje mi się że jedyne co mogłoby się zmienić to standardy.