رمزنگاری های کلاسیک در پایتون قسمت 1 - الگوریتم سزار (Caesar) :: Mr Python

Mr Python
سه شنبه, ۲۸ ارديبهشت ۱۴۰۰، ۱۲:۴۴ ب.ظ
۲۶۲۹

رمزنگاری های کلاسیک در پایتون قسمت 1 - الگوریتم سزار (Caesar)

درود به همه !

با یک سری پست دنباله دار دیگه در خدمت شما هستیم و این بار با مبحث بسیار پرکاربرد و جالب رمزنگاری . در این سری پست های دنباله دار قرار هستش که انواع روش های رمزنگاری کلاسیک رو به همراه روش های شکوندنشون در پایتون بررسی کنیم . در قسمت اول این سری ، به الگوریتم سزار (Caesar) میپردازیم و روش های شکوندن اون رو هم بررسی میکنیم . با ما همراه باشید .

در اینجا چون ابتدای سری رمزنگاری هستیم لازم هست تا یک سری مفاهیم رو یاد بگیریم :

- رمزنگاری چیست : علم رمزنگاری شامل مجموعه الگوریتم های ریاضی است که از طریق این الگوریتم ها میتوان یک متن آشکار (plain text) رو به یک متن غیر قابل فهم (cipher text) تبدیل کرد . به الگوریتم ریاضی مورد استفاده ، کلید رمز (key) میگوییم .

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

رمزگذاری : تبدیل کردن متن آشکار (plain text) به متن رمز شده و غیر قابل فهم (cipher text) با استفاده از کلید .
رمزگشایی : تبدیل کردن متن رمز شده و غیر قابل فهم (cipher text) به متن آشکار (plain text) با استفاده از کلید .

تا اینجا مفهوم متن آشکار (plain text) ، متن رمز شده (cipher text) و کلید رمزنگاری (key) رو متوجه شدیم .

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

تمامی الگوریتم های رمزنگاری کلاسیک از نوع الگوریتم های متقارن هستند . حالا این متقارن یعنی چی ؟ یعنی از همون کلیدی که برای رمزگذاری کردن پیام (تبدیل plain text به cipher text) استفاده میشه ، برای رمزگشایی کردن پیام نیز (تبدیل cipher text به plain text) استفاده میشه .

امروزه الگوریتم های رمزنگاری نامتقارنی نیز وجود دارن که کلید رمزگذاریشون با کلید رمزگشاییشون یکسان نیست که ما اصلا در این سری پست ها کاری به اونا نداریم .

اولین الگوریتمی که از مجموعه الگوریتم های کلاسیک قراره بررسی کنیم ، الگوریتم سزار (Caesar) است . این الگوریتم بر اساس جایگذاری عمل میکنه . یعنی حروف متن آشکار رو با حروف رمز شده جایگذاری میکنه تا غیر قابل فهم بشه . مثلا میاد هرچی a تو متن آشکار هست رو به c تبدیل میکنه .

در الگوریتم سزار به هر حرف حروف الفبا یک عدد اختصاص میگیرد . به صورت a=0 , b=1 , c=2 , d=3, .... همینجور اعداد از 0 میرن تا 25 (حروف الفبای انگلیسی 26 حرف است)

در روش سزار ، کلید (key) یکی از حروف الفبا است . یعنی به طور کلی ما میتونیم 26 کلید مختلف در روش سزار داشته باشیم .

فرض کنید متن آشکار ما (plain text) برابر با متن رو به رو است : i am here

کلید ما نیز حرف c است .

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

برای مثال اولین حرف متن آشکارمون ، i هستش . طبق عدد گذاری که گفتم ، عددی که به حرف i اختصاص میگیره عدد 8 هستش . کلیدمون هم حرف c هست که عدد 2 بهش اختصاص میگیره .

