[Powered by Google Translate] [RSA]
[روب بودين] [تومي MacWilliam] [جامعة هارفارد]
[هذا CS50.] [CS50.TV]
دعونا نلقي نظرة على RSA، وهي الخوارزمية المستخدمة على نطاق واسع لتشفير البيانات.
خوارزميات التشفير مثل قيصر والأصفار Vigenère ليست آمنة جدا.
مع الشفرات قيصر، مهاجم يحتاج فقط لمحاولة 25 مفاتيح مختلفة
للحصول على النص الرسالة عادي.
في حين أن الشفرات Vigenère أكثر أمانا من والشفرات قيصر
بسبب مساحة أكبر البحث عن مفاتيح، مرة واحدة لمهاجم
يعرف طول المفتاح في والشفرات Vigenère،
التي يمكن تحديدها عن طريق تحليل أنماط في النص المشفر،
والشفرات Vigenère ليست أكثر أمنا من والشفرات قيصر.
RSA، من ناحية أخرى، ليست عرضة لهجمات من هذا القبيل.
قيصر والشفرات والشفرات Vigenère استخدام نفس المفتاح
إلى كل من تشفير وفك تشفير الرسالة.
هذه الخاصية تجعل هذه الخوارزميات الأصفار مفتاح متماثل.
وهناك مشكلة أساسية مع خوارزميات مفتاح متماثل
هو أنها تعتمد على واحد تشفير وإرسال رسالة
وتلقي واحد وفك تشفير الرسالة
قد وافق بالفعل مقدما على المفتاح أنها سوف تستخدم كل.
ولكن لدينا قليلا من مشكلة بدء التشغيل هنا.
كيف أجهزة الكمبيوتر 2 التي ترغب في التواصل إنشاء مفتاح سري بينهما؟
إذا كان مفتاح يجب أن تكون سرية، فإننا بحاجة إلى وسيلة لتشفير وفك تشفير المفتاح.
إذا كل ما لدينا هو مفتاح متماثل التشفير
ثم كنت قد وصلنا للتو إلى نفس المشكلة.
RSA، من ناحية أخرى، تستخدم زوج من المفاتيح،
واحد للتشفير وآخر للفك التشفير.
واحد يسمى المفتاح العام، والآخر هو المفتاح الخاص.
يستخدم المفتاح العام لتشفير الرسائل.
كما قد يتبادر إلى ذهنك باسمه، يمكننا تبادل المفتاح العام لدينا مع
نريد أي شخص دون المساس بأمن رسالة مشفرة.
رسائل مشفرة باستخدام المفتاح العمومي
لا يمكن إلا أن يكون فك مع المفتاح الخاص المطابق.
بينما يمكنك مشاركة المفتاح العمومي الخاص بك، يجب أن تبقي دائما سرية المفتاح الخاص بك.
ويمكن استخدام المفتاح الخاص فقط على الرسائل فك تشفير
إذا 2 اعضاء ترغب في إرسال رسائل مشفرة مع RSA
جيئة وذهابا كل من المستخدمين في حاجة الى زوج المفاتيح الخاصة بها القطاعين العام والخاص.
رسائل من المستخدم 1 إلى المستخدم 2
الزوج فقط استخدام 2 عضو الرئيسية، ورسائل من المستخدم 2 إلى المستخدم 1
فقط استخدام زوج 1 عضو الرئيسية.
حقيقة وجود 2 مفاتيح منفصلة لتشفير الرسائل وفك تشفير
يجعل RSA خوارزمية مفتاح غير متناظر.
نحن لسنا بحاجة لتشفير المفتاح العام من أجل إرسالها إلى كمبيوتر آخر
منذ المفتاح العام على أي حال.
هذا يعني أن RSA ليس لديها نفس المشكلة بدء التشغيل
كما خوارزميات المفتاح المتماثل.
حتى لو كنت تريد إرسال الرسالة باستخدام التشفير RSA
لروب، أنا بحاجة أولا مفتاح روب العامة.
لتوليد زوج من المفاتيح، روب يحتاج لاختيار عدد 2 رئيس كبير.
وسوف تستخدم هذه الأرقام في كل من مفاتيح العامة والخاصة،
ولكن المفتاح العام فقط استخدام المنتج من هذه الأرقام 2،
لا الأرقام نفسها.
وبمجرد تشفير الرسالة باستخدام I مفتاح روب العامة
لا أستطيع إرسال الرسالة إلى روب.
لجهاز كمبيوتر، وأرقام التخصيم هو المشكلة الصعبة.
المفتاح العمومي، وتذكر، وتستخدم المنتج من 2 الأعداد الأولية.
يجب أن يكون هذا المنتج ثم فقط 2 العوامل،
الذي يحدث أن تكون الأرقام التي تشكل المفتاح الخاص.
من أجل فك تشفير الرسالة، وسوف RSA استخدام هذا المفتاح الخاص
أو ضرب الأرقام معا في عملية إنشاء المفتاح العمومي.
لأنه من الصعب حسابيا عامل عدد
المستخدمة في المفتاح العمومي في أرقام 2 المستخدمة في المفتاح الخاص
من الصعب للمهاجمين لمعرفة المفتاح الخاص
وسوف يكون من الضروري أن فك تشفير الرسالة.
الآن دعونا الخوض في بعض التفاصيل انخفاض مستوى RSA.
دعونا نرى أولا كيف يمكننا توليد زوج من المفاتيح.
أولا، سوف نحتاج 2 الأعداد الأولية.
سوف ندعو هذه الأرقام 2 ف س و.
من أجل اختيار p و q، من الناحية العملية فإننا توليد pseudorandomly
أعداد كبيرة ومن ثم استخدام اختبار لتحديد ما إذا كان أو لا
هذه الأرقام هي على الأرجح رئيس الوزراء.
نحن يمكن ان تبقى توليد أرقام عشوائية مرارا وتكرارا
حتى لدينا 2 يعبي أن نتمكن من استخدام.
دعونا هنا في اختيار p = 23 و س = 43.
نتذكر، في الممارسة العملية، يجب أن يكون س ص وأعداد أكبر من ذلك بكثير.
بقدر ما نعلم، فإن أكبر الأرقام، كلما كان من الصعب
للقضاء رسالة مشفرة.
لكنه أيضا أكثر تكلفة لتشفير وفك تشفير الرسائل.
اليوم أوصت في كثير من الأحيان أن p و q على الأقل 1024 بت،
الأمر الذي يضع كل رقم في أكثر من 300 أرقام عشرية.
ولكن سوف نختار هذه الأرقام الصغيرة على سبيل المثال هذا.
الآن سوف نضرب p و q معا للحصول على عدد 3،
الذي سوف نسميه ن.
في حالتنا، ن = 23 * 43، والتي = 989.
لدينا ن = 989.
المقبل سوف نضرب ف - 1 مع س - 1
للحصول على رقم 4، والذي سنتصل م.
في حالتنا، m = 22 * ​​42، والتي = 924.
لدينا م = 924.
الآن سوف نحتاج إلى عدد ه وهذا هو نسبيا لرئيس الحكومة م
وأقل من متر.
رقمين هي رئيس نسبيا أو coprime
إذا كان صحيحا موجبا الوحيد الذي يقسم بالتساوي لهم على حد سواء هو 1.
وبعبارة أخرى، فإن القاسم المشترك الأكبر من ه وم
يجب أن تكون 1.
في الممارسة العملية، فإنه من الشائع للبريد ليكون عدد أولي 65537
ما دام هذا العدد لا يحدث ليكون عاملا من عوامل م.
لدينا مفاتيح، سوف نختار ه = 5
منذ 5 هو رئيس نسبيا إلى 924.
وأخيرا، فإننا سوف تحتاج إلى واحد أكثر عدد، ونحن سوف ندعو د.
يجب أن يكون هناك بعض D قيمة ترضي معادلة دي = 1 (وزارة الدفاع م).
هذا يدل على وزارة الدفاع م سنستخدم ما يسمى وحدات حسابية.
في الحساب وحدات، مرة واحدة في عدد أعلى من يحصل بعض الحد الأعلى
فإنه سيتم التفاف حول العودة إلى 0.
على مدار الساعة، على سبيل المثال، يستخدم وحدات حسابية.
بعد دقيقة واحدة 01:59، على سبيل المثال، هو 2:00،
لا 1:60.
وقد لف حول عقرب الدقائق إلى 0
عند بلوغ الحد الأعلى من 60.
لذلك، يمكننا أن نقول أي ما يعادل 60 هو 0 (وزارة الدفاع 60)
و125 هو ما يعادل 65 ما يعادل 5 (وزارة الدفاع 60).
وسوف يكون لدينا مفتاح العامة ه ن الزوج و
حيث في هذه الحالة هو 5 ه وn هو 989.
وسوف يكون لدينا مفتاح الخاص د الزوج ون،
الذي هو في حالتنا 185 و 989.
لاحظت أن لدينا الأصلي يعبي p و q لا تظهر
لدينا في أي مكان في مفاتيح خاصة أو عامة.
الآن أن لدينا لدينا زوج من المفاتيح، دعونا نلقي نظرة على الطريقة التي يمكننا تشفير
وفك تشفير الرسالة.
أريد أن إرسال رسالة إلى روب،
وقال انه حتى تكون واحدة لتوليد مفتاح هذا الزوج.
ثم أنا أسأل روب للمفتاح علني له، والتي سوف تستخدم
لتشفير رسالة لإرسالها إليه.
تذكر، أنه بخير تماما عن روب لتبادل مفتاح علني له معي.
ولكن لن يكون حسنا لمشاركة مفتاحه الخاص.
ليس لدي أي فكرة عما هو مفتاحه الخاص.
يمكننا كسر م رسالتنا تصل إلى أجزاء عدة
جميع أصغر من ن ومن ثم تشفير كل من تلك القطع.
سنقوم تشفير CS50 السلسلة، والذي يمكننا تفريق إلى 4 قطع،
واحد لكل رسالة.
من أجل تشفير رسالتي، وأنا بحاجة لتحويله إلى
نوع من التمثيل رقمية.
دعونا سلسلة القيم ASCII مع شخصيات في رسالتي.
من أجل تشفير رسالة معينة م
أنا بحاجة لحساب ج = م ه إلى (ن وزارة الدفاع).
ولكن يجب أن يكون أصغر من م ن،
أو يمكن عدا ذلك لن يكون كاملا رسالة عبر مودولو ن.
يمكننا كسر م يصل إلى أجزاء عدة، وكلها أصغر من ن،
وتشفير كل من تلك القطع.
تشفير كل من هذه القطع، وحصلنا على C1 = 67 إلى 5 (وزارة الدفاع 989)
التي = 658.
لدينا الثانية قطعة لدينا من 83 إلى 5 (وزارة الدفاع 989)
الذي = 15.
لجزء الثالث من عمرنا لدينا 53 إلى 5 (وزارة الدفاع 989)
التي = 799.
وأخيرا، لدينا قطعة الماضي لدينا 48 إلى 5 (وزارة الدفاع 989)
= الذي 975.
الآن يمكننا أن نرسل أكثر من هذه القيم المشفرة إلى روب.
هنا تذهب، روب.
بينما رسالتنا هي في حالة فرار، دعونا نلقي نظرة أخرى
كيف وصلنا في تلك القيمة لد.
لدينا حاجة د عدد لتلبية 5D = 1 (وزارة الدفاع 924).
هذا يجعل د معكوس المضاعف من 5 مودولو 924.
أعطيت 2 أعداد صحيحة، و b، الخوارزمية الإقليدية الموسعة
يمكن استخدامها لإيجاد القاسم المشترك الأكبر من هذه الأعداد الصحيحة 2.
كما يعطي لنا 2 الأرقام الأخرى، X و Y،
التي تلبي الفأس المعادلة + = المقسوم عليه من قبل أكبر شيوعا من ألف وباء.
كيف هذا يساعدنا؟
حسنا، يسد في ه = 5 ل
وم = 924 ب
نحن نعلم بالفعل أن هذه الأرقام هي coprime.
المقسوم عليه من أعظم شيوعا هو 1.
هذا يعطينا 5X + 924y = 1
أو 5X = 1 - 924y.
ولكن إذا كنا نهتم فقط حول كل شيء مودولو 924
ثم يمكننا إسقاط - 924y.
فكر في العودة إلى الساعة.
إذا كان عقرب الدقائق على 1 و ثم تمرير 10 ساعة بالضبط،
نحن نعرف عقرب الدقائق ستظل على 1.
هنا نبدأ في 1 ثم يلتف حول ذ مرات بالضبط،
ولذا فإننا سوف يكون لا يزال في 1.
لدينا 5X = 1 (وزارة الدفاع 924).
وهنا هذا x هو نفس د كنا نبحث عن قبل،
إذا كان الأمر كذلك نستخدم خوارزمية ممتدة الإقليدية
للحصول على هذه × عدد، وهذا العدد يجب أن يستعمل مثل د لدينا.
الآن دعونا تشغيل الخوارزمية الإقليدية الموسعة ل5 =
وب = 924.
سنستخدم طريقة تسمى طريقة الجدول.
والجدول لدينا 4 أعمدة، س، ص، د، ك و.
طاولتنا يبدأ مع 2 صفوف.
في الصف الأول لدينا 1، 0، ثم لدينا من القيمة، والتي هي 5،
والصف الثاني هو لدينا 0، 1، وقيمة لدينا لب، وهو 924.
فإن قيمة العمود 4، ك، تكون نتيجة
تقسيم قيمة د في الصف فوقه مع قيمة د
في نفس الصف.
لدينا 5 مقسوما على 924 هي 0 مع بعض ما تبقى.
يعني ان علينا ك = 0.
الآن فإن قيمة كل خلية أخرى تكون قيمة الخلية الصفوف 2 فوقه
ناقص القيمة من الصف فوقه مرات ك.
دعونا نبدأ مع د في الصف 3.
لدينا 5 حتي 924 * 0 = 5.
المقبل لدينا 0 - 1 * 0 أي هو 0
و 1 - 0 * 0 الذي هو 1.
لا بأس بها، لذلك دعونا ننتقل إلى الصف التالي.
أولا نحن بحاجة لدينا من قيمة ك.
924 مقسمة بنسبة 184 = 5 مع بعض ما تبقى،
لذلك لدينا قيمة ك هو 184.
924 الآن - 5 * 184 = 4.
1-0 * 184 هو 1 و 0 - 1 * 184 -184 هو.
حسنا، دعونا نفعل الصف التالي.
وقيمة لدينا من ك 1 لأن يكون
5 مقسوما على 1 = 4 مع بعض ما تبقى.
دعونا ملء الأعمدة الأخرى.
5-4 * 1 = 1.
0-1 * 1 = -1.
و1 حتي 184 * 1 هو 185.
دعونا نرى ما هي القيمة القادم سيكون من ك.
حسنا، يبدو أن لدينا 4 مقسوما على 1، والذي هو 4.
في هذه الحالة حيث أننا تقسيم بحلول 1 ك بحيث يساوي
قيمة د في الصف أعلاه يعني أن ننتهي مع أنظمتنا.
هنا يمكننا أن نرى أن لدينا س = 185 و ص = -1 في الصف الأخير.
دعونا الآن نعود إلى هدفنا الأصلي.
قلنا أن قيمة X نتيجة لتشغيل هذه الخوارزمية
سيكون معكوس المضاعف من (وزارة الدفاع ب).
وهذا يعني أن 185 هو معكوس المضاعف من 5 (وزارة الدفاع 924)
وهو ما يعني أن لدينا قيمة لمن 185 د.
حقيقة أن د = 1 في الصف الأخير
ويتحقق coprime أن ه م ل.
لو لم يكن 1 ثم سيكون لدينا لاختيار البريد الجديد.
الآن دعونا نرى ما اذا كان روب تلقى رسالتي.
عندما يقوم شخص ما يرسل لي رسالة مشفرة
طالما كنت أبقى الرئيسية الخاصة بي سرا
أنا الشخص الوحيد الذي يستطيع فك تشفير الرسالة.
لجزء من فك تشفير ج يمكنني حساب الرسالة الأصلية
تساوي قطعة إلى السلطة د (ن وزارة الدفاع).
تذكر أن د ن وهي من مفتاحي الخاص.
للحصول على رسالة كاملة من قطع فيه، فك تشفير كل قطعة
وسلسلة النتائج.
بالضبط كيف هي آمنة RSA؟
الحقيقة هي، أننا لا نعرف.
ويستند الأمن بشأن كم من الوقت سيستغرق للمهاجمين للقضاء رسالة
تشفير RSA مع.
تذكر أن المهاجم لديه حق الوصول إلى المفتاح العمومي الخاص بك،
الذي يحتوي على كل وه ن.
إذا كان المهاجم تمكن من عامل ن يعبي (2)،، p و q،
ثم قالت انها يمكن ان يحسب د باستخدام خوارزمية ممتدة الإقليدية.
هذا يعطيها المفتاح الخاص، والتي يمكن استخدامها لفك تشفير أي رسالة.
ولكن كيف يمكن لنا بسرعة عامل الأعداد الصحيحة؟
مرة أخرى، نحن لا نعرف.
وقد وجدت لا أحد طريقة سريعة للقيام بذلك،
وهو ما يعني أنه نظرا كبيرة بما يكفي ن
سوف يستغرق فترة طويلة للمهاجمين بشكل غير واقعي
لعامل الرقم.
إذا كشف شخص طريقة سريعة من الأعداد الصحيحة العوملة
ويمكن تقسيم RSA.
ولكن حتى لو صحيح بطيئة بطبيعتها توكيل تجاري
يمكن للخوارزمية RSA التي لا تزال بعض الخلل في ذلك
فك التشفير التي تتيح سهولة الرسائل.
وقد وجدت أحد وكشف هذا الخلل بعد،
ولكن هذا لا يعني عدم وجود أحد.
من الناحية النظرية، يمكن أن يكون هناك شخص قراءة كل البيانات المشفرة مع RSA.
هناك نوعا آخر من قضية الخصوصية.
إذا تومي بتشفير الرسالة باستخدام بعض مفتاحي العام
وللمهاجمين بتشفير الرسالة باستخدام المفتاح الخاص بي نفس العام
سوف نرى أن المهاجم الرسائل 2 متطابقة
وبالتالي نعرف ما تومي تشفير.
من أجل منع هذا، وعادة مبطن الرسائل مع بت عشوائية
قبل تشفير بحيث نفس الرسالة مشفرة
سوف تبدو مختلفة عدة مرات طالما أن الحشو على رسالة مختلفة.
ولكن تذكر كيف علينا أن تقسيم الرسائل إلى أجزاء
بحيث كل قطعة أصغر من ن؟
حشوة وقطع يعني أن قد يكون لدينا لتقسيم الامور
إلى قطع أكثر حتى منذ يجب أن قطعة مبطن يكون أصغر من ن.
التشفير وفك التشفير هي مكلفة نسبيا مع RSA،
وهكذا يمكن أن تحتاج لتفريق رسالة إلى قطع العديد من أن يكون مكلفا للغاية.
إذا كمية كبيرة من البيانات يجب أن يكون فك تشفيرها و
يمكننا الجمع بين فوائد خوارزميات مفتاح متماثل
مع تلك RSA للحصول على كل من الأمن والكفاءة.
على الرغم من أننا لن أخوض في ذلك هنا،
AES هو خوارزمية مفتاح متناظر مثل Vigenère والأصفار قيصر
ولكن أصعب بكثير للقضاء.
بطبيعة الحال، لا يمكننا استخدام AES دون إنشاء مفتاح سري مشترك
بين النظم 2، وشاهدنا مشكلة في ذلك من قبل.
ولكن الآن يمكننا استخدام RSA لإنشاء مفتاح سري مشترك بين النظم 2.
سوف ندعو الكمبيوتر إرسال البيانات المرسل
والكمبيوتر المتلقي البيانات المتلقي.
المتلقي لديه مفتاح RSA الزوج ويرسل
المفتاح العام للمرسل.
المرسل بإنشاء مفتاح AES،
تشفير مع مفتاح RSA العامة المتلقي،
ويرسل مفتاح AES إلى المتلقي.
المتلقي فك تشفير الرسالة مع المفتاح الخاص RSA.
كل من المرسل والمتلقي الآن مفتاح AES المشتركة بينهما.
AES، وهو أسرع بكثير في التشفير وفك التشفير RSA من،
ويمكن الآن أن تستخدم لتشفير كميات كبيرة من البيانات وإرسالها إلى المتلقي،
يمكن فك تشفير الذين باستخدام نفس المفتاح.
AES، وهو أسرع بكثير في التشفير وفك التشفير RSA من،
ويمكن الآن أن تستخدم لتشفير كميات كبيرة من البيانات وإرسالها إلى المتلقي،
يمكن فك تشفير الذين باستخدام نفس المفتاح.
نحن فقط بحاجة لنقل RSA المفتاح المشترك.
لم نعد بحاجة إلى استخدام RSA على الإطلاق.
يبدو أنني قد حصلت على الرسالة.
لا يهم إذا كان أي شخص قراءة ما هو على طائرة ورقية قبل أن القبض عليه
لأنني واحد فقط مع المفتاح الخاص.
دعونا فك تشفير كل واحد من أجزاء في الرسالة.
في ذلك التكتل الأولى، 658، نرفع إلى قوة د، وهو 185،
ن وزارة الدفاع، والذي هو 989، يساوي 67،
وهو C حرف في ASCII.
الآن، على قطعة من الثانية.
وجزء الثاني له قيمة 15،
الذي نرفع إلى قوة 185،
وزارة الدفاع 989، وهذا يساوي إلى 83
وهو S حرف في ASCII.
الآن لجزء الثالث، الذي له قيمة 799، نرفع إلى 185،
وزارة الدفاع 989، وهذا يساوي 53،
التي هي قيمة الطابع 5 في ASCII.
الآن لجزء آخر، والتي لها قيمة 975،
نرفع إلى 185، وزارة الدفاع 989،
وهذا يساوي 48، وهو قيمة ال 0 حرف في ASCII.
اسمي روب بودين، وهذا هو CS50.
[CS50.TV]
RSA على الإطلاق.
RSA على الإطلاق. [ضحك]
على الإطلاق.