الگوریتم RSA از اولین شیوه های رمزنگاری به روش کلید عمومی (رمزنگاری نامتقارن) است که بصورت گسترده برای تامین امنیت انتقال داده از طریق SSL استفاده می شود.
این روش، نخستین روش مورد اعتماد در بین روش‌های رمزنگاری دیگر است و یکی از بزرگ‌ترین پیشرفت‌ها در زمینهٔ رمزنگاری به حساب می‌آید. آراس‌ای همچنان به صورت گسترده‌ای در تبادلات الکترونیکی استفاده می‌شود و در صورت استفاده درست با کلیدهای طولانی کاملاً امن می باشد.
حروف اولیه RSA، حروف اولیه نام های خانوادگی Ron RIvest ، Adi Shamir و Adleman است که در سال ۱۹۷۷ این الگوریتم را بطور عمومی معرفی کردند. یک ریاضی دان انگلیسی به نام Clifford Cocks، که برای ستاد ارتباطات دولت بریتانیا کار می کرد، سیستمی معادل این سیستم را در سال ۱۹۷۳ پیاده سازی کرده بود، که تا سال ۱۹۷۳ بصورت محرمانه باقی ماند.
روش عملکرد RSA
فرض کنید فرستنده پیام جفت عدد صحیح و بزرگ (e,n) را بعنوان کلید عمومی برای رمزنگاری اطلاعات خود در اختیار دارد. در طرف مقابل ،گیرنده نیز جفت عدد (d,n) را برای رمزگشایی پیام بکار می برد. بدیهی است که دو جفت عدد (e,n) و (d,n) با یکدیگر ارتباط زیرکانه ای دارند ولی بگونه ای نیست که بتوان با در اختیار داشتن e و n براحتی d را استنتاج کرد. با فرض وجود چنین کلید هایی، الگوریتم RSA در نهایت سادگی بصورت زیر است:
- پیامی که باید رمز شود به بلوکهای K کاراکتری (k بایتی) تقسیم بندی می شود.
- هر بلوک طبق قاعده ای کاملا دلخواه به یک عدد صحیح به نام Pi تبدیل می گردد.
- با جفت عدد (e,n) به ازای یکایک بلوکهای Pi اعداد جدیدی طبق رابطه زیر بدست می آیند:
Ci = (Pi )e mod n
- کدهای Ci بجای کدهای اصلی Pi ارسال می شوند.
روش رمزگشایی داده ها دقیقا مثل روش رمزنگاری است یعنی با داشتن جفت عدد (d,n) بلوکهای رمز شده بصورت زیر از رمز خارج می شوند:
Pi = ( Ci )d mod n
در RSA، به جفت عدد (e,n) که متن به کمک آن رمز می شود، اصطلاحا کلید عمومی (public key) و به جفت عدد (d,n) که متن بوسیله آن از رمز در می آید، کلید خصوصی (private key) گفته می شود. نکته اساسی در RSA آن است که جهت تضمین وارون پذیری روش رمز، اعداد بایستی در رابطه زیر صدق کنند لذا باید در انتخاب اعداد دقت کرد:
(x)e.d mod n = x
اصل اساسی دیگری که باید در رمزنگاری RSA حتما رعایت شود آن است که کدهای Pi که به هر بلوک نسبت می دهیم باید در شرط زیر صدق کند:
٠ ≤ Pi< n
بنابراین اگر بلوک ها بصورت رشته های k بیتی مدل شوند، باید شرط ٢K< n برقرار باشد. دلیل این امر آن است که براحتی بتوان گزاره Pi mod n = Pi را نوشت وگرنه در حالت کلی این گزاره درست نمی باشد و در این صورت رمزگشایی صحیح داده ها تضمین نخواهد شد.
بیشتر بدانید:
روش انتخاب e و d که توسط ابداع کنندگان RSA پیشنهاد شده، عبارت است از:
الف) دو عدد دلخواه (اما بزرگ) p و q را انتخاب می شود.
ب) اعداد n و z را طبق دو رابطه زیر محاسبه می گردد:
n = p * q
z = (p-١) * (q-١)
ج) عدد d طوری انتخاب می شود که نسبت به z اول باشد یعنی هیچ عامل مشترکی که هر دو بر آن بخشپذیر باشند یافت نشود.
د) بر اساس d، عدد e طوری انتخاب می شود که رابطه زیر برقرار باشد: (بعبارتی معکوس ضربی d در پیمانه z محاسبه شده و e نامیده می شود.)
( e * d ) mod z = ١
آنچه که مشخص است در کاربردهای عملی، اعداد p و q حداقل صد رقمی (صد رقم در مبنای ده) انتخاب می شوند یعنی این دو عدد حداقل از مرتبه ١٠١٠٠ هستند. در این حالت عدد صحیح متناظر با بلوکهای Pi که طبق شرط فوق باید کمتر از n باشند، نبایستی از ٨٣ کاراکتر بیشتر باشند، زیرا:
p , q ≈ ١٠١٠٠ → n = p * q ≈ ١٠٢٠٠ → (Pi <(٢٦٦٤≈١٠٢٠٠)) → Pi <٢٦٦٤
پس هر بلوک متن بایستی حداکثر ٦٦٤ بیت یا ٨٣ کاراکتر هشت بیتی باشد.
در اینجا توجه به این نکته ظریف لازم است که برای محاسبه Ae mod n لازم نیست که A به تعداد e بار در خودش ضرب و سپس باقیماده اش بر n پیدا شود زیرا با استفاده از برخی خواص ریاضی نتیجه محاسبات هیچگاه از n فراتر نمی رود.
حال فرض کنید یک نفذگر بخواهد با در اختیار داشتن کلید عمومی (e,n)، را بدست آورد. در اینصورت باید در وهله اول n را به دو عامل اول آن یعنی p و q تجزیه کند تا بتواند z را محاسبه کرده و سپس d را بدست آورد. برای تجزیه اعداد به عوامل اول آن هیچ راهی بجز جستجو و آزمون وجود ندارد و با توجه به این که n حداقل دویست رقمی است، تجزیه چنین اعدادی حتی به کمک کامپیوتر هزاران سال طول خواهد کشید.
اگر چه تحقیق بر روی مسئله تجزیه اعداد بزرگ به عوامل آن هنوز ادامه دارد اما هنوز الگوریتم کارآمدی که بتواند اعداد بزرگ را با هر طولی در زمان ثابت یا در حد متعارف کوچکی به عوامل اول آن تجزیه کند، یافت نشده است، لذا با گذشت ٣٠ سال از معرفی RSA هنوز از شان آن کاسته نشده است بلکه فقط کلیدها به جهت محکم کاری بزرگتر شده اند.
از آنجا که اعداد اول هیچ نظم شناخته شده ای ندارند لذا انتخاب اعداد اول بسیار بزرگ p و q یکی از چالش های بزرگ RSA است زیرا برای اثبات اول بودن عددی مثل p باید محدوده اعدادکمتر یا مساوی p √ بررسی و بخش ناپذیری p بر آنها مطالعه گردد که هرچه p بزرگتر باشد محدوده جستجوی p √ بزرگتر خواهد بود. برای مثال محدوده جستجوی عددی ٥١٢ بیتی از مرتبه ٢٢٥٦ می شود که جستجوی چنین فضایی عملا غیر ممکن است. بنابراین تنها راه چاره استفاده از یکسری از قضایای ریاضی است که به ما کمک می کنند محدوده جستجو را کوچکتر نموده و مراحل حدس زدن کمتر شود.
