مرجع
آخر الزيارات

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

1٬398 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: في علم التعمية، آر إس إيه هي خوارزمية تعمية بمفتاح عام. تجد هنا «إنتاج المفاتيح»، «تاريخ الخوارزمية» و«نحسب 134 بالنظام الثنائي: وهو» ضمن 18 قسماً.
المحتويات
  1. إنتاج المفاتيح
  2. تاريخ الخوارزمية
  3. نحسب 134 بالنظام الثنائي: وهو
  4. {
  5. حساب أي نفذ التالي
  6. 2- نحل المعادلة
  7. }
  8. int aa=a;
  9. امان الخوارزمية
  10. حساب مقلوب عدد
  11. تعمية الرسائلِ
  12. مثال
  13. فك تعمية الرسائلِ
  14. إيجاد أعداد أولية
  15. توزيع المفاتيح
  16. صحة الخوارزمية
  17. الرفع بواسطة التربيع المتكرر
  18. السرعة

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

وعلى صعيد آخر، آر إس إيه هي نسبيا خوارزمية بطيئة. لهذا السبب، لا تستعمل عادة من أجل تعمية كمية كبيرة من البيانات، بل تستعمل من أجل تعمية المفاتيح المستعملة في خوارزمية أخرى ثم تبادلها، كالخوارزميات ذات المفاتيح المتناظرة. بعدئذ، تستعمل الخوارزميات ذات المفاتيح المتناظرة من أجل تعمية كمية كبيرة من البيانات.

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

علاوةً على ذلك، اختيار عدد صحيح بشكل عشوائي حيث و (أَي أَنَّ العددين و- (يعني أنَّ ) أوليين فيما بينهما). هذا العدد سوف يكون الأُس العمومي.

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

إضافةً إلى ذلك، المفتاح العمومي يتكوّن من المعامل n والأُس العمومي encryption) e)

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

وعلى صعيد آخر، ايجاد قيمة d أو المفتاح الخصوصي، بحيث أنَّه يُحقق التالي: , ويمكن حساب المعادلة الاخيرة بواسطة خوارزمية اقليدس المُوسعة. d سوف يكون الأُس الخصوصي.

كذلك، حساب .حيث أنَّ الدالة تعطي عدد الأعداد التي بين 2 و n والتي هي أولية مع n أي أنه حيث . تسمى هذه الدالة مؤشر أويلر.

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

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

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

ومن جهة أخرى، وُصِفَتْ الخوارزمية علناً في عام 1977 من قبل ليونارد أدليمان وآدي شامير ورونالد ريفست في معهد ماساتشوستس للتقنية، الأحرف آر إس إيه هي الحروف الأولى من اسمائهم.

كذلك، لكنّ اكتشافه لم يُكْشَف حتّى 1997 بسبب تصنيفه السّرّيّ للغاية، وريفيست وشامير وأدليمان ورثوا أو أكملوا آر إس إيه (RSA) عن شغل كليفورد كوكس.

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

نحسب 134 بالنظام الثنائي: وهو

3. حينها y يكون حاصل ضرب كالتالي:

نحسب لكل بطريقة التربيع المتكرر أي:

{

  • if(k%2==1)
  • {
  • d=(d*a)%n;
  • }
  • k=(k-k%2)/2;
  • aa=(aa*aa) %n;
  • }

حساب أي نفذ التالي

  • حساب حيث أنَّ هو مؤشر أويلر. .
  • اختيار الذي ليس له أي عامل مشترك مع , مثل .
  • نختار d بحيث: , مثلا نختار: d = 2753 وهو ملائم لانه:
  • المفتاح العمومي هو (n= 3233, e= 17). لذا فإنَّ التعمية كالتالي:
  • المفتاح الخصوصي هو (n=3233, d=2753)، لذا فإنَّ فك التعمية كالتالي:
  • لنفرض انَّه يُراد تعمية m = 123، وهذا يكون كالتالي:
  • وفك تعمية c = 855، يكون ب- .
  • خوارزميات مُساعدة

2- نحل المعادلة

ومن ناحية أخرى، من المهم ان يكون المفتاح السري كبير كفاية، حيث اثبت السيد michel wiener في سنة 1990 انه إذا و فان d يمكن حسابها على نحو كاف من قيم n و e. لا يوجد هجوم معروف ضد الاسس الصغيرة العامة مثل e=3 باشتراط استخدام تبطين مناسب، على كل حال في حين عدم استخدام تبطين أو عمله بشكل خاطيء فان الاسس الصغيرة العامة لها مخاطرة أكبر تؤدي إلى هجوم، كما هو الحال في ضعف النص الصريح غير المبطن. 65537 هو قيمة تستعمل في غالب الأحيان ل e. هذه القيمة من الممكن ان تعتبر انها حل وسط بين تجنب الهجومات الاسية الصغيرة المحتملة ومع ذلك تسمح بالتعمية ات الفعالة.

وفي السياق ذاته، لذا فانه من السهل خرق الامان في الخوارزمية إذا ما توجد خوارزمية تحليل لعوامل بسرعة. ولكن لا يوجد خوارزمية سريعة لفعل هذا ! لذا يمكن اعتبار هذا الخرق غير مُعتبر.

