در کتاب الگوریتم و فلوچارت مختصری در مورد کاربرد عدد اول در رمزنگاری صحبت شده است. در این نوشته قصد دارم به صورت جامع‌تر و در عین حال با زبانی ساده در مورد رمزنگاری صحبت کنم.

برای اینکه با ایده استفاده از اعداد اول در رمزنگاری آشنا شوید بیایید با هم به چند صد سال قبل برگردیم!

 فرض کنید شما میخواهید قطعه ای طلا از شهر A برای دوستتان به شهر B ارسال کنید. برای اینکه طلاها از راهزنان احتمالی در امان باشند گاوصندوقی بسیار محکم در اختیار دارید که باز شدن آن با هیچ روشی به جز داشتن کلید امکان پذیر نیست. شما چطور میخواهید قطعه طلا را به آن شهر بفرستید؟ پاسخ های احتمالیتان را با هم مرور میکنیم:

-اگر طلا را در گاوصندوق قرار دهید و بخواهید گاوصندوق را به شهر B بفرستید مجبورید کلید را هم به همراه آن بفرستید. همراه بودن کلید با صندوق همان و به تاراج رفتن طلاهایتان نیز همان!
 -اگر بخواهید کلید را در بار مخفی کنید و امید داشته باشید که راهزن کلید را پیدا نمی‌کند هم کار اشتباهی مرتکب شده اید. راهزنان مو به مو بار شما را خواهند گشت.
-اگر بخواهید صندوق را از مسیر 1 و کلید را از مسیر 2 به مقصد B بفرستید  در کمال شرمندگی باید بگوییم باز هم اشتباه کرده اید. در همه مسیرها یکی از همکاران راهزنان منتظر شما هستند تا کلید را از شما بگیرند! 

دانشگاه برنامه نویسان کاربرد اعداد اول در رمزنگاری

راه حل این مساله چندان هم سخت نیست. کافی است دوست شما از شهر B یک صندوق با قفل باز برای شما بفرستد (و کلیدِ قفل دست دوست شما باقی بماند) شما طلاها را در صندوق قرار دهید و قفل را ببندید و به مقصد بفرستید. همانطور که میبینید دیگر نیازی نیست که کلید را با صندوق ارسال کنید و کلید در اختیار گیرنده قرار دارد.

همه مطالبی که عنوان شد اساس و پایه کلید عمومی و کلید خصوصی در رمزنگاری است. این بار بیایید با هم وارد سایت جیمیل شویم و ببینیم برای ورود با نام کاربری و رمز عبورمان چه اتفاقی می افتد:

وقتی شما وارد سایت gmail می شوید، مرورگر شما از سرور جیمیل درخواست یک کلید عمومی می‌کند (همان گاوصندوقِ در باز که در داستان بالا گفته شد). سرور به مرورگر کلید عمومی را ارسال می‌کند و مرورگر شما با استفاده از کلید عمومی داده  های شما که همان نام کاربری و رمزعبور است

را رمزنگاری می‌کند و به سرور ارسال میکند. حال اگر در میان راه هکرها (یا همان راهزنها) به این داده ها دسترسی پیدا کنند اصلا جای نگرانی نیست، زیرا تا زمانی که کلید خصوصی در اختیار نداشته باشند نمی‌توانند پیام را رمزگشایی کنند. (کلید خصوصی در اختیار چه کسی است؟ سرور جیمیل! پس فقط سرور جیمیل می تواند داده های شما را رمزگشایی کند)

اگر تا اینجای مطلب را با دقت خوانده باشید حتما این سوال برایتان پیش می‌آید که عدد اول کجای داستان قرار دارد و کاربرد این اعداد در رمزنگاری چیست؟ در پاسخ باید گفت که مبنای ساخت کلیدهای عمومی و خصوصی اعداد اول هستند.

نکته‌ی جالبی که می‌توان در مورد اعداد اول به آن اشاره کرد که در رمزنگاری به کار می‌آید، امکان تقسیم تمام اعداد، به اعداد اول است. یعنی می‌توان اعداد اول را به گونه‌ای در هم ضرب کرد، تا حاصلضرب، عددی باشد که در نظر داریم. برای مثال عدد 138 را می‌توان از ضرب سه عدد 2 در 3 در 23 که همگی عدد اول هستند به دست آورد. این موضوع در مورد اعداد بزرگ‌تر نیز صادق است، برای مثال می‌توان عدد 347423930 را با ضرب کردن اعداد 2 در 5 در 7 در 19 در 97 در 2693 به دست آورد. به این عمل قانون فاکتورگیری عدد اول گفته می‌شود. علاوه بر این هر عدد طبیعی را فقط می‌توان به یک مجموعه عدد اول تجزیه کرد. نکته اساسی اینجاست که اگر از بهترین الگوریتم موجود به منظور تقسیم یک عدد 200 رقمی یا 500 رقمی به فاکتورهای اول آن استفاده کنیم، بهترین سوپرکامپیوتر موجود نیز به زمان بسیار بسیار زیادی برای اتمام کار خود نیاز خواهد داشت، شاید معادل عمر کره زمین!  پس به زبان ساده، محدودیتی برای پیدا کردن فاکتورهای اول یک عدد وجود دارد و این موضوع برای امنیت در رایانه‌های مدرن بسیار حیاتی و ضروری است. در الگوریتمهای رمزنگاری با استفاده از دو عدد اول بزرگ حاصلضرب آنها را که یک عدد خیلی بزرگ است پیدا می‌کنند و با استفاده از این عدد خیلی بزرگ عملیات رمزگذاری پیام شروع می‌شود. حال اگر بخواهیم پیام رمزشده را رمزگشایی کنیم به آن دو عدد اولی که با آن عدد خیلی بزرگ تولید شده است نیاز داریم.

