باز کردن منو اصلی

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

تاریخچهویرایش

در سال ۱۹۷۶ (میلادی) وایتفیلد دیف (Whitfield Diffie) و مارتین هلمن (Martin Hellman) دانشجویان دانشگاه استنفورد یکی از کاربردی‌ترین روش‌های رمزنگاری اطلاعات را اختراع و به ثبت رساندند. در این روش که به روش رمزنگاری نامتقارن (asymmetric encryption) نیز شناخته می‌شود از دو کلید برای رمزنگاری اطلاعات استفاده می‌کند. در روش‌های قدیمی‌تر از یک کلید استفاده می‌شد که به آن رمزنگاری متقارن (symmetric encryption) گفته می‌شد. آن‌ها مقاله خود را با نام Transactions on Information Theory در یکی از شماره‌های سال ۱۹۷۶ مجله مؤسسه مهندسان برق و الکترونیک (IEEE) منتشر کردند که خیلی زود انقلابی در صنعت رمزنگاری در جهان به وجود آورد. رمزنگاری به روش کلید عمومی به معنی استفاده از کلید عمومی برای رمزنگاری و پنهان کردن اطلاعات است. در این روش هر کاربر برای رمزنگاری یا باز کردن رمز، دو کلید، یکی کلید عمومی (Public) و یکی کلید خصوصی (Private) در اختیار دارد. ویژگی این روش آن است که هر کدام از این کلیدها می‌توانند اطلاعاتی را که کلید دیگر رمزنگاری کرده‌است رمزگشایی کند.

الگوریتم RSA پس از آنکه رونالد ریوست، ادی شامیر، و لئونارد آدلمن در سال ۱۹۷۷ (میلادی) آنرا پایه‌گذاری به این نام شناخته شد. هرچند روش‌های اولیه آن پیشتر در سال ۱۹۷۳ (میلادی) توسط فردی به نام کلیفورد کاکس بدست آمده بود اما تا سال ۱۹۷۷ اولاً الگورتیم رمزنگاری او کاملاً محرمانه بود و دوم اینکه به سادگی آنچه در سال ۱۹۷۶ مطرح شد نبود.

در همان سال ۱۹۷۷ مؤسسه فناوری ماساچوست (اِم‌آی‌تی) حق اختراع روش RSA را به نام خود ثبت کرد. این حق اختراع در ۲۱ سپتامبر ۲۰۰۰ منقضی شد.

چگونگی کارکردویرایش

کلیاتویرایش

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

هر چند از لحاظ ریاضی کلیدهای عمومی و خصوصی با یکدیگر ارتباط دارند اما تقریباً محال است که کسی بتواند حتی با تجیهزات پیشرفته و صرف وقت زیاد با داشتن یکی از کلیدها، دیگری را تشخیص دهد. در واقع می‌توان گفت که با توجه به سطح دانش کنونی و سامانه‌های رایانه‌ای موجود، الگوریتم رمزنگاری و ارتباط میان کلیدها تقریباً غیرقابل شکستن است.

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

ساخت کلیدویرایش

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

  1. دو عدد اول بزرگ   و   را به صورت تصادفی بیابید به‌طوری‌که  .
  2. عدد n را محاسبه کنید به‌طوری‌که  .
  3. تابع فی را محاسبه کنید به‌طوری‌که  
  4. عدد   را انتخاب کنید به‌طوری‌که   و نسبت به   اول باشد.
    • عدد   به عنوان توان کلید عمومی منتشر می‌شود.
  5. عدد   را طوری بیابید که   (باقی‌مانده ضرب دو عدد   و   نسبت به   برابر ۱ باشد به صورت:   به ازای kهای طبیعی)
    • عدد   به عنوان توان کلید خصوصی محافظت می‌شود.
  • دو عدد اول می‌توانند توسط روش پیدا کردن اعداد اول احتمالی پیدا شوند.
  • معمولاً عدد عمومی (e) را در حدود ۲۱۶ انتخاب می‌کنند. البته بعضی از برنامه‌ها اعداد کوچکی را انتخاب می‌کنند که باعث سریعتر شدن و البته خطرات امنیتی در رمزنگاری می‌شود.
  • کلید عمومی تشکیل می‌شود از:
    • عدد n (عدد مشترک)
    • عدد e (عدد عمومی)
  • کلید خصوصی تشکیل می‌شود از:
    • عدد n (عدد مشترک)
    • عدد d (عدد خصوصی)
  • کلید خصوصی به صورت‌های دیگری غیر از   ممکن است نگهداری شود.
    •   و  : اعداد اول برای ساختن کلید.
    •   و  ،
    •  .
  • در تمام مراحل باید اجزای کلید خصوصی سری نگه داشته شود، دو عدد   و   اگر به عنوان صورتی از کلید خصوصی نگهداری نشود بهتر است به شیوه‌ای امن نابود شوند. زیرا با این دو عدد تمام اعداد   و  ،   قابل محاسبه خواهند بود.