حالا : 10 = 2 + 8 . میایم ببینیم عدد 10 که حاصل جمع کلید با حرف مورد نظرمون بود میشه کدوم یک از حروف الفبا . باز طبق تعریف عدد 10 میشه حرف k . پس حرف i در متن آشکار رو به حرف k تبدیل میکنیم .

همین عمل رو برای تمام حروف متنمون انجام میدیم (نکته : فاصله های متن رو در نظر نمیگیریم معمولا) :

همینطور که در تصویر میبینید iamhere (متن آشکار) تبدیل شده به kcojgtg (متن رمز شده)

نکته بسیار مهم اینه که اینجا باید از جمع پیمانه ای (به پیمانه ی 26) برای جمع کردن اعداد باهم استفاده کنیم .

چون اعداد حروف الفبا 26 تا است و ما شمارش رو از 0 شروع میکنیم ، بنابراین اگه جمع اعداد از 25 زد بالا باید برگردیم از 0 شروع کنیم . مثلا 26 میشه 0 . یا 28 میشه 2 . مثل عقربه های ساعت میمونه وقتی به 12 برسه دوباره از 1 شروع میکنه. اینم همینجوره وقتی به 26 رسیدین بقیشو از اول شروع کنید بشمارید .

مثلا میخواید حرف z که عدد 25 بهش اختصاص میگیره رو با کلیدمون (2) جمع کنید . طبق جمع معمولی ، حاصل این دو عدد میشه 27 ولی طبق جمع پیمانه ای که گفتم عددش میشه 1 .

تا اینجا روش رمزگذاری به شیوه سزار رو میدونیم . اما رمزگشایی کردنش چطوریه ؟ الان چطوری میشه با استفاده از کلید ، از cipher text به plain text رسید ؟ کاری نداره بسیار راحته . همون مرحله رو برعکسشو میریم . یعنی حروف رمزشده رو منهای کلید میکنیم .

باز هم از همون روش پیمانه ای برای تفریق استفاده میکنیم . اگر حاصل از 0 کمتر شد ، از 25 شروع به شمارش میکنیم .

اما میتونیم یه کار ساده تر بکنیم .

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

key = 26 - key

برای مثال الان کلید ما برابر c یا همون عدد 2 هستش . کلید جدید به شکل 24 = 2 - 26 میشه . حرف y معادل عدد 24 هستش . شروع میکنیم متن cipher text رو با کلید جدید "رمزگذاری" کنیم . با اینکار میرسیم به plain text قبلی .

کاری که اینجا کردیم این بود که به جای اینکه حروف cipher text رو منهای کلید اصلی کنیم ، اومدین کلید رو جوری تغییرش دادیم که وقتی cihper text رو باهاش رمزگذاری میکنیم برسه به plain text . جالبه نه ! با رمزگذاری کردن عمل رمزگشایی رو انجام دادیم :)))

خب تا اینجا الگوریتم رو میدونیم . میخوایم این الگوریتم ها رو با پایتون پیاده سازی کنیم . در اینجا دو سورس مینویسیم . 1- سورس رمزگذاری 2 - سور رمزگشایی

سورس رمزگذاری :

def encrypt(text , key):
    ciphertext = ""
    
    for plain_char in text:
        plain_number = ord(plain_char) - 65
        key_number = ord(key) - 65
        cipher_number = plain_number + key_number
        
        if cipher_number > 25: # if cipher_number > 25 -> start from 0 
            cipher_number = cipher_number - 26
            
        cipher_char = chr(cipher_number + 65)
        ciphertext += cipher_char
            
    return ciphertext

text = input("text : ").replace(" ","").upper()
key = input("key : ").upper()

ciphertext = encrypt(text , key)
print(ciphertext)

توضیح : تابعی به نام encrypt تعریف کردیم که عمل رمزگذاری رو انجام میده . این تابع متن آشکار و کلید رمزنگاری رو به عنوان ورودی دریافت میکنه و عمل رمزگذاری رو انجام میده .

