خوارزمية RSA علم التشفير و الاعداد الاولية

في علم التشفير، آر إس إيه (RSA) هي خوارزمية للتشفير بواسطة مفتاح عام. ولعلها الأولى المعروفةً على هذا الصعيد , وهي مناسبة للتّوقيع بالإضافة إلى التشفير، وكانت أحد التقدّمات العظيمة الأولى في التشفير بواسطة مفتاح عامّ. آر إس إيه مستخدم في بروتوكولات التّجارة الإلكترونيّة على نطاق واسع، وهي آمنة طالما كان طول المفتاح طويل جدا مثل  : 1024 بت , وهي تعتمد بشكل كبير على أنَّه لا يوجد خوارزمية لتحليل عدد لعوامل بسرعة عالية .

نظام RSA القياسي: أنشئ هذا النظام عام 1977، وأصبح اليوم، أحد الأنظمة القياسية المستخدمة في عمليات التشفير في إنترنت، وهو يعتمد على طريقة المفتاح العام (PKE). ويعتبر التعامل مع نظام RSA أسهل من نظام DES، على الرغم من أنه أقل سرعةً وأقل أماناً. ومن أساسيات هذا النظام، احتواؤه على توقيع رقمي (digital signature) يميز المرسل، ويؤكد هويته

تاريخ الخوارزمية

وُصِفَتْ الخوارزمية علناً في عام 1977 من قبل ليونارد أدليمان وآدي شامير ورونالد ريفست في معهد ماساتشوستس للتقنية , الأحرف آر إس إيه هي الحروف الأولى من اسمائهم. وَصفَ كليفورد كوكس، عالم رياضيّات بريطانيّ يعمل مع جي سي إتش كيو(GCHQ) وكالة مخابرات المملكة المتّحدة، نظاماً مكافئاً في وثيقةِ داخليةِ في عام 1973, لكنّه نظرا لغلاء الكومبيوترات نسبيًّا, المطلوبة لتنفيذ هذا النطام في ذاك الوقت, تم اعتبار هذا النظام وكأنه فضول فقط، فلهذا لم يُنْشَر هذا النظام أبدًا. لكنّ اكتشافه لم يُكْشَف حتّى 1997 بسبب تصنيفه السّرّيّ للغاية، وريفيست وشامير وأدليمان ورثوا أو أكملوا آر إس إيه (RSA) عن شغل كليفورد كوكس.

مُنِحَ معهد مساشوستس للتكنولوجيا براءة اختراع ل"نظام وطريقة اتصالاتِ مشفّرةِ" الذي استعملت الخوارزميةَ في عام 1983. انتهت صلاحية براءة الاختراع في 21 سبتمبر 2000. ولأنه تم نشر ورقة تصف الخوارزميةَ في أغسطس 1977، قبل ديسمبر 1977 (وهو تاريخ تقديم الطلب لبرائة الاختراع), القوانين في مُعظم بقيّة العالمِ اعاقت براءاتَ الاختراع في مكان آخر وبراءة الاختراع الأمريكيّة فقط هي التي كانت تمنح.

انتاج المفاتيح

خوارزمية آر إس إيه تَتضمّنُ مفتاحا عامّا ومفتاحا خاصّا. المفتاح العامّ هو مفتاح التشفير فقط ويجب ان يكون معلوما لكل من يحاول الاتصال بمالك المفتاح . الرسائل المشفّرة بالمفتاح العامّ يمكن أن تُفَكّ فقط باستخدام المفتاح الخاصّ. المفاتيح لقاعدة آر إس إيه تُولد بالطريقة التالية :

1. اختيار عددين أوَلييّن عشوائييّن كبيرين مختلفين  و .
2. حساب  . يُسْتَخْدَم  كالمعامل لكلا المفاتيح الخاصّة والعامّة.
3. حساب .حيث أنَّ الدالة  تعطي عدد الأعداد التي بين 2 و n والتي هي أولية مع n اي انه  حيث أنَّ  .
4. اختيار عدد صحيح بشكل عشوائي  بحيث أَنَّ  و  (اي أَنَّ العددين  و-  (يعني أنَّ  ) أوليين فيما بينهما ) . هذا العدد  سوف يكون الأُس العمومي.
5. ايجاد قيمة d او المفتاح الخصوصي ,بحيث أنَّه يُحقق التالي :  , ويمكن حساب المعادلة الاخيرة بواسطة خوارزمية اقليدس المُوسعة . d سوف يكون الأُس الخصوصي .

المفتاح العمومي يتكوّن من المعامل n والأُس العمومي encryption) e)

المفتاح الخصوصي يتكوّن من المعامل n والأُس الخصوصي decryption) d), والذي يجب أن يكون سريا للحفاظ على امان الخوارزمية.

تَشْفيرُ الرسائلِ

لنفرض أن A و- B يردا ان يتواصلا فيما بينهما , لنفرض أَنَّ مفتاح A العمومي هو  اما المفتاح الخصوصي هو  ومفتاح B العمومي هو  والمفتاح الخصوصي  .

لنفرض أنَّ A يريد ان يرسل رسالة إلى B , لذا عليه فعل التالي :

1. يحصل على المفتاح العام للمستقبل B والذي هو  .
2. وجد ناتج التشفير لهذا الرقم عن طريق المعادله 
3. يُرسِل c إلى B.

ملاحظة :

• اذا كانت الرسالة مكتوبة بالحروف حينها يجب اولا تحويلها لشكل مناسب بحيث يتوافق مع العمليات الحسابية ويمكن ان يتم هذا بتحويل الرسالة إلى ASCII .

فك تَشْفير الرسائلِ

ليحصل B على الرسالة يفعل التالي :

يستخدم مفتاحه الخاص  ويحسب  . حينها m هي الرسالة التي بعث بها A

صحة الخوارزمية

في كل نظام تشفير أهم خصلة يجب ان تتوفر فيه أنَّه يحقق الصفة التالية :  اي أنَّه اذا شفرنا رسالة ثم فككنا التشفير نحصل على نفس الرسالة . وهذا أيضا صحيح ل-RSA :  وفك التشفير هو : 

مثال

1. اختيار اثنين من الاعداد الأولية: 
2. حساب  اي نفذ التالي 
3. حساب  حيث أنَّ  هو مؤشر أويلر.  .
4. اختيار  الذي ليس له اي عامل مشترك مع  , مثل .
5. نختار d بحيث :  , مثلا نختار : d = 2753 وهو ملائم لانه : 

المفتاح العمومي هو (n= 3233, e= 17). لذا فإنَّ التشفير كالتالي : 

المفتاح الخصوصي هو (n=3233, d=2753)، لذا فإنَّ فك التشفير كالتالي : 

لنفرض انَّه يُراد تشفير m = 123، وهذا يكون كالتالي : 

وفك تشفير c = 855، يكون ب-  .

للمزيد حول RSA من هنا

المصادر:

ar.wikipedia

MathMaroc

الخميس, يناير 08, 2015

شارك الموضوع مع أصدقائك كي تعم اﻹستفادة

قوقل+

تويتر

فيس بوك

مواضيع مشابهة قد تهمك

آخر كتب تم نشرها Mathematics books for free

نرحب بجميع تعليقاتكم واستفساراتكم هنا