رمزنگاری پیامویرایش

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

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

باز کردن پیامویرایش

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

 

نمونهویرایش

  1. انتخاب دو عدد اول مانند:
      and  
  2. محاسبه n = pq:
     
  3. محاسبه تابع فی اویلر با ساخت φ(n) = (p − 1)(q − 1) خواهدشد:
     
  4. انتخاب هر عددی   که نسبت به ۳۱۲۰ اول باشد.
      در نظر می‌گیریم
  5. محاسبه d, the وارون ضربی (هم‌نهشتی) e (mod φ(n)) ,
     
     
     

کلید عمومی (n = 3233, e = ۱۷) برای پیام m هست. بنابران تابع رمز به صورت زیر است:

 

کلید خصوصی (d = ۲۷۵۳) هست. برای متن رمز c تابع رمزگشایی به صورت زیر خواهد بود:

 

برای نمونه در رمزگشایی m = ۶۵, را حساب می‌کنیم.

 

برای رمزگشایی c = ۲۷۹۰ را حساب می‌کنیم.

 

نمونه دیگرویرایش

● تهیه کلیدهای عمومی و خصوصی به‌طور خلاصه روش کار برای تهیه کلیدها به شرح زیر است: ۱- دو عدد بزرگ (هر چه بزرگتر بهتر) اول به نام‌های p و q را انتخاب می‌کنیم، بهتر است این اعداد از لحاظ سایز نزدیک به یکدیگر باشند. ۲- عدد دیگری به نام n را معادل با حاصلضرب p در q تعریف می‌کنیم: n = p x q ۳- عدد چهارم یعنی m را معادل حاصلضرب p-۱ در q-۱ تعریف می‌کنیم: (m = (p-۱) x (q-۱ ۴- عدد e را که از m کوچکتر است آنگونه پیدا می‌کنیم که بزرگترین مقسوم علیه مشترک این دو یک باشد به عبارتی نسبت به هم اول باشند. ۵- عددی مانند d را پیدا کنید که باقی‌مانده حاصلضرب d در e تقسیم بر m مساوی عدد ۱ باشد، یعنی: d x e) mod m = ۱) حال پس از طی این مراحل شما می‌توانید از e و n به عنوان کلید عمومی و از d و n به عنوان کلید اختصاصی استفاده کنید.

● روش پنهان کردن و آشکار کردن برای رمزنگاری اطلاعات کافی است عدد منتصب به هر کاراکتر - مثلاً ASCII - را که در اینجا M می‌نامیم در فرمول زیر قرار دهید و به جای ارسال آن عدد C = M^e mod n را ارسال کنید. در واقع دراینجا شما توانسته‌اید با کمک کلید عمومی، کاراکتر M را به C تبدیل کنید. حال گیرنده برای آشکارسازی کافی است عدد دریافتی یعنی C را با استفاده از کلید خصوصی به M تبدیل کند. برای اینکار کافی است از این فرمول استفاده کنید: M = C^d mod n، بنابراین شما با دریافت کاراکتر کد شده C و در دست داشتن کلید خصوصی توانسته‌اید کاراکتر اصلی را مشخص نمایید. در اینجا به عنوان نمونه نمونهی از نحوه تعریف کلیدهای عمومی و خصوصی خواهیم آورد. اما برای سادگی محاسبات از اختیار کردن اعداد بزرگ دوری خواهیم کرد و توجه شما را به این نکته جلب می‌کنیم که هرچقدر اعداد اولیه بزرگتر باشند احتمال شکستن رمز در مدت زمان محدود ناچیزتر می‌شود. ۱- ابتدا باید دو عدد اول بزرگ انتخاب کنیم که در اینجا از اعداد ساده و هم اندازه‌ای مانند ۱۱ و ۳ استفاده می‌کنیم. پس p=۱۱ , q=۳ ۲- حاصلضرب p در q که همان n است را به اینصورت خواهیم داشت: n = ۱۱ x ۳ = ۳۳ ۳- حاصلضرب p-۱ در q-۱ که همان m است را به اینصورت خواهیم داشت: m = ۱۰ x ۲ = ۲۰ ۴- برای انتخاب عدد e که نسبت به m=۲۰ اول باشد و کمتر از آن هم باشد ساده‌ترین گزینه یعنی عدد ۳ را انتخاب می‌کنیم. ۵- برای یافتن عدد d که در رابطه d x e) mod m = ۱) صادق باشد اعداد ۱٬۲,۳٬۴,۵ و... را امتحان می‌کنیم، بنظر می‌رسد که عدد ۷ برای اینکار مناسب باشد چرا که ۷x۳=۲۱ باقی‌مانده‌ای معادل ۱ بر m=۲۰ دارد. حال می‌توانیم از زوج (۳۳٬۳) به عنوان کلید عمومی و از زوج (۳۳٬۷) به عنوان کلید خصوصی استفاده کنیم. حال اگر از فرمول‌هایی که در مطلب قبل برای رمزنگاری و آشکارسازی استفاده کنیم برای اعداد ۱ تا ۱۶۳۲ به جدول زیر خواهیم رسید. m: ۰ ۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ c: ۰ ۱ ۸ ۲۷ ۳۱ ۲۶ ۱۸ ۱۳ ۱۷ ۳ ۱۰ ۱۱ ۱۲ ۱۹ ۵ ۹ ۴ m: ۱۷ ۱۸ ۱۹ ۲۰ ۲۱ ۲۲ ۲۳ ۲۴ ۲۵ ۲۶ ۲۷ ۲۸ ۲۹ ۳۰ ۳۱ ۳۲ c: ۲۹ ۲۴ ۲۸ ۱۴ ۲۱ ۲۲ ۲۳ ۳۰ ۱۶ ۲۰ ۱۵ ۷ ۲ ۶ ۲۵ ۳۲ بنابراین هم‌اکنون شما یک جدول تبدیل کد دارید که با کمک کلید عمومی اعداد صفر تا ۳۲ را به اعدادی کد شده و در همین رنج تبدیل کرده‌اید. اما اگر دقت کنید تعدادی از اعداد دقیقاً به همان عدد خود تبدیل شده‌اند که به این‌ها unconcealed یا مخفی نشده گفته می‌شود. اولآ باید بدانیم که ۰ و ۱ همواره به همین اعداد تبدیل می‌شوند و مطلب دیگر اینکه اگر رنج دو عدد اول ابتدایی را بزرگ در نظر بگیریم دیگر مشکلی پیش نخواهد آمد. حال کافی است فرض کنیم A=۲، B=۳، C=۴ و... Z=۲۷ و جملات مربوطه را کد نماییم. دقت کنید که معمولاً از ۰ و ۱ برای رمزنگاری استفاده نمی‌شود.

