Доказ правильності RSA базується на Маленька теорема Ферма, зазначивши, що астор − 1 ≡ 1 (mod p) для будь-якого цілого числа a та простого p, що не ділить a. для кожного цілого числа m, коли p і q — різні прості числа, а e і d — натуральні числа, що задовольняють ed ≡ 1 (mod λ(pq)).
RSA використовує пару закритого та відкритого ключів. Приватний ключ зберігається в таємниці та відомий лише автору пари ключів, тоді як відкритий ключ доступний будь-кому. Для шифрування можна використовувати відкритий або закритий ключ, а для розшифровки – інший ключ.
У RSA ми маємо два великих простих числа p і q, модуль N = pq, показник шифрування e і показник дешифрування d, які задовольняють ed = 1 mod (p – 1)(q – 1). Відкритий ключ — це пара (N,e), а закритий — d. C = Я мод N.
Криптосистема RSA складається з трьох кроків: Генерація ключа: кожен користувач u генерує два прості числа p,q, обчислює n=pq і φ(n)=(p−1)(q−1), вибирає випадкове e (яке має бути взаємно простим до φ(n)) і обчислює d=e−1(modφ(n)). Користувач публікує відкритий ключ pubu=(n,e) і зберігає для себе закритий ключ priu=d.
Теорема Ейлера лежить в основі криптосистеми RSA, яка широко використовується в Інтернет-комунікаціях. У цій криптосистемі використовується теорема Ейлера n є добутком двох великих простих чисел, а безпека системи базується на складності розкладання такого цілого числа на множники.
RSA є тип асиметричного шифрування, який використовує два різні, але пов’язані ключі. У криптографії RSA як відкритий, так і закритий ключі можуть шифрувати повідомлення. Ключ, протилежний тому, який використовується для шифрування повідомлення, використовується для його розшифровки.