Security: RSA

Liczby używane w szyfrowaniu RSA

W szyfrowaniu RSA ważne są liczby pierwsze, ponieważ algorytm opiera się na faktoryzacji dużych liczb. W celu dobrania liczb do algorytmu RSA wybiera się dwie liczby pierwsze p i q.

Przykładowe liczby:

57: nie jest liczbą pierwszą (57 = 3 × 19).

67: jest liczbą pierwszą.

77: nie jest liczbą pierwszą (77 = 7 × 11).

97: jest liczbą pierwszą.

Funkcja Eulera

Funkcja Eulera to funkcja matematyczna, która dla każdej liczby całkowitej n zwraca liczbę liczb całkowitych dodatnich mniejszych od n, które są względnie pierwsze z n (tj. mają największy wspólny dzielnik równy 1). Funkcja ta jest użyteczna w teorii liczb, szczególnie w kontekście kryptografii, zwłaszcza w algorytmie RSA.

Wzór

Dla liczby pierwszej p:

Dla liczby n będącej iloczynem dwóch różnych liczb pierwszych p i q:

Obliczenia dla 53 i 71

Szyfrowanie i deszyfrowanie w systemie RSA

RSA to jedna z najpopularniejszych metod kryptografii asymetrycznej, która wykorzystuje parę kluczy: publiczny do szyfrowania i prywatny do deszyfrowania.

Klucz RSA

Aby wygenerować klucz RSA, wykonujemy następujące kroki:

Wybór dwóch dużych liczb pierwszych:

Niech i będą dwoma liczbami pierwszymi. Na przykład:

Obliczenie n:

Obliczenie funkcji Eulera :

Wybór wykładnika publicznego :

Wybieramy takie, aby było względnie pierwsze z . Najczęściej wybieranym jest , ale w tym przykładzie weźmiemy .

Można sprawdzić tutaj: https://www.calculatorsoup.com/calculators/math/gcf.php

Obliczenie wykładnika prywatnego :

Musimy znaleźć tak, aby spełniał równanie:

Używając algorytmu rozszerzonego Euklidesa, otrzymujemy d=2753.

Klucze

Klucz publiczny:

Klucz prywatny:

Szyfrowanie

Aby zaszyfrować wiadomość , używamy klucza publicznego :

* Obliczenie szyfrogramu

Na przykład, jeśli :

Obliczenia prowadzą do (po pełnych wyliczeniach).

Deszyfrowanie

Aby odszyfrować szyfrogram , używamy klucza prywatnego :

Obliczenie odszyfrowanej wiadomości

Dla :

Obliczenia prowadzą do .

Flowchart

Program

https://github.com/DavidoTek/rsa-calc-edu

https://wiki.ostrowski.net.pl/php_mysql/rsa/