آراس‌ای

در بحث رمزنگاری، آراس‌اِی (RSA) شیوه‌ای برای رمزنگاری به روش کلید عمومی (Public Key) است. این روش نخستین روش مورد اعتماد در بین روش‌های رمزنگاری دیگر است و یکی از بزرگ‌ترین پیشرفت‌ها در زمینهٔ رمزنگاری به حساب می‌آید. آراس‌ای همچنان به صورت وسیعی در تبادلات الکترونیکی استفاده می‌شود و در صورت استفاده درست با کلیدهای طولانی کاملاً امن به نظر می‌رسد.

تاریخچه

این روش نخستین بار در سال ۱۹۷۷ توسط رونالد ریوست، آدی شامیر و لئونارد آدلمن در دانشگاه ام آی تی مطرح شد. اصطلاح آراس‌آ نیز از حروف ابتدای نام فامیل آنها گرفته شده است. دانشگاه ام‌آی‌تی حق اختراع این روش را به نام خود ثبت کرد. این حق اختراع در ۲۱ سپتامبر سال ۲۰۰۰ میلادی منقضی شد.

توضیحات کارکرد

کلیات

آراس‌ای به طور کلی از دو کلید تشکیل می‌شود. کلید عمومی و کلید خصوصی. کلید عددی ثابت است که در محاسبات رمزنگاری استفاده می‌شود. کلید عمومی برای همه معلوم بوده و برای رمز کردن پیام استفاده می‌شود. این پیام فقط توسط کلید خصوصی باز می‌شود. به عبارتی دیگر همه می‌توانند یک پیام را رمز کنند اما فقط صاحب کلید خصوصی می‌تواند پیام را باز کند و بخواند.

تولید کلید

مراحل زیر برای تولید کلید طی می‌شود:

1. دو عدد اول بزرگ p و q را به صورت تصادفی بیابید به طوری کهp ≠ q.
2. عدد n را محاسبه کنید به طوری که n = p*q.
3. تابع فی را محاسبه کنید به طوری که (φ(n) = (p-1)*(q-1
4. عدد e را انتخاب کنید به طوری که بین ۱ و (φ(n باشد و نسبت به (φ(n اول باشد
   • عدد e به عنوان توان کلید عمومی منتشر می‌شود.
5. عدد d را طوری بیابید که باقی‌مانده ضرب دو عدد d و e نسبت به (φ(n برابر ۱ باشد،
   • عدد d به عنوان توان کلید خصوصی محافظت می‌شود.

• دو عدد اول می‌توانند توسط روش پیدا کردن اعداد اول احتمالی پیدا شوند.
• معمولاً عدد عمومی (e) را در حدود ۲^۱۶ انتخاب می‌کنند. البته بعضی از برنامه‌ها اعداد کوچکی را انتخاب می‌کنند که باعث سریعتر شدن و البته خطرات امنیتی در رمزنگاری می‌شود.
• کلید عمومی تشکیل می‌شود از:
  • عدد n (عدد مشترک)
  • عدد e (عدد عمومی)
• کلید خصوصی تشکیل می‌شود از:
  • عدد n (عدد مشترک)
  • عدد d (عدد خصوصی)

• در تمام مراحل باید اجزای کلید خصوصی سری نگه داشته شود، دو عدد p و q اگر به عنوان صورتی از کلید خصوصی نگهداری نشود بهتر است به شیوه‌ای امن نابود شوند. زیرا با این دو عدد تمام اعداد n و d, e قابل محاسبه خواهند بود.

رمز کردن پیام

فرض کنید می‌خواهید پیامی را رمزنگاری کرده و به فردی دیگر بفرستید. شما می‌بایست کلید عمومی آن فرد را از او دریافت کرده و پیام خود را در قالب یک عدد (m) در بیاورید به طوری که این فرایند برگشت‌پذیر بوده و عدد شما از n کوچک‌تر باشد. بدیهی است اگر پیام بزرگ‌تر از حد معمول باشد آن را در بسته‌های جداگانه می‌فرستیم. شما اکنون عدد C را محاسبه می‌کنید به طوری که c = m^e mod n حال اگر پیام رمزنگاری شدهٔ C را برای فرد مذکور بفرستید او می‌تواند توسط کلید خصوصی اش آن را رمز گشایی کند و بفهمد.

باز کردن پیام

فرض کنید شما پیام رمز نگاری شدهٔ C را دریافت کرده‌اید و کلید خصوصی خود را در دسترس دارید. حال شما می‌توانید عدد m را که معادل پیام اصلی است از C،n،d بازیابی کنید. m = c^d mod n

مثال

1. انتخاب دو عدد اول مثلا p=3 , q=5
2. عدد n را محاسبه می‌کنیم ۱۵ = ۳*۵ = n = p*q.
3. تابع فی را محاسبه مي‌کنیم ۸ = ۲ * ۴ = (۱-۵)*(۱-۳)= (φ(n) = (p-1)*(q-1
4. عدد e را انتخاب کنید به طوری که بین ۱ و (φ(n یعنی ۸ باشد و نسبت به آن اول باشد. ۳و۵و۷ قابل انتخاب هستند که ۵ را در این مثال انتخاب می‌کنیم.
5. عدد d را طوری بیابید که باقی‌مانده ضرب دو عدد d و e یعنی ۷d نسبت به (φ(n یعنی ۸ برابر ۱ باشد، که ۷ کوچک ترین انتخاب برای d هست.
6. با توجه به c = m^e mod n رمزنگاری ما به این صورت انجام می‌شود: c = m^۵ mod ۱۵
7. با توجه به m = c^d mod n رمزنگاری ما به این صورت انجام می‌شود: m = c^۷ mod ۱۵

منابع

ویکیپدیای فارسی

• R. Rivest، A. Shamir، L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM، Vol. ۲۱ (۲)، pp.۱۲۰–۱۲۶. ۱۹۷۸. Previously released as an MIT "Technical Memo" in April ۱۹۷۷. انتشار اولیه روش رمز نگاری آر اس ای.
• توماس اچ کورمن، Charles E. Leiserson، رونالد ریوست، and کلیفورد استین. مقدمه‌ای بر الگوریتم‌ها، Second Edition. MIT Press and McGraw-Hill، ۲۰۰۱. ISBN ۰-۲۶۲-۰۳۲۹۳-۷. Section ۳۱٫۷: The RSA public-key cryptosystem، pp.۸۸۱–۸۸۷.