لگوريتم Rsa

الگوريتم RSA قسمت - 1



http://www.cohn-family.com/images/ce...encryption.jpg

Rivest , Shamir , Adleman در مطلب قبل راجع به کليدهاي عمومي و خصوصي براي کد کردن و پنهان سازي اطلاعات صحبت کرديم و در آنجا صحبت از الگوريتمي بنام RSA نموديم. در اين مطلب سعي ميکنيم و با ذکر يک مثال ساده به تشريح اين لگوريتم بپردازيم. از اين الگوريتم براي تهيه کليد هاي مذکور، کد کردن اطلاعات، دي کد کردن يا آشکار سازي اطلاعات، تهيه امضاهاي الکترونيکي و .... استفاده مي شود.


الگوريتم RSA پس از آنکه ران ريوست (Ron Rivest)، آدام شامير (Adam Shamir) و لن ادلمن (Len Adleman) در سال 1977 آنرا بدست آوردند به اين نام مشهور شد، هرچند تکنيک هاي اوليه آن پيشتر در سال 1973 توسط فردي بنام کليفورد کوکس (Clifford Cocks) بدست آمده بود اما تا سال 1977 اولا" الگورتيم کاملا" محرمانه بود و ثانيا" به سادگي آنچه در زير بيان خواهيم کرد نبود.

تهيه کليد هاي عمومي و خصوصي
بطور خلاصه روش کار براي تهيه کليدها به شرح زير است :

1- دو عدد بزرگ (هر چه بزرگتر بهتر) اول به نام هاي p و q را انتخاب مي کنيم، بهتر است اين اعداد از لحاظ سايز نزديک به يکديگر باشند.

2- عدد ديگري بنام n را معادل با حاصلضرب p در q تعريف مي کنيم : n = p x q

3- عدد چهارم يعني m را معادل حاصلضرب p-1 در q-1 تعريف مي کنيم : (m = (p-1) x (q-1

4- عدد e را که از m کوچکتر است آنگونه پيدا مي کنيم که بزرگترين مقسوم عليه مشترک اين دو يک باشد به عبارتي نسبت به هم اول باشند.

5- عددي مانند d را پيدا کنيد که باقيمانده حاصلضرب d در e تقسيم بر m مساوي عدد 1 باشد، يعني : d x e) mod m = 1)

حال پس از طي اين مراحل شما مي توانيد از e و n بعنوان کليد عمومي و از d و n بعنوان کليد اختصاصي استفاده کنيد.

روش پنهان کردن و آشکار کردن
براي کد کردن اطلاعات کافي است عدد منتصب به هر کاراکتر - مثلا" ASCII - را که در اينجا M مي ناميم در فرمول زير قرار دهيد و بجاي ارسال آن عدد C = Me mod n را ارسال کنيد. در واقع دراينجا شما توانسته ايد با کمک کليد عمومي، کاراکتر M را به C تبديل کنيد.

حال گيرنده براي آشکار سازي کافي است عدد دريافتي يعني C را با استفاده از کليد خصوصي به M تبديل کند. براي اينکار کافي است از اين فرمول استفاده کنيد : M = Cd mod n ، بنابراين شما با دريافت کاراکتر کد شده C و در دست داشتن کليد خصوصي توانسته ايد کاراکتر اصلي را مشخص نماييد.