رمزنگاری مقدماتی : ریاضیات و شرح کارکرد الگریتم های نامتقارن

در این قسمت میخوایم وارد ریاضیات بشیم که خیلی هم ساده هستند، پنیـــــک نکنید ! و بعد وارد الگریتم های نامتقارن میشیم و یکم تکنیکال تر توضیحش میدیم و میخوایم یکم دید ریاضی داشته باشیم که ببینیم اون پشت چه اتفاقی می افته، دید ریاضی کمی که توی قسمت مقدماتی پیدا میکنید خیلی لازمه و اگر بخواید بعدا روی حملات هم کار کنید به دردتون میخوره، ریاضیات پیشرفته ترو (که باز تکرار میکنم ، اونا هم سخت نیستن) میزاریم برای سری پیشرفته

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

نکته : ما هم میتونیم بگیم 2و6 جزو فاکتور های 12 هستن ، هم میتونیم بگیم 6و4 جزو فاکتور های 12 هستن، دقت کنید که اینجا نه جمع 6و4 میشه 12 و نه ضربشون ولی میتونیم بگیم 6و4 جزو فاکتور های 12 هستن، یا میتونیم بگیم 1و3 جزو فاکتور های 12 هستن

اعداد اول : اعداد اول اعدادین که جز خودشون و 1 به عدد دیگری بخش پذیر نیستن، مثلا عدد 2 به خودش فقط بخش پذیره (یعنی تقسیم میشه و جوابش عدد صحیح میاد) و 1

اعداد نیمه اول : این مفهوم توی زبان فارسی جایگزینی نداره و ما بهش میگیم نیمه اول، اعداد نیمه اول اعدادی هستن که عوامل یا فاکتور هاشون اعداد اول هستن، بجز 1 و خود عدد، مثلا نگاه کنید به مثال عدد 21 ، عدد 21 به 1،3،7،21 بخش پذیره، اگر 1 و 21 رو حذف کنیم میرسیم به 3و7 که جفتشون عدد اول هستن ، پس اینجا 21 میشه نیمه اول، پس به طور خلاصه هر عددی که به اعداد اول بخش پذیر باشه میشه نیمه اول !

نکته : با ضرب اعداد اول در هم میتونیم به اعداد نیمه اول برسیم ، مثلا 2و3 رو ضرب کنیم میشه 6 و میشه نیمه اول، 2×5 یا 3×7 و...

باقی مانده : ما در تقسیم سه رکن داریم، باقی مانده، خارج قسمت و مقسوم علیه ، مثلا 8 تقسیم به 4 میشه 2 و باقی مونده میشه صفر، 4 میشه مقسوم علیه و 2 میشه خارج قسمت

مثلا 12 تقسیم به 5 باقی موندش میشه 2 ، مثلا 15 تقسیم به 3 خارج قسمتش میشه 5 و باقی مانده صفر

hpn# bc
12%5
2

ما در برنامه نویسی هم با علامت درصد "%" باقی مانده رو نشون میدیم

توان : خیلی راحته ، بجای اینکه بگیم عدد 2 رو 4 بار در خودش ضرب کن میگیم 2 به توان 4

hpn# bc
2^4
16

لگاریتم : لگاریتم برعکس شده توان هست، ما توی توان میگیم 2 به توان 4 میشه 16 ، توی لگاریتم میگیم 16 در مبنای 2 میشه چند؟ در واقع لگاریتم برای این آمد که ما میخواستیم ببینیم 2 رو چند بار درخودش ضرب کنیم (به توان چند برسونیم) میشه 16 ، پس امدیم 16 و 2 رو گذاشتیم تو لگاریتم و جواب میشه 4 ، یعنی 2 رو 4 بار در خودش ضرب کنی میشه 16

دیدید چه راحت بود؟ ?

بررسی الگریتم RSA :

وقتی میخوایم توی الگریتم RSA کلید بسازیم برای شروع دوتا عدد اول میخوایم، رندوم ما 7 و 19 رو انتخاب میکنیم، اینجا PوQ رو داریم، حالا باید این دوتارو ضرب کنیم تا N بدست بیاد (چرا شو کاری نداشته باشید) و اگر تونستید بگید این N که عدد 133 هست چه عددیه؟ عدد Semi-Prime یا نیمه اوله (چون از ضرب دوتا عدد اول بدست آمده) ، حالا باید Totient رو حساب کنیم که میاد و دوتا عدد PوQ ای که اول داشتیم رو یکی ازش کم میکنه و ضرب هم میکنه که اینجا میشه 108، حالا بریم سراغ ساخت کلید و رمز کردن

برای ساخت کلید عمومی میاییم و یه عدد انتخاب میکنیم که حتما اول باشه، حتما از T کوچک تر باشه و عاملش از T نباشه، یعنی اگر تقسیمش کردیم بر 108 باقی ماندش 0 نیاد، ما میاییم عدد 3 رو انتخاب میکنیم و میبینیم باقی ماندش 0 میاد، این کنکله ! میریم سراغ 5 و میبینیم باقی مانده داره، خب این خوبه ولی ضعیفه، میریم سراغ 29 و میبینیم باقی ماندش 21 میاد، همین خوبه، میتونیم ادامه بدیم ولی خب فعلا بسنده میکنیم به همین؛ برای کلید خصوصی میاییم و یه عددی انتخاب میکنیم که توی فرمول صدق کنه، یعنی یه عددی باشه که ضربدر کلید عمومی ، باقی ماندش بر T بشه 1 ، که خب مثلا عدد 41 رو انتخاب میکنیم و میبینیم این شرطو داره

حالا وقت انکریپت کردنه ، ما یه پیام داریم اینجا که عدد 55 هست، فرمول Encrypt کردن اینطوریه که اول اون پیام رو به توان کلید عمومی میرسونیم و باقی موندشو بر N بدست میاریم که بهش میگن Cipher Text

اینجا 55 رو به توان 29 رسوندیم و باقی ماندش بر 133 شد 118 که Cipher Text ما هست، برای Decryption میاییم و 118 رو به توان کلید خصوصی میرسونیم و باقی ماندش بر N میشه پیام اصلی ما که 118 به توان 41 باقی ماندش بر 133 میشه 55 که پیام ماست :)

نکته : خودتون تست کنید و اینبار پیام رو بجای کلید عمومی با کلید خصوصی تست کنید و با کلید عمومی باز کنید و ببینید که نتیجه همونه

بررسی امنیت الگریتم RSA از دیدگاه ریاضی :

Semi-Prime Factorization :

امنیت الگریتم RSA وابستس به تجزیه اعداد نیمه اول !

توی ریاضی ما نمیتونیم ببینیم چه اعداد اولی در هم ضرب شدن که یه عدد نیمه اول بدست امده، مثلا عدد 133 تو مثال عکس 3 رو نگاه کنید، نمیتونید بفهمید از ضرب 7 و 19 بدست آمده، اگر فکر میکنید میتونید بفهمید و راحته بگید عدد 2623 که عدد نیمه اوله از ضرب چه اعداد اولی بدست آمده ☺️

از سال 1991 سازنده های RSA امدن 54 تا عدد نیمه اول منتشر کردن و براش جایزه گذاشتن که کیا میتونن بگن چه این اعداد نیمه اول از ضرب چه اعدادی بدست آمدن ، تا سال 2018 فقط 20 تا از اون اعداد بدست امده و هنوز 34 تای دیگه از اون اعداد مبهم هستن :) اون اعداد تو رنج 700 بیت بودن !

وقتی بعد 20 سال یه عدد 700 بیتی کشف بشه، اگر طول کلید شما 1024 باشه بنظرتون امن نیست ؟ طول کلید توصیه شده 2048 عه و مطمئن باشید اگر این عدد رو انتخاب کنید هیچوقت نمیتونن بفهمن کلیدتون چی بوده! هرچند شما 20-30 سال هم بزاری نمیتونی یه کلید 1024 بیتی رو بفهمی :))

عدد 2623 فقط 12 بیته ! فکر کنید یه عدد که 100 برابر این باشه چه امنیتی داره !!

بررسی امنیت الگریتم Diffie-Hellman از دیدگاه ریاضی :

در اینجا اول رز و الکس سر دوتا عدد توافق میکنن، یکی 13 که P عه و یکی 6 که G هست ، بعد هر کدوم عشقی یه عدد برای خودشون انتخاب میکنن ، حالا کاری که باید بکنن اینه که G یا همون 6 رو به توان عدد خودشون بکنن، برای الکس 6 به توان 5 و برای رز 6 به توان 4 ، بعد باقی ماندشو بر 13 بدست بیارن ، برای الکس شد 2 و برای رز شد 9، این 2 و 9 اینجا میشه یه چیز عمومی( Public Key نمیشه ها، میشه یه چیزی) حالا این چیزو به هم دیگه میدن و باید این عدد رو به توان کلید خصوصی خودشون کنن، الکس 9 رز رو به توان 5 خودش میکنه و رز هم 2 الکس رو به توان 4 خودش، حالا باقی ماندش بر 13 رو میگیرن و هردو به یه عدد رسیدن، هردو به 3 رسیدن که کلید خصوصی مشترک بینشونه!

Discrete Logarithm Problem :

اگر خواستید روی بحث امنیت الگریتم دفی هلمن کار کنید باید مسئله لگاریتم گستته رو درک کنید!

ما یه توان داشتیم و یه لگاریتم، اگر ما داشته باشیم G به توان X میشه N

G^X=N

خیلی سادست اگر G و X رو داشته باشیم و به N برسیم، ولی خیلی سخته که G و N رو داشته باشیم و به X برسیم؛ دقت کنید گفتم سخته نگفتم نشدنیه، حالا ما میاییم و مسئله لگاریتم رو گسستش میکنیم، یعنی چیکار میکنیم ؟

G^X MOD P = N 

میگیم خب بیا x رو بکن حاصل باقی مانده یه چیزی ! حالا اگر G-P و N رو داشته باشیم، غیر ممکنه برسیم به X، چرا این حرفو میزنم؟

باقی مانده تقسیم 12 بر 5 میشه 2 - باقی مانده تقسیم 17 بر 5 میشه 2 - باقی مانده تقسیم 22 بر 5 هم میشه 2 - باقی مانده تقسیم 27 بر 5 هم میشه 2 تا ..بینهایت

حالا من به شما 2 و 5 رو بدم بگم عدد X رو پیدا کن، دمـــارت در میاد !

تنها راهش اینه که بشینی و تمام اعداد رو امتحان کنی که اوووووه خیلی طول میکشه و به این روش میگن Brute Force که میشه گفت نشدنیه !

در این مطلب شما با مفاهیم پایه ریاضی و فرمول های الگریتم های نامتقارن آشنا شدید، دیدید که چیز سختی اصلا نیست ! کل رمزنگاری و ریاضیات پیچیده ای که میگن همینه ! همش با توضیحات ساده قابل فهمه؛ ولی اگر بخواید الگریتمی طراحی کنید... یکم ریزه کاری و سختی و دانش ریاضی بالایی میخواد که واقعا نیازه متخصص باشید و الگریتمتونم توسط چندین متخصص خبره تست بشه !

در مطلب بعدی سراغ رمزنگاری منحنی بیضوی یا Elliptic Curve Cryptography میریم، هرجای این مطلب سوال یا ابهام یا انتقادی بود در خدمتم، یاعلی ;)