RSA به زبون ساده + پیاده سازی بدون کتابخانه در Python

اگر نمیدونید RSA چیه، پیشنهاد میکنم اول مطلب انواع رمزنگاری، تفاوت ها، مزایا و معایب رو بخونین.

برای این پیاده

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

خب کارمون کلا ۳ مرحله هست:

1. تولید کلید
2. رمزنگاری با کلید عمومی
3. رمزگشایی با کلید خصوصی

۱. تولید کلید

۲-۱ انتخاب P و Q

برای ساختن کلید به ۲ تا عدد اول (خیلی) بزرگ رندوم نیاز داریم. اگه اعداد کوچیک باشن، ممکنه به راحتی شکسته بشن. منظور از عدد بزرگ، چیزیه که حاصل ضربشون حدود حداقل ۲۰۰۰ بیت بشه! که برای نشون دادنش توی مبنای ۱۰ حدود ۶۰۰ رقم نیازه!

سوال: چطوری بفهمیم عدده به این بزرگی اوله؟!

جواب: نمیشه ۱۰۰٪ مطمئن باشیم اوله! یعنی میشه ولی خیلی زمان میبره تا همه ی فاکتور هارو تست کنیم و بصرفه نیست. برای همین یه سری الگوریتم ابداع شده که اول نبودن یک عدد رو میتونن تشخیص بدین. به این الگوریتم ها میگن Primality test. اگر این چند الگوریتم رو روی یک عدد تست کردن و نتونستن ثابت کنن این عدد اول هست، فرض میکنن اوله و ازش استفاده میکنن ممکنه بنظرتون مسخره باشه ولی الان همینطوری دارن استفاده میکنن

خب حالا فرض کنیم ۲ عدد انتخابی ما به اسم p و q به ترتیب مقادیر 61 و 53 رو گرفتن:

p = 61
q = 53

۲-۱ محاسبه N

حالا باید مقدار n که فیلدی هست که میخوایم توش محاسباتمون انجام بشه رو حساب کنیم. فیلد عملا یه عدده که میگیم اگر یه عدد بخواد بزرگتر از عدد فیلد ما واردش بشه، باید ازش باقیمونده (mod) گرفته بشه. مثلا عدد ۲۰ توی فیلد ۱۵ میشه ۵، و عدد ۱۰ توی فیلد ۲۰ میشه ۱۰.

خب حالا توی RSA، عدد n اینشکلی حساب میشه:

n = p * q

پس:

61 * 53 = 3233

در نتیجه (توی مثال ما) تمام عملیات رمزنگاری و رمزگشایی توی فیلد 3233 حساب میشن. برای نشون دادن عملیات ها توی یک مد خاص، از علامت % یا کلمه ی mod و یا علامت هم ارزی استفاده میشه.

۳-۱ محاسبه Phi

عدد Phi یا φ میشه حاصل عدد n در تابع Totient اویلر. این تابع میاد تعداد اعدادی که کمتر از n هستن و به نبست n اول هستن‌(co-prime) هستن رو حساب میکنه. برای اعداد اول، حاصل این تابع میشه یکی کمتر از خود عدد چون بجز یک و خودش، هیچ عدد دیگه ای بهش بخش پذیر نیست. طبق یک قضیه زمانی که n یک عدد مرکب باشه که حاصل ضرب دو عدد اول هست، Phi(n) اینشکلی حساب میشه:

phi(n) = phi(p) * phi(q)

پس توی مثال ما حاصل phi(n) میشه:

3120 = 52 * 60

۴-۱ انتخاب e

عدد e باید نسبت به phi(n) اول باشه(co-prime) و همچنین کمتر از phi(n) باشه. مثلا عدد ۲ و ۳ نمیتونن مقدار مناسبی برای e باشن ولی ۷ میتونه. پس ما اینجا e رو ۷ در نظر میگیریم. البته اکثراً به دلایلی عدد e رو ۶۵۵۳۷ در نظر میگیرن.

اینجا اعضای کلید عمومی مثال ما میشن عدد e و n

۵-۱ محاسبه d

d یک بخش از کلید خصوصی هست. برای محاسبه d، باید معکوس e توی مد phi(n) رو حساب کنید. اینکار از طریق الگوریتم تعمیم یافته اقلیدسی (Extended Euclidean algorithm) با سرعت بالایی محسابه میشه. (فکر نمیکنم فعلا نیاز باشه ریز الگوریتم بررسی شه)

توی مثال ما:

1783 = 7 inverse_mode ( 3120 ) 

و کلید خصوصی میشه عدد d و n. یعنی n هم در رمزنگاری نیازی هم در رمزگشایی.

با Phi هم دیگه کاری نداریم و نیازی نیست ذخیره بشه.

۲. رمزنگاری با کلید عمومی

خب تا الان کلید های مورد نیاز رو آماده کردیم و میتونیم بریم برای پیاده سازی. برای جمع بندی مطالب، خیلی سریع کار هایی که بالا کردیم رو یبار توی پایتون پیاده میکنیم.