در ابتدای تابع یک متغییر خالی به نام ciphertext تعریف کردیم که قراره متن رمزگذاری شده داخلش ذخیره بشه . سپس اومدیم برای تک تک کاراکتر های متغییر text که حاوی متن آشکار است اعمال زیر را توسط حلقه for انجام دادیم :

عدد مربوط به حرف مورد نظر رو حساب کردیم و ریختیم داخل متغییر plain_number . تابع ord معادل کد unicode کاراکتر ها رو بر میگردونه . چون کاراکتر A در جدول unicode دارای کد 65 هستش و بقیه حروف به ترتیب 66 و 67 و 68 و ... هستند ، اومدیم حاصل رو منهای 65 کردیم تا از صفر شروع بشن .
سپس برای محاسبه ی عدد مربوط به حرف کلید رمزنگاری هم همینکارو کردیم (متغییر key_number)
در مرحله بعد طبق الگوریتم ، حرف آشکار رو با کلید جمع کردیم . بعد چک کردیم اگه از 25 بیشتر شد عددش بره از صفر شده کنه (جمع پیمانه ای)
نهایتا بعد از اینکه عدد رمزگذاری شده (cipher_number) رو بدست آوردیم ، اونو تبدیل به کاراکتر مربوطه میکنیم . این کارو با استفاده از تابع chr کردیم . این تابع دقیقا برعکس تابع ord عمل میکنه یعنی یک عدد میگیره و معادل کاراکتری اون عدد رو در جدول unicode بر میگردونه .
تا اینجا حرف رمزگذاری شده رو بدست آوردیم پس اضافش میکنیم به متغییر ciphertext که قراره متن کامل رمزگذاری شده داخلش باشه .
بعد از اتمام این مراحل متغییر ciphertext رو به صورت خروجی برگردوندیم .

اولین ورودی که از کاربر گرفتیم متنی هست که میخوایم رمزگذاریش کنیم (text) . با استفاده از تابع replace اومدیم فاصله های داخل متن ورودی رو حذف کردیم و تمام حروفش رو به حروف بزرگ انگلیسی تبدیل کردیم (تابع upper) .

بعد از اون کلید رو به همین روش از کاربر گرفتیم و تابع encrypt رو فراخونی کردیم .

خروجی تابع رو به کاربر نشون دادیم .

تستش میکنیم :

خب بریم سراغ سورس رمزگشا . این سورس بسیار راحته . اگه یادتون باشه گفتم فقط کافیه کلید رو به key = 26 - key تبدیل کنیم و دوباره متن رمزگذاری شده رو رمزگذاری کنیم. با اینکار میرسیم به متن آشکار . برای اینکار از همین تابع encrypt که نوشتیم استفاده میکنیم فقط عدد کلید رو عوض میکنیم :

def decrypt(text , key):
    ciphertext = ""
    for plain_char in text:
        plain_number = ord(plain_char) - 65
        key_number = ord(key) - 65
        key_number = 26 - key_number
        cipher_number = plain_number + key_number
        
        if cipher_number > 25: # if cipher_number > 25 -> start from 0 
            cipher_number -= 26
            
        cipher_char = chr(cipher_number+65)
        ciphertext += cipher_char
            
    return ciphertext

text = input("cipher text : ").replace(" ","").upper()
key = input("key : ").upper()
plaintext = decrypt(text, key)
print(plaintext)

همینطور که میبینید این دقیقا کار سورس قبلی رو انجام میده فقط دوتا تغییر کوچولو دادیم . یکی اینکه عدد کلید (key_number) رو به روشی که گفتم تغییرش دادیم و اینکه اسم تابع encrypt رو عوض کردیم گذاشتیم decrypt همین .

تستش کنیم :

میبینید که متن kcojgtg رو بهش دادیم رسید به iamhere (همون i am here بدونه رعایت فاصله اجتماعی :) )

روش های شکستن رمز سزار :

