Kryptografia Asymetryczna (Algorytm RSA)

Kiedy wpisujesz hasło do banku, Twoja przeglądarka musi przesłać je na serwer w taki sposób, aby nikt po drodze nie mógł go przechwycić. Problem polega na tym, że gdyby serwer i komputer używały tego samego klucza do szyfrowania i rozszyfrowywania (szyfrowanie symetryczne), jak miałyby sobie ten klucz najpierw przekazać przez publiczną sieć tak, aby nikt go nie podsłuchał?

Tu wkracza kryptografia asymetryczna z algorytmem RSA na czele. Polega to na tym, że każdy serwer tworzy nie jeden, a dwa klucze:

1. Klucz Publiczny: Wysyłany każdemu (np. Twojej przeglądarce). Służy on tylko i wyłącznie do zamykania kłódki (szyfrowania danych).
2. Klucz Prywatny: Zatrzymywany ściśle w tajemnicy na serwerze. Służy do otwierania tej kłódki.

To, co zaszyfrujesz kluczem publicznym, nie może zostać nim rozszyfrowane! Może to zrobić tylko klucz prywatny.

Matematyka w pigułce

Algorytm opiera się na prostym założeniu: bardzo łatwo jest pomnożyć przez siebie dwie wielkie liczby pierwsze, ale niesamowicie ciężko jest zrobić coś odwrotnego - posiadając jedynie ich gigantyczny wynik z powrotem odgadnąć z jakich liczb powstał (jest to tzw. problem rozkładu na czynniki pierwsze / faktoryzacji).

Generowanie kluczy krok po kroku (w uproszczeniu):

1. Losujesz dwie liczby pierwsze, p i q.
2. Mnożysz je, uzyskując moduł klucza: n = p * q. Ta liczba podawana jest publicznie.
3. Wyliczasz Funkcję Eulera: phi = (p-1) * (q-1). O tym wyniku nie wie nikt!
4. Wybierasz klucz publiczny e (względnie pierwszy z phi).
5. Obliczasz klucz prywatny d, stosując magię modularną, wyliczając tzw. odwrotność z e względem phi.

Samo szyfrowanie to zwykłe potęgowanie. Jeśli chcesz zaszyfrować wiadomość (np. liczbę M), potęgujesz ją przez klucz publiczny: Szyfrogram = (M ^ e) mod n.

Kod - Generowanie małych kluczy

Poniższy kod przedstawia uproszczoną implementację. Skupimy się w niej na ręcznym wyliczaniu Funkcji Eulera i prostej pętli znajdującej pierwszy lepszy klucz publiczny e oraz odpowiadający mu klucz prywatny d.

NWD używane w kodzie do znajdowania wzajemnej pierwszości opisałem w lekcji o Algorytmie Euklidesa.

[!WARNING] Prawdziwy kod kryptograficzny operuje na liczbach mających setki cyfr, dlatego w C++ zjawisko przepełnienia pamięci byłoby natychmiastowe. Poniższe przykłady zadziałają poprawnie tylko dla bardzo małych liczb pierwszych i małych wiadomości.

Python

# Funkcja pomocnicza: Algorytm Euklidesa (NWD)
def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def generuj_klucze_rsa(p, q):
    print(f"Wybrano liczby pierwsze: p={p}, q={q}")
    
    # Krok 1: Wyliczenie modułu 'n' (podawane publicznie)
    n = p * q
    
    # Krok 2: Wyliczenie Funkcji Eulera (ukrywane)
    phi = (p - 1) * (q - 1)
    print(f"Funkcja Eulera phi = {phi}")
    
    # Krok 3: Wybranie klucza publicznego 'e'
    # 'e' musi być większe od 1, mniejsze od phi, oraz wzajemnie pierwsze z phi
    e = 2
    while e < phi:
        if nwd(e, phi) == 1:
            break # Znaleźliśmy odpowiednie 'e'
        e += 1
        
    # Krok 4: Wyliczenie klucza prywatnego 'd'
    # Odwrotność modulo: (e * d) mod phi = 1
    # Dla ułatwienia robimy to tu zwykłą pętlą sprawdzającą
    d = 1
    while True:
        if (d * e) % phi == 1:
            break
        d += 1
        
    print(f"Klucz PUBLICZNY: (e={e}, n={n})")
    print(f"Klucz PRYWATNY: (d={d}, n={n})")
    return (e, n), (d, n)

# --- Testowanie szyfrowania ---
klucz_pub, klucz_priv = generuj_klucze_rsa(11, 13)
e, n = klucz_pub
d, _ = klucz_priv

wiadomosc_M = 7
print(f"\n--- SZYFROWANIE WIADOMOŚCI ({wiadomosc_M}) ---")

# Szyfrujemy podnosząc M do potęgi 'e' modulo 'n'
szyfrogram = (wiadomosc_M ** e) % n
print(f"Zaszyfrowany tekst (C): {szyfrogram}")

# Odszyfrowujemy podnosząc szyfrogram do potęgi 'd' modulo 'n'
odszyfrowana = (szyfrogram ** d) % n
print(f"Odszyfrowana wiadomość (M): {odszyfrowana}")

C++

#include <iostream>
using namespace std;

// Funkcja pomocnicza: Algorytm Euklidesa (NWD)
int nwd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

void generuj_klucze_rsa(int p, int q) {
    cout << "Wybrano liczby pierwsze: p=" << p << ", q=" << q << endl;
    
    // Krok 1: Wyliczenie modułu 'n'
    int n = p * q;
    
    // Krok 2: Wyliczenie Funkcji Eulera
    int phi = (p - 1) * (q - 1);
    cout << "Funkcja Eulera phi = " << phi << endl;
    
    // Krok 3: Wybranie klucza publicznego 'e'
    int e = 2;
    while (e < phi) {
        if (nwd(e, phi) == 1) break;
        e++;
    }
    
    // Krok 4: Wyliczenie klucza prywatnego 'd'
    int d = 1;
    while (true) {
        if ((d * e) % phi == 1) break;
        d++;
    }
    
    cout << "Klucz PUBLICZNY: (e=" << e << ", n=" << n << ")" << endl;
    cout << "Klucz PRYWATNY:  (d=" << d << ", n=" << n << ")" << endl;
}

int main() {
    generuj_klucze_rsa(11, 13);
    
    // Uwaga: Ze względu na przepełnienia typów całkowitych potęgowanie
    // zaszyfrowanych wiadomości w C++ wymaga użycia specjalnego, bezpiecznego
    // mnożenia w pętli. Nie używaj bezpośredniego potęgowania pow()!
    
    return 0;
}