این وبلاگ به آدرس زیر منتقل شده است :

http://riazinevis.blogspot.com

دو نوع سیستم رمزنگاری متقارن و نامتقارن داریم .الگوریتم رایج برای رمزگذاری نامتقارن RSA می باشد .

ایده اولیه الگوریتم RSA بسیار ساده است : ضرب اعداد خیلی ساده ولی تجزیه اعداد بسیار مشکل است .

الگوریتم RSA در 3 مرحله کار خود انجام می دهد :

1- ساخت کلید    2- رمزگذاری  3- رمز گشایی

در مرحله اول الگوریتم RSA شما نیاز به ساخت کلید دارید . کلید عمومی برای رمزگذاری و کلید اختصاصی برای رمزگشایی استفاده می شود .

در ادامه،  مراحل کار RSA را شرح داده و سپس با یک مثال ساده بیشتر با کاربرد آن آشنا خواهیم شد .

A- مراحل ساخت کلید

1- انتخاب اعداد اول :

دو عدد اول به اندازه کافی بزرگ در نظر گرفته می شود ، آنها را p و q می نامیم.

2- تعیین پیمانه همنهشتی :

حاصلضرب دو عدد p و q را محاسبه نمایید .(n=pq) عدد n پیمانه همنهشتی شما خواهد بود .

حاصلضرب pq تجزیه منحصر به فردی به دو عامل p و q دارد . بدون داشتن p و q تجزیه pq کار بسیار مشکلی است ، ضمنا p و q به اندازه کافی بزرگ در نظر گرفته شده اند که به آسانی با داشتن n قابل دستیابی نباشند .

3- محاسبه فی-اویلر عدد n ؛

p و q دو عدد اولند پس داریم :                        

که به آسانی با داشتن عوامل p و q قابل محاسبه است .

4- انتخاب توان رمزگذری :

برای رمزگذاری به عددی مثل e هم نیاز داریم . به شرط اینکه :    

این بدین معنی است که و e نسبت به هم اولند .این شرط در واقع محک معکوس پذیری عدد e به پیمانه ی خواهد بود .

عدد e به همراه n  کلید عمومی شما خواهند بود که می توانید در اختیار هر فردی قرار دهید .

5- محاسبه ی توان رمزگشایی :

عدد d (توان رمزگشایی) را چنان محاسبه می کنیم که  :    

این عدد در واقع معکوس عدد e به پیمانه همنهشتی خواهد بود .

چون e و را داریم پس به راحتی به کمک الگوریتم توسعه یافته اقیلدسی (برای مقادیر m و n) می توان مقدار d را هم محاسبه کرد که جایگاه اصلی کلید اختصاصی شما برای رمزگشایی است .

حالا یک زوج (n,d) داریم که برای رمزگشایی استفاده می کنیم و آن کلید اختصاصی ماست و یک زوج عدد (n, e) داریم که برای رمزگذاری استفاده می کنیم و آن را کلید عمومی می نامیم .

B- مرحله رمزگذاری 

فرض کنید m پیغام ما باشد .( پیغامی که به راحتی از حالت رشته ای تبدیل به حالت عددی شده است )

پیام رمز شده ای که به استفاده کننده ارسال می شود برابر باقیمانده در تقسیم بر n است که به صورت به پیمانه n آن را مختصر می کنیم .

 r پیغام رمزشده است که ارسال می شود .

C- مرحله رمزگشایی 

استفاده مقدار r را دریافت می کند و آن را به توان d به پیمانه n می رساند .( باقیمانده  را بر n محاسبه می کند)

نتیجه کار ، پیغام اولیه m است ، چون d معکوسی برای e به پیمانه است  ، داریم :

از این رو :

توجه کنید در قسمت سوم به جای عبارت مقدار 1 را قرار داریم چون بنا به قضیه اویلر داریم :

مثال RSA با اعداد p=7 و q=11 و توان رمزگذاری e=13 ( اعداد به طور غیر واقع بینانه ای کوچک انتخاب شده اند) .

1- انتخاب اعداد اول :

2- تعیین پیمانه همنهشتی :

3- محاسبه فی-اویلر عدد 77 :

4- انتخاب توان رمزگذاری :

عدد e=13 را به عنوان توان رمزگذاری انتخاب می کنیم . می دانیم که  :           

5- محاسبه توان رمزگشایی :

عدد d را که معکوس e=13 به پیمانه همنهشتی  می باشد به کمک الگوریتم اقلیدسی می یابیم :

از سطر آخر داریم :

عدد بر a بخش پذیر است یعنی :

و چون از همنهشتی داریم :

پس می توان نتیجه گرفت که مقدار توان رمزگشایی برابر 37 است .

B- رمزگذاری : 

فرض می کنیم m =7 پیغام ماست که به صورت عددی تبدیل شده است .

باقیمانده 7¹³ را بر 77 به دست می آوریم . این کار توسط کامپیوتر به آسانی و به کمک روشهای مربع کردن و استفاده از هم نهشتی میسر است  :

پیغام رمز شده برابر r=35 خواهد بود .

C- مرحله رمزگشایی :

باقیمانده عدد 35³⁷  بر عدد 77 برابر عدد مورد نظر یعنی 7خواهد بود که برای کامپیوتر این کار نیز آسان خواهد بود .

سه مطلب مرتبط با الگوریتم RSA :

1- ریاضیات و امنیت – الگوریتم رمزنگاری RSA – قسمت اول

2-ریاضیات و امنیت – الگوریتم رمزنگاری RSA – قسمت دوم

3- رمزنگاری در رایانه ها

منابع :

نوشته شده توسط حمید دیواندری در سه شنبه دهم شهریور 1388 |