شرح مفصل لخوارزمية التشفير RSA
لمحة تاريخية :
وضعت خوارزمية التشفير هذه في عام 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
شغل شغل شغل 5/5
جميل ...
(:
رد: شرح مفصل لخوارزمية التشفير RSA
.... ألطافك يا الله ...
لم أتوقع أبدأ أن أجد شخص بهذا القدر من الإهتمام .. والله إنك متميز كثييييييير
بصراحة .. أقدر الآن أن أقول ... يمكننا البدء في إنشاء مشاريع كبيرة ... بمثل هذا الإهتمام ..
راح تكون لغة البرمجة المستخدمة VB لسهولتها .. ولأنها ما تحتاج FrameWork .
قل لي متى جاهر على شان نبدأ .. ولو تريد .. من الآن نبدأ ..
رد: شرح مفصل لخوارزمية التشفير RSA
سلام
مستعد ان شاء الله :)
بس نوضح الأمور اكثر عن نوعية البرامج
وبعض الوقت لاني مشغوووووووووووول اليومين:bigeyes:
رد: شرح مفصل لخوارزمية التشفير RSA
ااااااااااااااااااااااااااااااااااااة:bigeyes:
لسة مقفل الكمبيوتر ومشغلة من جديد قبل 6 ثواني جات لي فكرة جهنمية
من خلال مطالعتي لعالم الهاكرز وحماية الويب لاحظت خطورة عرض الكود المصدري لصفحات الويب
خاصة عند محاولة المهاجم لادخال بيانات غير متوقة إلى السرفر حيث يقوم احيانا بإعطاء معلومات
حساسة من موقع حدوث الخطاءو عن اسامي الحقول في قواعد البيانات وغيرها والكثير من الأمور طبعا هذة المعلومات ماتكون موجود عند عرض الصفحةلا تكون موجودة في السورس كود والهاكرز خبراء في كيفية استدراج السيرفرات عشان تسرب هذي المعلومات:D :D
امممممممممممممممممممم طيب :33: :33:
ايش رايكم بمشورع تشفير للكود المصدري حيث نقوم بالتشفير ووضع الكود المشفر في صفحة ويب على السرفر ونقوم بعمل برنامج اخر يرتبط بمتصفح الإنترنت لفك تشفير هذا الكود
وبهذة الطريقة من المستحيل على الهاكرز الحصول على ا معلومااااااااات:boggled: :boggled: :boggled:
منتظرين ارائكم :bigok:
رد: شرح مفصل لخوارزمية التشفير RSA
اقتباس:
المشاركة الأصلية كتبت بواسطة majd_1232002
ااااااااااااااااااااااااااااااااااااة:bigeyes:
لسة مقفل الكمبيوتر ومشغلة من جديد قبل 6 ثواني جات لي فكرة جهنمية
من خلال مطالعتي لعالم الهاكرز وحماية الويب لاحظت خطورة عرض الكود المصدري لصفحات الويب
خاصة عند محاولة المهاجم لادخال بيانات غير متوقة إلى السرفر حيث يقوم احيانا بإعطاء معلومات
حساسة من موقع حدوث الخطاءو عن اسامي الحقول في قواعد البيانات وغيرها والكثير من الأمور طبعا هذة المعلومات ماتكون موجود عند عرض الصفحةلا تكون موجودة في السورس كود والهاكرز خبراء في كيفية استدراج السيرفرات عشان تسرب هذي المعلومات:D :D
امممممممممممممممممممم طيب :33: :33:
ايش رايكم بمشورع تشفير للكود المصدري حيث نقوم بالتشفير ووضع الكود المشفر في صفحة ويب على السرفر ونقوم بعمل برنامج اخر يرتبط بمتصفح الإنترنت لفك تشفير هذا الكود
وبهذة الطريقة من المستحيل على الهاكرز الحصول على ا معلومااااااااات:boggled: :boggled: :boggled:
منتظرين ارائكم :bigok:
مشروعك فكرته غامضة .. ما فهمت إشي ..
يعني هلأ إنت بدك تعمل Browser ... ولا برنامج ؟؟
وما قصدك بالبرنامج المصدري .. قصدك ال HTML ؟؟؟ و صفحات ال PHP وال ASP ؟؟؟
إذا كان هيك قصدك .. فال PHP وال ASP يتم تشغيلها على السيرفر .. والهاكر ما يستطيعون رؤيتها ...
وبالنسبة للأخطاء ... قصدك مثلاً ( خطأ في إدخال إسم في التيبل الفلاني .. ذو الرقم العلنتاني ؟؟)
يا ريت توضح أكثر من ذلك ..
رد: شرح مفصل لخوارزمية التشفير RSA
اقتباس:
مشروعك فكرته غامضة .. ما فهمت إشي ..
يعني هلأ إنت بدك تعمل Browser ... ولا برنامج ؟؟
وما قصدك بالبرنامج المصدري .. قصدك ال HTML ؟؟؟ و صفحات ال PHP وال ASP ؟؟؟
إذا كان هيك قصدك .. فال PHP وال ASP يتم تشغيلها على السيرفر .. والهاكر ما يستطيعون رؤيتها ...
وبالنسبة للأخطاء ... قصدك مثلاً ( خطأ في إدخال إسم في التيبل الفلاني .. ذو الرقم العلنتاني ؟؟)
يا ريت توضح أكثر من ذلك ..
السلام عليكم
اقصد بالكود المصدري السورس كود لصفحة الويب الي تطلع عندنا لاتنسى اخي انة في صفحات الويب
التي ترتبط بقواعد البيانات تحمل اسماء للمتغيرات التي تحمل معلومات يتطلبها السيرفر مثل طلب إستعلام من قاعدة بيانات قد يتم عمل إخفاء للمتغيرات حيث لاتظهر في الوصلة لاكن يمكن العثور على هذة المتغيرات بكل سهولة من الكود المصدري للصفحة
اقتباس:
فال PHP وال ASP يتم تشغيلها على السيرفر .. والهاكر ما يستطيعون رؤيتها ...
كلام سليم لاكن ليس المقصود رؤية كود ال اي اس بي او بي اتش بي
اقصد عند وجود تغرات في الموقع مع إرسال تعليمات معينة الى السرفر تظهر لنا رسالة خطاء من السيرفر او قاعدة البيانات رسالة الخطاء هذة تفيد المخترقين بتفاصيل مهمة عن قاعدة البيانات او اليرفر بشكل عام مما يسهل الإختراق
اقتباس:
يعني هلأ إنت بدك تعمل Browser ... ولا برنامج ؟؟
عمل برنامج يقوم بتشفير ملفات ال HTML-ASP-PHP.......etc
ومن ثم نضع الملفات على السرفر بالشكل المشفر
وعمل برنامج اخر (ليس متصفح مستقل) يرتبط مع الـ internet Explorer ليقوم بفك التشفير
والمعذرة انا دائما سيء التعبير عن افكاري:09:
رد: شرح مفصل لخوارزمية التشفير RSA
فكرة رائعة .. ولكنها تحتاج لوقت ... وكمان تحتاج لبرنامج يقوم بتفهيم السيرفر إنوا هذه الصفحة مشفرة ..
وللعلم .. أتوقع إنوا الهاكر لو ضلوا وراها .. ممكن يكسروا شيفرتها .. ويحصلوا على معلومات من نفس الشيفرة تسهل عليهم عملهم .
بس للآن ما أخبرتني ؟؟؟
شو صار بال RSA ؟؟؟؟ وين وصلت فيها ؟
أنا منتظر ردك
رد: شرح مفصل لخوارزمية التشفير RSA
سلام عليكم
اقتباس:
وللعلم .. أتوقع إنوا الهاكر لو ضلوا وراها .. ممكن يكسروا شيفرتها .. ويحصلوا على معلومات من نفس الشيفرة تسهل عليهم عملهم .
مثل هذي الشفرات تحتاج إلى وقت لكسرها
لو عملنا اكثر من مفتاح والمفتاح يتغير كل 24 ساعة فهكذا سيصعب كسر الشفرة
