الگوریتم RSA+عیدانه+تقویم ۸۶
بر چهره گل نسيم نوروز خوش است
در صحن چمن روي دلفروز خوش است
از دي که گذشت هر چه گويي خوش نيست
خوش باش و ز دي مگو که امروز خوش است
فرا رسیدن سال نو و بهار طبیعت مبارک
انشاءالله سالی پر از خیر و برکت داشته باشید.
از همه دوستان می خواهم که موقع سال تحویل همه مریض ها را مخصوصا بچه هایی که عید رو توی بیمارستان می گذرانند دعا کنید راستش این دعا رو ازتون به این دلیل می خواهم که پارسال در ایام نوروز توی بیمارستان بخاطر یکی از اقوام عیدی نداشتم و حالا بهتر این موضوع رو درک می کنم . اگر در سال گذشته از دست ما رنجیده خاطر شدید ما رو به بزرگی خودتون ببخشید .
راستی آخرین پروژه مشترک من و آقا شهریار هم که در زمینه تحقیق در عملیات است از لینک زیر قابل دریافت است.
و در انتها تقویم ۸۶ از دوست عزیزم آقا تایماز
{فرما در حاشیه نسخه رونوشتش از Diophantus' Arithmetica می نویسد }
برای تقسیم کردن یک عدد مکعب کامل به دو مکعب دیگر ، توان 4 و در حالت کلی هر توانی از هر عددی به دو توان هم جنس همانطور که ذکر شد حالت دومی نیز ممکن است ، و من مطمئنا یک اثبات تحسین بر انگیز برای آن پیدا کرده ام ، اما حاشیه کتاب برای نوشتن آن بسیار باریک است!!!!!!
پیر فرما
در ابتدای این سلسله مقالات به بیان مفهوم کلید عمومی و شیوه رمز نگاری نا متقارن پرداختیم سپس در ادامه روش های تایید هویت که مکمل این شیوه است مورد بررسی قرار گرفت و پس از آن از ایده اولیه الگوریتم آر اس ای -که نوعی روش به رمز در آوردن اطلاعات مبتنی بر شیوه کلید عمومی است- صحبت شد و حالا در ادامه مثال کاملی را برای بیان الگوریتم RSA مطرح می کنیم .در اینجا سعی شده تا از اعداد اول بسیار کوچکی استفاده شود تا ادامه روند محاسبات ساده باشد اما باید توجه داشت که در کاربرد واقعی روش RSA این اعداد باید بسیار بزرگ ،حداقل دارای 100 رقم ، انتخاب می شود:
در طول این مثال فرض کنید شخص A می خواهد یک کلید عمومی برای خود بسازد و شخص B می خواهد با استفاده از این کلید عمومی برای A پیغامی بفرستد. فرض می کنیم که A و B بر سر روشی برای برمز در آوردن متن بصورت اعداد توافق کرده اند .بنابراین این گام ها باید پیموده شود :
1. ابتدا شخص A دو عدد اول انتخاب می کند . ما از اعداد p=23 و q=41 استفاده می کنیم .
2. شخص A دو عدد p و q را در هم ضرب میکند تا به N=p.q=(23)(41)=934 برسد . 934 کلید عمومی او است ، که آنرا به نفر B می دهد ( و همچنین به باقی افرادی در جهان که متمایل باشد )
3. شخص A همچنین عدد دیگری چون e را که نسبت به (M=(p-1)(q-1 اول باشد. یعنی بزرگترین مقسوم علیه مشترک آنها یک باشد یا p-1)(q-1),e)=1)). در این مورد خاص M=(p-1)(q-1)=(22)(40)=880 بنابراین e=7 مناسب است. e نیز قسمتی از کلید عمومی است و باید علاوه بر p.q ، e نیز به شخص B گفته شود.
4. حالا B اطلاعات کافی برای برمز در آوردن یک پیغام برای A را دارد . فرض کنید که در این مثال پیغامی مورد نظر عدد P=35 باشد .
5. شخص B مقدار(C=Pe(mod N)=357(mod 943 را حساب می کند.
۶.5357=6433929687 و ۵64339296875(mod 943)=545
عدد 545در واقع پیغام رمزگذاری شده ای است که B به A می فرستد.
7. حالا A می خواهد 545 را رمزگشایی کند برای این کار او عددی را چون d نیاز دارد طوری که((ed=1(mod (p-1)(q-1 ، یا در این مثال(7d=1(mod 880جواب فرد A برای d عدد 503 خواهد بود ، زیرا داریم(7x503=3521=(4x(880)+1)(mod 800.
8. برای پیدا کردن متن رمزگشایی شده ، A مجبور است
(Cd (mod N)=545503 (mod 943
را حساب کند. در ابتدا به نظر می آید که این کار بسیار دشوار است اما توجه کنید
503 = 256+128+64+32+16+4+2+1
(که در واقع بسط دودویی عدد 503 است ) بنابر این خواهیم داشت
545503 = 545256+128+64+32+16+4+2+1 = 545256545128 … 5451
اما از آنجا که ما تنها علاقمند به پیدا کردن باقی مانده به پیمانه 943 هستیم ، می توانیم با محاسبه باقیمانده تمام عامل های ضربی در این پیمانه به مقصودمان برسیم و این کار را می توانیم با به توان 2 رساندن های متوالی عدد 545 انجام دهیم زیرا تمام توان های عامل های ضربی ، مضربی از 2 هستند.
به عنوان مثال برای اینکه به باقی مانده توان 4 ام عدد 545 برسیم داریم :
5452(mod 943) = 545 . 545 = 297025(mod 943) = 923
با به توان 2 رساندن مجدد داریم :
5454(mod 943) =(5452)2(mod 943) = 923 . 923 = 851929(mod 943) = 400
و به همین ترتیب برای توان های بالا تر عمل می کنیم و در نهایت به نتایج زیر می رسیم :
5451(mod 943) = 545
5452(mod 943) = 923
5454(mod 943) = 400
5458(mod 943) = 633
54516(mod 943) = 857
54532(mod 943) = 795
54564(mod 943) = 215
545128(mod 943) = 18
545256(mod 943) = 324
بنابراین عدد مورد نظر ما به صورت زیر بدست می آید :
545503(mod 943) = 324 . 18 . 215. 795. 857. 400. 923. 545(mod 943) = 35
بوسیله چنین عملیات کسالت آوری ( البته برای رایانه این محاسبات کاملا ساده و دارای سخت افزار راحتی است ) شخص A می تواند پیام B را رمزگشایی کند و به پیام اصلی یعنی P=35 برسد.
خوب اگر می خواهید با هم یک دور دیگه الگوریتم را مرور کنیم مثال ساده تر زیر را در نظر بگیرید :
ابتدا دو اول پیدا میکنیم :
p = 7
q = 19
تعیین مقدار N:
N=7x19=133
تعیین مقدار M:
M=(7-1)X(19-1)=108
انتخاب عدد کوچک e که نسبت به M اول باشد :
e = 2 => gcd(e, 108) = 2 (غ.ق.ق)
e = 3 => gcd(e, 108) = 3 (غ.ق.ق)
e = 4 => gcd(e, 108) = 4 (غ.ق.ق)
e = 5 => gcd(e, 108) = 1 (ق.ق)
gcd : greatest common divisor
ب.م.م بزرگترین مقسوم علیه مشترک
انتخاب d طوریکه((ed=1 (mod (p-1)(q-1 یا de % M = 1
= > de % M = 1 => de = 1 + nM
=> d = (1 +nM) / e
n = 0 => d = 1 / 5 (غ.ق.ق)
n = 1 => d = 109 / 5 (غ.ق.ق)
n = 2 => d = 217 / 5 (غ.ق.ق)
n = 3 => d = 325 / 5 = 65 (ق.ق)
رمزگذاری متن(عدد) p=6:
C = Pe % n
= 65 % 133
= 7776 % 133
= 62
رمزگشایی متن رمز گذاری شده C=62:
P = Cd % n
= 6265 % 133
= 62 * 6264 % 133
= 62 * (622)32 % 133
= 62 * 384432 % 133
= 62 * (3844 % 133)32 % 133
= 62 * 12032 % 133
با ادامه کاهش توان به روش فوق که توان عبارت 6265 به 12032 کاهش داد و در واقع همان روش فوق یعنی تجزیه توان به جمعوند هایی که توان های 2 هستند ولی این بار در جهت عکس حرکت می کنیم یعنی از جمعوند آخری داریم :
= 62 * 3616 % 133
= 62 * 998 % 133
= 62 * 924 % 133
= 62 * 852 % 133
= 62 * 43 % 133
= 2666 % 133
= 6
که با متن اولیه p=6 مطابق است . بنابراین الگوریتم RSA درست کار می کند !
تمرین
حالا برای تمرین فرض کنید شما شخص ، A هستید و عدد های p=97 و q=173 را بعنوان عدد های اول و همچنین عدد e را 5 انتخاب کرده اید . بنابراین شما عدد N=16781 ( که همان حاصل p.q ) و e=5 را در اختیار فرد B می گذارید .
او متنی را(یک عدد) برای شما رمزگذاری می کند و برای شما عدد رمزگذاری شده 5347 را می فرستد . خوب حالا ببینید می توانید عدد اصلی را رمز گشایی کنید .
کلید واژه ها :الگوریتم رمزنگاری آر اس ای RSA Encryption Algorithm متن رمزگشایی شده (متن اصلی) Plaintext متن رمزگذاری شده Ciphertext
«آيا کساني که مي دانند با کساني که نمي دانند يکسانند. » قرآن کريم