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

خوارزمية ال ار اس ايه 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 بشرط أن يكونRelation، و e وRelation ليس لهم اي عامل مشترك غير ال 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, d=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). لنفترض ان توفيق له طريقة ما لإعطاء أحمد مفاتيح تحكمية وجعله يصدق ان هذه المفاتيح هي مفاتيح سهيلة. لنفترض أيضا ان سهيلة قادرة على ان تقطع الرسائل بين أحمد وتوفيق. سهيلة تقوم بارسال مفتاحها العام لأحمد والتي يعتقد أحمد انها مفاتيح توفيق، ومن ثم يستطيع توفيق ان يقطع أي نص مشفر مرسل بواسطة أحمد ومن ثم فك تشفيره بمفتاحه السري الخاص وابقاء نسخة من هذه الرسالة ومن ثم تشفيرها بمفتاح سهيلة ثم إرسال النص المشفر الجديد لسهيلة. في الحقيقة ان أحمد وسهيلة لا يستطيعوا ان يكشفوا وجود توفيق. الدفاعات ضد كهذه الهجومات كثيرا ما تكون معتمدة على الشهادات الرقمية أو مكونات أخرى للبنية التحتية للمفتاح العام.

RSA بشيفرة الفيجوال البيسك

Public Class MyRSA

      Public Function isPrime(ByVal v As Byte) As Boolean
       For i = 2 To v - 1
           If v Mod i = 0 Then
               Return False
           End If
       Next
       Return True
   End Function

   Private _Prime1 As Byte
   Public Property Prim1() As Byte
       Get
           Return _Prime1
       End Get
       Set(ByVal value As Byte)
           If Not isPrime(value) Then
               Throw New Exception("The Number is not Prim")
           End If
           _Prime1 = value
       End Set
   End Property

   Private _Prime2 As Byte
   Public Property Prim2() As Byte
       Get
           Return _Prime2
       End Get
       Set(ByVal value As Byte)
           If Not isPrime(value) Then
               Throw New Exception("The Number is not Prim")
           End If
           _Prime2 = value
       End Set
   End Property

   Private _Prime3 As Byte
   Public Property Prim3() As Byte
       Get
           Return _Prime3
       End Get
       Set(ByVal value As Byte)
           If Not isPrime(value) Then
               Throw New Exception("The Number is not Prim")
           End If
           _Prime3 = value
       End Set
   End Property

   Private _E As Byte
   Public Property E() As Byte
       Get
           Return _E
       End Get
       Set(ByVal value As Byte)
           _E = value
       End Set
   End Property

   Private _d As Integer
   Public ReadOnly Property D() As Integer
       Get
           Dim s = 0
           _d = 1
           Do
               s = (_d * E) Mod phi
               _d += 1
           Loop While (s <> 1)
           _d = _d - 1
           Return _d
       End Get

   End Property

   Public Function Phi() As Integer
       Return (Prim1 - 1) * (Prim2 - 1) * (Prim3 - 1)
   End Function

   Public Function n() As Integer
       Return (Prim1) * (Prim2) * (Prim3)
   End Function

   Function Check() As Integer
       Dim i = 3
       While (e Mod i == 0) And (phi Mod i == 0)
           i += 2
           Return 1
       End While
       Return 0
   End Function
   Function encrypt(ByVal M As Byte) As Byte
       Dim i As Byte = 0
       C = 1
       For i = 0 To E - 1
           C = C * M Mod n()
           C = C Mod n()
       Next
       Return C Xor E
   End Function
   Function decrypt(ByVal K As Byte) As Byte
       K = K Xor E
       Dim i As Byte
       Dim M = 1
       For i = 0 To D - 1
           M = M * K Mod n()
           M = M Mod n()
       Next
       Return M
   End Function
   Public Function EncryptString(ByVal S As String) As String
       Dim asc As Byte
       Dim st = ""
       Dim enc As New System.Text.UnicodeEncoding
       Dim Bytes() As Byte = enc.GetBytes(S)
       Dim i = 0
       For Each B In Bytes
           asc = encrypt(B)
           Bytes(i) = asc
           i = i + 1
       Next
       Return enc.GetChars(Bytes)

   End Function
   Public Function DecryptString(ByVal S As String) As String

       Dim asc As Byte
       Dim st = ""
       Dim enc As New System.Text.UnicodeEncoding
       Dim Bytes() As Byte = enc.GetBytes(S)
       Dim i = 0
       For Each B In Bytes
           asc = decrypt(B)
           Bytes(i) = asc
           i = i + 1
       Next
       Return enc.GetChars(Bytes)

   End Function
   Public Function EncryptBytes(ByVal B() As Byte) As Byte()
       For i = 0 To B.Length - 1
           B(i) = encrypt(B(i))
       Next
       Return B
   End Function
   Public Function DecryptBytes(ByVal B() As Byte) As Byte()
       For i = 0 To B.Length - 1
           B(i) = decrypt(B(i))
       Next
       Return B
   End Function
   Public Sub EnryptFile(ByVal inputFile As String, ByVal outFile As String)
       Dim inFile As New IO.FileStream(inputFile, IO.FileMode.Open)
       Dim oFile As New IO.FileStream(outFile, IO.FileMode.Create)
       Dim B(0 To 1023) As Byte
       Dim L As Integer
       While True
           L = inFile.Read(B, 0, B.Length - 1)
           If L = 0 Then
               Exit While
           End If
           B = EncryptBytes(B)
           oFile.Write(B, 0, L)
       End While
       inFile.Close()
       oFile.Close()
   End Sub
   Public Sub DeryptFile(ByVal inputFile As String, ByVal outFile As String)
       Dim inFile As New IO.FileStream(inputFile, IO.FileMode.Open)
       Dim oFile As New IO.FileStream(outFile, IO.FileMode.Create)
       Dim B(0 To 1023) As Byte
       Dim L As Integer
       While True
           L = inFile.Read(B, 0, B.Length - 1)
           If L = 0 Then
               Exit While
           End If
           B = DecryptBytes(B)
           oFile.Write(B, 0, L)
       End While
       inFile.Close()
       oFile.Close()
   End Sub

End Class

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

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

bg:RSA ca:RSA cs:RSA da:RSA de:RSA-Kryptosystem el:RSA RSA]] eo:RSA es:RSA et:RSA (algoritm) eu:RSA fa:آراس‌ای fi:RSA fr:Rivest Shamir Adleman gl:RSA he:RSA hr:RSA hu:RSA-eljárás id:RSA is:RSA it:RSA ja:RSA暗号 ka:RSA ალგორითმი ko:RSA 암호 lt:RSA lv:RSA šifrēšanas algoritms nl:RSA (cryptografie) no:RSA pl:RSA (kryptografia) pt:RSA ro:RSA ru:RSA simple:RSA sl:RSA sr:RSA sv:RSA th:RSA tr:RSA uk:RSA vi:RSA (mã hóa) zh:RSA加密演算法