الگوریتم آراس‌ای

توضیحات بیشتر در مورد الگوریتم آراس‌ای در زیر آمده‌است:
در سال ۱۹۷۶ وایتفیلد دیف (Whitfield Diffie) و مارتین هلمن (Martin Hellman) دانشجویان دانشگاه استنفورد، یکی از کاربردی‌ترین روش‌های کد کردن اطلاعات را اختراع و به ثبت رساندند. در این روش که به روش کدینگ نا متقارن (asymmetric encryption) نیز معروف است از دو کلید برای کد کردن اطلاعات استفاده می‌شود. (در روش‌های قدیمی‌تر از یک کلید استفاده می‌شد که به آن symmetric encryption گفته می‌شد.) آن‌ها مقاله خود را در یکی از شماره‌های سال ۱۹۷۶ مجله IEEE که با عنوان Transactions on Information Theory منتشر شده بود به چاپ رساندند که خیلی زود انقلابی در صنعت Cryptography (پنهان‌سازی اطلاعات) در دنیا بوجود آورد. Public Key Cryptography یا PKC به معنی استفاده از کلید عمومی برای کد کردن و پنهان کردن اطلاعات است. در این روش هر کاربر برای کد کردن یا باز کردن کد دو کلید در اختیار دارد، یکی کلید عمومی (Public) و یکی کلید خصوصی (Private). خاصیت این روش آن است که هر کدام از این کلیدها می‌تواند اطلاعاتی را که کلید دیگر کد و مخفی کرده‌است به حالت اصل در بیاورند.
هر چند از لحاظ ریاضی کلیدهای Public و Private با یکدیگر ارتباط دارند اما تقریبا محال است که کسی بتواند حتی با تجیهزات فوق العاده مدرن و صرف وقت زیاد با داشتن یکی از کلیدها، دیگری را تشخیص دهد. در واقع می‌توان گفت که با توجه به سطح دانش کنونی و دستگاه‌های کامپیوتری موجود، الگوریتم کدینگ و ارتباط میان کلیدها تقریبا غیر قابل شکستن است. روش کار اینگونه‌است که هر کاربر دو کلید در دست خود دارد که یکی را در اختیار همه دوستان و اطرافیان برای خواند مطالبی که او کد کرده‌است قرار می‌دهد، این همان کلید عمومی یا Public است. حال کافی است که او برای ارسال مطالب به دیگران مطالب را با کلید خصوصی خود کد یا مخفی‌سازی نماید. دیگران به راحتی می‌توانند مطالب او را با کلید Public ای که از وی دارند با حالت اولیه بازگردانند (Decrypt) و آن‌ها را مطالعه کنند. یا اگر کسی بخواهد برای شما یک مطلب کد شده بفرستد با کلید Public شما آن را کد می‌کند و این تنها شما و فقط شما هستنید که می‌توانید آن را با کلید Private خود باز کنید و به محتوای اصلی دسترسی داشته باشید. اساس استفاده از این روش کدینگ یا مخفی‌سازی اطلاعات به الگوریتم مشهوری به نام Rivest Shamir Adleman یا RSA برمی‌گردد. از این الگوریتم برای تهیه کلیدهای مذکور، کد کردن اطلاعات، دی کد کردن یا آشکارسازی اطلاعات، تهیه امضاهای الکترونیکی و…. استفاده می‌شود. الگوریتم RSA پس از آنکه ران ریوست (Ron Rivest)، آدام شامیر (Adam Shamir) و لن ادلمن (Len Adleman) در سال ۱۹۷۷ آن را بدست آوردند به این نام مشهور شد، هرچند تکنیک‌های اولیه آن پیشتر در سال ۱۹۷۳ توسط فردی به نام کلیفورد کوکس (Clifford Cocks) بدست آمده بود اما تا سال ۱۹۷۷ اولا الگورتیم کاملا محرمانه بود و ثانیا به سادگی آنچه در زیر بیان خواهیم کرد نبود.
● تهیه کلیدهای عمومی و خصوصی بطور خلاصه روش کار برای تهیه کلیدها به شرح زیر است: ۱- دو عدد بزرگ (هر چه بزرگتر بهتر) اول به نام‌های 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 نمونه‌ای از این الگوریتمها ست.
کاربرد در امضای دیجیتال.
کلیدهای این نوع از الگوریتمها (نامتقارن) بسیار طولانی‌تر از الگوریتم‌های مرسوم (کلید متقارن) می‌باشند.
کاربردهای رمزنگاری کلید عمومی
دسته بندی کلی کاربردها
-رمزگذاری/ رمز گشایی : برای حفظ محرمانگی
-امضاء رقمی : برای حفظ اصالت پیام و معین نمودن فرستنده پیام (پیوند دادن پیام با امضاء‌کننده)
-توزیع کلید : برای توافق طرفین روی کلید جلسه مخفی
رمز نگاری RSA
کلیات
توسط Adleman- Shamir- Rivestدر سال ۱۹۷۷ در MIT ارائه شد
مشهورترین و پرکاربردترین الگوریتم رمزگذاری کلید عمومی
مبتنی بر توان‌رسانی پیمانه ایی
استفاده از اعداد طبیعی خیلی بزرگ
امنیت آن ناشی از دشوار بودن تجزیه اعداد بزرگ، که حاصلضرب دو عامل اول بزرگ هستند، می‌باشد.
مستندات مربوط به آن تحت عنوان PKCS استاندارد شده‌است.
شکستن الگوریتم
آیا متنی که توسط الگوریتم RSA به صورت رمز شده و مخفی درآمده‌است قابل شکسته شدن است؟ این سئوالی است که اغلب راجع به همه روش‌های رمز کردن اطلاعات پرسیده می‌شود. واقعیت آن است که همه روش‌های رمز کردن قابل شکستن است، اما نکته مهم آن است که در چه مدت زمان و با چه امکاناتی این اطلاعات باید رمزگشایی شوند. در ارتباط با الگوریتم RSA باید گفت روش‌های محدودی برای شکستن متن رمز شده توسط آن وجود دارد که در اینجا به مواردی از آن اشاره می‌کنیم.
تجزیه n به عوامل اول
اولین روش آن است که بتوان کلید خصوصی را حدس زد یا پیدا کرد، در این صورت هکر می‌تواند تمامی متن‌های تهیه شده با کلید عمومی را رمزگشایی کند و بخواند یا می‌تواند از امضای الکترونیک صاحب کلید استفاده کند. فرض را بر این می‌گذاریم که فردی که قصد حدس زدن کلید خصوصی را دارد، از جمله افرادی است که کلید عمومی را دارا است. در این حالت او n و e را در دسترس دارد.
بدست آوردن روش موثر برای محاسبه ریشه e ام
حدس زدن پیام
برای باز کردن رمز پیامهایی که با الگوریتم RSA رمز شده‌اند، روش‌های محاسبه ریاضی عملا راه به جایی نمی‌برند، این است که در مواردی که متن کوچک باشد شاید حدس زدن متن اصلی ساده‌ترین روش برای رمزگشایی باشد.
راه‌های مقابله با حمله زمانی به RSA
استفاده از توان رساندن با زمان ثابت محاسباتی.
تابع باید به ازای همه ورودیها زمان ثابتی به طول بینجامد
قرار دادن اعمال اضافی و گمراه‌کننده در بین محاسبات
ضرب کردن متن رمزشده در یک عدد تصادفی قبل از عملیات به توان رسانی
اضافه کردن تاخیرهای تصادفی