Algorytm RSA

1. Wprowadzenie do RSA

RSA (Rivest-Shamir-Adleman) to jeden z najważniejszych algorytmów kryptografii asymetrycznej. Jest szeroko stosowany w zabezpieczaniu danych, podpisach cyfrowych oraz w komunikacji internetowej. Jego siła opiera się na trudności faktoryzacji dużych liczb na czynniki pierwsze.

Kryptografia symetryczna vs asymetryczna:

• Kryptografia symetryczna: Ten sam klucz jest używany zarówno do szyfrowania, jak i deszyfrowania wiadomości. Jest szybka, ale wymaga bezpiecznego przekazania klucza.
• Kryptografia asymetryczna: Używa pary kluczy – klucza publicznego do szyfrowania i klucza prywatnego do deszyfrowania. Choć jest wolniejsza, eliminuje problem bezpiecznego przekazywania klucza.

Krótka historia RSA: Algorytm RSA został opracowany w 1977 roku przez Ronalda Rivesta, Adiego Shamira i Leonarda Adlemana na Uniwersytecie MIT. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców. Od tamtej pory RSA stało się fundamentem współczesnej kryptografii.

2. Podstawowe pojęcia RSA

• Klucz publiczny (e, n): Używany do szyfrowania wiadomości.
• Klucz prywatny (d, n): Używany do deszyfrowania wiadomości.
• Moduł n: Iloczyn dwóch dużych liczb pierwszych.
• Funkcja Eulera (phi): Ważna funkcja matematyczna w procesie generowania kluczy.

3. Generowanie kluczy RSA

1. Wybierz dwie liczby pierwsze (p i q)
   • Przykład: p = 61, q = 53
2. Oblicz n

   •    

3. Oblicz funkcję Eulera
4. Wybierz klucz publiczny (e)
   • e musi być względnie pierwsze z
   • Przykład: e = 17
5. Oblicz klucz prywatny (d)
   • Rozwiąż równanie:
   • Przykład: d = 2753

Klucz publiczny: (17, 3233)
Klucz prywatny: (2753, 3233)

Bezpieczeństwo kluczy RSA:

• Dla zapewnienia odpowiedniego poziomu bezpieczeństwa zaleca się obecnie używanie kluczy o długości co najmniej 2048 bitów.
• Długość klucza wpływa bezpośrednio na poziom bezpieczeństwa, ale także na wydajność algorytmu.
• Dla zastosowań wymagających wysokiego poziomu bezpieczeństwa, jak podpisy cyfrowe w instytucjach finansowych, zalecane są klucze o długości 4096 bitów.
• Starsze klucze o długości 1024 bitów są obecnie uznawane za niewystarczająco bezpieczne.

4. Szyfrowanie wiadomości

Każda wiadomość jest zamieniana na liczbę całkowitą (M), gdzie M < n. Następnie stosuje się wzór:

Przykład:

• Wiadomość: M = 123

•    

Bardziej zaawansowany przykład:

• Wiadomość: M = 350

•    

5. Deszyfrowanie wiadomości

Do odszyfrowania wiadomości używamy klucza prywatnego (d):

Przykład:

•    

•    

6. Podpis cyfrowy RSA

RSA pozwala również na podpisywanie wiadomości:

1. Tworzenie podpisu przez nadawcę:

• Nadawca tworzy skrót wiadomości (hash) za pomocą algorytmu skrótu (np. SHA-256).
• Następnie szyfruje ten skrót swoim kluczem prywatnym RSA.
• Wynik tego procesu to podpis cyfrowy, który jest dołączany do wiadomości

2. Weryfikacja podpisu przez odbiorcę:

• Odbiorca otrzymuje wiadomość oraz podpis cyfrowy.
• Za pomocą klucza publicznego nadawcy RSA odszyfrowuje podpis cyfrowy i uzyskuje oryginalny skrót wiadomości.
• Następnie samodzielnie generuje skrót otrzymanej wiadomości.
• Porównuje uzyskane skróty.

Praktyczny przykład podpisu cyfrowego RSA: Wyobraźmy sobie scenariusz podpisywania wiadomości e-mail:

• Nadawca tworzy podpis cyfrowy wiadomości za pomocą swojego klucza prywatnego.
• Wiadomość oraz podpis cyfrowy są wysyłane do odbiorcy.
• Odbiorca używa klucza publicznego nadawcy, aby zweryfikować autentyczność wiadomości.
• Jeśli podpis jest prawidłowy, odbiorca ma pewność, że wiadomość pochodzi od właściwego nadawcy i nie została zmodyfikowana.

