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

شکستن الگوریتم RSA
http://www.ipnetsecurity.com/archives/images/rsa-2.jpg
Rivest , Shamir , Adleman
آیا متنی که توسط الگوریتم RSA بصورت رمز شده و مخفی درآمده است قابل شکسته شدن است؟ این سئوالی است که اغلب راجع به همه روشهای رمز کردن اطلاعات پرسیده می شود. واقعیت آن است که همه روشهای رمز کردن قابل شکستن است، اما نکته مهم آن است که در چه مدت زمان و با چه امکاناتی این اطلاعات باید رمزگشایی شوند. در ارتباط با الگوریتم RSA باید گفت روشهای محدودی برای شکستن متن رمز شده توسط آن وجود دارد که در اینجا به مواردی از آن اشاره می کنیم.

تجزیه n به عوامل اول
اولین روش آن است که بتوان کلید خصوصی را حدس زد و یا پیدا کرد، در این صورت هکر می تواند تمامی متن های تهیه شده با کلید عمومی را رمزگشایی کند و بخواند و یا می تواند از امضای الکترونیک صاحب کلید استفاده کند. فرض را بر این می گذاریم که فردی که قصد حدس زدن کلید خصوصی را دارد، از جمله افرادی است که کلید عمومی را دارا است. در این حالت او n و e را در دسترس دارد. (برای یادآوری به مطلب الگوریتم RSA قسمت - ۱ مراجعه کنید.)

حال اولین قدم برای این آقای هکر آن است که بتواند از روی عدد n عاملهای p و q را حدث بزند. این مشکلترین قسمت کار است که محاسبات ریاضی و بررسی های انجام داده شده نشان می دهد اگر عدد n مثلا" 155 رقم داشته باشد (RSA-155) در آن صورت با قوی ترین کامپیوتر های موجود بیش از 7 ماه زمان لازم است تا بتوان عوامل اول تشکیل دهنده n را مشخص کرد. الگوریتم های ریاضی بدست آمده نشان می دهد که اعداد بزرگ اگر عوامل اول کوچکتری داشته باشند، ساده تر تجزیه می شوند تا اعداد بزرگی که عوامل اول بزرگتری دارند.

نکته بسیار جالب آن است که هرچقدر هم که توانایی و سرعت کامپیوتر ها برای تجزیه یک عدد بزرگ بالاتر رود شما می توانید در هنگام استفاده از RSA با پیشنهاد کلید بزرگتر (انتخاب اعدد p و q بزرگتر) کار تجزیه n را برای کامپیوترهای جدید، بسیار دشوارتر سازید.

بدست آوردن روش موثر برای محاسبه ریشه e ام
با توجه به روش رمز کردن شما با داشتن کلید عمومی (n و e) و استفاده از فرمول C = Me mod n می توانید حروف را رمز کنید. اما با نگاهی به فرمول می توان دریافت که کافی است شما بتوانید ریشه e ام C mod n را بدست آورید در آن صورت شما می توانید به عدد m نزدیک شوید و کاراکتر اولیه برسید.

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

حدس زدن پیام
برای باز کردن رمز پیامهایی که با الگوریتم RSA رمز شده اند، روشهای محاسبه ریاضی عملا" راه به جایی نمی برند، این است که در مواردی که متن کوچک باشد شاید حدس زدن متن اصلی ساده ترین روش برای رمزگشایی باشد. ارسال پیام های کوتاه دو یا سه کلمه ای و تشخیص ساده آنها توسط هکر می تواند به او کمک کند که از روی پیام رمزگشایی شده کلید خصوصی شما را حدس بزند. در این گونه موارد کافی است تعداد زیادی کلمات یا بیت های اتفاقی (Random) در انتهای پیام بگذارید تا هکر نتواند پیام شما را حدس بزند.