تا اینجا به طور کامل با رمز سزار آشنا شدیم و اونو در پایتون پیاده سازی کردیم . حالا میریم ببینیم آیا روش هایی هست که بشه با اونا بدون دونستن کلید رمز ، از متن رمزگذاری شده (cipher text) به متن آشکار (plain text) رسید یا نه .

1 - روش آزمون جامع (Brute Force) : اگه دقت کنید در الگوریتم سزار ، کلا 26 کلید وجود داره (حروف الفبا) . این یعنی ما کلا 26 حالت کلید داریم . بنابراین با 26 تست خیلی راحت میتونیم تمام حالت های ممکن رو برسی کنیم .

برای اینکار از سورس رمزگشایی که بالا نوشتیم استفاده میکنیم با این تفاوت که با استفاده از یک حلقه ی for ، برای تمام کلید های ممکن متن رو رمزگشایی میکنیم :

def decrypt(text , key):
    ciphertext = ""
    for plain_char in text:
        plain_number = ord(plain_char) - 65
        key_number = ord(key) - 65
        key_number = 26 - key_number
        cipher_number = plain_number + key_number
        
        if cipher_number > 25: # if cipher_number > 25 -> start from 0 
            cipher_number -= 26
            
        cipher_char = chr(cipher_number+65)
        ciphertext += cipher_char
            
    return ciphertext

text = input("cipher text : ").replace(" ","").upper()
for key in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":  
    plaintext = decrypt(text, key)
    print("KEY #{} -> {}".format(key , plaintext))
    
input()

سورس بالا رو اجرا میکنیم و متن kcojgtg رو بهش میدیم :

با چند دقیقه وقت گذاشتن و خواندن تک تک متن های آشکار تصویر بالا متوجه میشویم که کلید C درست هست چون به متن IAMHERE رسیده .

البته اینکه تک تک کلید ها رو بخونیم برای وقتی هستش که اصلا ندونیم ممکنه چه چیزی داخل متن آشکار باشه . اگه از محتوای متن آشکار خبر داشته باشیم نیازی به خواندن تک تک متن ها نیست . برای مثال فرض کنید میدونیم که داخل متن آشکار کلمه ی HERE وجود داره . بنابراین حلقه for در سورس بالا رو به شکل پایین تغییر میدیم :

for key in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":  
    plaintext = decrypt(text, key)
    if "HERE" in plaintext:
        print("KEY #{} -> {}".format(key , plaintext))

همینطور که میبینید یه if گذاشتیم که اگر کلمه HERE داخل متن آشکار بود اون رو چاپ کنه و اینطوری مستقیما کلید صحیح برای ما آشکار میشه .

2 - روش درصد فراوانی

روش درصد فراوانی یک روش بسیار کاربردی برای بدست آوردن کلید بعضی از الگوریتم های رمزنگاری کلاسیک از روی متن رمز شده (cipher text) است .

در این روش ما باید درصد فراوانی حروف انگلیسی رو بدونیم :

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

اما این موضوع به چه درد شکوندن رمز سزار میخوره ؟ کافیه ببینیم در متن رمز شده (cipher text) چه حرفی بیشترین تکرار رو داره . مثلا متن زیر رو در نظر بگیرید . این یک متن رمزگذاری شده در الگوریتم سزار است :

RWLAHYCXPAJYQHJLJNBJALRYQNAJUBXTWXFWJBLJNBJA0BLRYQNACQNBQROCLRYQNALJNBJA0BLXMNXALJNBJABQROCRBXWNXOCQNBRVYUNBCJWMVXBCFRMNUHTWXFWNWLAHYCRXWCNLQWRZDNBRCRBJCHYNXOBDKBCRCDCRXWLRYQNARWFQRLQNJLQUNCCNARWCQNYUJRWCNGCRBANYUJLNMKHJUNCCNABXVNORGNMWDVKNAXOYXBRCRXWBMXFWCQNJUYQJKNCOXANGJVYUNFRCQJUNOCBQROCXO<MFXDUMKNANYUJLNMKHJNFXDUMKNLXVNKJWMBXXWCQNVNCQXMRBWJVNMJOCNASDURDBLJNBJAFQXDBNMRCRWQRBYAREJCNLXAANBYXWMNWLN

