أخبار عاجلة

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

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

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

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

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

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

  1. اختيار عددين أوَلييّن عشوائييّن كبيرين مختلفين q و p.
  2. حساب n p cdot q ! . يُسْتَخْدَم n معاملا لكلا المفتاحين الخاصّة والعامّة.
  3. حساب phi(n) (p-1)(q-1) .حيث أنَّ الدالة phi (n) تعطي عدد الأعداد التي بين 2 و n والتي هي أولية مع n أي أنه GCD(n,i) 1 حيث 2le i le n .
  4. اختيار عدد صحيح بشكل عشوائي e حيث 2 le e le phi (n) و GCD(phi (n) ,e) 1 (أَي أَنَّ العددين e و- phi (n) (يعني أنَّ e in mathbb Z ^*_ n ) أعداد أولية فيما بينها أوليين فيما بينهما ) . هذا العدد e سوف يكون الأُس العمومي.
  5. ايجاد قيمة d او المفتاح الخصوصي ,بحيث أنَّه يُحقق التالي d cdot e equiv 1 (mod phi (n)) , ويمكن حساب المعادلة الاخيرة بواسطة خوارزمية اقليدس المُوسعة . d سوف يكون الأُس الخصوصي .

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

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

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

لنفرض أن A و- B يريدان أن يتواصلا فيما بينهما. لنفرض أَنَّ مفتاح A العمومي هو (n_A,e_A ) أما المفتاح الخصوصي هو (n_A,d_A ) ومفتاح B العمومي هو (n_B,e_B ) والمفتاح الخصوصي (n_B,d_B ) .

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

  1. يحصل على المفتاح العام للمستقبل B والذي هو (n_B, e_B) .
  2. وجد ناتج التشفير لهذا الرقم عن طريق المعادلة c m^ e_B (mod ~ n_B)
  3. يُرسِل c إلى B.
ملاحظة
  • إذا كانت الرسالة مكتوبة بالحروف حينها يجب أولا تحويلها لشكل مناسب حيث يتوافق مع العمليات الحسابية ويمكن أن يتم هذا بتحويل الرسالة إلى أسكي نظام أسكي .
  • فك تَشْفير الرسائلِ

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

    يستخدم مفتاحه الخاص (n_B, d_B) ويحسب m c^ d_B (mod ~ n_B) . حينها m هي الرسالة التي بعث بها A

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

    في كل نظام تشفير أهم خصلة يجب ان تتوفر فيه أنَّه يحقق الصفة التالية D(E(m,e),d) m اي أنَّه اذا شفرنا رسالة ثم فككنا التشفير نحصل على نفس الرسالة . وهذا أيضا صحيح ل-RSA
    E(m,e) m^e (mod n) وفك التشفير هو 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. اختيار اثنين من الاعداد الأولية p 61 mbox and q 53
    2. حساب n pcdot q ,! اي نفذ التالي n 61cdot 53 3233
    3. حساب phi (n) (p-1)cdot(q-1) حيث أنَّ phi (n) هو مؤشر أويلر . phi(n) (61-1)(53-1) 3120 .
    4. اختيار e > 1 الذي ليس له اي عامل مشترك مع 3120 , مثل e 17.
    5. نختار d بحيث d cdot e equiv 1 (mod phi (n)) , مثلا نختار d 2753 وهو ملائم لانه 2753 cdot 17 (mod ~ 3120 ) equiv 46801 (mod ~ 3120 ) equiv 1

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

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

    لنفرض انَّه يُراد تشفير m 123، وهذا يكون كالتالي c 123^ 17 (mod 3233) 855 (mod 3233 )

    وفك تشفير c 855، يكون ب- m 855^ 2753 (mod 3233) 123 .

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

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

    فليكن a,k,n اعداد صحيحة عندها يمكن حساب a^k (mod n) والتعقيد الحسابي للخوارزمية هو 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 بواسطة النظام الثنائي اي أنَّه k k_0+k_1 cdot 2+cdots +k_ s-1 cdot 2^ s-1 حينها كل ما علينا هو حساب 2^ 2^j (mod n) (j 1,2,cdots,s-1)

    مثال نريد أن نحسب y 1311^ 134 (mod 39979)

    1. نحسب 134 بالنظام الثنائي وهو 134 128+4+2 2^7+2^2+2^1
    2. نحسب T_j 1311^ 2^j لكل 1 le j le 7 بطريقة التربيع المتكرر اي
    T_1 T_0^2(mod 39979)

    T_2 T_1^2(mod 39979)

    vdots

    T_7 T_6^2(mod 39979)

    3. حينها y يكون حاصل ضرب كالتالي 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 أردنا أن نجد d بحيث يتحقق edequiv 1 (mod phi(n)) لذا فإنه علينا أن نجد d equiv e^ -1 (mod phi(n)) لذا سوف نستخدم خوارزمية اقليدس المُوسعة والسبب هو بما أنَّ gcd(e,phi(n)) 1 حينها يمكن ايجاد عددين صحيحين a,b بحيث acdot e +b cdot phi(n) 1 Rightarrow (acdot e +b cdot phi(n))(mod phi(n)) 1(mod phi (n)) Rightarrow a cdot e 1 (mod phi(n)) , لذا فان العدد a سوف يكون d . الخوارزمية تعقيدها O(log^2_2(n)) .

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

  • أيسر الوسائل لخرق امان الخوارزمية هي ايجاد عوامل العدد n , لنقل انه يمكن ايجاد عوامل n بالاضافة لنفرض أنَّ n pcdot q حينها وبما أنَّ المفتاح العمومي موجود ولنفرض أنّه e لنجد المفتاح الخصوصي d
  • 1- نجد مؤشر أويلر للعدد n phi(n) (p-1)(q-1)

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

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

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

    • p و- q لا يجب أن يكون قريبين جدا خشية ان التحليل إلى العوامل على طريقة فيرمات ل n ان تكون ناجحة، إذا p و q على سبيل المثال هم اقل من 2n^ frac14 سوف يكون الحل ل p و q سهل. بالإضافة إلى ذلك إذا كانت اي من p -1 أو q-1 لهم عوامل اولية صغيرة فقط، ممكن ان تحلل n إلى عواملها يشكل سريع عن طريق خوارزمية بولارد وهذه القيم ل p و q يجب أن تهمل.
    • من المهم ان يكون المفتاح السري كبير كفاية، حيث اثبت السيد michel wiener في عام 1990 انه إذا q le p le 2q و d
      في علم التشفير ، آر إس إيه إنك RSA هي خوارزمية للتشفير بواسطة مفتاح عام. ولعلها الأولى المعروفةً على هذا الصعيد، وهي مناسبة للتّوقيع بالإضافة إلى التشفير، وكانت أحد التقدّمات العظيمة الأولى في التشفير بواسطة مفتاح عامّ. آر إس إيه مستخدم في بروتوكولات التّجارة الإلكترونيّة على نطاق واسع، وهي آمنة طالما كان طول المفتاح طويلا جدا مثل 1024 بت، وهي تعتمد بشكل كبير على أنَّه لا يوجد خوارزمية لتحليل عدد لعوامل بسرعة عالية.

    اترك تعليقاً

    لن يتم نشر عنوان بريدك الإلكتروني.