7. Zalety RSA

• Bezpieczeństwo dzięki trudności faktoryzacji.
• Możliwość szyfrowania i podpisywania wiadomości.
• Powszechne zastosowanie w Internecie.

8. Wady RSA

• Wysokie wymagania obliczeniowe.
• Powolność w porównaniu do kryptografii symetrycznej.
• Wrażliwość na ataki z wykorzystaniem komputerów kwantowych.

Alternatywy dla RSA:

• ECC (Elliptic Curve Cryptography): Algorytm oparty na matematyce krzywych eliptycznych. Zapewnia podobny poziom bezpieczeństwa jak RSA, ale przy znacznie krótszych kluczach, co przekłada się na większą wydajność.
• Algorytm Diffie-Hellmana: Popularny do bezpiecznej wymiany kluczy kryptograficznych.
• Post-Quantum Cryptography: Nowa generacja algorytmów odpornych na ataki kwantowe, takich jak algorytm Crystals-Kyber.
• Wysokie wymagania obliczeniowe.
• Powolność w porównaniu do kryptografii symetrycznej.
• Wrażliwość na ataki z wykorzystaniem komputerów kwantowych.

9. Praktyczne zastosowania RSA

Algorytm ten odgrywa kluczową rolę w protokole TLS/SSL (Transport Layer Security / Secure Sockets Layer), który jest podstawą zabezpieczonych połączeń internetowych. W praktyce:

• Ustanawianie bezpiecznego połączenia: Algorytm jest używay podczas nawiązywania sesji TLS/SSL do wymiany kluczy symetrycznych.
• Proces handshake: Podczas początkowego etapu komunikacji serwer przesyła swój klucz publiczny do klienta. Klient używa tego klucza do zaszyfrowania klucza sesyjnego.
• Deszyfrowanie po stronie serwera: Serwer używa swojego klucza prywatnego do odszyfrowania klucza sesyjnego.
• Szyfrowanie danych: Po ustanowieniu bezpiecznego klucza sesyjnego dane są szyfrowane przy użyciu szybszego algorytmu symetrycznego (np. AES).

Dzięki RSA, protokół TLS/SSL zapewnia poufność, autentyczność i integralność przesyłanych danych, co jest fundamentem bezpiecznego przeglądania stron internetowych, realizacji transakcji online i ochrony wrażliwych informacji.

• Protokół HTTPS.
• Bezpieczne logowanie.
• Podpisy cyfrowe.
• Kryptowaluty.
• Blockchain.
• Internet Rzeczy (IoT).

10. Podsumowanie

RSA pozostaje jednym z najważniejszych algorytmów kryptografii asymetrycznej, mimo wyzwań ze strony komputerów kwantowych. Rozwój technologii kwantowych stanowi istotne zagrożenie dla bezpieczeństwa RSA, ponieważ algorytmy takie jak algorytm Shora mogą skutecznie rozłożyć duże liczby na czynniki pierwsze, co osłabia fundamenty bezpieczeństwa.

Algorytmy postkwantowe: W odpowiedzi na to zagrożenie trwają prace nad algorytmami kryptograficznymi odpornymi na ataki kwantowe. Przykłady obejmują:

• Crystals-Kyber: Algorytm klucza publicznego oparty na kratownicach.
• Crystals-Dilithium: Schemat podpisu cyfrowego.
• Falcon: Efektywny schemat podpisu cyfrowego.

Przyszłość kryptografii prawdopodobnie będzie oparta na algorytmach hybrydowych, łączących tradycyjne metody, takie jak RSA, z nowoczesnymi technologiami odpornymi na komputery kwantowe. RSA pozostaje jednym z najważniejszych algorytmów kryptografii asymetrycznej, mimo wyzwań ze strony komputerów kwantowych.

Przykład kodu RSA w Pythonie

# Generowanie kluczy RSA
from Crypto.PublicKey import RSA

# Tworzenie kluczy
key = RSA.generate(2048)
private_key = key.export_key()
public_key = key.publickey().export_key()

print("Klucz prywatny:")
print(private_key.decode('utf-8'))

print("Klucz publiczny:")
print(public_key.decode('utf-8'))

Zapraszam na stronę główną