خانه / اخبار فناوری / پیوند ریاضیات و رایانه، رمزنگاری

پیوند ریاضیات و رایانه، رمزنگاری

رمز گذاری چیست ؟

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

رمزگذاری و رمزگشایی تکنیک هایی در رمزنگاری هستند

روش های رمزگذاری و رمزگشایی یا الگوریتم های متفاوتی برای این کار وجود دارد .

کلید چیست ؟
آنچه که برای رمزگذاری استفاده می شود کلید نامیده می شود.

در رمزنگاری رایانه، کلید به سری بلندی از بیت ها گفته می شود که به وسیله الگوریتم برای رمزنگاری استفاده می شود .

برای مثال یک کلید فرضی ۴۰ بیتی به صورت زیر است.
۰۰۰۰۱۰۱۰ ۰۱۱۰۱۰۰۱  ۱۰۰۱۱۱۱۰  ۰۰۰۱۱۱۰۰  ۰۱۰۱۰۱۰۱

دو روش مهم برای رمزگذاری وجود دارد . ۱- رمزگذاری متقارن ۲- رمزگذاری نامتقارن
رمزگذاری متقارن :

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

رمز گذاری نامتقارن :

رمزگذاری نامتقارن یا کلید عمومی بر اساس دو کلید به نام های عمومی و خصوصی صورت می گیرد .
هر فردی یک کلید عمومی و یک کلید خصوصی خواهد داشت . کلید عمومی شما در دسترس دیگران می باشد ولی کلیدخصوصی فقط از آن شما و در دسترس شما می باشد .
فرض کنید فردی برای شما پیغامی را بفرستد .این پیغام در کامپیوتر مبدا با کلید عمومی شما رمزگذاری شده و برای شما فرستاده می شود تنها کسی که قادر به باز کردن رمز می باشد شما می باشید زیرا کلید خصوصی دارید که با کلید عمومی شما ارتباط دارد .

امروزه در دنیای اینترنت انتقال اطلاعات مهم بر اساس رمزگشایی نامتقارن می باشد .

باقیمانده تقسیم   بر ۱۱ را به دست آورید ؟

معکوس ۳۷ به پیمانه همنهشتی ۲۰۰ کدام عدد است ؟

دو عدد m و n را بیابید که  ۵۵m+37n=1

بزرگترین عدد اول شناخته شده چیست و چند رقم دارد؟


در بحث نظریه اعداد با این سوالات زیاد برخورد داریم . راستی چه اهمیتی دارد که به دنبال فرمولی برای اعداد اول باشیم یا باقیمانده تقسیم  را بر ۱۱ بدانیم .

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

مقدمه ای بر رمزنگاری :

رمزنگاری(Cryptography) علم کدها و رمزهاست .

 علم رمزنگاری در جستجوی روشهایی برای کد کردن یا رمز کردن پیغام ها ، و روش های متناظری برای از کد در آوردن یا رمز خواندن است .رمزگذاری و رمزگشایی تکنیک هایی در رمز نگاری هستند .

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

دو سیستم رمز نگاری مهم وجود دارد :

۱- سیستم رمزنگاری متقارن   ۲- سیستم رمزنگاری نامتقارن یا کلید عمومی

سیستم رمز نگاری متقارن :

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

سیستم رمزنگاری نامتقارن یا کلید عمومی:

رمزگذاری نامتقارن یا کلید عمومی بر اساس دو کلید به نام های عمومی و خصوصی صورت می گیرد .هر فردی یک کلید عمومی و یک کلید خصوصی خواهد داشت . کلید عمومی شما در دسترس دیگران می باشد ولی کلید خصوصی فقط از آن شما و در دسترس شما می باشد .

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

امروزه در دنیای اینترنت انتقال اطلاعات مهم بر اساس رمزگشایی نامتقارن می باشد .

معمولی ترین الگوریتمی که برای رمزنگاری نامتقارن استفاده می شود ، الگوریتم RSA می باشد .

این روش پس از کارهای اولیه سه ریاضیدان به نام های ریوست(Ron Rivest) ، شامیر(Adi Shamir) و ادلمن(Leonard Adleman) در سال ۱۹۷۸ منتشر شد .ایده اولیه الگوریتم RSA بسیار ساده به نظر می رسد : ضرب اعداد خیلی ساده است ولی تجزیه اعداد بسیار مشکل است .

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

