زنگ‌تفریح تصادفی

 پيوندهاي المپياد كامپيوتر
 سايت‌هاي المپياد كامپيوتر
 
 رمزنگاري كليد عمومي (زنگ تفريح شماره‌ي 43)
رمزنگاري كليد عمومي (زنگ تفريح شماره‌ي 43)زنگ تفريح كامپيوتر
روش رمزنگاري و رمزگشايي

رمزنگاري كليد عمومي






اشاره
آن‌چه با عنوان «چكيده» در اول مسابقه‌ها و زنگ‌تفريح‌ها مشاهده مي‌كنيد صرفاً مخصوص معلمان، مربيان، كارشناسان محترم آموزشي و ساير علاقه‌مندان است.




چكيده
اهداف آموزشي
 اهداف آموزشي در حوزه‌ي شناختي – دانش
    - «دانش امور جزوي» > «دانش اصطلاح‌ها»
    - «دانش امور جزوي» > «دانش واقعيت‌هاي مشخص»
    - «دانش راه‌ها و وسايل برخورد با امور جزوي» > «دانش روش‌ها و روش‌شناسي»
    - «دانش امور كلي و مسائل انتزاعي» > «دانش نظريه‌ها و ساخت‌ها»
 اهداف آموزشي در حوزه‌ي شناختي - توانايي‌ها و مهارت‌هاي ذهني
    - «فهميدن» > «ترجمه» > «تفسير»
    - «فهميدن» > «ترجمه» > «كاربستن»
    - «فهميدن» > «ترجمه» > «تحليل» > «تحليل روابط»
    - «فهميدن» > «ترجمه» > «تحليل» > «تحليل عناصر»
    - «فهميدن» > «ترجمه» > «تركيب» > «توليد يك نقشه يا مجموعه‌ اقدام‌هاي پيشنهادي»
    - «فهميدن» > «ترجمه» > «تركيب» > «استنتاج مجموعه‌اي از روابط انتزاعي»
 اهداف آموزشي در حوزه‌ي عاطفي 
    - «دريافت‌ كردن (توجه كردن)» > «آگاهي»
    - «پاسخ دادن» > «رضايت به پاسخ‌دهي (اجابت يا اطاعت)»
    - «پاسخ دادن» > «ميل به پاسخ‌دهي»
 نتايج مورد نظر
    - آشنايي با روش رمزنگاري و رمزگشايي
    - آشنايي با روش «رمزنگاري كليد عمومي» (Public Key Cyptography)
 محتواي آموزشي
    - رمزنگاري.




شكل 1 - انيميشني با عنوان «مقدمه‌اي بر رمزنگاري».

نمايش بزرگ‌تر انيميشن







شكل 3 - «آدي شامير» (Adi Shamir).




مبدأ تفكر
تفكر «رمزنگاري كليد عمومي» (Public Key Cryptography) از آن‌جايي آغاز شد كه افراد به فكر ارسال پيام‌ها افتادند به‌گونه‌اي كه تنها شخص مورد نظري كه آن را دريافت مي‌كند بتواند آن را بفهمد حتي اگر يك «دشمن» آن را دريافت مي‌كند قادر به درك آن نباشد.

شخصي كه پيام را مي‌فرستد آن را «رمزنگاري» (Encode) مي‌كند. شخصي كه پيام رمز شده را دريافت مي‌كند آن را «رمزگشايي» (Decode) مي‌نمايد. به عبارت ديگر به‌شكل قابل خواندن در مي‌آورد.

«رمزنگاري كليد عمومي» (Public Key Cryptography) در سال 1349 (1970 ميلادي) توسط محققاني به‌نام‌هاي «رونالد لين ريوست» (Ronald Lin Rivest)، «آدي شامير» (Adi Shamir) و «لئونارد مكس آدلمن» (Leonard Max Adleman) كشف (يا اختراع!) شد. اين روش به‌صورتي وسيع براي ايجاد امنيت در روابط الكترونيكي به‌خصوص زماني كه مبادله‌هاي مادي مطرح مي‌شود به‌كار مي‌رود.

اين امر به اين واقعيت بستگي دارد:

