لمحة تاريخية :
وضعت خوارزمية التشفير هذه في عام 1977 من قبل العلماء Ron Rivest و Adi Shamir و Len Adleman في معهد ماسشيوتس للتكنولوجيا في الولايات المتحدة الأمريكية وسميت اختصارا ً لأسمائهم RSA.
لم تنشر الخوارزمية حتى عام 1997 بسبب سريتها.
نظرة عامة:
تحتوي هذه الطريقة على مفتاحين عام وخاص, العام يكون معروفا ً من قبل أي شخص ويستعمل لتشفير الرسائل, بينما يكون الخاص سريا ً ويستخدم لفك تشفير الرسائل.
تعتمد هذ الخوارزمية بشكل أساسي على رياضيات بواقي القسمة والتي سألخصها بالنقاط الآتية:
كود:
- <LI class=MsoNormal>X = a ( mod b) à X = k * b + a k is a natural number
- X1 = Y1 ( mod a )
X2 = Y2 ( mod a ) à X1 (* or +) X2 = Y1 (* or +) Y2 ( mod a )
Example :
9835 = 7 ( mod 12 )
1176 = 0 ( mod 12 )
Therefore:
9835 + 1176 = 11011 = 7 + 0 ( mod 12 ) = 7 ( mod 12 )
9835 * 1176 = 11565960 = 7 * 0 ( mod 12 ) = 0 ( mod 12 )
وتعتمد طريقة التشفير هذه أيضا ً بشك كبير على الأعداد الأولية والتي تعد أساسا ً هاما ً في الرياضيات وخاصة في تحليل الأعداد إلى عواملها الأولية حيث أن أي رقم يمكن كتابته بطريقة وحيدة فقط كجداء عوامله الأولية.
( على فكرة أحب أن أنوه إلى أن العدد 1 لا يعد أوليا ً, حيث أنه لو كان أوليا ً لأمكن إيجاد عدة صيغ للعدد كجداء عوامل أولية).
تابع Totient للعالم Euler :
مراجعة صغيرة : إذا كان القاسم المشترك الأكبر لعددين هو الواحد فإننا نقول عينهما " أوليان فيما بينهما ".
يعطي هذا التابع عدد الأعداد الأولية فيما بينها مع العدد N , ويرمز له بالحرف الإغريقي فاي Phi Φ .
كود:
Φ ( N ) = how many numbers between 1 and N are relatively prime to N.
And Φ ( 1 ) = 1
Examples:
Φ ( 4 ) = 2 ( 1 and 3 )
Φ ( 5 ) = 4 ( 1, 2, 3 and 4 )
Φ ( 6 ) = 2 ( 1 and 5 )
Φ ( 7 ) = 6 ( 1, 2, 3, 4, 5 and 6 )
وإذا كان N عبارة عن جداء عددين أوليين P و Q فإن :
كود:
Φ ( N ) = ( P – 1 ) * ( Q – 1 )
e.g. Φ ( 15 ) = 2 * 4 = 8 ( 1, 2, 4, 7, 8, 11, 13 and 14 )
نظرية Totient للعالم Euler :
تنص النظرية على ما يلي :
إذا كان T و R أوليان فيما بينهما, وكان T < R, فإننا إذا رفعنا T للقوة Φ ( R ) وقسمنا الناتج على R فإن باقي القسمة هو 1 دائما ً.
كود:
If GCD ( T, R ) = 1 AND T < R Then T ^ (Φ ( R )) = 1 ( mod R )
مثال :
كود:
Φ ( 6 ) = ( 2 – 1 ) * ( 3 – 1 ) = 1 * 2 = 2
5 ^ (Φ (6 )) = 5 ^ 2 = 25
25 = 24 + 1 = 6 * 4 + 1 = 1 ( mod 6 )
Φ ( 15 ) = ( 3 – 1 ) * ( 5 – 1 ) = 8
2 ^ (Φ ( 15 )) = 2 ^ 8 = 256
256 = 255 + 1 = 17 * 15 + 1 = 1 ( mod 15 )
شكل آخر للنظرية ينتج معنا من المعادلة:
كود:
T ^ (Φ ( R )) = 1 ( mod R )
نضرب الطرفين بـ T ^ (Φ ( R )) :
كود:
T ^ (Φ ( R )) * T ^ (Φ ( R )) = 1 * 1 ( mod R )
T ^ (2 * Φ ( R )) = 1 ( mod R )
وبتكرار العملية :
كود:
T ^ (K * Φ ( R )) = 1 ( mod R )
وبترميز :
كود:
S = K * Φ ( R )
T ^ S = 1 ( mod R )
وينتج لدينا النظرية :
كود:
If GCD( T, R ) = 1 AND T < R Then T ^ S = 1 ( mod R )
whenever S = 0 ( mod Φ ( R ))
ويمكننا أيضا ً بضرب الطرفين الآن بـ T أن نستنتج :
كود:
T ^ ( S + M ) = T ^ M ( mod R )
Since S = 0 ( mod Φ ( R )) then S + M = M ( mod Φ ( R ))
Therefore
T ^ E = T ^ F ( mod R ) whenever E = F ( mod Φ ( R ) )
اقتربنا الآن من استنتاج شيء هام جدا ً, لنعد أدراجنا إلى المعادلة :
كود:
T ^ ( S + M ) = T ^ M ( mod R )
We put M = 1 :
T ^ ( S + 1 ) = T ( mod R )
ستتساءلون ما المهم هنا؟ الجواب هو أننا أخذنا T ورفعناه إلى قوة معينة, وبحسابات بسيطة في رياضيات باقي القسمة استطعنا أن نجد T مرة أخرى.
مرة أخرى أين تكمن الأهمية في ذلك؟ تخيلوا لو أننا قسمنا العملية السابقة إلى عمليتين كالتالي :
نبحث عن عددين P و Q واللذان يحققان المعادلة :
أو بشكل أفضل :
كود:
P * Q = 1 ( mod Φ ( R ))
فباستطاعتنا كتابة :
كود:
T ^ ( P * Q ) = T ( mod R )
( T ^ P ) ^ Q = T ( mod R )
وبترميز :
نجد التالي :
كود:
T ^ P = X ( mod R )
X ^ Q = T ( mod R )
تخيلوا الآن أن كلا ً من العمليتين تم إجراؤهما على جهازي كمبيوتر منفصلين, وتم إرسال X عبر خط هاتف أو شبكة غير محمي من الجهاز الأول للثاني.
T تعبر عن نص الرسالة الأصلي, P و Q و R هم تمثل مفاتيح الشيفرة -- حيث P و R يسميان بالمفتاح العام ويسمى Q و R بالمفتاح الخاص, وتصبح X الرسالة بعد التشفير!
لاحظو أن كلا ً من P و Q سيكونان أوليان فيما بينهما وبين Φ ( R ) وذلك لأن:
لو امتلك أيا ً منهما قاسما ً مشتركا ً مع Φ ( R ) فإن جداءهما P * Q سيملك هذا العدد كقاسم أيضا ً, ولكننا نعلم أن باقي قسمة P * Q على Φ ( R ) هو 1.
لو أنه كان العكس لكنا حصلنا في بعض الأحيان على X = T وبالتالي لن نعرف أهي مشفرة أم لا, وأيضا ً فإننا سنعثر على أكثر من قيمة لـ Q والتي تعيد T من X .
تكمن القوة في هذه العملية كما التالي :
لو أن العمليتين كانتا :
وكما نعلم فإن P معروف بشكل عام فإنه من السهل الوصول لـ T عن طريق X دون معرفة Q.
لكن العمليتين لدينا :
كود:
T ^ P = X ( mod R )
X ^ Q = T ( mod R )
والتي يصعب فيها إيجاد T من X دون معرفة Q .
لنجعل هذه العملية قيد العمل:
لكي نبدأ بالتشفير يجب علينا أن نصنع زوجا ً من المفاتيح, ولعمل ذلك نحتاج لأن نختار قيمة مناسبة لـ R.
لذا سنبدأ عشوائيا ً باختيار عددين أوليين U و V ونأخذ جاءهما :
وهناك سببان لاختيارنا عددين أوليين:
أولا ً نستطيع بسهولة حساب Φ ( R ) حيث :
كود:
Φ ( R ) = ( U – 1 ) * ( V – 1 )
ثانيا ً نريد أن يكون R صعب التحليل فكلما قل عدد عوامله فإنه يزداد الوقت اللازم لإيجاده.
والآن نريد أن نجد قيما ً لـ Q و P والتي تحقق المعادلة :
كود:
P * Q = 1 ( mod Φ ( R ))
وبعد اختيار القيمتين يمكننا نسيان U و V لأننا لن نحتاجهم بعد الآن.
مثال :
سنختار في هذا المثال أعدادا ً يسهل التعامل معها فقط لكي نفهم الفكرة بشكل أوضح.
لنأخذ R = 55 = 5 * 11 وبالتالي:
Φ ( 55 ) = 40
والآن نبحث عن P و Q :
أول ما يهمنا في البحث عن العددين P و Q هو أن يكونا أوليان فيما بينهما وبين الـ 40 لذلك سنستبعد مضاعفات الـ 2 والـ 5. نريد أيضا ً منهما أن يكونا عمليا ً أوليان فيما بينهما أيضا ً. لنعطي P قيمة 7 ونبحث عن Q :
7 * Q = 1 ( mod 40 )
7 * Q = K * 40 + 1
أول قيمة تبقي Q عددا ً صحيحا ً هي K = 4 :
7 * Q = 4 * 40 + 1 = 161
Therefore
Q = 161 / 7 = 23
إذا استطعنا أن نجد P = 7 و Q = 23 , وهكذا نكون قد انتهينا من صناعة المفاتيح.
وللتشفير يجب أن نتذكر أن T < R أي أننا سنقوم بترميز المحارف بحيث لا نتجاوز الـ R - 1 , ولا نريد أيضا ً استخدام الواحد في الترميز لأن الواحد إذا رفع لأي قوة يبقى واحد, ولا ننسى أن T و R أوليان فيما بينهما فلن نستخدم مضاعفات الـ 5 و مضاعفات الـ 11 :
كود:
A B C D E F G H I J K L M
2 3 4 6 7 8 9 12 13 14 16 17 18
N O P Q R S T U V W X Y Z
19 21 23 24 26 27 28 29 31 32 34 36 37
Space 0 1 2 3 4 5 6 7 8 9 *
38 39 41 42 43 46 47 48 49 51 52 53
والآن لنقم بتشفير كلمة "VENIO" :
كود:
V E N I O
31 7 19 13 21
والآن نقوم برفع كل حرف من هذه الأحرف للقوة P ونأخذ باقي قسمة الناتج على R :
كود:
V: 31 ^ 7 (mod 55) = 27512614111 (mod 55) = 26
E: 7 ^ 7 (mod 55) = 823543 (mod 55) = 28
N: 19 ^ 7 (mod 55) = 893871739 (mod 55) = 24
I: 13 ^ 7 (mod 55) = 62748517 (mod 55) = 7
O: 21 ^ 7 (mod 55) = 1801088541 (mod 55) = 21
والآن أصبحت الرسالة بعد التشفير 26, 28, 24, 7, 21 أو "RTQEO" بالتعبير عنها من خلال الجدول الذي وضعناه أعلاه.
عندما تصل الكلمة "RTQEO" للطرف الآخر فإنه سيقوم برفع كل حرف للقوة Q ويأخذ باقي قسمة الناتج على R :
كود:
R: 26^23 (mod 55) = 350257144982200575261531309080576 (mod 55) = 31
T: 28^23 (mod 55) = 1925904380037276068854119113162752 (mod 55) = 7
Q: 24^23 (mod 55) = 55572324035428505185378394701824 (mod 55) = 19
E: 7^23 (mod 55) = 27368747340080916343 (mod 55) = 13
O: 21^23 (mod 55) = 2576580875108218291929075869661 (mod 55) = 21
وتكون النتيجة 31, 7, 19, 13, 21 أو "VENIO" , عدنا للرسالة الأصلية.
كيف نجعل من تشفيرنا تشفيرا ً صعب الكسر؟
في الحقيقة تكمن الصعوبة في كسر تشفير الـ RSA في إيجاد R , وكلما زادت قيمة R زادت صعوبة الحصول عليه, وبالمقابل فإننا سنحصل على Φ ( R ) أكبر, وبالتالي سنستطيع أن نغطي محارف أكثر بجدول التشفير ومن الممكن أن نستطيع أن نشفر أكثر من حرف في كل مرة مما سيزيد صعوبة كسر الشيفرة.
ولكن لن نعود قادرين على إيجاد P و Q باستخدام القلم والورقة, لذا سنستخدم الحاسب لهذه العملية, لكن احزروا أين تكمن المشكلة الآن؟
المشكلة ستكون في أننا لن نستطيع أن نستخدم متغيرا ً نضع فيه القيمة الكبيرة لناتج رفع الحرف لقوة كبيرة جدا ً, مما سيعطل عمل التشفير بالأرقام الكبيرة!
شو ارتعبتوا ؟ لا تخافو رح ندبرها بإذن الله.
القوى العظيمة باستخدام رياضيات باقي القسمة :
يوجد الآن بصيص أمل يكمن في استخدام رياضيات باقي القسمة لحساب القوى العظيمة.
إن نظرة سريعة على التعبير 9 ^ 9 ^ 9 ستجعلنا نعتقد بأن الناتج لن يكون كبيرا ً لهذا الحد إلا أن الناتج ببساطة عبارة عن عدد مؤلف من 369693100 خانة فقط!
كيف سنتمكن من تشفير البيانات دون استخدام التيرابايت للتخزين؟
ببساطة رح منكب الرامة يلي عنا ونستنا ليساوو رامة أكبر من 2 Terabyte ووقتها منفكر.
عمبمزح.
الطريقة بكل بساطة هي أن نقوم بحساب باقي قسمة كل قوة على R على حده, رياضيات باقي القسمة يصغر كل شيء كبير.
الآن لنتذكر المثال السابق:
كيف نحسب 28 ^ 23 ( mod 55 ) ؟
أولا ً ننظر إلى التركيبة الثنائية للـ 23 والتي هي 10111 أي:
23 = 16 + 4 + 2 + 1
Or
23 = 2 ^ 4 + 2 ^ 2 + 2 ^ 1 + 2 ^ 0
والآن نفكك القوة الكبيرة إلى جداء قوى صغيرة:
28 ^ 23 = 28 ^ ( 2 ^ 4 + 2 ^ 2 + 2 ^ 1 + 2 ^ 0 )
= 28 ^ ( 2 ^ 4 ) * 28 ^ ( 2 ^ 2 ) * 28 ^ 2 * 28
= 28 ^ ( 2 * 2 * 2 * 2 ) * 28 ^ ( 2 * 2 ) * 28 ^ 2 * 28
= (((28 ^ 2) ^ 2) ^ 2 ) ^ 2 * (28 ^ 2) ^ 2 * 28 ^ 2 * 28
بعرف أنو رح تقولو إجى ليكحلها قام عماها, يعني ما في شي بيشبه التبسيط بهاللعبة!
لكن الجميل الآن أنه لدينا الكثير من الحدود المتماثلة, وأيضا ً لا تنسوا أننا نحسب باقي القسمة على 55, والآن نحسب أول حد:
28 ^ 2 = 784 = 14 ( mod 55 )
نعوض في المعادلة :
28 ^ 23 = (((28 ^ 2) ^ 2) ^ 2 ) ^ 2 * (28 ^ 2) ^ 2 * 28 ^ 2 * 28 ( mod 55 )
فنجد :
28 ^ 23 = ((14 ^ 2) ^ 2) ^ 2 * 14 ^ 2 * 14 * 28 ( mod 55 )
And
14 ^ 2 = 196 = 31 ( mod 55 )
Therefore
28 ^ 23 = (31 ^ 2) ^ 2 * 31 * 14 * 28 ( mod 55 )
And finally
31 ^ 2 = 961 = 26 ( mod 55 )
26 ^ 2 = 676 = 16 ( mod 55 )
So
28 ^ 23 = 16 * 31 * 14 * 28 ( mod 55 )
الآن نحسب باقي قسمة جداء كل حدين على 55 ونعوضه بدلا منهما :
28 ^ 23 = 16 * 31 * 14 28 ( mod 55 )
= 16 * 31 * 392 ( mod 55 )
= 16 * 31 * 7 ( mod 55 )
= 16 * 217 ( mod 55 )
= 16 * 52 ( mod 55 )
= 832 ( mod 55 )
= 7 ( mod 55 ) = 1925904380037276068854119113162752 (mod 55)
شرح مفصل لخوارزمية التشفير RSA
رد: شرح مفصل لخوارزمية التشفير RSA
المشاركة الأصلية كتبت بواسطة majd_1232002