اگر دو عدد اول مانند :   و   را در نظر بگیریم آنگاه به سادگی می توان حاصلضرب آنها یعنی   را بیابیم .( حتی با استفاده از روش های مدرسه ای برای ضرب کردن که برای یک جفت عدد n رقمی در حدود    گام زمان می برد )

با این حال اگر عدد ۱۸۷۲۸۷۳۶۲۷۶۴۲۱ را به کسی بدهیم و از وی بخواهیم تا عوامل آن را بیابد احتمالا در حدود یک میلیون گام لازم دارد .
خاصیت به ظاهر صعب الرجوع عمل ضرب ، مبنای معمولی ترین روش رمزنگاری استفاده شده امروز یعنی دستگاه RSA است .

الگوریتم RSA در ۳ مرحله کار خود انجام می دهد :

۱- ساخت کلید    ۲- رمزگذاری  ۳- رمز گشایی
همانطور که گفتیم ، این دستگاه برای عملیات رمزنگاری نیاز به یک جفت کلید عمومی و اختصاصی دارد .
کلید عمومی برای رمز گذاری استفاده می شود و می تواند برای همه شناخته شده باشد .اما پیام هایی که با یک کلید عمومی رمزگذاری شوند فقط توسط کلید خصوصی متناظر قابلیت رمزگشایی دارند
در دنیای کامپیوتر ، موسساتی وجود دارند که وظیفه ثبت کلید های عمومی و تایید  هویت طرفین ارتباط را به عهده دارند .
برای آشنایی با طرز کار RSA باید با یک سری ایده های نظری آشنا باشیم : عکس به پیمانه یک عدد طبیعی ، تابع  – اویلر و قضیه اویلر مرتبط با آن یعنی   .در قسمت بعدی به یادآوری این مباحث ریاضی می پردازیم .
دو نوع سیستم رمزنگاری متقارن و نامتقارن داریم .الگوریتم رایج برای رمزگذاری نامتقارن RSA می باشد .ایده اولیه RSA بسیار ساده به نظر می رسد : ضرب اعداد خیلی ساده است ولی تجزیه اعداد بسیار مشکل است.الگوریتم RSA در ۳ مرحله کار خود انجام می دهد :

۱- ساخت کلید    ۲- رمزگذاری  ۳- رمز گشایی

در هر سه مرحله ، از قضیه ها و تعاریفی در نظریه اعداد استفاده می شود . قبل از آشنایی با طرز کار این الگوریتم یادآوری این قضایا مفید به نظر می رسد.

ایده های نظری برای آشنایی با RSA :

۱- الگوریتم اقلیدس : محاسبه ی ب.م.م بوسیله تقسیم بر باقیمانده 

در این روش برای زوج   داده شده با شرط زوج بعدی توسط قاعده زیر تولید می شود :

مقدار bi+1 برابر باقیمانده تقسیم ai بر bi میباشد .

توقف هنگامی اتفاق می افتد که bk عدد ak را عاد کند که در این حالت نتیجه می گیریم :

gcd(a,b) = gcd(ak,bk)=bk

مثال) a=34 و b=19 :

(a1,b1)=(34,19)

(a2,b2)=(19, 34-19)=(19 ,15)

(a3,b3)=(15, 19- 15)=(15, 4)

(a4, b4)=(4, 15 -12)=(4,3)

(a5 , b5)=(3,4-3)=(3,1)

از این رو gcd(34,19)=1 می باشد ، چون ۱ عدد ۳ را عاد می کند .


۲- نمایش خطی ب.م.م :

احتمالا بهترین نتیجه الگوریتم اقلیدسی این است که برای اعداد صحیحی مانند m و n می توان نوشت :

gcd(a,b)=ma+nb

همچنین این برهان ، روشی جهت یافتن m و n برای a و b داده شده پیشنهاد می کند .

مثال) m و n را طوری بیابید که

(۳۴ , ۱۹)=(a , b)

(۱۹ , ۱۵)=(b, a-b)

(۱۵ , ۴)=(a-b, b-(a-b))=(a-b , -a+2b)

(۴ , ۳)=( -a+2b , a-b-3(-a+2b))=(-a+2b , 4a-7b)