وعلى صعيد آخر، p و- q لا يجب أن يكون قريبين جدا خشية ان التحليل إلى العوامل على طريقة «فيرمات» ل n ان تكون ناجحة، إذا p و q مثلًا هم اقل من سوف يكون الحل ل p و q سهل. علاوةً على ذلك إذا كانت أي من p -1 أو q-1 لهم عوامل اولية صغيرة فقط، ممكن ان تحلل n إلى عواملها يشكل سريع عن طريق «خوارزمية بولارد» وهذه القيم ل p و q يجب أن تهمل.

من جانب آخر، ملاحظة: بيتر شور، في عام 1997 قدم خوارزمية سريعة لايجاد العوامل ولكن ذلك كان بمساعدة ادوات فيزيائية بالتحديد بواسطة الحسابات الكمومية. وهذه الخوارزمية لا تُعتبر قابلة للبرمجة لانها تحتاج حاسوب كمومي وهو غير موجود للآن (أي عام 2013) ولكن هناك بصيص من الامل لامكانية اختراع مثل هذه الحواسيب.

}

مثال: نريد أن نحسب:

وفي هذا السياق، صحة هذه الخوارزمية تعتمد على أنّه يمكن كتابة كل عدد k بواسطة النظام الثنائي أي أنَّه: حينها كل ما علينا هو حساب

int aa=a;

while(k>0)

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

1- نجد مؤشر أويلر للعدد n :

من جانب آخر، أيسر الوسائل لخرق امان الخوارزمية هي ايجاد عوامل العدد n , لنقل انه يمكن ايجاد عوامل n بالإضافة لنفرض أنَّ حينها وبما أنَّ المفتاح العمومي موجود ولنفرض أنّه لنجد المفتاح الخصوصي d :

حساب مقلوب عدد

كذلك، في خوارزمية RSA أردنا أن نجد بحيث يتحقق: لذا فإنه علينا أن نجد: لذا سوف نستعمل خوارزمية اقليدس المُوسعة والسبب هو: بما أنَّ حينها يمكن ايجاد عددين صحيحين a,b بحيث , لذا فان العدد a سوف يكون d . الخوارزمية تعقيدها: .

تعمية الرسائلِ

  • لنفرض أنَّ A يريد أن يرسل رسالة إلى B , لذا عليه فعل التالي:
  • يحصل على المفتاح العام للمستقبل B والذي هو .
  • وجد ناتج التعمية لهذا الرقم عن طريق المعادلة
  • يُرسِل c إلى B.
  • ملاحظة:

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

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

مثال

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

فك تعمية الرسائلِ

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

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

إيجاد أعداد أولية

وفي هذا الصدد، لإيجاد أعداد أولية و نختار بشكل عشوائي أعدادا ويتم فحصها. لذا كل ما يُحتاج إليه هو وسيلة لفحص الأولية بطريقة سريعة. هناك عدة خوارزميات منها خوارزميات احتمالية مثل اختبار ميلر-رابن لأولية عدد ما وأخرى حتمية مثل اختبار أ.ك.أس.

توزيع المفاتيح

  • انظر كذلك
  • دالة وحيدة الاتجاه
  • تبادل مفتاح ديفي-هيلمان
  • نظرية التعقيد الحسابي

وفي هذا السياق، يجب أن يكون توزيع المفاتيح آمنا جدا ضد هجوم الرجل في الوسط. لنفترض أن توفيق له طريقة ما لإعطاء أحمد مفاتيح تحكمية وجعله يصدق أن هذه المفاتيح هي مفاتيح سهيلة. لنفترض كذلك أن سهيلة قادرة على أن تقطع الرسائل بين أحمد وتوفيق. سهيلة تقوم بارسال مفتاحها العام لأحمد والتي يعتقد أحمد أنها مفاتيح توفيق، ومن ثم يستطيع توفيق أن يقطع أي نص مشفر مرسل بواسطة أحمد ومن ثم فك تعمية ه بمفتاحه السري الخاص وابقاء نسخة من هذه الرسالة ومن ثم تعمية ها بمفتاح سهيلة ثم إرسال النص المشفر الجديد لسهيلة. في الحقيقة أن أحمد وسهيلة لا يستطيعوا أن يكشفوا وجود توفيق. الدفاعات ضد هذه الهجومات كثيرا ما تكون معتمدة على الشهادات الرقمية أو مكونات أخرى للبنية التحتية للمفتاح العام.

ومن جهة أخرى، كما في كل الشيفرات، كيفية توزيع مفاتيح آر إس إيه العامة مهم جدا الأمن.

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

وفك التعمية هو:

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

الرفع بواسطة التربيع المتكرر

في هذا الإطار، فليكن a,k,n اعداد صحيحة عندها يمكن حساب والتعقيد الحسابي للخوارزمية هو: والخوارزمية كالتالي:

  • int exp_mod(a,k,n)
  • {
  • int d=1;

السرعة

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.