در حالي كه در همه‌ي موارد عملي محاسبه‌ي حاصل‌ضرب دو عدد اول بزرگ (به‌ويژه با كمك كامپيوتر) ساده شده است پيدا كردن عوامل يك عدد بزرگ – زماني كه عوامل آن اعدادي اول و بزرگ باشند - غيرممكن است. علت آن است كه همه‌ي روش‌هاي يافتن چنين عواملي حتي با كاربرد سريع‌ترين كامپيوترهاي امروزي هزاران سال طول مي‌كشد!

براي درك اين مسأله لازم است اين قضيه را بدانيم:

دو عدد «هم‌نهشت» (Congruent) يكديگر در «حساب پيمانه‌اي» (Modulus Arithmetics) ناميده مي‌شوند اگر قدر مطلق اختلاف آن‌ها بر پيمانه‌ بخش‌پذير باشد.

به‌عنوان مثال:
23 با 2 به‌پيمانه‌ي 7 هم‌نهشت است  بدين‌خاطر كه تفاوت بين 2 و 23 بر 7 بخش‌پذير است.

راه ديگر بيان اين مطلب آن است كه گزاره‌ي ذيل ذكر شود:

شرط لازم و كافي براي آن‌كه رابطه‌ي ذيل برقرار باشد:






(رابطه‌ي 1)

آن است كه رابطه‌‌ي ذيل صدق كند:






(رابطه‌‌ي 2)

كه در آن  عددي «صحيح» است.



شكل 4 - «رونالد لين ريوست»
(Ronald Lin Rivest)
.





روش رمزنگاري و رمزگشايي
- «فريد» مي‌خواهد پيام رمز شده‌‌اي از «فرناز» دريافت كند.

- «هركس» مي‌داند چگونه آن پيام را به‌شكل كد دراورد.

- «فريد» «تنها شخصي» است كه مي‌داند چگونه پيام رمز شده را رمزگشايي كند.

يك روش آن است كه «فريد» دو عدد اول و خيلي بزرگ  و  را انتخاب كند و سپس رابطه‌ي ذيل را بنويسد:






(رابطه‌‌ي 3)

سپس براي رمز كردن پيام استفاده مي‌شود اما  و  براي رمزگشايي پيام مذكور به‌كار مي‌رود.






شكل 5 - «آدي شامير» (Adi Shamir).





جزويات
- «فريد» دو عدد اول، خيلي بزرگ و مجزاي  و  را انتخاب مي‌كند.

- بنابراين روابط ذيل صادق است:






(رابطه‌ي 4)






(رابطه‌ي 5)

ياداوري – منظور از  عبارت است از: كوچك‌ترين مضرب مشترك.

- «فريد»  را انتخاب مي‌كند كه در آن رابطه‌ي‌ ذيل برقرار است:






(رابطه‌ي 6)

 و نسبت به هم اول هستند (يعني داراي عامل مشترك نيستند).

- «فريد» يك عدد منحصر به‌فرد  را مي‌يابد به‌گونه‌اي كه رابطه‌ي ذيل برقرار باشد:






(رابطه‌ي 7)

- «فريد» اكنون به همه مي‌گويد كه  و  چيست‌اند اما از ،  و  نمي‌گويد.

- «فرناز» مي‌خواهد پيام  (يك عدد) را بفرستد كه در آن  و  نسبت به هم اول بوده و رابطه‌ي ذيل برقرار است:






(رابطه‌‌ي 8)

- «فرناز»  را مي‌يابد كه در آن رابطه‌ي ذيل برقرار است:






(رابطه‌ي 9)

و پيام  را به «فريد» مي‌فرستد.

- «فريد» پيام  را از «فرناز» دريافت مي‌كند و آن را رمزگشايي مي‌نمايد.

اكنون «فريد» ، ، ، ،  و  را مي‌شناسد و از آن‌ها براي رمزگشايي پيام  از «فرناز» استفاده مي‌كند به‌گونه‌اي كه پيام  را بيابد. براي اين منظور «فريد» از قضيه‌ي  استفاده مي‌كند.

