تفكر «رمزنگاري كليد عمومي» (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)
كه در آن .gif)
عددي «صحيح» است.
- «فريد» مي‌خواهد پيام رمز شده‌‌اي از «فرناز» دريافت كند.
- «هركس» مي‌داند چگونه آن پيام را به‌شكل كد دراورد.
- «فريد» «تنها شخصي» است كه مي‌داند چگونه پيام رمز شده را رمزگشايي كند.
يك روش آن است كه «فريد» دو عدد اول و خيلي بزرگ و .gif)
را انتخاب كند و سپس رابطهي ذيل را بنويسد:
(رابطهي 3)
سپس براي رمز كردن پيام استفاده مي‌شود اما و براي رمزگشايي پيام مذكور به‌كار مي‌رود.
- «فريد» دو عدد اول، خيلي بزرگ و مجزاي و را انتخاب مي‌كند.
- بنابراين روابط ذيل صادق است:
(رابطهي 4)
(رابطهي 5)
ياداوري – منظور از .gif)
عبارت است از: كوچك‌ترين مضرب مشترك.
- «فريد» .gif)
را انتخاب مي‌كند كه در آن رابطهي ذيل برقرار است:
(رابطهي 6)
و .gif)
نسبت به هم اول هستند (يعني داراي عامل مشترك نيستند).
- «فريد» يك عدد منحصر به‌فرد را مي‌يابد به‌گونه‌اي كه رابطهي ذيل برقرار باشد:
(رابطهي 7)
- «فريد» اكنون به همه مي‌گويد كه .gif)
و چيست‌اند اما از ، و .gif)
نمي‌گويد.
- «فرناز» مي‌خواهد پيام .gif)
(يك عدد) را بفرستد كه در آن و نسبت به هم اول بوده و رابطهي ذيل برقرار است:
(رابطهي 8)
- «فرناز» .gif)
را مي‌يابد كه در آن رابطهي ذيل برقرار است:
(رابطهي 9)
و پيام را به «فريد» مي‌فرستد.
- «فريد» پيام را از «فرناز» دريافت مي‌كند و آن را رمزگشايي مي‌نمايد.
اكنون «فريد» ، ، ، ، و را مي‌شناسد و از آنها براي رمزگشايي پيام از «فرناز» استفاده مي‌كند به‌گونه‌اي كه پيام را بيابد. براي اين منظور «فريد» از قضيه‌ي .gif)
استفاده مي‌كند.
ذيلاً طي مثالي از اعداد كوچك استفاده كرده‌ايم به‌گونه‌اي كه مي‌توانيم از يك ماشين‌حساب استفاده كنيم. ولي در موارد عملي، اعداد خيلي بزرگ هستند.
«فرناز» مي‌خواهد پيام را بفرستد.
«فريد» مقادير ذيل را براي ، ، ، ، و برمي‌گزيند:
(رابطهي 10)
بنابراين خواهيم داشت:
(رابطهي 11)
«فريد» به «فرناز» مي‌گويد كه مقادير و عبارت است از:
(رابطهي 12)
ياداوري – اهميتي ندارد چه تعداد افراد اين اطلاعات را داشته باشند آنها هنوز نمي‌توانند را بيابند.
«فرناز» را محاسبه كرده و مقدار ذيل را مي‌يابد:
(رابطهي 13)
«فريد» پيام رمز شده‌ي 180 را از «فرناز» دريافت مي‌كند.
اكنون «فريد» مقدار ذيل را مي‌يابد:
(رابطهي 14)
هم‌چنين پيام رمز شده‌ي را مي‌يابد. آيا مي‌توانيد آن را بيابيد؟
براي يافتن پيام «فرناز» نياز به كمي كمك به‌شرح ذيل داريد.
|
كار كردن با «حساب پيمانه‌اي» (Modulus Arithmetics) |
لازم است از واقعيت‌هاي ذيل آگاه باشيم:
اگر رابطهي ذيل برقرار باشد:
(رابطهي 15)
آن‌گاه رابطهي ذيل صادق است:
(رابطهي 16)
اگر رابطهي ذيل برقرار باشد:
(رابطهي 17)
آن‌گاه رابطهي ذيل صادق است:
(رابطهي 18)
اثبات نتايج فوق ساده است.
اگر رابطهي ذيل برقرار باشد:
(رابطهي 19)
بنابراين بر .gif)
بخش‌پذير است و اگر بر بخش‌پذير باشد پس بر .gif)
بخش‌پذير است كه معادل رابطهي ذيل است:
(رابطهي 20)
همان‌طور كه .gif)
داراي عامل براي همه‌ي مقادير .gif)
است در نتيجه اگر بر بخش‌پذير باشد پس بر بخش‌پذير است بنابراين اگر رابطهي ذيل برقرار باشد:
(رابطهي 21)
در اين صورت رابطهي ذيل برقرار خواهد بود:
(رابطهي 22)
به‌منظور يافتن عدد مخفي‌اي كه «فرناز» به «فريد» بفرستد همان‌گونه كه توضيح داده شد نياز داريم از همان روشي استفاده كنيم كه در مثال ذكر شد.
فرض كنيد مي‌خواهيم مقدار عدد .gif)
را بيابيم كه در آن روابط ذيل برقرار باشند:
(رابطهي 23)
(رابطهي 24)
از آن‌جايي كه .gif)
براي بيش‌تر ماشين‌حساب‌ها خيلي بزرگ است كه نتيجه‌ي آن نشان داده شود با .gif)
شروع مي‌كنيم. ابتدا آن را بر عدد 101 تقسيم مي‌كنيم. در اين‌صورت خواهيم داشت:
(رابطهي 25)
بنابراين مي‌دانيم رابطهي ذيل برقرار خواهد بود:
(رابطهي 26)
مرحله‌ي بعد استفاده از رابطهي 26 در محاسبه‌ي است. در اين صورت روابط ذيل برقرار خواهد بود:
(رابطهي 27)
بنابراين مقدار به‌دست خواهد آمد:
(رابطهي 28)
نهايتاً اين قضيه را ثابت خواهيم كرد كه با فرض برقراري روابط ذيل:
(رابطهي 29)
(رابطهي 30)
(رابطهي 31)
رابطهي ذيل برقرار خواهد بود:
(رابطهي 32)
كه در آن و نسبت به هم اول هستند.
ياداوري – منظور از عبارت است از: كوچك‌ترين مضرب مشترك.
اگر بخواهيم اين قضيه را ثابت كنيم بايد بگوييم:
همان‌طور كه و نسبت به هم اول هستند مي‌دانيم و هم نسبت به هم اول هستند هم‌چنين و هم نسبت به هم اول هستند.
با استفاده از «قضيه‌ي كوچك فرما» (Fermat’s Little Theorem) روابط ذيل برقرار خواهد بود:
(رابطهي 33)
(رابطهي 34)
هم‌چنين .gif)
و .gif)
عدد را به‌گونه‌اي تقسيم مي‌كنند كه داشته باشيم:
(رابطهي 35)
بنابراين رابطهي ذيل را خواهيم داشت:
(رابطهي 36)
به‌طور مشابه رابطهي ذيل برقرار خواهد بود:
(رابطهي 37)
بنابراين هم و هم عدد .gif)
را تقسيم مي‌كنند و از آن‌جايي كه .gif)
رابطهي ذيل برقرار خواهد بود:
(رابطهي 38)
بنابراين براي بعضي از مقادير «صحيح» .gif)
رابطهي ذيل برقرار خواهد بود:
(رابطهي 39)
با جمع‌بندي روابط گذشته رابطهي ذيل به‌دست خواهد آمد:
(رابطهي 40).