RSA (Rivest–Shamir–Adleman) is a public-key Cryptosystem:
الگوریتم RSA یک رمزنگاری اساسی در علم رمزنگاری است که بر اساس مسائل ریاضی در زمینه نظریه اعداد مبنی بر محاسبههای پیچیده مانند فاکتوریزاسیون اعداد بزرگ اعداد صحیح است. در این روش، دو کلید استفاده میشود:
یک کلید عمومی (Public Key) برای رمزنگاری اطلاعات و یک کلید خصوصی (Private Key) برای رمزگشایی اطلاعات.
برای تولید کلیدها، ابتدا دو عدد اول بزرگ انتخاب میشوند (به عنوان مثال p و q) و حاصلضرب آنها را به عنوان n میگیریم. سپس عددی کوچکتر از (p-1) * (q-1) به عنوان عدد e (عدد عمومی) انتخاب میشود که با n ارتباط اولیه داشته باشد و از طریق الگوریتم اویلر (Euler's Totient Function) محاسبه میشود.
سپس عددی به نام d به طوری انتخاب میشود که (e * d) را در مقسوم عدد (p-1) * (q-1) برابر با 1 باقی میگذارد (در واقع معکوس مدولار e نسبت به (p-1) * (q-1) را محاسبه میکنیم). حالا کلید عمومی به صورت (n، e) و کلید خصوصی به صورت (n، d) تشکیل میشود.
برای رمزنگاری، فرستنده اطلاعات خود را با کلید عمومی (n، e) رمزگذاری میکند و دریافتکننده میتواند اطلاعات را با کلید خصوصی (n، d) رمزگشایی کند.
مهمترین ویژگی RSA این است که فاکتوریزه کردن عدد n به دو عدد اول p و q در زمان معقولی برای اعداد بزرگ و با توجه به فرآیند زمانبر آن، بسیار سخت است. این ویژگی باعث میشود که امنیت الگوریتم RSA به بزرگی اعداد انتخاب شده وابسته باشد.