# 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:
1. Wyszukuje **2 liczby pierwsze p1 i p2** (im większe, tym całość działania algorytmu jest bezpieczniejsza)
2. Wymnaża je i zapisuje jako **wartości N**
3. 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