بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بهبود سرعت سيستم رمزنگاري کليد عمومي با استفاده از ماتريس ها
چکيده : نظريه اعداد در رياضيات يکي از اصول اساسي استفاده شده در بيشتر سيستم هاي رمزنگاري است . مفاهيمي همچون اعداد اول، مقسوم عليه مشترک ، ضرب و جمع پيمانه اي مي توانند در ايجاد يک کليد رمز امن نقش مهمي را ايفا کنند. در اين مقاله با استفاده از روابط بين ماتريس ها و همچنين حساب پيمانه اي، روشي سريع براي رمزنگاري کليد عمومي ارائه شده است . براي تشکيل کليد هاي رمزنگاري در اين مقاله از مساله تبديل اعداد مرکب به عوامل اول، استفاده مي شود. مهاجم براي دسترسي به متن اصلي و با داشتن متن رمز شده در قالب کليد عمومي بايد عمل تجزيه ضرب هاي معکوس را بر روي ماتريس ها انجام دهد. در ضمن با استفاده از کاهش ضرايب ماتريس ها و تغيير در الگوريتم هاي انتخاب اعداد تصادفي در مقاله Baocang و Yupu، روشي جديد براي رمزگشايي با ضريب امنيتي معادل 1,٦ برابر RSA ارائه شده است .
واژه هاي کليدي: ماتريس معکوس، رمزنگاري، تئوري اعداد، قضيه باقيمانده چيني ، کليد عمومي
1- مقدمه
مقوله ي امنيت شبکه در بسياري از ارتباطات آينده و سيستم هاي کامپيوتري نقش مهمي را ايفا خواهد کرد. نيازهاي امنيتي بنيـادي شـامل احـراز هويت 1، سري بودن ٢، درستي ٣ و عدم انکار٤ هستند[٤]. اکثر سيستمها براي مهيا کردن سرويس هاي امنيتـي در سـطح نـرم افـزار از الگـوريتم هـاي رمزنگاري کليد عمومي از قبيل الگوريتم RSA٥، الگوريتم ديفي هلمن ٦ و ...، استفاده مي کنند. ويژگي مفيد سيستم هاي رمزنگاري کليد عمومي ايـن است که بدون نياز به انتقال اطلاعات سري، امنيت داده ها را برقرار مي کنند. اين مساله مشـکل تبـادل اوليـه کليـد خصوصـي را در سيسـتم هـاي رمزنگاري متقارن حل کرده است .
در بازه زماني بين ساخته شدن اولين سيستم رمزنگاري کليد عمومي ديفي -هلمن تا ساخته شدن جديد ترين سيستم رمزي ، تعداد زيـادي از ايـن سيستم هاي رمزي کليد عمومي پيشنهاد شده و پس از مدتي شکسته شده اند. بيشتر اين طرح ها بر مفروضات تئـوري اعـداد در رمزنگـاري يعنـي مساله تجزيه اعداد و مساله لگاريتم گسسته مبتني بوده اند. در ميان اين سيستم هاي رمزنگاري به طور خاص RSA بر روي تجزيه اعـداد و سيسـتم هاي رمزي الجمال و تبادل کليد ديفي – هلمن بر روي لگاريتم گسسته مبتني هستند[ ]. يکي از ويژگي هاي مشترک الگوريتم هاي رمزنگاري ايـن است که آنها فقط بر روي يکي از اين فرضيات رمزنگاري متمرکز شده اند[٣]. انتظار مي رود تا با استفاده از فرضيه هاي رياضي ، با توجه به سخت تر شدن امکان برگشت از روي الگوريتم ، مساله امنيت رمزنگاري افزايش يابد.همزماني و پيچيدگي اين مسائل سخت ، پيچيدگي زماني بـراي شکسـتن کليد را نيز بالا مي برد.
با توجه به توضيحات بالا، يک الگوريتم توزيع کليد بر اساس تجزيه در اين مقاله پيشنهاد مي شود. در [٢] اطلاعاتي درباره مفروضـات رياضـي انـواع روش هاي رمزنگاري کليد عمومي آورده شده است . در اين مقاله سعي مي شود تا با استفاده از رابطه بين تجزيه اعداد و ماتريس معکوس مطرح شده يک رابطه جديد با سرعتي بالاتر بين ماتريس ها ايجاد شود. کار بر روي ماتريس هاي مطرح شده در اين برنامه و محاسبه مقادير در حالات تست ، با استفاده از برنامه هاي زبان برنامه نويسي #c پياده سازي شده اند. پس از طي مراحل تست مقادير بر روي ماتريس هاي تصـادفي ، بهتـرين پيشـنهاد براي ساختن يک الگوريتم امن رمزنگاري ارائه شده است .
٢- روابط رياضي رمزنگاري براي توليد کليد و ضرب پيمانه اي ماتريس ها
علم رمزنگاري بر پايه مقدماتي همچون تئوري اطلاعات، نظريه اعداد و آمار بنا نهاده شده است . تبديل داده ساده به يک داده رمزي از طريـق انجـام يکسري عمليات رياضي صورت مي گيرد. همچنين بازگشت داده رمز شده نيز، با محاسبات رياضياتي انجام مي شود. در اين بخش تعدادي از قضايا و تعاريف مورد نياز براي رمزنگاري کليد عمومي با ماتريس ها را توضيح مي دهيم .
٢-1- توابع مستقل خطي
جبر خطي از خانواده بردارهاي خطي است . N ماتريس را با يکديگر مستقل خطي گويند، اگر هيچ رابطه رياضي مستقيمي بين سطر هـا يـا سـتون هاي آنها برقرار نباشد. براي مثال سه ماتريس A1، A3، A2 را در نظر بگيريد.
طبق تعريف ، ماتريس هاي A2، A1 مستقل خطي هستند ولي ماتريس هاي A1 ،A2 ،A3 وابسته خطي با رابطه هستند.
به ازاي هر x از دامنه تعريف مشترک توابع {An ,.. A2 ,A1}، تابعي که مستقل خطي نباشد، وابسته خطي ناميده مي شود[1].
٢-٢- قضيه باقيمانده چيني
قضيه باقي مانده چيني ٧ قضيه اي در تئوري اعداد است که شرح آن بصورت زير است [٦]:
فرض کنيد اعداد صحيحي باشند که دو به دو نسبت به يکديگر اول باشند. اين روابط را مي توان به صورت فرمول 1 نشان داد:
براي اعداد صحيح عدد صحيح ... وجود دارد به طوري که در روابط همنهشتي زير صدق کند:
براي اثبات قضيه فوق از قضيه اقليدس استفاده مي شود که طبق آن قضيه اگر باشد، آنگاه داريم :
براي مثال مقدار عدد صحيح ... در دستگاه معادلاتي زير را مي توان از روش باقيمانده چيني محاسبه کرد.
پس از حل معادلات فوق مقدار٦٠ = s که کوچکترين جواب ممکن براي حل اين معادله است ، به دست مي آيد. براي پيدا کردن روند محاسـباتي قضاياي باقيمانده چيني در مثال هاي رمزنگاري به [٧] رجوع شود.
٢-٣- ماتريس هاي وارون پذير
ماتريس وارون پذير:هر ماتريس مربعي را در جبر خطي وارون پذير گويند، اگر و فقط اگر ماتريسي مانند B يافت شود به طوريکه :
که در آن ماتريس هماني و АВ ضرب ماتريسي است . هر ماتريس مربعي حداکثر يک ماتريس وارون خواهد داشت [1].
ماتريس وارون پذير به پيمانه m : هر ماتريس مربعي A را وارون پذير به پيمانه m گويند اگر، ماتريسي مانند B يافت شود، بطوريکه :
با توجه به اينکه قضاياي تئوري اعداد و به ويژه ضرب پيمانه اي، نقش مهمي را در رمزنگاري دارند، ايـن مـاتريس کـارايي زيـادي در پيـاده سـازي الگوريتم هاي رمزنگاري دارد.
٣- روش پيشنهادي رمزنگاري
سرعت و امنيت در رمزنگاري به دو عامل مهم وابسته هستند. عامل اول که مهمترين عامل نيز مي باشد، نوع الگوريتم رمزنگاري مي باشد. کـه ايـن عامل در بخش هاي ٣-٢ ، ٣-٣ و ٣-٤ به طور مفصل شرح داده مي شود. عامل تاثيرگذار ديگر براي رمزنگاري، طول و نحوه انتخاب کليـد اسـت . در بخش ٣-1 ايده مقاله براي نحوه انتخاب کليد به طور کامل بيان مي شود، در اين بخش به نکات مهمي در انتخاب р و q اشاره مي کنيم .
٣-1- شرايط لازم براي انتخاب اعداد اول در پارامترهاي کليد
در اين بخش تاکيد بر روي مرحله توليد کليد است ، زيرا حمله احتمالي با کشف کليد صورت مي گيرد. در ميان تمام سيستم هاي رمزي کـه امنيـت شان مبتني بر عامل هاي الگوريتم است ، عامل هاي اول N ،p و q بايد به صورت تقريبي انتخاب شوند تا ثابت شود که تقسيم عامـل هـا غيـر ممکـن است . عوامل زيادي در تعيين سرعت و امنيت کليد رمزنگاري نقش دارند. در اينجا به بررسي سه مورد از عوامل تاثير گذار در انتخاب کليـد مـي پـردازيم .
مساله اول قوي بودن p و q است . مساله دوم اختلاف چند بيتي بين آنها و سومين مساله بزرگ بودن مقدار عددي p وq است . نکات اصـلي بـراي
انتخاب اعداد اول تشکيل دهنده کليددر الگوريتم پيشنهادي با فرمول يه شرح ذيل مي باشند:
٣-1-1- اعداد اول قوي
اگر p عددي اول باشد و دو عدد و حاصل ضرب يک عدد صحيح در يک عدد اول خيلي بزرگ باشند، آنگاه مـي تـوان گفت که P يک عدد اول قوي است . نمونه اي از نحوه رسيدن به عدد اول قوي P در شکل 1 نشان داده شده است [٥].
شکل 1. ساختار عدد اول قوي P
در صورتي که N را به گونه اي انتخاب نماييم که حاصلضرب اعداد اول قوي p و q باشد، عامل هاي الگوريتم يک مسـاله دشـوار رياضـي مـي شـوند.
مطابق شکل 1، ما مي توانيم در ابتدا اعدادي تصادفي با طول ثابت را توليد کنيم . سپس با اضافه کردن 1+ و 1- اعداد اول قوي سطح يک را مشخص کنيم . سرانجام با تکرار مجدد همين روند و در صورت رسيدن به سطح دو، يک عدد قوي موثر حاصل مي شود.روند رسيدن بـه عـدد اول قـوي p در ساختار فوق از پايين به بالا مي باشد.
٣-1-٢- اختلاف چند بيتي بين p و q
1
p q
وقتي اختلاف بين р و q کوچک باشد، ما مي توانيم طبق فرمول 1، مقادير q، p را تحت شرايط پيش بيني کنيم .
براي مثال اگر 1٦٤٠٠٩ = N باشد، ما پيش بيني مي کنيم که
و از طريق معادله (٦) داريم
ما مي دانيم که : و از حل دستگاه فوق داريم : ، در نتيجه :
و داريم :
نتيجتاً تفاوت بين р و q بايد بزرگ (بيشترازچندين بيت ) باشد، که آن را براي رمزگشايي غيرممکن سازد.
٣-1-٣- بزرگ بودن مقدار عددي p , q
بديهي است که اگر عامل N بتواند تقسيم شود، آنگاه الگوريتم مي تواند رمزگشايي شود. بنابراين طول р ,q بايد به اندازه کافي بزرگ باشند تـا تقسيم به عامل N غيرممکن شود. از آنجائي که عاملهاي تقسيم ، مساله اساسي در رمزنگاري است ، در دهه هاي گذشته الگوريتم هـاي فاکتورهـاي تقسيم ، پيشرفت هاي بسياري داشته اند. ما نتايج بدست آمده از فاکتور الگوريتم را در جدول 1 فهرست کردهايم .
اطلاعات درج شده در جدول 1 شامل بررسي ميزان مشکل بودن تقسيم با توجه به ضرب دو عدد اول قوي با طول يکسان است .
٣-٢- الگوريتم انتخاب کليد
