آموزش رمزنگاری RSA  و پیاده سازی در Python

برای این آموزش هیچ پیش نیازی وجود نداره و از هیچ لایبری خاصی استفاده نمیشه و همه چی از ۰ تا ۱۰۰ گفته و پیاده سازی میشه و مهمترین نکته کسایی هم که از ریاضی بدشون میاد هم میتونن کامل بخونن و درک بکنن چون نیازی به ریاضیات پیشرفته و درک عمیقی نداره و ریاضیات نسبتا متوسط هم جوابه .RSAاصلا RSA چیه‌ ؟بصورت معمولی بگیم RSA یک روزش رمزنگاری نا متقارن (asymmetric) هستش که خیلی استفاده ازش رایج هستش و دوتا کلید داره یک کلید خصوصی برای رمزگشایی (decryption) و یک کلید عمومی برای رمزنگاری (encryption) این تعریف برای همه الگوریتم های رمزنگاری نا متقارن یکی هستش و در سال 1978 این الگوریتم RSA درست شدش, خب اینا زیاد مهم نیستش بیایم یخورده شفافتر بکنیم منظورمون از کلید های خصوصی و عمومی.خب بیاید فرض کنیم شما بخاطر کرونا نمیتونید برید به محل کارتون و نوع کاری هم که دارید خیلی حساسه و اطلاعات حساسی از مشتری هاتون دیافت میکنید و یا ارسال میکنید و هیچکس بجز خودتون و مشتری نباید ازشون اگاه بشه ولی مشکل اینجاست که بخاطر حساسیت زیاد نه میتونید این اطلاعات از طریق اینترنت رد و بدل کنید و نه از طریق پست چون حتی ممکنه خود پستچی نامه بخونه و یا حتی گمش بکنه یا بدزدنش و اگه کسی نامه باز بکنه اطلاعات مهمی میبینه که نباید میدید و خطرات زیادی واسه مشتری ایجاد میشه یا حتی واسه خودتون . خب چون حساسیت موضوع درک کردید تصمیم گرفتید یکسری جعبه برای رد و بدل کردن اطلاعات بسازید و این جعبه ها یکسری خصوصیات جالب دارن اول اینکه کلید باز کردنشون فقط و فقط دست خودتون هستش و خصوصیت دیگش هم این هستش بعد از اینکه مشتری اطلاعات خودشو تو جعبه گذاشت جعبه قفل میشه و دیگه حتی خود مشتری هم به اطلاعات داخل جعبه دسترسی نداره , پس حتی اگه این جعبه ها موقع حمل و نقل گم بشن و یا کسی سعی کنه بزور اطلاعات داخل جعبه برداره کارش ناموفق میمونه چون نه رمز جعبه بلد و نه این جعبه های جالب قابل تخریب هستن خب این RSA هم شبیه همین هستش یکسری کلید رمزنگاری بصورت عمومی ( همون جعبه ها ) به همه میده که تا بشه باهاش اطلاعات خودشونو موقع ارسال به شما امن نگه دارن و بعد اتمام کار بدون داشتن کلید خصوصی (کلید جعبه) حتی خودتونم نمیتونید به اطلاعات رمزنگاری شده دسترسی داشته باشید خب این کلیت ماجرا بودش حالا بریم ببینیم چطور اصلا پیاده سازی میشه.چطوری کاری میکنه RSA ؟در واقع RSA بر پایه اعداد اول کار میکنه حالا عداد اول چی هستن محض یادآوری Prime numbersعدادی هستن که بجز 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) باشن نیاز داریم. اصلا کوپرایم چیه ؟Prime numbers 13 and 4زمانی میگیم یک عدد کوپرایم عدد دیگه هستش که بزرگترین مضرب مشترک(ب م م ) اون دو عدد 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 برای سادگی بجای گفتن ایا فلان عدد کوپرایم فلان عدد هستش از علامت Φ (فی) استفاده میکنیم. اینم یک سایت خوب برای اینکه بفهمیم ایا یک عدد کوپرایم عدد دیگه هستش یا نه code exampleکوپرایم های درست : 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ساخت کلید های عمومی و خصوصیKeysخب الا تمام چیزایکه برای ساخت کلید های خصوصی و عمومی نیازه داریم یعنی c, phi. برای ساخت کلید عمومی رمزنگاری (Encryption) ما باید کوپرایمی برای phi پیدا بکنیم که از 2 بزرگتر و از عدد phi کوچیکتر باشه که همزمان کوپرایم عدد c هم باشه2 < E < phi2 < E < 24 code example خب کوپرایمی که بین این بازه هستش اعدد 11, 13, 17, 19, 23 هستن و اگه رنج بزرگتری داشتیم میتونستیم چندین کوپرایم دیگه هم داشته باشیم برای اسونی کوچیکترین عدد پیدا شده انتخاب میکنیم یعنی 11 و ازش برای ساخت کلید خصوصی استفاده میکنیممثال : فاکتور های عدد 11 اعداد 1, 11 و فاکتور های عدد 24 اعداد 1, 2, 3, 4, 6, 8, 12, 24 چون بزرگترین مضرب مشترک عدد 1 هستش کوپرایم هستن برای عدد 35 یا همون c هم کوپرایم هم محسوب میشن چون بزرگترین مضرب مشترک یا همون ب م م اونها عدد 1 هستشخب تا اینجا ما داریمa = 5b = 7c = 35phi = 24e = 11خب الا وقتشه کلید خصوصی رمزگشایی(Decryption) بسازیم یا پیدا بکنیم فرمولی که باهاش کلید خصوصی بدست میاریم به شکل زیر هستش (D * E) % phi = 1(D * 11) % 24 = 1به زبون ساده ما باید یک عددی (D) پیدا بکنیم که حاصل ضربش با 11 (E) , اگه تقسیم بر 24 (phi) بکنیم مقدار باقی ماندش مساوی با 1 باشهچندتا نکته : رنجی که ما دنبال عدد درست برای D هستیم به این صورت محاسبه میشه از phi+1 تا phi+n که این n میتونه هر چقدر میخواد بزرگ باشه من اینجا 1000 انتخاب کردمانجام این عملیات ها با دست و یا روی برگه خیلی تاقت فرسا هستش واسه همین این محاسبات با کامیپوتر انجام میدیمcode exampleما میتوینم به تعداد خیلی زیادی کلید داشته باشیم و در اخر از بین گزینه ها یکی انتخاب میکنیم و ادامه میدیم مثلا برای جواب بالا ما کلید های خصوصی (D) ... 35, 59, 83, 107 , داریم که برای آسونی اینجا کوچیکترین انتخاب میکنیمخب عدد صحیح برای D ما اعدد ... 35, 59, 83, 107 هستن میتونیم بصورت دلخواه یکی انتخاب کنیم پس الا ما این چیزا داریمa = 5b = 7c = 35phi = 24e = 11d = 59خب کلید ها از دو بخش تشکیل میشن برای کلید عمومی (e , c) و برای کلید خصوصی (d , c) و در این صورت کلید های ما اینا هستنکلید عمومی رمزنگاری (E) : (11, 35)کلید خصوصی رمزگشایی (D) : (59, 35)خب تبریک تا اینجا نود درصد راه رفتیم فقط مونده بفهمیم چطور باید ازشون استفاده کنیم :))اینکار هم خیلی ساده دوتا مرحله داره مرحل اول تبدیل دیتا به معادل کد ascii اونا هستش اگه نیاز بودش و مرحله بعد بیایم تک تک اونارو با یک فرمول رمزنگاری یا رمز گشایی کنیم مراحل رمز نگاری :اول میایم یکسری عدد معمولی رمزنگاری میکنیم مثلا24 , 32 , 11الا تک تک این عدد هارو به توان E که مقدارش 11 هستش میرسونیم و بعد میزان باقی ماندش بر عدد c بدست میاریمcode example(number) ** e % c(11 ** 11 ) % 35 : 16(24 ** 11 ) % 35 : 19(32 ** 11 ) % 35 : 23خب حالا بیاید همینو رمزگشایی کنیممراحل رمزگشایی :خب دیتای که میخوایم رمزگشایی کنیم همون دیتای هستش که مرحله قبل با کلید عمومی رمزنگاریش کردیم یعنی encrypted_data : 16, 23, 19خب برای رمز گشایی از فرمول زیر استفاده میکنیم(encrypted_data) ** d % ccode example(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 = 25decrypt : 0 ** 59 % 35 = 0 1 ** 59 % 35 = 1 25 ** 59 % 35 = 30خب دقت کردید؟ الگوریتم کار نمیکنه اصلا جالا دلیلش چیه ؟ بخاطر اینکه حداکثر عددی که میتونیم رمزنگاری بکنیم و برعکس مسقیما وابسته به مقدار c که الا مقدار 35 داره و از 35 بع بعد الگوریتم کار نمیکنه :))کلیت ماجرا همینه و هر نوع الگوریتم دیگه و لایبری واسه RSA میشناسید بیس اونا همینه فقط یخورده بهشون پر بال دادن مثلا کلید های ساخته شده به یک نوع متن و یا هش تبدیل میکنن که شکل متفاوتی داشته باشه و یا از الگوریتم های بهینه تری برای پیدا کردن اعداد استفاده میکنن مثل استفاده از الگوریتم اقلیدس برای پیدا کردن بزرگترین مضرب مشترک یا ب م م