(۳ , ۱)= (۴a-7b , -a+2b-(4a-7b))=(4a-7b , -5a+9b)

از سطر آخر ب.م.م را می خوانیم :

تساوی اخیر درست است ،چون :

پس m= -5 و n= +9 می باشد .


۳- همنهشتی

تعریف :

اعداد صحیح a و b را همنهشت به پیمانه n می نامیم و می نویسیم :

هر گاه در تقسیم بر n باقیمانده یکسانی داشته باشند ، به طور معادل ، a با b به پیمانه n همنهشت است هر گاه n عدد a-b را عاد کند .


۴-  الف) معکوس یک عدد به پیمانه عدد طبیعی n :

عدد b را معکوس a به پیمانه همنهشتی n گوییم هر گاه :

به عنوان مثال عدد ۲ معکوس ۱۰ در پیمانه همنهشتی ۱۹ می باشد . زیرا حاصلضرب آنها ، عدد ۲۰ با یک به پیمانه ۱۹ همنهشت است :

ب) محک برای وجود معکوس به پیمانه n :

یک عدد صحیح مانند a معکوسی به پیمانه n دارد فقط و فقط اگر یا دو عدد a , n نسبت به هم اول باشند .


۵- چگونه معکوس یک عدد را در یک پیمانه همنهشتی بیابیم ؟

معکوس یک عدد را در یک پیمانه همنهشتی می توان به راحتی به کمک الگوریتم اقلیدسی به دست آورد .

مثال) معکوس عدد ۱۹ را در پیمانه همنهشتی ۳۴ بیابید .

عدد مذکور را d می نامیم داریم داریم  :

بنا به محک معکوس پذیری باید داشته باشیم :

پس داریم :

(۳۴ , ۱۹)=(a , b)

(۱۹ , ۱۵)=(b, a-b)

(۱۵ , ۴)=(a-b, b-(a-b))=(a-b , -a+2b)

(۴ , ۳)=( -a+2b , a-b-3(-a+2b))=(-a+2b , 4a-7b)

(۳ , ۱)= (۴a-7b , -a+2b-(4a-7b))=(4a-7b , -5a+9b)

از سطر آخر می توان نتیجه گرفت که :

نتیجه می گیریم که معکوس ۱۹ در پیمانه ۳۴ عدد ۹ می باشد .


۶- تابع فی – اویلر :

به ازای n>=1 ، عبارت است از تعداد اعداد صحیح مثبتی که کوچکتر از n بوده و نسبت به n اولند .

مثال ) ، زیرا اعداد صحیح مثبت کوچکتر از ۸ که نسبت به این عدد اولند عبارتند از ۱ و۳ و۵ و۷

 

قضیه : اگر p اول باشد ، در این صورت داریم :

قضیه : تابع یک تابع ضربی است  برای n و m که نسبت به هم اول باشند داریم :


۷- قضیه اویلر :

اگر m یک عدد طبیعی و a عدد صحیحی باشد به طوریکه در این صورت :


دو نوع سیستم رمزنگاری متقارن و نامتقارن داریم .الگوریتم رایج برای رمزگذاری نامتقارن RSA می باشد .

ایده اولیه الگوریتم RSA بسیار ساده است : ضرب اعداد خیلی ساده ولی تجزیه اعداد بسیار مشکل است.

الگوریتم RSA در ۳ مرحله کار خود انجام می دهد :

۱- ساخت کلید    ۲- رمزگذاری  ۳- رمز گشایی

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

در ادامه،  مراحل کار RSA را شرح داده و سپس با یک مثال ساده بیشتر با کاربرد آن آشنا خواهیم شد .

A- مراحل ساخت کلید

۱- انتخاب اعداد اول :

دو عدد اول به اندازه کافی بزرگ در نظر گرفته می شود ، آنها را p و q می نامیم.

۲- تعیین پیمانه همنهشتی :

حاصلضرب دو عدد p و q را محاسبه نمایید .(n=pq) عدد n پیمانه همنهشتی شما خواهد بود .

حاصلضرب pq تجزیه منحصر به فردی به دو عامل p و q دارد . بدون داشتن p و q تجزیه pq کار بسیار مشکلی است ، ضمنا p و q به اندازه کافی بزرگ در نظر گرفته شده اند که به آسانی با داشتن n قابل دستیابی نباشند .