ذيلاً طي مثالي از اعداد كوچك استفاده كرده‌ايم به‌گونه‌اي كه مي‌توانيم از يك ماشين‌حساب استفاده كنيم. ولي در موارد عملي، اعداد خيلي بزرگ هستند.




شكل 6 - «لئونارد مكس آدلمن»
(Leonard Max Adleman)
.






يك مثال
«فرناز» مي‌خواهد پيام  را بفرستد.

 «فريد» مقادير ذيل را براي ، ، ، ،  و  برمي‌گزيند:






(رابطه‌ي 10)

بنابراين خواهيم داشت:






(رابطه‌‌ي 11)

«فريد» به «فرناز» مي‌گويد كه مقادير  و  عبارت است از:






(رابطه‌ي 12)

 ياداوري – اهميتي ندارد چه تعداد افراد اين اطلاعات را داشته باشند آن‌ها هنوز نمي‌توانند  را بيابند.

 «فرناز»  را محاسبه كرده و مقدار ذيل را مي‌يابد:






(رابطه‌ي 13)

 «فريد» پيام رمز شده‌ي 180 را از «فرناز» دريافت مي‌كند.

 اكنون «فريد» مقدار ذيل را مي‌يابد:






(رابطه‌ي 14)

هم‌چنين پيام رمز شده‌ي  را مي‌يابد. آيا مي‌توانيد آن را بيابيد؟

براي يافتن پيام «فرناز» نياز به كمي كمك به‌شرح ذيل داريد.





شكل 7 - «لئونارد مكس آدلمن»
(Leonard Max Adleman)
.








 كار كردن با «حساب پيمانه‌اي» (Modulus Arithmetics)
لازم است از واقعيت‌هاي ذيل آگاه باشيم:

 اگر رابطه‌ي ذيل برقرار باشد:






(رابطه‌ي 15)

آن‌گاه رابطه‌ي ذيل صادق است:






(رابطه‌‌ي 16)

 اگر رابطه‌ي ذيل برقرار باشد:






(رابطه‌ي 17)

آن‌گاه رابطه‌ي ذيل صادق است:






(رابطه‌‌ي 18)

اثبات نتايج فوق ساده است.

 اگر رابطه‌ي ذيل برقرار باشد:






(رابطه‌ي 19)

بنابراين  بر  بخش‌پذير است و اگر  بر  بخش‌پذير باشد پس  بر  بخش‌پذير است كه معادل رابطه‌ي ذيل است:






(رابطه‌ي 20)

 همان‌طور كه داراي عامل  براي همه‌ي مقادير است در نتيجه اگر  بر  بخش‌پذير باشد پس بر  بخش‌پذير است بنابراين اگر رابطه‌ي ذيل برقرار باشد:






(رابطه‌ي 21)

در اين صورت رابطه‌ي ذيل برقرار خواهد بود:






(رابطه‌ي 22)

به‌منظور يافتن عدد مخفي‌اي كه «فرناز» به «فريد» بفرستد همان‌گونه كه توضيح داده شد نياز داريم از همان روشي استفاده كنيم كه در مثال ذكر شد.

فرض كنيد مي‌خواهيم مقدار عدد  را بيابيم كه در آن روابط ذيل برقرار باشند:






(رابطه‌‌ي 23)






(رابطه‌ي 24)

از آن‌جايي كه  براي بيش‌تر ماشين‌حساب‌ها خيلي بزرگ است كه نتيجه‌ي آن نشان داده شود با  شروع مي‌كنيم. ابتدا آن را بر عدد 101 تقسيم مي‌كنيم. در اين‌صورت خواهيم داشت:






(رابطه‌ي 25)

بنابراين مي‌دانيم رابطه‌ي ذيل برقرار خواهد بود:






(رابطه‌ي 26)

مرحله‌ي بعد استفاده از رابطه‌ي 26 در محاسبه‌ي  است. در اين صورت روابط ذيل برقرار خواهد بود:













(رابطه‌ي 27)

بنابراين مقدار  به‌دست خواهد آمد:






(رابطه‌ي 28)

نهايتاً اين قضيه را ثابت خواهيم كرد كه با فرض برقراري روابط ذيل:






(رابطه‌ي 29)






(رابطه‌ي 30)