برای پیاده سازی عملیات های ریاضی، من از کتابخونه libnum کمک میگیرم. این کتاب خونه توسط Aleksei توسعه داده شده اما برای پایتون ۳ به روزرسانی ای انجام نداد. برای همین من اون رو به پایتون ۳ تبدیل کردم و توی pypi گذاشتم که بشه راحت استفاده کرد. کدش هم در گیتهاب موجوده.

خب اول کتابخونه رو نصب میکنیم:

pip3 install libnum

و شروع میکنیم به پیاده سازی (بخاطر اینکه توضیحات تکراری نشه اینجا فقط کد رو میزارم) :

import libnum

"""
Key Generation
"""
p = 61
q = 53
e = 7

n = p * q
phi = (p - 1) * (q - 1)
d = libnum.invmod(e, phi)
print("d = {}".format(d)) # Prints: d = 1783

خب تا اینجا فقط توضیحاتی که توی بخش تولید کلید داشتیم رو پیاده کردیم.

حالا برای اینکه یک عدد رو رمز کنیم، کافیه عدد مورد نظر رو توی مد n، به توان e برسونیم و خروجی میشه عدد رمز شده!

من عدد plain رو ۸۵ در نظر گرفتم و میخوام رمزش کنم:

plain_number = 85
encrypted_number = pow(plain_number, e, n) 
print("Encrypted number = {}".format(encrypted_number)) # Prints: Encrypted number = 2509

نکته: اگر در تابع pow در پایتون، آرگومان سوم رو هم تعیین کنیم یعنی داریم بهش میگیم توی مد اون عدد محاسبات رو انجام بده

pow(x, y, z ):

x**y (with two arguments) or x**y % z (with three arguments)

عدد رمز شده بدست اومده شد ۲۵۰۹

همونطور که گفتیم اجزائی که ازش توی رمزنگاری استفاده شد یکی e بود و یکی n. پس با همینا میتونین هر عددی مثبت ای که کوچکتر از n هست رمز کنید.

۳. رمزگشایی با کلید خصوصی

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

اما رمزگشایی به چه شکلی انجام میشه؟

طبق کار هایی که انجام دادیم:

بخش m به توان e شد عدد رمز شده. از اونجایی که d معکوس e هست، پس عدد رمز شده رو به توان d برسونیم، انگار داریم عدد اصلی رو به توان e ضربدر d میرسونیم. چون e معکوس d هست، خنثی اش میکنه و به عدد اصلی خودمون میرسیم.

پس برای پیاده سازی، کافیه عدد رمز شده رو به توان d برسونیم:

decrypted_number = pow(encrypted_number, d, n)
print("Decrypted number = {}".format(decrypted_number))  # Prints: Decrypted number = 85

و دیدیم که خروجی کد شد 85 پس تونستیم به راحتی کار رمز گشایی رو انجام بدیم.

۴. دیگه چی؟

خب اینجا ۲ تا سوال پیش میاد:

۱. اعداد بزرگتر از n رو چطوری رمزنگاری کنیم؟

برای اعداد بزرگتر از n، باید داده رو به چند بخش تقسیم کنید و هر بخش رو جدا گونه ( و یا ترکیبی ) رمز نگاری کنید.

۲. اگر بخوایم بجای عدد، یک داده باینری یا رشته رو رمز کنیم چه کنیم؟

برای اینکار، کافیه داده مورد نظرتون رو به عدد تبدیل کنید. مثلا میتونید عدد اسکی معادل حرف هارو به hex تبدیل کنید، و عدد hex نهایی رو به مبنای ۱۰ بیارین تا با همین کارها قابل محاسبه باشه.

پیداه سازی این بخش رو به عنوان یه gist توی گیتهابم گذاشتم:

#!/usr/bin/python3
"""
Sample code snippet to work with RSA encryption ( Don't use it in production :| )
"""

import libnum


def generate_keys(p, q, e):
    n = p * q
    phi = (p - 1) * (q - 1)
    d = libnum.invmod(e, phi)
    return n, d


def encrypt_text(e, n, plain_text):
    plain_number = libnum.s2n(plain_text)
    cipher_number = pow(plain_number, e, n)
    return cipher_number


def decrypt_text(d, n, encrypted_number):
    decrypted_number = pow(encrypted_number, d, n)
    decrypted_text = libnum.n2s(decrypted_number)
    return decrypted_text


p = 1071456887129021
q = 627715068764519
e = 65537
n, d = generate_keys(p, q, e)

plain_text = "I'm secret"
encrypted_text = encrypt_text(e, n, plain_text)
print("Encrypted text as number = {}".format(encrypted_text))
# Prints: Encrypted text as number = 661208835941892016866488406464

decrypted_text = decrypt_text(d, n, encrypted_text)
print("Decrypted text = {}".format(decrypted_text))
# Prints: Decrypted text = I'm secret