اجزای سامانه رمزنگاریویرایش

  • کلید رمزنگاری
  • الگوریتم رمزنگاری
  • کلید رمزگشایی
  • الگوریتم رمزگشایی
  • اگر از یک کلید برای رمزنگاری و رمزگشایی استفاده شود سامانه رمزنگاری متقارن است و در غیر اینصورت، نامتقارن خواهد بود.

انواع روش‌های رمزنگاری مبتنی بر کلیدویرایش

الگوریتم‌های کلید متقارن:

رمزنگاری و رمزگشایی با یک کلید انجام می‌گیرد.

الگوریتم‌های کلید نامتقارن (کلید عمومی):

هر فرد یک کلید عمومی و یک کلید خصوصی دارد.

دفی هلمن و RSA نمونه‌ای از این الگوریتم‌ها است.

کاربرد در امضای دیجیتال.

کلیدهای این نوع از الگوریتم‌ها (نامتقارن) بسیار طولانی‌تر از الگوریتم‌های مرسوم (کلید متقارن) هستند.

شکستن الگوریتمویرایش

واقعیت آن است که همه روش‌های رمزنگاری قابل شکستن است، اما نکته مهم آن است که در چه مدت زمان و با چه امکاناتی این اطلاعات باید رمزگشایی شوند. در ارتباط با الگوریتم RSA باید گفت روش‌های محدودی برای شکستن متن رمزنگاری شده توسط آن وجود دارد که در اینجا به مواردی از آن اشاره می‌کنیم.

تجزیه n به عوامل اولویرایش

نخستین روش، آن است که بتوان کلید خصوصی را حدس زد یا پیدا کرد. در این صورت رخنه‌گر می‌تواند همه متن‌های تهیه شده با کلید عمومی را رمزگشایی کند و بخواند یا می‌تواند از امضای الکترونیک صاحب کلید استفاده کند. فرض بر این است که فردی که قصد حدس زدن کلید خصوصی را دارد، از جمله افرادی است که کلید عمومی را دارا است. در این حالت او n و e را در دسترس دارد.

روش مؤثر برای محاسبه ریشه e امویرایش

برای باز کردن رمز پیام‌هایی که با الگوریتم RSA رمزنگاری شده‌اند روش‌های محاسبه ریاضی عملاً راه به جایی نمی‌برند و در مواردی که متن کوچک باشد شاید حدس زدن متن اصلی ساده‌ترین روش برای رمزگشایی باشد.

راه‌های مقابله با حمله زمانی به RSAویرایش

استفاده از به توان رساندن با زمان ثابت محاسباتی.

تابع باید به ازای همه ورودی‌ها زمان ثابتی به طول بینجامد

قرار دادن اعمال اضافی و گمراه‌کننده در بین محاسبات

ضرب کردن متن رمزنگاری شده در یک عدد تصادفی قبل از عملیات به توان رسانی

اضافه کردن تاخیرهای تصادفی

پانویسویرایش

منابعویرایش