بیشترین تعداد تکرار حروف در متن بالا مربوط به حرف N میباشد که فراوانی آن در متن بالا برابر 51 است . اگه دقت کنید طبق جدول فراوانی حروف انگلیسی ، حرف e بیشترین تکرار رو داره . چون در این متن رمز شده نیز حرف N بیشترین تکرار رو داره پس به احتمال زیاد این پنجاه و یکی N داخل متن بالا همون حرف e داخل متن آشکار بودن که تبدیل شدن .

حالا ما میتونیم با یه معادله درجه 1 ریاضی خیلی راحت کلید رو بدست بیاریم . عدد مربوط به حرف e برابر 4 هستش و عدد مربوط به حرف N نیز برابر 13 :

e + key = N
=> 4 + key = 13
=> key = 13 - 4 
=> key = 9  ---> key = j

همونطور که میبینید طبق معادله بالا ، متغییر key عدد 9 بدست اومد که معادل حرف j در حروف انگلیسیه . حالا بزارید متن بالا رو با کلید j رمزگشایی کنیم ببینیم به چی میرسیم :

همینطور که میبینید با رمزگشایی متن بالا با کلید j به متن زیر رسیدیم :

In cryptography a Caesar cipher also known as Caesar's cipher the shift cipher Caesar's code or Caesar shift is one of the simplest and most widely known encryption techniques It is a type of substitution cipher in which each letter in the plain text is replaced by a letter some fixed number of positions down the alphabet For example with a left shift of 3 D would be replaced by A E would become B and so on The method is named after Julius Caesar who used it in his private correspondence

البته متنی که در عکس بدست آوردیم کمی مشکل داشت . برای مثال بعضی کاراکتر ها درست تبدیل نشده بودند . این به این دلیل است که در متن کاراکتر های غیر الفبایی هم وجود داره مثل کاراکتر تک کوتیشن (') بنابراین طبق اسکریپت رمزگذاری که ما نوشتیم این کاراکتر های غیر الفبایی یکم مشکل پیدا میکنن . اگه میخواین این مشکل حل بشه کافیه در اسکریپت رمزگذاری وقتی میخواید حروف رو رمز کنید یه if بزارید که مثلا اگه کاراکتر غیر الفبایی مثل کاما و ... بود تبدیلش نکنه به چیزی خودشو بنویسه ( این کار میتونه امنیتیشو بیاره پایین )

اسکریپت بدست آوردن کلید (key) با استفاده از روش درصد فراوانی :

text = input("text : ")
text_set = set(text)

max_count = 0 
ch = '' 
for char in text_set:
    if text.count(char) > max_count :
        max_count = text.count(char)
        ch = char


key = (ord(ch) - 65) - (ord("E") - 65)
print("key : {}".format(chr(key+65)))

در سورس بالا متن رمزشده رو میگیریم (text) . سپس یه نمونه تبدیل شده به set ازش میسازیم و میریزیم داخل متغییر text_set. این کار باعث میشه هر کدوم از حروفش فقط یک بار حساب بشن (set ها عضو تکراری قبول نمیکنن) .

بعد با استفاده از یک حلقه for اومدیم چک کردیم کدوم یک از حروف متن رمزشده بیشترین تکرار رو داره و اونو ریختیم داخل متغییر ch . سپس با فرمولی که گفتیم بالا ، کلید رو حساب کردیم(key) .

امیدوارم که از قسمت اول این سری لذت برده باشید .

سوالی بود مطرح کنید .

یا حق !

Telegram Channel : @mrpythonblog