خوارزمية آر إس إيه

خوارزمية ال ار اس ايه RSA

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

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

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

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

طريقة عمل الخوارزميةَ

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

1) اختر عددين أوّليّين عشوائيّين كبيرين مختلفين Q و P

2) حساب n = p * q

n يُسْتَخْدَم كالمعامل لكلا المفاتيح الخاصّة و العامّة

3) نحسب ال (Totient: φ(n) = (p-1)(q-1

φ(n) او الTotient= كمّ من الأعداد بين 1 و n أوليه نسبيًّا إلى n

4) اختر عدد صحيح e بشرط أن يكون ، و e و ليس لهم اي عامل مشترك غير ال 1 (coprime)

e تنْشَر كالأسّ (exponent) للمفتاح العامّ

5)الان نجد قيمة d التي تكمل علاقة التطابق التاليه: mod φ(n)) 1 ≡ de) والتي هي (de = 1+kφ(n لعدد صحيح ما k

d تنْشَر كالأسّ (exponent) للمفتاح السري

ملاحظه: لعمل هذا بالأعداد الكبيرة، قاعدة متطوّرة أكثر تسمى "extendid Euclid" يجب أن تسْتَخْدَم .

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

المفتاح السري يتكوّن من المعامل n و الأُس السري decryption) d), والذي يحتفظ به سرياً.

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

المرسل A يفعل التالي:

1) يحصل على المفتاح العام للمستقبل B والذي هو (n, e).

2) يحول الرساله من لغه إلى رقم صحيح عن طريق بروتوكول قابل للعكس (Padding Scheme).

3) وجد ناتج التشفير لهذا الرقم عن طريق المعادله c = m^e % n ^ تعني للقوة % هي إشارة باقي القسمه

4) إرسال الناتج عن القسمه c إلى المستقبل B.

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

المستقبل B يفعل التالي:

1) يستخدم مفتاحه الخاص ( n, d ) لحساب m = c^d mod n

2) يستخلص اللغة او محتوى الرساله الأصلي من العدد الصحيح m.

مثال: 1) اختيار اثنين من الاعداد الاولية:

p=61 and q=53

2) حساب n= pq n=61*53 = 3233

3) حساب الTotient: φ(n) = (p-1)(q-1 φ(n)= (61-1)(53-1) = 3120

4) اختيار e > 1 الذي ليس له اي عامل مشترك غير ال 1 مع ال 3120 e=17

5) حساب d على أن تكون (mod φ(n)) 1 ≡ de d = 2753 17 * 2753 = 46801 = 1 + 15 * 3120

المفتاح العام هو (n= 3233, e= 17). ومعادلة التشفير هي: c= m^e % n = m^17 % 3233

المفتاح الخاص هو ( n=3233, e=2753 ) ، ومعادلة فك التشفير هي: m=c^d % n = c ^2753 % 3233

على سبيل المثال، لتشفير m = 123 ، نحسب c = 123^17 mod 3233 = 855

أو لفك تشفير c = 855 ، نحسب m=855^2753 mod 3233 = 123

نظام التبطين

عند الإستخدام عمليًّا ، يدمج ال (RSA) بشكل عام مع (نظام تبطين) . هدف نظام التبطين(padding schemes ) هو منع كمية من الهجمات التي تعمل بشكل امكاني ضد ال (RSA) دون استخدام نظام التبطين:

• عند التّشفير باستخدام اسس تّشفيرية رياضية منخفضة المستوى (م.س=3) و بقيم صغيرة من m بمعنى ان m<n1/e تكون قيمة me الناتجة بدقة اقل من قيمة باقي القسمة n . في هذه الحالة تسهل عملية قك تشفير النص المشفر و ذلك بأخذ الجذر ال eth الخاص بالنص المشفر بواسطة الاعداد الصحيحة .
• لان ال(RSA) نظان تشفير محدد اي انه لا يحتوي على عناصر عشوائية ، فبإمكان المهاجم بشكل ناجح بدأ (هجوم نص صريح مختار) ضد نظام التشفير ، عن طريق تشفير النصوص الصريحة الملائمة باستخدام (المفتاح العام) و فحص التشابه مع النص المشفر. يمكن القول ان نظام تشفير معين عبارة عن نظام امن اذا لم يستطع المهاجم ان يميز بين نصان مشفران حتى لو انه كان على علم مسبق بالنص الصريح المناظر. و كما تم القول لا تعتبر ال (RSA) نظام تشفير امن دون التبطين.
• تملك ال(RSA) خاصية ان ناتج نصان مشفران مساوي لتشفير ناتج نص صريح خاص حيث (( m1^e*m2^e=(m1m2)^e (mod n) . لهذا السبب فان مضاعفة خاصية (هجوم نص صريح مختار) محتملة. مثال : الذي يريد معرفة تشفير النص المشفر (c=m^e (mod n) ) سيطلب من الشخص الذي يعرف المفتاح السري ان يفك تشفير النص المشفر على نحو جازم ( c'=cr^e (mod n)) ، اذن اذا نجح المهاجم سوف يعلم ( mr mod n ) التي باستخدامها يستطيع ان يشتق ال الرسالة m من خلال ضرب mr بمقلوب باقي قسمة ( r mod n ) .

لتجنّب هذه المشاكل ، عمليات تنفيذ ال(RSA) بشكل عملي قد ضمن نموذجيا شكل من اشكال بناء التبطين العشوائي لقيمة m قبل تشفيرها . هذا التبطين يكفل ان لا تكون m ضمن النص الصريح غير الامن، انه في مجرد تبطين رسالة معينة سيشفرها لواحد من العديد من النصوص المشفرة المحتملة .

• • توقيع الرسالة:

يجب التنوية ال ان ال( RSA-PSS ) اساسية في حماية تقويع الرسالة كما هي للرسالة نفسها ، و يجب عدم استخدام المفتاح نفسه نهائيا لتشفير الرسالة و التوقيع معا.

• • الحماية :

حماية نظام ال(RSA) تعتمد على مشكلتان رياضيان : مشكلة تحليل ارقم كبيرة إلى عواملها و مشكلة ال(RSA) . فك التشفير الكامل لنص (RSA) مشفر يعتقد انها غير عملية على افتراض ان كلتا المشكلتان صعبة ، لا يوجد نظام فعال لحلهم ، التزويد بحماية ضد فك التشفير المتحيز يتطلب زيادة في نظام تبطين امن.

اعتبارات عملية

توليد المفتاح

ايجاد الارقام الاولية P و q عادة ما يتم بفحص ارقام عشوائية ذات العدد الصحيح بفحص اولي محتمل التي تقوم بإزالة سريعة لجميع الارقام غير الاولية . P وQ لا يجب ان يكون قريبين جدا خشية ان التحليل إلى العوامل على طريقة "فيرمات" ل n ان تكون ناجحة ، اذا p و q على سبيل المثال هم اقل من(2n^1/4) سوف يكون الحل ل p و q سهل. بالاضافة إلى ذلك اذا كانت اي من p -1 او q-1 لهم عوامل اولية صغيرة فقط ، ممكن ان تحلل n إلى عواملها يشكل سريع عن طريق "خوارزمية بولارد" و هذه القيم ل p و q يجب ان تهمل . من المهم ان يكون المفتاح السري كبير كفاية ، حيث اثبت السيد michel wiener في عام 1990 انه اذا كانت قيمة p بين q و 2q و d<n^1/4 /3 فان d يمكن حسابها على نحو كاف من قيم n و e . لا يوجد هجوم معروف ضد الاسس الصغيرة العامة مثل e=3 باشتراط استخدام تبطين مناسب ، على كل حال في حين عدم استخدام تبطين او عمله بشكل خاطيء فان الاسس الصغيرة العامة لها مخاطرة أكبر تؤدي إلى هجوم ، كما هو الحال في ضعف النص الصريح غير المبطن . 65537 هو قيمة تستخدم في غالب الاحيان ل e . هذه القيمة من الممكن ان تعتبر انها حل وسط بين تجنب الهجومات الاسية الصغيرة المحتملة و مع ذلك تسمح بالتشفيرات الفعالة .

السرعة RSA أبطا بكثير من ال DES و نظم التشفير المتناسقة . مع التجربة علي سبيل المثال احمد يقوم بتشفير رسالة سرية بواسطة خوارزمية متناسقة ، يشفر المفتاح التناسق بواسطة ال RSA و من ثم يبعث المفتاح المتناسق المشفر بواسطة الRSA و الرسالة المشفرة تشفيرا تناسقيا إلى سهيلة. هذا الاجراء يرفع المزيد من الاحتياطات الامنية . فعلى سبيل المثال : المهمة الكبرى هي استخدام مولد ارقام عشوائية قوي للمفتاح المتناسق لان توفيق (مختلس السمع يريد ان يرى ما تم بعثة ) يمكن ان يجتاز الRSA فقط بتخمين المفتاح المتناسق.

توزيع المفاتيحكما في كل الشيفرات ، كيفية توزيع المفاتيح ال RSA العامة مهم جدا الامن .يجب ان يكون توزيع المفاتيح امن جدا ضد هجوم (رجل في الوسط) (a man in the middle ) . لنفترض ان توفيق له طريقة ما لاعطاء احمد مفاتيح تحكمية و جعله يصدق ان هذه المفاتيح هي مفاتيح سهيلة . لنفترض ايضا ان سهيلة قادرة على ان تقطع الرسائل بين احمد و توفيق . سهيلة تقوم بارسال مفتاحها العام لاحمد والتي يعتقد احمد انها مفاتيح توفيق ، و من ثم يستطيع توفيق ان يقطع أي نص مشفر مرسل بواسطة احمد و من ثم فك تشفيره بمفتاحه السري الخاص و ابقاء نسخة من هذه الرسالة و من ثم تشفيرها بمفتاح سهيلة ثم إرسال النص المشفر الجديد لسهيلة . في الحقيقة ان احمد و سهيلة لا يستطيعوا ان يكشفوا وجود توفيق . الدفاعات ضد كهذه الهجومات كثيرا ما تكون معتمدة على الشهادات الرقمية او مكونات اخرى للبنية التحتية للمفتاح العام .

المصادر و المراجع

ترجمة عن النسخة الإنجليزية