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

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

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

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

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

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

1. اختيار عددين أوَلييّن عشوائييّن كبيرين مختلفين ${\displaystyle q$ و${\displaystyle p$.
2. حساب ${\displaystyle n=p\cdot q\!$ . يُسْتَخْدَم ${\displaystyle n$ معاملا لكلا المفتاحين الخاصّة والعامّة.
3. حساب ${\displaystyle \phi (n)=(p-1)(q-1)$.حيث أنَّ الدالة ${\displaystyle \phi (n)$ تعطي عدد الأعداد التي بين 2 وn والتي هي أولية مع n أي أنه ${\displaystyle GCD(n,i)=1$ حيث ${\displaystyle 2\leq i\leq n$ .
4. اختيار عدد سليم بشكل عشوائي ${\displaystyle e}$${\displaystyle e$ يفترض أنقد يكون الأُس العمومي.
5. ايجاد قيمة d أوالمفتاح الخصوصي، بحيث أنَّه يُحقق التالي: ${\displaystyle d\cdot <!--\; \cdot \; -->e\equiv <!--\; \equiv \; -->1(mod\mathrm{\varphi <!--\; \varphi \; -->}(n))}$

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

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

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

لنفرض حتى A و- B يريدان حتى يتواصلا فيما بينهما. لنفرض أَنَّ مفتاح A العمومي هو${\displaystyle (n_{A ,e_{A )$ أما المفتاح الخصوصي هو${\displaystyle (n_{A ,d_{A )$ ومفتاح B العمومي هو${\displaystyle (n_{B ,e_{B )$ والمفتاح الخصوصي ${\displaystyle (n_{B ,d_{B )$ .

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

1. يحصل على المفتاح العام للمستقبل B والذي هو${\displaystyle (n_{B ,e_{B )$ .
2. وجد ناتج التشفير لهذا الرقم عن طريق المعادلة ${\displaystyle c=m^{e_{B (mod~n_{B )$
3. يُرسِل c إلى B.

ملاحظة:

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

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

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

يستخدم مفتاحه الخاص ${\displaystyle (n_{B ,d_{B )$ ويحسب ${\displaystyle m=c^{d_{B (mod~n_{B )$ . حينها m هي الرسالة التي بعث بها A

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

في جميع نظام تشفير أبرز خصلة يجب ان تتوفر فيه أنَّه يحقق الصفة التالية: ${\displaystyle D(E(m,e),d)=m$ اي أنَّه إذا شفرنا رسالة ثم فككنا التشفير نحصل على نفس الرسالة. وهذا أيضا سليم ل-RSA : ${\displaystyle E(m,e)=m^{e (mod\ n)$ وفك التشفير هو: ${\displaystyle D(E(m,e),d)=(m^{e )^{d (mod\ n)\ =m^{ed (mod\ n)\ =m^{ed\ (mod\ \phi (n)) (mod\ n)\ =m^{1 (mod\ n)=m$

مثال

1. اختيار اثنين من الاعداد الأولية: ${\displaystyle p=61\ {\mbox{and \ q=53$
2. حساب ${\displaystyle n=p\cdot q\,\!$ اي نفذ التالي ${\displaystyle n=61\cdot 53=3233$
3. حساب ${\displaystyle \mathrm{\varphi <!--\; \varphi \; -->}(n)=(p-<!--\; -\; -->1)\cdot <!--\; \cdot \; -->(q-<!--\; -\; -->1)}$${\displaystyle \phi (n)=(61-1)(53-1)=3120$ .
4. اختيار ${\displaystyle e>1$ الذي ليس له اي عامل مشهجر مع ${\displaystyle 3120$ , مثل ${\displaystyle e=17$.
5. نختار d بحيث: ${\displaystyle d\cdot e\equiv 1(mod\ \phi (n))$ , مثلا نختار: d = 2753 وهوملائم لانه: ${\displaystyle 2753\cdot 17(mod~3120)\equiv 46801(mod~3120)\equiv 1$

المفتاح العمومي هو(n= 3233, e= 17). لذا فإنَّ التشفير كالتالي: ${\displaystyle c=m^{e (mod~n)=m^{17 (mod~3233)$

المفتاح الخصوصي هو(n=3233, d=2753)، لذا فإنَّ فك التشفير كالتالي: ${\displaystyle m=c^{d (mod~n)=c^{2753 (mod~3233)$

لنفرض انَّه يُراد تشفير m = 123، وهذاقد يكون كالتالي: ${\displaystyle c=123^{17 (mod3233)=855(mod\ 3233)$

وفك تشفير c = 855،قد يكون ب- ${\displaystyle m=855^{2753 (mod\ 3233)=123$ .

خوارزميات مُساعدة

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

فليكن a,k,n اعداد سليمة عندها يمكن حساب ${\displaystyle a^{k (mod\ n)$ والتعقيد الحسابي للخوارزمية هو: ${\displaystyle O((\log _{2 k)(log_{2 ^{2 n))$ والخوارزمية كالتالي:

int exp_mod(a,k,n)
{
   int d=1;
   int aa=a;
   while(k>0)
   {
      if(k%2==1)
      {
         d=(d*a)%n;
       
      k=(k-k%2)/2;
      aa=(aa*aa) %n;
    
 

صحة هذه الخوارزمية تعتمد على أنّه يمكن كتابة جميع عدد k بواسطة النظام الثنائي اي أنَّه: ${\displaystyle k=k_{0 +k_{1 \cdot 2+\cdots +k_{s-1 \cdot 2^{s-1$ حينها جميع ما علينا هوحساب ${\displaystyle 2^{2^{j (mod\ n)(j=1,2,\cdots ,s-1)$

مثال: نريد حتى نحسب: ${\displaystyle y=1311^{134 (mod\ 39979)$

1. نحسب 134 بالنظام الثنائي: وهو${\displaystyle 134=128+4+2=2^{7 +2^{2 +2^{1$
2. نحسب ${\displaystyle T_{j =1311^{2^{j$ لكل ${\displaystyle 1\leq j\leq 7$ بكيفية التربيع المتكرر اي:

3. حينها yقد يكون حاصل ضرب كالتالي: ${\displaystyle y=1311^{134 (mod\ 39979)\ =1311^{2^{7 +2^{2 +2^{1 (mod\ 39979)=1311^{2^{7 (mod\ 39979)\cdot 1311^{2^{2 (mod\ 39979)\cdot 1311^{2^{1 (mod\ 39979)\ =T_{7 \cdot T_{2 \cdot T_{1 \ =17236$

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

في خوارزمية RSA أردنا حتى نجد ${\displaystyle d$ بحيث يتحقق: ${\displaystyle ed\equiv 1(mod\phi (n))$ لذا فإنه علينا حتى نجد: ${\displaystyle d\equiv e^{-1 (mod\phi (n))$ لذا يفترض أن نستخدم خوارزمية اقليدس المُوسعة والسبب هو: بما أنَّ ${\displaystyle gcd(e,\phi (n))=1$ حينها يمكن ايجاد عددين سليمين a,b بحيث ${\displaystyle a\cdot e+b\cdot \phi (n)=1\ \Rightarrow \ (a\cdot e+b\cdot \phi (n))(mod\ \phi (n))\ =1(mod\ \phi (n))\ \Rightarrow \ a\cdot e=1(mod\ \phi (n))$ , لذا فان العدد a يفترض أنقد يكون d . الخوارزمية تعقيدها: ${\displaystyle O(log_{2 ^{2 (n))$ .

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

• أيسر الوسائل لخرق امان الخوارزمية هي ايجاد عوامل العدد n , لنقل انه يمكن ايجاد عوامل n بالإضافة لنفرض أنَّ ${\displaystyle n=p\cdot q$ حينها وبما أنَّ المفتاح العمومي موجود ولنفرض أنّه ${\displaystyle e$ لنجد المفتاح الخصوصي d :

1- نجد مؤشر أويلر للعدد n : ${\displaystyle \phi (n)=(p-1)(q-1)$

2- نحل المعادلة ${\displaystyle ed\equiv 1(mod\ \phi (n))$

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

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

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

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

لايجاد أعداد أولية ${\displaystyle p}$

السرعة

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

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

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

انظر أيضا

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

المراجع