۳- محاسبه فی-اویلر عدد n ؛

p و q دو عدد اولند پس داریم :                        

که به آسانی با داشتن عوامل p و q قابل محاسبه است .

۴- انتخاب توان رمزگذری :

برای رمزگذاری به عددی مثل e هم نیاز داریم . به شرط اینکه :    

این بدین معنی است که و e نسبت به هم اولند .این شرط در واقع محک معکوس پذیری عدد e به پیمانه ی خواهد بود .

عدد e به همراه n  کلید عمومی شما خواهند بود که می توانید در اختیار هر فردی قرار دهید .

۵- محاسبه ی توان رمزگشایی :

عدد d (توان رمزگشایی) را چنان محاسبه می کنیم که  :    

این عدد در واقع معکوس عدد e به پیمانه همنهشتی خواهد بود .

چون e و را داریم پس به راحتی به کمک الگوریتم توسعه یافته اقیلدسی (برای مقادیر m و n) می توان مقدار d را هم محاسبه کرد که جایگاه اصلی کلید اختصاصی شما برای رمزگشایی است .

حالا یک زوج (n,d) داریم که برای رمزگشایی استفاده می کنیم و آن کلید اختصاصی ماست و یک زوج عدد (n, e) داریم که برای رمزگذاری استفاده می کنیم و آن را کلید عمومی می نامیم .

B- مرحله رمزگذاری 

فرض کنید m پیغام ما باشد .( پیغامی که به راحتی از حالت رشته ای تبدیل به حالت عددی شده است )

پیام رمز شده ای که به استفاده کننده ارسال می شود برابر باقیمانده در تقسیم بر n است که به صورت به پیمانه n آن را مختصر می کنیم .

 r پیغام رمزشده است که ارسال می شود .

C- مرحله رمزگشایی 

استفاده مقدار r را دریافت می کند و آن را به توان d به پیمانه n می رساند .( باقیمانده  را بر n محاسبه می کند)

نتیجه کار ، پیغام اولیه m است ، چون d معکوسی برای e به پیمانه است  ، داریم :

از این رو :

توجه کنید در قسمت سوم به جای عبارت مقدار ۱ را قرار داریم چون بنا به قضیه اویلر داریم :


مثال RSA با اعداد p=7 و q=11 و توان رمزگذاری e=13 ( اعداد به طور غیر واقع بینانه ای کوچک انتخاب شده اند) .

۱- انتخاب اعداد اول :

۲- تعیین پیمانه همنهشتی :

۳- محاسبه فی-اویلر عدد ۷۷ :

۴- انتخاب توان رمزگذاری :

عدد e=13 را به عنوان توان رمزگذاری انتخاب می کنیم . می دانیم که  :           

۵- محاسبه توان رمزگشایی :

عدد d را که معکوس e=13 به پیمانه همنهشتی  می باشد به کمک الگوریتم اقلیدسی می یابیم :

از سطر آخر داریم :

عدد بر a بخش پذیر است یعنی :

و چون از همنهشتی داریم :

پس می توان نتیجه گرفت که مقدار توان رمزگشایی برابر ۳۷ است .


B- رمزگذاری : 

فرض می کنیم m =7 پیغام ماست که به صورت عددی تبدیل شده است .

باقیمانده ۷۱۳ را بر ۷۷ به دست می آوریم . این کار توسط کامپیوتر به آسانی و به کمک روشهای مربع کردن و استفاده از هم نهشتی میسر است  :

پیغام رمز شده برابر r=35 خواهد بود .


C- مرحله رمزگشایی :

باقیمانده عدد ۳۵۳۷  بر عدد ۷۷ برابر عدد مورد نظر یعنی ۷خواهد بود که برای کامپیوتر این کار نیز آسان خواهد بود .

پایان – برداشتی ازاد

این مطلب هم یک نگاه بیاندازید

لطفا خودتان را تکرار (کپی) نکنید!

یک اصل یا قاعده یا توصیهٔ برنامه‌نویسی هست که علی رغم آن که عموماً جماعت …

۲ نظر

  1. بسیار عالی بود و بسیار خوب واضح گفتن
    اگر امکان داشته باشد یک چند مثال عملی کار میکردین خیلی خوب میشد
    تشکر

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *