برای این آموزش هیچ پیش نیازی وجود نداره و از هیچ لایبری خاصی استفاده نمیشه و همه چی از ۰ تا ۱۰۰ گفته و پیاده سازی میشه و مهمترین نکته کسایی هم که از ریاضی بدشون میاد هم میتونن کامل بخونن و درک بکنن چون نیازی به ریاضیات پیشرفته و درک عمیقی نداره و ریاضیات نسبتا متوسط هم جوابه .
بصورت معمولی بگیم RSA یک روزش رمزنگاری نا متقارن (asymmetric) هستش که خیلی استفاده ازش رایج هستش و دوتا کلید داره یک کلید خصوصی برای رمزگشایی (decryption) و یک کلید عمومی برای رمزنگاری (encryption) این تعریف برای همه الگوریتم های رمزنگاری نا متقارن یکی هستش و در سال 1978 این الگوریتم RSA درست شدش, خب اینا زیاد مهم نیستش بیایم یخورده شفافتر بکنیم منظورمون از کلید های خصوصی و عمومی.
خب بیاید فرض کنیم شما بخاطر کرونا نمیتونید برید به محل کارتون و نوع کاری هم که دارید خیلی حساسه و اطلاعات حساسی از مشتری هاتون دیافت میکنید و یا ارسال میکنید و هیچکس بجز خودتون و مشتری نباید ازشون اگاه بشه ولی مشکل اینجاست که بخاطر حساسیت زیاد نه میتونید این اطلاعات از طریق اینترنت رد و بدل کنید و نه از طریق پست چون حتی ممکنه خود پستچی نامه بخونه و یا حتی گمش بکنه یا بدزدنش و اگه کسی نامه باز بکنه اطلاعات مهمی میبینه که نباید میدید و خطرات زیادی واسه مشتری ایجاد میشه یا حتی واسه خودتون . خب چون حساسیت موضوع درک کردید تصمیم گرفتید یکسری جعبه برای رد و بدل کردن اطلاعات بسازید و این جعبه ها یکسری خصوصیات جالب دارن اول اینکه کلید باز کردنشون فقط و فقط دست خودتون هستش و خصوصیت دیگش هم این هستش بعد از اینکه مشتری اطلاعات خودشو تو جعبه گذاشت جعبه قفل میشه و دیگه حتی خود مشتری هم به اطلاعات داخل جعبه دسترسی نداره , پس حتی اگه این جعبه ها موقع حمل و نقل گم بشن و یا کسی سعی کنه بزور اطلاعات داخل جعبه برداره کارش ناموفق میمونه چون نه رمز جعبه بلد و نه این جعبه های جالب قابل تخریب هستن
خب این RSA هم شبیه همین هستش یکسری کلید رمزنگاری بصورت عمومی ( همون جعبه ها ) به همه میده که تا بشه باهاش اطلاعات خودشونو موقع ارسال به شما امن نگه دارن و بعد اتمام کار بدون داشتن کلید خصوصی (کلید جعبه) حتی خودتونم نمیتونید به اطلاعات رمزنگاری شده دسترسی داشته باشید
خب این کلیت ماجرا بودش حالا بریم ببینیم چطور اصلا پیاده سازی میشه.
در واقع RSA بر پایه اعداد اول کار میکنه حالا عداد اول چی هستن محض یادآوری
عدادی هستن که بجز 1 و به خودشون به هیچ عدد دیگه موقع تقسیم کردن عدد صحیح نمیدن مثلا 7 فرض کنید به هیچ عددی بجز خودش و 1 موقع تقسیم عدد صحیحی نمیده مثلا 3.5 = 2 / 7 و یا به زبان دیگه اصلا نمیشه با ضرب کردن دو عدد صحیح دیگه به اون رسید مثلا برای رسیدن به 7 باید عدد 2 * 3.5 بشه تا نتیجه 7 بدست بیاد یا به طریق دیگه هیچ فاکتوری (عاملی) بجز خودش و 1 نداره
خب ما برای شروع نیاز داریم دوتا عدد اول انتخاب بکنیم و به این دوتا اعدد اول میگیم a و b
a = 7
b = 5
نکته مهم : بین اعداد انتخابی عدد 2 نباشه و همینطور هر دو عدد یکسان نباشن اگه هرکدوم از این دو شرط نقص بشن الگوریتم خراب میشه
نکته خیلی مهمتر : سعی کنید اگر نیاز نیستش اعداد اول کوچیک انتخاب نکنید دلیلشو اخر مقاله میگم
و هیمنطور نیاز داریم تا حاصل ضرب این دوتا اعدد اول یکجا ذخیره کنیم خب اینجا تو متغیر c ذخیره میکنیمش
c = a * b
و به یک متغیر phi برای ذخیره تعداد اعدادی که تو بازه 1 تا عدد c هستن و نسبت به c متباین یا کوپرایم (coprime) باشن نیاز داریم. اصلا کوپرایم چیه ؟
زمانی میگیم یک عدد کوپرایم عدد دیگه هستش که بزرگترین مضرب مشترک(ب م م ) اون دو عدد 1 باشه و یا هیچ فاکتور (عاملی) بزرگتری بجز 1 بین اون دو عدد مشترک نباشه مثلا.
آیا عدد 13 کوپرایم عدد 4 هستش ؟ اره ولی چرا؟ چون فاکتور های عدد 13 اعداد 1 , 13 هستن و فاکتور های عدد 4 عداد 1, 4, 2 هستن و بزرگترین عدد مشترک بین فاکتور ها عدد 1 هستش
آیا عدد 11 کوپرایم عدد 10 هستش ؟ بله چون فاکتور های عدد 11 اعداد 1, 11 هستن و فاکتورهای 10 اعداد 1, 2, 5, 10 و بزرگترین عدد مشترکشون عدد 1 هستش
آیا عدد 13 کوپرایم عدد 26 هستش ؟ نه چون فاکتور های عدد 13 اعداد 1, 13 هستن و فاکتور های عدد 26 اعداد 1, 2, 13, 26 و بزرگترین فاکتور مشترک عدد 13 هستش درصورتیکه باید عدد 1 برای کوپرایم شدن میشدش
حالا بیایم a , b, c, phi محاسبه کنیم با فرض اینکه ما دو عدد اول خودمونرو اعداد 2 و 7 انتخاب کردیم
a = 5
b =7
c = a * b = 35
خب بریم ببینیم تعداد کوپرایم بین رنج 1 تا c یعنی 1 تا 35 چندتا هستن نسبت به عدد c برای سادگی بجای گفتن ایا فلان عدد کوپرایم فلان عدد هستش از علامت Φ (فی) استفاده میکنیم. اینم یک سایت خوب برای اینکه بفهمیم ایا یک عدد کوپرایم عدد دیگه هستش یا نه
کوپرایم های درست :
1 Φ 35 : "T" | 2 Φ 35 : "T" | 3 Φ 35 : "T" | 4 Φ 35 : "T" | 6 Φ 35 : "T" | 8 Φ 35 : "T" | 9 Φ 35 : "T"
11 Φ 35 : "T" | 12 Φ 35 : "T" | 13 Φ 35 : "T" | 16 Φ 35 : "T" | 17 Φ 35 : "T" | 18 Φ 35 : "T" | 19 Φ 35 : "T" | 22 Φ 35 : "T" | 23 Φ 35 : "T" | 24 Φ 35 : "T" | 26 Φ 35 : "T" | 27 Φ 35 : "T" | 29 Φ 35 : "T" | 31 Φ 35 : "T" | 32 Φ 35 : "T" | 33 Φ 35 : "T" | 34 Φ 35 : "T"
کوپرایم های نادرست :
5 Φ 35 : "F" | 7 Φ 35 : "F" | 10 Φ 35 : "F" | 14 Φ 35 : "F" | 15 Φ 35 : "F" | 20 Φ 35 : "F" | 21 Φ 35 : "F" | 25 Φ 35 : "F" | 28 Φ 35 : "F" | 30 Φ 35 : "F" | 24
و برای اینکه اینا دستی هم برسی بکنید میتونید از سایت بالا استفاده کنید. خب تعداد کل کوپرایم های ها ما شدش 24 پس
phi = 24
یک راه ساده برای بدست اوردن phi استفاده از فرمول زیر هستش
phi = (a-1) * (b-1)
phi = (5-1) * (7-1) = 24
خب الا تمام چیزایکه برای ساخت کلید های خصوصی و عمومی نیازه داریم یعنی c, phi. برای ساخت کلید عمومی رمزنگاری (Encryption) ما باید کوپرایمی برای phi پیدا بکنیم که از 2 بزرگتر و از عدد phi کوچیکتر باشه که همزمان کوپرایم عدد c هم باشه
2 < E < phi
2 < E < 24
خب کوپرایمی که بین این بازه هستش اعدد 11, 13, 17, 19, 23 هستن و اگه رنج بزرگتری داشتیم میتونستیم چندین کوپرایم دیگه هم داشته باشیم برای اسونی کوچیکترین عدد پیدا شده انتخاب میکنیم یعنی 11 و ازش برای ساخت کلید خصوصی استفاده میکنیم
مثال : فاکتور های عدد 11 اعداد 1, 11 و فاکتور های عدد 24 اعداد 1, 2, 3, 4, 6, 8, 12, 24 چون بزرگترین مضرب مشترک عدد 1 هستش کوپرایم هستن برای عدد 35 یا همون c هم کوپرایم هم محسوب میشن چون بزرگترین مضرب مشترک یا همون ب م م اونها عدد 1 هستش
خب تا اینجا ما داریم
خب الا وقتشه کلید خصوصی رمزگشایی(Decryption) بسازیم یا پیدا بکنیم فرمولی که باهاش کلید خصوصی بدست میاریم به شکل زیر هستش
(D * E) % phi = 1
(D * 11) % 24 = 1
به زبون ساده ما باید یک عددی (D) پیدا بکنیم که حاصل ضربش با 11 (E) , اگه تقسیم بر 24 (phi) بکنیم مقدار باقی ماندش مساوی با 1 باشه
چندتا نکته :
رنجی که ما دنبال عدد درست برای D هستیم به این صورت محاسبه میشه از phi+1 تا phi+n که این n میتونه هر چقدر میخواد بزرگ باشه من اینجا 1000 انتخاب کردم
انجام این عملیات ها با دست و یا روی برگه خیلی تاقت فرسا هستش واسه همین این محاسبات با کامیپوتر انجام میدیم
ما میتوینم به تعداد خیلی زیادی کلید داشته باشیم و در اخر از بین گزینه ها یکی انتخاب میکنیم و ادامه میدیم مثلا برای جواب بالا ما کلید های خصوصی (D) ... 35, 59, 83, 107 , داریم که برای آسونی اینجا کوچیکترین انتخاب میکنیم
خب عدد صحیح برای D ما اعدد ... 35, 59, 83, 107 هستن میتونیم بصورت دلخواه یکی انتخاب کنیم پس الا ما این چیزا داریم
خب کلید ها از دو بخش تشکیل میشن برای کلید عمومی (e , c) و برای کلید خصوصی (d , c) و در این صورت کلید های ما اینا هستن
کلید عمومی رمزنگاری (E) : (11, 35)
کلید خصوصی رمزگشایی (D) : (59, 35)
خب تبریک تا اینجا نود درصد راه رفتیم فقط مونده بفهمیم چطور باید ازشون استفاده کنیم :))
اینکار هم خیلی ساده دوتا مرحله داره مرحل اول تبدیل دیتا به معادل کد ascii اونا هستش اگه نیاز بودش و مرحله بعد بیایم تک تک اونارو با یک فرمول رمزنگاری یا رمز گشایی کنیم
اول میایم یکسری عدد معمولی رمزنگاری میکنیم مثلا
24 , 32 , 11
الا تک تک این عدد هارو به توان E که مقدارش 11 هستش میرسونیم و بعد میزان باقی ماندش بر عدد c بدست میاریم
(number) ** e % c
(11 ** 11 ) % 35 : 16
(24 ** 11 ) % 35 : 19
(32 ** 11 ) % 35 : 23
خب حالا بیاید همینو رمزگشایی کنیم
خب دیتای که میخوایم رمزگشایی کنیم همون دیتای هستش که مرحله قبل با کلید عمومی رمزنگاریش کردیم یعنی
encrypted_data : 16, 23, 19
خب برای رمز گشایی از فرمول زیر استفاده میکنیم
(encrypted_data) ** d % c
(16 ** 59 ) % 35 : 11
(19 ** 59 ) % 35 : 24
(23 ** 59 ) % 35: 32
خب دیدیم که یک الگوریتم رمزنگاری نامتقارن چیکار میکنه و تنها کاری که میکنه این هستش که میتونه یک عددی به عدد دیگه تبدیل بکنه و باز همونو برگردونه به حالت اولیش باتوجه یک یک فرمول و چند عدد :)
خب یادتونه گفتم اگه نیازی نیستش عداد اول کوچیک انتخاب نکنید ؟ الا میبینیم چرا اینکارو باید بکنیم خب بیاید عدد های 35 و 36 و 100 رمزنگاری کنیم و باز رمزگشایی کنیم
encrypt :
35 ** 11 % 35 = 0
36 ** 11 % 35 = 1
100 ** 11 % 35 = 25
decrypt :
0 ** 59 % 35 = 0
1 ** 59 % 35 = 1
25 ** 59 % 35 = 30
خب دقت کردید؟ الگوریتم کار نمیکنه اصلا جالا دلیلش چیه ؟ بخاطر اینکه حداکثر عددی که میتونیم رمزنگاری بکنیم و برعکس مسقیما وابسته به مقدار c که الا مقدار 35 داره و از 35 بع بعد الگوریتم کار نمیکنه :))
کلیت ماجرا همینه و هر نوع الگوریتم دیگه و لایبری واسه RSA میشناسید بیس اونا همینه فقط یخورده بهشون پر بال دادن مثلا کلید های ساخته شده به یک نوع متن و یا هش تبدیل میکنن که شکل متفاوتی داشته باشه و یا از الگوریتم های بهینه تری برای پیدا کردن اعداد استفاده میکنن مثل استفاده از الگوریتم اقلیدس برای پیدا کردن بزرگترین مضرب مشترک یا ب م م