پس بیایید با هم یک بار دیگر مرور کنیم:

کلید عمومی و خصوصی با استفاده از اعداد اول تولید می‌شوند. پیامها با استفاده از کلید عمومی گیرنده کدگذاری می‌شود و با استفاده از کلید خصوصی که فقط گیرنده دارد رمزگشایی می‌شود. اگر در بین راه کلید عمومی توسط هکرها به اعداد اول شکسته شوند با استفاده از اعداد اول تولیدی می‌توانند به کلید خصوصی دسترسی پیدا کنند و پیام را رمزگشایی کنند. اما همانطور که پیش تر گفته شد شکسته شدن اعداد بزرگ به فاکتورهای اول بسیار زمانبر است و عملا امکان پذیر نیست.

دانشگاه برنامه نویسان کاربرد اعداد اول در رمزنگاری

اساس و پایه رمزنگاری اعداد اول است و نبود راهی بهینه برای یافتن فاکتورهای اول یک عدد بزرگ، بنیان رمزنگاری در کامپیوترها است.


برای اینکه بتوانیم بهتر درمورد رمزنگاری صحبت کنیم به بررسی چند تعریف در حوزه رمزنگاری که مورد نیاز است می‌پردازیم:

متن آشکار(Plaintext) : متنی که رمز نشده است.

متن رمز(Ciphertext): متنی که رمز شده است

رمز(Cipher): الگورتیمی که Plaintext را به Ciphertext تبدیل میکند را گویند

کلید(Key): اطلاعاتی که در Cipher استفاده میشود و فقط فرستنده و یا گیرنده آن را میدانند

رمز گذاری(Encipher,Encrypt): تبدیل Plaintext به Ciphertext

رمز گشایی(Decipher,Decrypt): استخراج Plaintext از Ciphertex

رمز نگاری(Cryptology): الگوریتمهایی که اصول روشهای رمزگذاری و رمزگشایی را تعیین میکند.

در توضیح الگوریتمها از اصطلاحات رمزنگاری به صورت انگلیسی استفاده شده است تا درک و فهم الگوریتم ها بهتر صورت گیرد.

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

رمزنگاری متقارن(Symmetric Key Cryptography):

در روش متقارت یک کلید برای encrypt و decrypt کردن  Cipher Text وجود دارد که به آن کلید معمولا secret key گفته می‌شود (به همین دلیل به این روش  متقارن گفته می‌شود ).

متن یا فایلی که با یک کلید و الگوریتم در مبدا ، رمز (encrypt) می‌شود با همان کلید و همان الگوریتم در مقصد باز می‌شود. به عبارت دیگر دری که قفل شد فقط با همان کلید باز می‌شود.

در این روش کلید باید بین فرستنده و گیرنده secret نگاه داشته شود زیرا که با داشتن کلید به راحتی می‌توان Cipher Text را Decrypt کرد. یکی از مشکلات اصلی این الگوریتمها این است که چگونه این کلید را برای ارتباط با طرف مقابل (مقصد) به دستش برسانیم. (زیرا ممکن است خط انتقال امن نباشد.)

از الگوریتمهای این روش می‌توان به  AES،   DES،  3DES،  Blowfish،  RC4 و … اشاره کرد.

رمزنگاری نامتقارن(Asymmetric)

رمز نگاری نا متقارن برای جایگزینی روش رمز نگاری متقارن به وجود نیامده است بلکه برای تکمیل روش رمز نگاری متقارن به وجود آمده است که به آن اصطلاح کلید عمومی گفته میشود و برای رسیدن به دو هدف طراحی شده است

  • حل مساله در اختیار داشتن کلید در روش رمز نگاری متقارن
  • امضای دیجیتال

ویژگی های روش نامتقارن را میتوان موارد زیر عنوان کرد

  • رسیدن به encryption key از decryption key از لحاظ محاسبانی نا ممکن است
  • در حفظ محرمانگی(Confidentiality) رمزگذاری امری همگانی است و نیازی به اشتراک گذاری اطلاعات محرمانه وجود ندارد
  • در حفظ محرمانگی(Confidentiality) رمزگذاری امری اختصاصی بوده است و محرمانگی پیام ها محفوظ می ماند

برای رمزنگاری گام های زیر را بر می داریم

  • هر کاربر یک جفت public key و private key تولید میکند
  • کاربران public key خود را به صورت عمومی اعلام می کنند
  • همگان قادر به ارسال پیام رمز شده برای هر کاربر دلخواه با استفاده از public key او هستند
  • هر کاربر میتواند با استفاده از private key پیام هایی که با public key او رمز شده است را رمز گشایی کند.

از الگوریتمهای این روش می‌توان به  RSA و ElGamal اشاره کرد.

در این نوشته سعی شد تا به زبان ساده مفاهیم رمزنگاری بیان شود. اگر همچنان علاقه‌مند هستید که مطالب بیشتری در اینباره یاد گیرید بد نیست فایل آموزشی رمزنگاری نامتقارن که آزمایشگاه داده و شبکه دانشگاه شریف منتشر کرده است را بخوانید: کلیک کنید.