(رابطه‌ي 31)

رابطه‌ي ذيل برقرار خواهد بود:









(رابطه‌ي 32)

كه در آن  و  نسبت به هم اول هستند.

ياداوري – منظور  از عبارت است از: كوچك‌ترين مضرب مشترك.

اگر بخواهيم اين قضيه را ثابت كنيم بايد بگوييم:

همان‌طور كه  و  نسبت به هم اول هستند مي‌دانيم  و  هم نسبت به هم اول هستند هم‌چنين  و هم نسبت به هم اول هستند.

با استفاده از «قضيه‌ي كوچك فرما» (Fermat’s Little Theorem) روابط ذيل برقرار خواهد بود:






(رابطه‌ي 33)






(رابطه‌ي 34)

هم‌چنين  و  عدد  را به‌گونه‌اي تقسيم مي‌كنند كه داشته باشيم:






(رابطه‌ي 35)

بنابراين رابطه‌ي ذيل را خواهيم داشت:












(رابطه‌ي 36)

به‌طور مشابه رابطه‌ي ذيل برقرار خواهد بود:













(رابطه‌ي 37)

بنابراين هم  و  هم عدد  را تقسيم مي‌كنند و از آن‌جايي كه  رابطه‌ي ذيل برقرار خواهد بود:






(رابطه‌ي 38)

بنابراين براي بعضي از مقادير «صحيح»  رابطه‌ي ذيل برقرار خواهد بود:






(رابطه‌ي 39)

با جمع‌بندي روابط گذشته رابطه‌ي ذيل به‌دست خواهد آمد:








(رابطه‌ي 40).

1387/5/26لينک مستقيم

فرستنده :
reza rashidi HyperLink HyperLink 1387/11/30
مـتـن : با سلام
یک مشکل بسیار بزرگدر این معادله شما وجود دارد که باعث نامعتبر بودن آن می شود
آنهم این است
n=p*q
که در سمت راست این معادله دو عدد اول قرار می گیرد پس این یک معاده برگشت پذیر است چون دو متغیر ورودی آن اول و تجزیه ناپزذیر می باشند پس آنها تنها عامل های n می باشند (مقسوم الیه) و براحتی قابل محاسبه می باشد. و در صورت بدست اوردن انها کل رمز لو می رود.
ولی در صورت غیر اول بودنp و q (بطوری که عامل های زیادی داشته باشند) در این صورت حدس p و q از روی n سخت می شود (نه غیر ممکن)
با تشکر
پاسـخ :ايميل فرستنده: reza_r_na@yahoo.com
تاريخ ارسال: 1387/7/11
رضا جان!
از اين‌كه با دقت به مطالب زنگ تفريح توجه مي‌كني و موارد درج شده در آن را مورد تجزيه و تحليل قرار مي‌دي ازت تشكر مي‌كنيم.
از ساير دوستان رشد (شما خوانندگان گرامي) تقاضا داريم در مورد اظهارنظر رضا جان هرگونه مطلب دارن مطرح بكنن.
انشاء‌الله موفق باشي!

فرستنده :
رضا رشیدی HyperLink HyperLink 1387/11/30
مـتـن : با سلام
رابطه ی 6 شما کامل نیست r>1 کافی نیست
در انیمیشن شما رابطه زیر بسیار نامفهوم است
d*e=1 mod phi(n) شاید منظور شما این بوده
(d*e) mod phi(n)=1
اگر ممکن است هر چه زودتر جواب دهید
با تشکر
پاسـخ :

ايميل فرستنده: reza_R_na@yahoo.com
تاريخ ارسال: 1387/6/12
رضا جان!
سلام
از اين‌كه به مطالب ارائه شده چنين با دقت نگاه كرديد ازت تشكر مي‌كنيم.
رابطه‌‌ي  عبارت است از رابطه‌ي ذيل:

ببخشيد عليرغم تأكيد جنابعالي تأخيري در پاسخ به سؤال شما پيش آمد.
منتظر حضور فعالت در ساير بخش‌ها هستيم.
انشاء‌الله موفق باشي!


نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 زنگ تفريح‌ها

 
 المپياد كامپيوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  2090
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  2090